Projections of polyhedra are polyhedra
ProvedLinearOptimization.polyhedron_projection(Corollary 2.4) Let be a polyhedron. Then, the set
is also a polyhedron.
(Equivalently, by repeated application of the elimination algorithm, every projection of a polyhedron is a polyhedron.)
import Definitions.Def_Polyhedron
/-- **Bertsimas & Tsitsiklis, Corollary 2.4 (p. 74).** The projection of a polyhedron
`P ⊆ ℝ^{n+k}` onto its first `n` coordinates is a polyhedron: it admits a
general-form presentation `{x | A'x ≥ b'}`. -/
theorem LinearOptimization.polyhedron_projection {m n k : ℕ}
(A : Matrix (Fin m) (Fin (n + k)) ℝ) (b : Fin m → ℝ) :
∃ (m' : ℕ) (A' : Matrix (Fin m') (Fin n) ℝ) (b' : Fin m' → ℝ),
{x : Fin n → ℝ | ∃ y : Fin k → ℝ, Fin.append x y ∈ polyhedron A b} =
polyhedron A' b' := by
sorry
Read-back
What the Lean code literally says, in plain math · claude-fable-5
For all natural numbers , every real matrix and , the theorem asserts the existence of a natural number , a real matrix , and such that , where and denotes the concatenated vector whose first coordinates are and last are . In words: the projection of a ""-form polyhedron onto its first coordinates is again a ""-form polyhedron, with no bound claimed on the number of rows of the describing system. Degenerate cases (, , empty — the empty set must then be cut out by some infeasible system) are included.
Confirmed by the mission captain (proposal self-audit).