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.
Builds on
Leads to
Not sure where to start? Take the ten-question placement test.