Pointedness of a polyhedral cone: zero is an extreme point iff the cone contains no line
ProvedLinearOptimization.cone_pointed_iff_extreme_zeroconesextreme-pointspolyhedra
(Theorem 4.12) Let be the polyhedral cone defined by the constraints , . Then, the following are equivalent:
- (a) the zero vector is an extreme point of ;
- (b) the cone does not contain a line;
- (c) there exist vectors out of the family , which are linearly independent.
Preamble
import Mathlib.LinearAlgebra.LinearIndependent.Defs
import Definitions.Def_LinearOptimization_RecessionCone
import Definitions.Def_ContainsLine
open Matrix
/-- **Bertsimas & Tsitsiklis, Theorem 4.12 (p. 175).** For the polyhedral cone
`C = {x | Ax ≥ 0}`, the following are equivalent: (a) `0` is an extreme
point of `C` (the cone is pointed); (b) `C` contains no line; (c) some
`n` of the constraint vectors `a₁, …, aₘ` are linearly independent. -/
Formal statement
theorem LinearOptimization.cone_pointed_iff_extreme_zero {m n : ℕ}
(A : Matrix (Fin m) (Fin n) ℝ) :
(IsPointedCone (polyhedron A 0) ↔ ¬ContainsLine (polyhedron A 0)) ∧
(¬ContainsLine (polyhedron A 0) ↔
∃ s : Finset (Fin m), s.card = n ∧
LinearIndependent ℝ (fun i : s => A i.1)) := by
sorry
Source
Bertsimas & Tsitsiklis, Introduction to Linear Optimization, Athena Scientific, 1997, Theorem 4.12, p. 175