A nonempty bounded polyhedron is the convex hull of its extreme points
ProvedLinearOptimization.polyhedron_bounded_convex_hull_extremeconvexityextreme-pointspolyhedra
(Theorem 2.9 = Corollary 4.4) A nonempty and bounded polyhedron is the convex hull of its extreme points.
Preamble
import Mathlib.Analysis.Convex.Hull import Mathlib.Analysis.Convex.Extreme import Definitions.Def_Polyhedron /-- **Bertsimas & Tsitsiklis, Theorem 2.9 (p. 68) = Corollary 4.4 (p. 182).** A nonempty bounded polyhedron equals the convex hull of its extreme points. -/
Formal statement
theorem LinearOptimization.polyhedron_bounded_convex_hull_extreme {m n : ℕ}
(A : Matrix (Fin m) (Fin n) ℝ) (b : Fin m → ℝ)
(hne : (polyhedron A b).Nonempty)
(hbd : IsBoundedSet (polyhedron A b)) :
polyhedron A b =
convexHull ℝ (Set.extremePoints ℝ (polyhedron A b)) := by
sorry
Source
Bertsimas & Tsitsiklis, Introduction to Linear Optimization, Athena Scientific, 1997, Theorem 2.9, p. 68; restated as Corollary 4.4, p. 182
Read-back
What the Lean code literally says, in plain math · claude-fable-5
For all , every real matrix and : if the polyhedron is (i) nonempty and (ii) bounded in the sense that a single constant satisfies for every and every coordinate , then equals (set equality, both inclusions) the convex hull over of the set of extreme points of , where an extreme point is a point of that does not lie in the open segment between two points of other than itself.
Human review
Confirmed by the mission captain (proposal self-audit).