I still cannot understand why the topic is true.

The following is from convex optimization, S. Boyd

enter image description here

enter image description here

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.

  • $\begingroup$ But there is no guarantee that the feasible set on the lower dimension will be a polyhedron. $\endgroup$ – sleeve chen Sep 4 '16 at 0:25
  • $\begingroup$ The feasible set is not necessarily bounded, but it is always a polyhedron of some dimension. $\endgroup$ – Anon Sep 4 '16 at 0:58

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Not the answer you're looking for? Browse other questions tagged or ask your own question.