The convex hull of finitely many vectors is a polyhedron
ProvedLinearOptimization.convex_hull_finite_is_polyhedronconvexitygeometrylinear-programmingpolyhedra
(Corollary 2.6) The convex hull of a finite number of vectors is a polyhedron.
(Proof route: the convex hull
of is the image of the polyhedron under the linear mapping .)
Preamble
import Mathlib.Analysis.Convex.Hull import Definitions.Def_Polyhedron /-- **Bertsimas & Tsitsiklis, Corollary 2.6 (p. 74).** The convex hull of finitely many vectors in `ℝⁿ` admits a general-form polyhedral presentation. -/
Formal statement
theorem LinearOptimization.convex_hull_finite_is_polyhedron {n k : ℕ}
(v : Fin k → (Fin n → ℝ)) :
∃ (m' : ℕ) (A' : Matrix (Fin m') (Fin n) ℝ) (b' : Fin m' → ℝ),
convexHull ℝ (Set.range v) = polyhedron A' b' := by
sorry
Source
Bertsimas & Tsitsiklis, Introduction to Linear Optimization, Athena Scientific, 1997, Corollary 2.6, p. 74