# Why feasible set of LP is a polyhedron

I still cannot understand why the topic is true.

The following is from convex optimization, S. Boyd

My claim is the following:

• The feasible region for $Gx \preceq h$ is a polyhedron, which is easy to understand and can be easily drawn on the paper.
• The feasible region for $Ax=b$ is the intersection of all affine set defined by $a_i^Tx = b_i$ for each $i$, where $a_i, \forall i$ are rows of $A$. So there are three possibilities: 1. No solution. Then the feasible set of LP is empty. 2. One solution. Then the feasible set of LP is "at most" a point. 3. $\infty$ solution. Then the feasible set of LP is "at most" a line.

Why is the feasible set a polyhedron?

The feasible region for $Ax=b$ is an intersection of affine sets, therefore also an affine set. However there are no further restrictions on the dimension of the solution space for $Ax=b$. It may very well be two- or higher-dimensional.