Unboundedness of a linear program via extreme rays of the feasible set
ProvedLinearOptimization.lp_unbounded_iff_extreme_ray(Theorem 4.14) Consider the problem of minimizing subject to , and assume that the feasible set has at least one extreme point.
The optimal cost is equal to if and only if some extreme ray of the feasible set satisfies .
(Interestingly, this criterion does not involve the right-hand side vector .)
import Mathlib.Analysis.Convex.Extreme
import Definitions.Def_LinearOptimization_RecessionCone
open Matrix
/-- **Bertsimas & Tsitsiklis, Theorem 4.14 (p. 178).** For `min c'x` over `{x | Ax ≥ b}` with
at least one extreme point: the optimal cost is `−∞` iff some extreme ray
`d` of the feasible set satisfies `c'd < 0`. -/
theorem LinearOptimization.lp_unbounded_iff_extreme_ray {m n : ℕ}
(A : Matrix (Fin m) (Fin n) ℝ) (b : Fin m → ℝ) (c : Fin n → ℝ)
(hext : (Set.extremePoints ℝ (polyhedron A b)).Nonempty) :
lpValue c (polyhedron A b) = ⊥ ↔
∃ 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 the polyhedron has at least one extreme point (standard sense). Then the following are equivalent: (i) in the extended reals (this in particular forces , since the infimum over an empty set is ); (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 that the extreme-ray notion in (ii) refers only to the matrix (via the cone ) and is independent of the right-hand side .
Confirmed by the mission captain (proposal self-audit).