Terminal simplex states are optimal or unbounded
ProvedLinearOptimization.simplex_terminal_classificationlinear-optimizationsimplex-method
Consider the standard-form linear program with linearly independent rows of . Let be a simplex state from which no admissible simplex pivot exists. Then exactly the stopping alternatives needed by the simplex method are available: either is an optimal basis and is globally optimal, or there is a feasible recession direction such that
This theorem isolates the terminal classification step: nonnegative reduced costs give the optimality certificate, while a negative reduced cost whose pivot column has no positive entry gives an unbounded ray.
Formalization Note The optimal value is EReal-valued, so unboundedness below is expressed by lpValue c (stdPolyhedron A b) = ⊥.
Preamble
import Mathlib.LinearAlgebra.LinearIndependent.Defs import Definitions.Def_LinearOptimization_SimplexPivot import Definitions.Def_LinearOptimization_OptimalBasis open Matrix
Formal statement
theorem LinearOptimization.simplex_terminal_classification {m n : ℕ}
(A : Matrix (Fin m) (Fin n) ℝ) (b : Fin m → ℝ) (c : Fin n → ℝ)
(hA : LinearIndependent ℝ (fun i => A i))
(B : Fin m ↪ Fin n) (x : Fin n → ℝ)
(hstate : IsSimplexState A b B x)
(hterminal : ¬∃ (B' : Fin m ↪ Fin n) (x' : Fin n → ℝ),
IsSimplexPivot A c B x B' x') :
(IsOptimalBasis A b c B ∧ IsLpOptimal c (stdPolyhedron A b) x) ∨
∃ d : Fin n → ℝ, A.mulVec d = 0 ∧ 0 ≤ d ∧ c ⬝ᵥ d < 0 ∧
lpValue c (stdPolyhedron A b) = ⊥ := by
sorrySource
Dimitris Bertsimas and John N. Tsitsiklis, Introduction to Linear Optimization (Athena Scientific, 1997), simplex stopping criteria and Theorem 3.3(a,b), p. 91.