Unboundedness over a pointed polyhedral cone via extreme rays
ProvedLinearOptimization.cone_unbounded_iff_extreme_ray(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 .
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`. -/
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
Read-back
What the Lean code literally says, in plain math · claude-fable-5
For all , an real matrix , and , assume that is an extreme point of the cone (standard extreme-point sense: , and lying in the open segment between two points of forces both to be ). Then the following are equivalent: (i) the infimum , computed in the extended reals, equals ; (ii) there exists with (strict) which is an extreme ray of the matrix in this development's sense, namely: componentwise, , and there exists a finite set of row indices with exactly elements (natural-number subtraction, so elements when ) such that for every and the rows are linearly independent over . Note , so the infimum in (i) is at most and in particular never .
Confirmed by the mission captain (proposal self-audit).