Projections of polyhedra are polyhedra
ProvedLinearOptimization.polyhedron_projectiongeometrylinear-programmingpolyhedraprojection
(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.)
Preamble
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'}`. -/
Formal statement
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
Source
Bertsimas & Tsitsiklis, Introduction to Linear Optimization, Athena Scientific, 1997, Corollary 2.4, p. 74