How can an unbounded polyhedron be described by finitely many geometric objects? Sections 4.8-4.9 of Bertsimas-Tsitsiklis build the cone machinery: recession cones and their rays, extreme rays (defined, like basic solutions, by linearly independent active constraints), the pointedness criterion (Theorem 4.12: is an extreme point of a polyhedral cone iff the cone contains no line iff of the constraint vectors are linearly independent), and the characterization of unbounded linear programs (Theorems 4.13-4.14: over a pointed polyhedral cone, and then over any polyhedron with an extreme point, the optimal cost is iff some extreme ray has ). The capstone is the resolution theorem (Theorem 4.15): a nonempty polyhedron with at least one extreme point equals — the convex hull of its extreme points plus the cone generated by a complete set of its extreme rays. It specializes to Theorem 2.9 / Corollary 4.4 (a nonempty bounded polyhedron is the convex hull of its extreme points) and Corollary 4.5 (a pointed polyhedral cone is generated by its extreme rays). The converse, Theorem 4.16, states that every finitely generated set is a polyhedron — in particular the convex hull of finitely many vectors is a polyhedron. Together these form the Minkowski-Weyl equivalence of the two representations of polyhedra, verified absent from Mathlib and the genuine content of this mission.
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
(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, .
No open leaves. Every sub-goal is proved or awaiting decomposition.