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.