A lexicographic simplex pivot preserves positive rows and increases the zeroth row
ProvedLinearOptimization.simplex_lexicographic_pivot_steplinear-optimizationsimplex-method
Consider one iteration of the simplex method for the standard-form problem subject to and . Let be the current basis, let every nonzeroth row of its tableau
be lexicographically positive, and perform a pivot according to the lexicographic pivoting rule, producing the new basis .
Then every nonzeroth row of the new tableau is lexicographically positive, and the new zeroth row
is strictly lexicographically larger than the old zeroth row.
This is the one-iteration invariant underlying lexicographic anticycling; iterating it and using the finiteness of the set of bases yields finite termination.
Preamble
import Mathlib.LinearAlgebra.LinearIndependent.Defs import Definitions.Def_LinearOptimization_SimplexPivot open Matrix
Formal statement
theorem LinearOptimization.simplex_lexicographic_pivot_step {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)
(hpos : ∀ i, LexPos (tableauRow A b B i))
(hpivot : IsLexicographicPivot A b c B x B' x') :
(∀ i, LexPos (tableauRow A b B' i)) ∧
LexLt (tableauZerothRow A b c B) (tableauZerothRow A b c B') := by
sorrySource
Bertsimas & Tsitsiklis, Introduction to Linear Optimization, Athena Scientific, 1997, Theorem 3.4(a,b), p. 110, especially Eq. (3.5). https://studylib.net/doc/28617911/bertsimas-linear-cap-1-a-5