3

In many places, results about Polyhedral sets (for example the Characterization Theorem of Polyhedral sets) are proved for the canonical polyhedral set $\{x \in \mathbb R^n: Ax = b\}$ with $b\in \mathbb R^m \text{and} \ rank(A)=m$. How does one convert a general polyhedral set (in some $\mathbb R^k$) to this form?

EDIT: The canonical form $\{x \in \mathbb R^n: Ax = b, x\ge0\}$ is also used sometime. How to also convert it to this form?

Miheer
  • 825
  • 4
  • 12

1 Answers1

0

You really want $Ax\geq b$,meaning each term in the first vector is at least as big as the corresponding term in the other vector. Each coordinate of the equation determines a half-space, and convex polyhedra are exactly the intersections f i tely many halfspaces.

For instance, a cube is given by A being the matrix obtaine by stacking he identity matrix on top of the matrix with -1 on the diagonal, and b being the vector with all 1's.

Brian Rushton
  • 13,255
  • 11
  • 59
  • 93
  • Can you please explain how converting to the form ${x: Ax\ge b}$ suffices to convert it to ${x: Cx = d, x\ge0}$ with the $rank(C)$ being full. – Miheer Dec 04 '13 at 05:49
  • I think the other definition is wrong; the definition you have just written places all points in the first 'octant' (or generalization thereof), and then requires that they lie in in the intersection of several hyperplanes, generically giving the emoty set or a point. – Brian Rushton Dec 04 '13 at 12:33
  • Do you have a reference using this notation? – Brian Rushton Dec 04 '13 at 12:34
  • I came across it while reading The representation theorem for polyhedral sets here. What I am not sure of is if this proof works for any general polyhedral set or not. – Miheer Dec 04 '13 at 13:18