Where should one look for the optimum of a linear programming problem? Chapter 1 of Bertsimas–Tsitsiklis suggests that optima "tend to occur at corners" of the feasible polyhedron; §§2.5–2.6 turn this intuition into theorems. Not every polyhedron has a corner — a halfspace in () has none — and the exact dividing line is the presence of an infinite line: a nonempty polyhedron
has an extreme point if and only if it does not contain a line, if and only if of the vectors are linearly independent (Theorem 2.6). In particular every nonempty bounded polyhedron and every nonempty standard-form polyhedron has a basic feasible solution (Corollary 2.2). The capstone, Theorem 2.8, is the sharpest form of the corner principle: if has at least one extreme point, then for any cost vector either the optimal cost is , or there is an extreme point of that is optimal — existence of an optimal solution comes for free once the cost is bounded below. Its companion Theorem 2.7 places an optimal extreme point under the weaker assumption that an optimal solution exists, and Corollary 2.3 — the fundamental theorem of linear programming — concludes that every feasible LP either has optimal cost or attains an optimal solution, in stark contrast with nonlinear problems such as minimizing over . These results license the extreme-point search that the simplex method (Mission IV) performs.
theorem LinearOptimization.lp_extreme_point_optimality {m n : ℕ} (A : Matrix (Fin m) (Fin n) ℝ)
(b : Fin m → ℝ) (c : Fin n → ℝ)
(hext : (Set.extremePoints ℝ (polyhedron A b)).Nonempty) :
lpValue c (polyhedron A b) = ⊥ ∨
∃ x ∈ Set.extremePoints ℝ (polyhedron A b),
IsLpOptimal c (polyhedron A b) x := by
sorry
(Theorem 2.8, GOAL) Consider the linear programming problem of minimizing over a polyhedron . Suppose that has at least one extreme point.
Then, either the optimal cost is equal to , or there exists an extreme point which is optimal.
No open leaves. Every sub-goal is proved or awaiting decomposition.