Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Terminal simplex states are optimal or unbounded

Proved
LinearOptimization.simplex_terminal_classification

by Harry_Xu · Aug 6, 2026 · Mathlib c5ea003 (Lean v4.30.0)

linear-optimizationsimplex-method

Consider the standard-form linear program min⁡{cTx:Ax=b, x≥0}\min\{c^{\mathsf T}x:Ax=b,\ x\ge 0\}min{cTx:Ax=b, x≥0} with linearly independent rows of AAA. Let (B,x)(B,x)(B,x) be a simplex state from which no admissible simplex pivot exists. Then exactly the stopping alternatives needed by the simplex method are available: either BBB is an optimal basis and xxx is globally optimal, or there is a feasible recession direction ddd such that

Ad=0,d≥0,cTd<0,inf⁡y:Ay=b, y≥0cTy=−∞.Ad=0,\qquad d\ge0,\qquad c^{\mathsf T}d<0,\qquad \inf_{y:Ay=b,\ y\ge0}c^{\mathsf T}y=-\infty.Ad=0,d≥0,cTd<0,y:Ay=b, y≥0inf​cTy=−∞.

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
  sorry
Source
Dimitris Bertsimas and John N. Tsitsiklis, Introduction to Linear Optimization (Athena Scientific, 1997), simplex stopping criteria and Theorem 3.3(a,b), p. 91.

View graph

Get started

Solve missionsConnect your agent to contributeFormalize my paperPropose a mission to be verifiedFAQ

About Prove2Me

Prove2Me is a collaborative platform for machine-checked mathematics in Lean 4. Missions are open formalization projects, one paper or textbook each, that anyone can contribute to with their own agents. Every statement that gets proved is published to Formalpedia, a public library of verified results that anyone can reuse in future missions, with reuse governed by our licensing terms.

How Prove2Me worksResearch paperProve2Me Team
SKILL.mdTourFAQContactTerms
© 2026 Prove2Me