A simplex pivot yields a new basic feasible solution with lower cost
ProvedLinearOptimization.simplex_pivot_basis_change(Theorem 3.2) In the setting of a simplex iteration — a nondegenerate basic feasible solution with basis matrix , a nonbasic index with , the th basic direction,
finite and attained at the index (so ), and obtained from by replacing with (Eqs. (3.3)–(3.4)):
- (a) the columns , , and are linearly independent and, therefore, is a basis matrix;
- (b) the vector is a basic feasible solution associated with the basis matrix .
import Mathlib.LinearAlgebra.LinearIndependent.Defs import Definitions.Def_LinearOptimization_SimplexPivot open Matrix /-- **Bertsimas & Tsitsiklis, Theorem 3.2 (p. 89).** Basis change at a simplex pivot: with entering index `j` (`c̄_j < 0`), exiting row `ℓ` attaining the ratio test, and `B'` obtained from `B` by replacing `B(ℓ)` with `j`, the new basic columns are linearly independent (so `B'` is a basis matrix), and `y = x + θ* • d` is a basic feasible solution associated with `B'`. -/
theorem LinearOptimization.simplex_pivot_basis_change {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) (hB : IsStdBasis A B)
(x : Fin n → ℝ) (hx : x ∈ stdPolyhedron A b)
(hxB : ∀ j ∉ Set.range B, x j = 0)
(hnd : ¬IsStdDegenerateBasicSolution A b x)
(j : Fin n) (hj : j ∉ Set.range B) (hcj : reducedCost A c B j < 0)
(ℓ : Fin m) (hℓ : 0 < pivotColumn A B j ℓ)
(hmin : ∀ i, 0 < pivotColumn A B j i →
x (B ℓ) / pivotColumn A B j ℓ ≤ x (B i) / pivotColumn A B j i)
(hB'ne : ∀ i, i ≠ ℓ → B' i = B i) (hB'ℓ : B' ℓ = j) :
IsStdBasis A B' ∧
x + (x (B ℓ) / pivotColumn A B j ℓ) • basicDirection A B j ∈
stdPolyhedron A b ∧
∀ k ∉ Set.range B',
(x + (x (B ℓ) / pivotColumn A B j ℓ) • basicDirection A B j) k = 0 := 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, , . Assume: are injections ; the columns of selected by are linearly independent; satisfies , , and vanishes outside the range of ; is not std-degenerate (not both: a basic solution of the standard-form system, and more than zero coordinates); is a nonbasic column with negative reduced cost , where ; is a position with attaining the minimum ratio, for every with ; and agrees with off with . Writing with , the conclusion is threefold: (i) the columns of selected by are linearly independent; (ii) satisfies and ; (iii) for every outside the range of . I.e. the pivot produces a legitimate new simplex state.
Confirmed by the mission captain (proposal self-audit).