Polyhedra

x : Ax ≤ b — an intersection of half-spaces, with corners where constraints go tight.

The idea

Definition (Polyhedron).

A polyhedron is the set of points satisfying finitely many linear inequalities at once, $\{x : A x \le b\},$ one inequality per row of $A x \le b$. A polyhedron that fits inside some finite ball is bounded, and a bounded polyhedron is called a polytope.

A single inequality $a_i^{\top} x \le b_i$ keeps the points on one side of a hyperplane — a half-space — so a polyhedron is an intersection of half-spaces, and it is always convex, since an intersection of convex sets is convex. The figure shows three half-spaces $H_{1}, H_{2}, H_{3}$, each arrow pointing into the side its inequality keeps, overlapping in the shaded polyhedron $P$.

A vertex (or extreme point) of a polyhedron is a feasible point that cannot be written as the midpoint of two other feasible points: a genuine corner, not a point partway along a flat face. There is an equivalent description that is far easier to compute with. Call a constraint tight at a point when it holds with equality there, and slack when it holds strictly.

Proposition (Vertices by tight constraints).

A feasible point of a polyhedron in $n$ dimensions is a vertex exactly when $n$ linearly independent constraints are tight at it.

That is enough equations to pin the point down completely. In the plane it means two independent constraint lines crossing at a feasible point, which is why corners can be found by solving pairs of boundary equations.

Ways to work on it

• Walkthrough. Build a triangle from three inequalities, find a vertex, and characterize extreme points.
• Practice. Check feasibility of a point or count the vertices of a small region.
• Hardest. Identify the active constraints at a vertex, or decide bounded versus unbounded.

Not sure where to start? Take the ten-question placement test.