Some optimal solution is an extreme point
ProvedLinearOptimization.lp_optimal_extreme_point(Theorem 2.7) Consider the linear programming problem of minimizing over a polyhedron . Suppose that has at least one extreme point and that there exists an optimal solution.
Then, there exists an optimal solution which is an extreme point of .
import Mathlib.Analysis.Convex.Extreme import Definitions.Def_Polyhedron /-- **B&T Theorem 2.7 (p. 65).** If the feasible polyhedron has an extreme point and the LP has an optimal solution, then some extreme point is optimal. -/
theorem LinearOptimization.lp_optimal_extreme_point {m n : ℕ} (A : Matrix (Fin m) (Fin n) ℝ)
(b : Fin m → ℝ) (c : Fin n → ℝ)
(hext : (Set.extremePoints ℝ (polyhedron A b)).Nonempty)
(hopt : ∃ x, IsLpOptimal c (polyhedron A b) x) :
∃ x ∈ Set.extremePoints ℝ (polyhedron A b),
IsLpOptimal c (polyhedron A b) x := by
sorry
Read-back
What the Lean code literally says, in plain math · claude-fable-5
Let be a real matrix, , , and write . Assume: (i) has at least one extreme point (in Mathlib's sense: a point of not expressible as a strict convex combination , , of two points of other than itself), and (ii) there exists an optimal point, i.e. some with for all (minimization). The conclusion: there exists a point that is simultaneously an extreme point of and optimal ( and for every ). This transfers attainment to an extreme point; it does not assert uniqueness.
Confirmed by the mission captain (proposal self-audit).