Resolution theorem for polyhedra
ProvedLinearOptimization.polyhedron_resolution(Theorem 4.15, resolution theorem — GOAL) Let be a nonempty polyhedron with at least one extreme point. Let be the extreme points, and let be a complete set of extreme rays of . Let
Then, .
import Mathlib.Analysis.Convex.Extreme
import Definitions.Def_LinearOptimization_RecessionCone
import Definitions.Def_LinearOptimization_FinitelyGeneratedSet
open Matrix
/-- **Bertsimas & Tsitsiklis, Theorem 4.15 (p. 179).** Resolution theorem: a nonempty
polyhedron `P = {x | Ax ≥ b}` with at least one extreme point equals the
finitely generated set built from its extreme points and any complete set
of its extreme rays. -/
theorem LinearOptimization.polyhedron_resolution {m n k r : ℕ}
(A : Matrix (Fin m) (Fin n) ℝ) (b : Fin m → ℝ)
(hne : (polyhedron A b).Nonempty)
(x : Fin k → (Fin n → ℝ)) (hk : 0 < k)
(hx : Set.extremePoints ℝ (polyhedron A b) = Set.range x)
(w : Fin r → (Fin n → ℝ)) (hw : IsCompleteExtremeRaySet A w) :
finitelyGeneratedSet x w = polyhedron A b := by
sorry
Read-back
What the Lean code literally says, in plain math · claude-fable-5
Resolution of a polyhedron. For all , an real matrix and , write . Hypotheses: (a) is nonempty; (b) a family with whose range equals the set of extreme points of — so every listed is an extreme point of and every extreme point of occurs among the (the listing may contain repetitions, and in particular must actually have extreme points for the hypothesis with to hold); (c) a family forming a complete extreme ray set for : every is an extreme ray of the matrix in this development's sense, namely: componentwise, , and there exists a finite set of row indices with exactly elements (natural-number subtraction, so elements when ) such that for every and the rows are linearly independent over , and every vector satisfying that extreme-ray predicate equals for exactly one index (with some ). Conclusion (set equality): . The case is admitted only when has no extreme rays at all (otherwise hypothesis (c) fails), in which case the left-hand side is the convex hull of the .
Confirmed by the mission captain (proposal self-audit).