Convex hull of discrete ray generators
ProvedLinearOptimization.convexHull_natGenerated_eq_finitelyGeneratedSetconvex-geometryinteger-programminglinear-optimization
Let be finitely many base points and let be finitely many directions. Define the discrete generated set by choosing one base point and nonnegative integer multiples of the directions. Then its convex hull is exactly the finitely generated polyhedron obtained by allowing a convex combination of the base points and arbitrary nonnegative real multiples of the directions:
This is the purely convex-geometric bridge used after the integer monoid has been finitely generated.
Preamble
import Mathlib.Analysis.Convex.Combination import Mathlib.Algebra.Order.Floor.Ring import Definitions.Def_LinearOptimization_FinitelyGeneratedSet import Theorems.Thm_LinearOptimization_finitely_generated_is_polyhedron
Formal statement
theorem LinearOptimization.convexHull_natGenerated_eq_finitelyGeneratedSet {n k r : ℕ}
(x : Fin k → (Fin n → ℝ)) (w : Fin r → (Fin n → ℝ)) :
convexHull ℝ
{y | ∃ (i : Fin k) (q : Fin r → ℕ),
y = x i + ∑ j, (q j : ℝ) • w j} =
finitelyGeneratedSet x w := by sorrySource
Bertsimas and Tsitsiklis, Introduction to Linear Optimization (Athena Scientific, 1997), Exercise 11.8(c)-(d), p. 525; purely formal convexification bridge for the finite integer-generator representation in Theorem 11.3, p. 496.