Strict objective decrease under a nondegenerate simplex pivot
ProvedLinearOptimization.simplex_pivot_state_cost_decreaselinear-optimizationsimplex-method
Consider the standard-form linear program . Assume the rows of are linearly independent, is a simplex state, and every basic feasible solution is nondegenerate. If is obtained from by one admissible simplex pivot (negative reduced cost, positive pivot entry, and the minimum-ratio rule), then
Thus every pivot in a nondegenerate simplex run makes strict objective progress. This is the local descent fact used to rule out cycling by finiteness of the set of bases.
Formalization Note A simplex state records a valid standard basis, feasibility, and zero coordinates outside that basis; IsSimplexPivot packages the entering/leaving indices and the minimum-ratio update.
Preamble
import Mathlib.LinearAlgebra.LinearIndependent.Defs import Definitions.Def_LinearOptimization_SimplexPivot open Matrix
Formal statement
theorem LinearOptimization.simplex_pivot_state_cost_decrease {m n : ℕ}
(A : Matrix (Fin m) (Fin n) ℝ) (b : Fin m → ℝ) (c : Fin n → ℝ)
(hA : LinearIndependent ℝ (fun i => A i))
(B B' : Fin m ↪ Fin n) (x x' : Fin n → ℝ)
(hstate : IsSimplexState A b B x)
(hnd : ∀ y, IsBasicFeasibleSolution (stdFormSystem A b) y →
¬IsStdDegenerateBasicSolution A b y)
(hpivot : IsSimplexPivot A c B x B' x') :
IsSimplexState A b B' x' ∧ c ⬝ᵥ x' < c ⬝ᵥ x := by
sorrySource
Dimitris Bertsimas and John N. Tsitsiklis, Introduction to Linear Optimization (Athena Scientific, 1997), Theorem 3.2, p. 89, and proof of Theorem 3.3, p. 91.