Unboundedness over a pointed polyhedral cone via extreme rays
ProvedLinearOptimization.cone_unbounded_iff_extreme_rayconesextreme-rayslinear-programming
(Theorem 4.13) Consider the problem of minimizing over a pointed polyhedral cone .
The optimal cost is equal to if and only if some extreme ray of satisfies .
Preamble
import Definitions.Def_LinearOptimization_RecessionCone
open Matrix
/-- **Bertsimas & Tsitsiklis, Theorem 4.13 (p. 177).** Over a pointed polyhedral cone
`C = {x | Ax ≥ 0}`, the optimal cost of `min c'x` is `−∞` iff some
extreme ray `d` of `C` has `c'd < 0`. -/
Formal statement
theorem LinearOptimization.cone_unbounded_iff_extreme_ray {m n : ℕ}
(A : Matrix (Fin m) (Fin n) ℝ) (c : Fin n → ℝ)
(hpointed : IsPointedCone (polyhedron A 0)) :
lpValue c (polyhedron A 0) = ⊥ ↔
∃ d : Fin n → ℝ, IsExtremeRay A d ∧ c ⬝ᵥ d < 0 := by
sorry
Source
Bertsimas & Tsitsiklis, Introduction to Linear Optimization, Athena Scientific, 1997, Theorem 4.13, p. 177