Resolution theorem for polyhedra
ProvedLinearOptimization.polyhedron_resolutionconesconvexityextreme-pointspolyhedra
(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, .
Preamble
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. -/
Formal statement
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
Source
Bertsimas & Tsitsiklis, Introduction to Linear Optimization, Athena Scientific, 1997, Theorem 4.15, p. 179
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.