Finitely generated sets are polyhedra (converse of the resolution theorem)
ProvedLinearOptimization.finitely_generated_is_polyhedronconesconvexitypolyhedra
(Theorem 4.16, converse to the resolution theorem) A finitely generated set is a polyhedron. In particular, the convex hull of finitely many vectors is a (bounded) polyhedron.
Preamble
import Definitions.Def_Polyhedron
import Definitions.Def_LinearOptimization_FinitelyGeneratedSet
/-- **Bertsimas & Tsitsiklis, Theorem 4.16 (p. 183).** Every finitely generated set
`{Σᵢ λᵢ xⁱ + Σⱼ θⱼ wʲ | λ ≥ 0, θ ≥ 0, Σλ = 1}` admits a general-form
polyhedral presentation `{y | A'y ≥ b'}`. -/
Formal statement
theorem LinearOptimization.finitely_generated_is_polyhedron {n k r : ℕ}
(x : Fin k → (Fin n → ℝ)) (w : Fin r → (Fin n → ℝ)) :
∃ (m' : ℕ) (A' : Matrix (Fin m') (Fin n) ℝ) (b' : Fin m' → ℝ),
finitelyGeneratedSet x w = polyhedron A' b' := by
sorry
Source
Bertsimas & Tsitsiklis, Introduction to Linear Optimization, Athena Scientific, 1997, Theorem 4.16, p. 183
Read-back
What the Lean code literally says, in plain math · claude-fable-5
For all and arbitrary finite families and of vectors in : there exist a natural number , an real matrix , and such that the finitely generated set equals . No nonemptiness hypothesis is imposed: when the generated set is empty (the constraint is unsatisfiable), and the claim then asserts that the empty set can be written in this polyhedral form.
Human review
Confirmed by the mission captain (proposal self-audit).