The lexicographic pivoting rule prevents cycling
ProvedLinearOptimization.simplex_lexicographic_anticycling(Theorem 3.4) Suppose that the simplex algorithm starts with all the rows in the simplex tableau, other than the zeroth row, lexicographically positive. Suppose that the lexicographic pivoting rule is followed. Then:
- (a) every row of the simplex tableau, other than the zeroth row, remains lexicographically positive throughout the algorithm;
- (b) the zeroth row strictly increases lexicographically at each iteration;
- (c) the simplex method terminates after a finite number of iterations.
(No nondegeneracy assumption; the th tableau row is and the zeroth row is .)
import Mathlib.LinearAlgebra.LinearIndependent.Defs import Definitions.Def_LinearOptimization_SimplexPivot open Matrix /-- **Bertsimas & Tsitsiklis, Theorem 3.4 (p. 110).** Lexicographic anticycling: under the lexicographic pivoting rule, (a) lexicographic positivity of the tableau rows `1, …, m` is preserved by every pivot, (b) the zeroth tableau row strictly increases lexicographically at every pivot, and (c) there is no infinite lexicographic pivot run starting from a tableau whose rows other than the zeroth are lexicographically positive. -/
theorem LinearOptimization.simplex_lexicographic_anticycling {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 → ℝ),
IsSimplexState A b B x →
(∀ i, LexPos (tableauRow A b B i)) →
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')) ∧
¬∃ f : ℕ → (Fin m ↪ Fin n) × (Fin n → ℝ),
(∀ k, IsSimplexState A b (f k).1 (f k).2) ∧
(∀ i, LexPos (tableauRow A b (f 0).1 i)) ∧
∀ k, IsLexicographicPivot A b c (f k).1 (f k).2 (f (k + 1)).1 (f (k + 1)).2 := by
sorry
Read-back
What the Lean code literally says, in plain math · claude-fable-5
Let be a real matrix with linearly independent rows, , — no non-degeneracy or feasibility assumptions. Write for the -vector , for with the reduced-cost vector, for the first-difference lexicographic strict order on such vectors, and "lex-positive" for . The theorem asserts a conjunction. (a) For all bases and points : if is a simplex state ('s columns independent, , , nonbasic coordinates zero), every is lex-positive, and is a lexicographic pivot (a pivot step at some entering / leaving , such that for every other row with positive pivot-column entry the scaled row is the scaled row ), then every is lex-positive and (the zeroth row strictly increases lexicographically). (b) There is no infinite sequence of simplex states whose initial tableau rows are all lex-positive and in which every consecutive pair is a lexicographic pivot.
Confirmed by the mission captain (proposal self-audit).