Why LP optima sit at corners, with a proof you can step through.
Chapter: 0 — LP theory · lesson id lp-geometry · theory lesson
Linear programming has a careful one-line punchline: when an LP has an optimum, at $least\ one$ of its optima is a vertex of the feasible region. That "at least one" matters. When the objective contour is parallel to a face of the polyhedron, every point on that face is optimal — but the face's endpoints are still vertices, so the theorem holds. This lesson states the result precisely, proves it, and unpacks the degenerate case explicitly so the algorithms (combinatorial $and$ interior-point) make sense.
Definition (Polyhedron). A $polyhedron$ in $\mathbb{R}^n$ is the intersection of finitely many closed half-spaces: $$P = { x \in \mathbb{R}^n : a_{i}^{\top} x \leq b_{i}, ; i = 1, \ldots, m }.$$ A bounded polyhedron is a $polytope$.
The feasible region of an LP is by construction the intersection of finitely many linear inequalities and equalities, so it is a polyhedron. The picture in the last lesson — the shaded polygon — is the $n = 2$ case. In $\mathbb{R}^3$ you would see a polyhedron with flat faces. In higher dimensions you cannot draw it, but the algebra still works.
Definition (Vertex (extreme point)). A point $x \in P$ is a $vertex$ (or $extreme\ point$) of $P$ if it cannot be written as a strict convex combination of two distinct points in $P$. Equivalently, if $x = \lambda y + (1 - \lambda) z$ with $y, z \in P$ and $0 < \lambda < 1$, then $y = z = x$.
In two dimensions, a vertex is a corner where two constraint boundaries meet. In three dimensions, three faces meet at a vertex. In general $n$ dimensions, you need $n$ linearly-independent constraints to be active to pin down a single vertex.
Theorem (Fundamental Theorem of Linear Programming). Consider an LP $\min\ c^{\top} x$ subject to $x \in P$, where $P$ is a non-empty $pointed$ polyhedron — one that has at least one vertex, equivalently one that contains no line (automatic whenever the variables carry sign constraints such as $x \geq 0$, as ours always do). If the LP has a finite optimal value, then there exists an optimal solution that is a vertex of $P$.
Read it carefully. The statement does $not$ say every optimum is a vertex. It says $at\ least\ one$ optimum is a vertex. That is enough: a combinatorial algorithm only has to check vertices.
The "at least one" matters. When the objective gradient $c$ is perpendicular to a constraint hyperplane (equivalently, the objective contours are $parallel$ to a face of $P$), the entire face becomes optimal. The Fundamental Theorem still applies because the face's endpoints are vertices — but interior points of the face are also optimal. This is the $degenerate$ case of LP.
Example (Parallel objective and a face of optima). For $\min\ x_{1} + x_{2}$ subject to $x_{1} + x_{2} \geq 5$ and $x_{1}, x_{2} \geq 0$, the objective gradient is $(1, 1)$, perpendicular to the binding constraint $x_{1} + x_{2} = 5$. Every point on the segment from $(5, 0)$ to $(0, 5)$ is optimal with value $5$. The vertices $(5, 0)$ and $(0, 5)$ are still optimal — they are just two of infinitely many.
This is also where the simplex method ($vertex$-to-$vertex$ walker) and interior-point methods ($barrier$ methods that slide through the polytope interior) diverge. Simplex always returns one of the optimal vertices. Interior-point methods converge to the $analytic\ centre$ of the optimal face — a point in the relative interior of that face, $not$ a vertex. Both are correct; they just answer slightly different questions. If you need a vertex (for sensitivity analysis, basis identification, etc.) and you ran an interior-point method, most solvers run a $crossover$ step afterwards to pivot to an adjacent vertex.
Proof, step by step (Fundamental Theorem of LP).
This is the engine behind the simplex method: walk from vertex to vertex along edges, always moving in a direction that does not worsen the objective, and stop when no neighbour is strictly better. The argument above is why this is enough.
Quick check. A 2D LP has 4 inequality constraints on top of $x_1, x_2 \geq 0$ (so $m = 6$ inequalities in total, $n = 2$). What is the tight bound on the number of vertices of the (bounded, non-degenerate) feasible polygon?
The looser combinatorial bound $\binom{m}{n}$ counts $basic\ solutions$ — every choice of $n$ constraints from $m$ defines a point if those $n$ constraints are linearly independent. Most basic solutions are infeasible. The tight $worst$-$case$ bound on the number of $vertices$ of a bounded polytope in $\mathbb{R}^{n}$ with $m$ facets is given by McMullen's $Upper$ $Bound$ $Theorem$: in dimension $n$, vertex count is $O(m^{\lfloor n/2 \rfloor})$. For $n = 2$ that is $O(m)$; in higher dimensions it can grow much faster.
[feasible-region diagram: A 2D polygon with m = 6 inequality constraints achieving the bound: a hexagon with 6 vertices and 6 facets.]
Count the vertices on the diagram: $(1, 0)$, $(3, 0)$, $(3, 2)$, $(2, 3)$, $(0, 3)$, $(0, 1)$. Six vertices, six edges, one per inequality constraint. That is the $tight$ bound in two dimensions.
The combinatorial growth in higher dimensions is why the worst-case complexity of the simplex method is exponential — Klee–Minty constructed a cube in dimension $n$ where simplex traverses all $2^{n}$ vertices. In practice the method visits a tiny fraction, and average / smoothed-analysis bounds are far better.
Recap.
Read this through MCP: read with path: "lessons/lp-geometry", or resource hlpl://lessons/lp-geometry.