Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Corollary 7 — within O(nL)O(\sqrt n L)O(n​L) iterations the algorithm finds optimal solutions of (LP) and (LD) or detects infeasibility

Disproved
SelfDualLP.Complexity.corollary_7

by mikedeng1 · Oct 6, 2026 · Mathlib 0df444a (Lean v4.33.1)

complexityinterior-point-methodslinear-programmingp2o-batch-pfp2bp2o-gran-per-chapterp2o-plan-paperp2o-v1

Let (LP) min⁡{cTx:Ax=b, x≥0}\min\{c^Tx: Ax=b,\ x\ge0\}min{cTx:Ax=b, x≥0} and (LD) max⁡{bTy:ATy≤c}\max\{b^Ty: A^Ty\le c\}max{bTy:ATy≤c} have integer data A∈Zm×nA\in\mathbb Z^{m\times n}A∈Zm×n, b∈Zmb\in\mathbb Z^mb∈Zm, c∈Znc\in\mathbb Z^nc∈Zn with n≥1n\ge1n≥1 and bit length LLL. There is an absolute constant C>0C>0C>0 such that there is a finite predictor–corrector run under the choice (7) ending at an iteration

k≤Cn Lk\le C\sqrt n\,Lk≤Cn​L

at which the termination projection has an output, and every termination output u=(y∗,x∗,τ∗,θ∗,s∗,κ∗)u=(y^*,x^*,\tau^*,\theta^*,s^*,\kappa^*)u=(y∗,x∗,τ∗,θ∗,s∗,κ∗) at zkz^kzk satisfies one of:

  1. τ∗>0\tau^*>0τ∗>0, x∗/τ∗x^*/\tau^*x∗/τ∗ is an optimal solution of (LP) and (y∗/τ∗, s∗/τ∗)(y^*/\tau^*,\,s^*/\tau^*)(y∗/τ∗,s∗/τ∗) is an optimal solution of (LD);
  2. τ∗=0\tau^*=0τ∗=0 and the output indicates infeasibility: either cTx∗<0c^Tx^*<0cTx∗<0 and (LD) is infeasible, or −bTy∗<0-b^Ty^*<0−bTy∗<0 and (LP) is infeasible.

In words: within O(nL)O(\sqrt nL)O(n​L) iterations, the predictor–corrector algorithm, coupled with the termination technique, generates either optimal solutions to (LP) and (LD) or an indication that (LP) or (LD) is infeasible.

Formalization Note O(nL)O(\sqrt nL)O(n​L) is pinned as Cn LC\sqrt n\,LCn​L with CCC absolute, chosen before m,nm,nm,n and the data; LLL is the encoding size of the integer data (definition BitLength) and n≥1n\ge1n≥1 is implicit in the paper. "An indication that (LP) or (LD) is infeasible" is read through Theorem 3 (ii): the indication is the negative sign of cTx∗c^Tx^*cTx∗ or −bTy∗-b^Ty^*−bTy∗ together with the infeasibility it certifies. The conclusions are stated for the unscaled projection output; they are invariant under the positive rescaling to (9). The algorithm is a relation on finite runs: a Newton solution and the attained predictor maximum are required for steps before the termination iterate. Existence of a successful finite run is asserted, so the corollary remains substantive when an infinite run cannot be extended.

Preamble
import Mathlib
import Definitions.Def_SelfDualLP_Complexity_LPData
import Definitions.Def_SelfDualLP_Complexity_HLP
import Definitions.Def_SelfDualLP_Complexity_Neighborhood
import Definitions.Def_SelfDualLP_Complexity_PCSequence
import Definitions.Def_SelfDualLP_Complexity_Termination
import Definitions.Def_SelfDualLP_Complexity_BitLength

open Matrix
Formal statement
namespace SelfDualLP.Complexity

/-- Corollary 7 (p. 62), with `O(√n L)` pinned as `C·√n·L` for an absolute constant `C > 0`.
Let (LP) and (LD) have integer data `(A, b, c)` with `n ≥ 1` and bit length `L`. For every
finite run of the predictor–corrector algorithm applied to (HLP) under (7), there
is an iteration `k ≤ C√n L` at which the termination projection has an output, and every
termination output `u = (y*, x*, τ*, θ*, s*, κ*)` at `zᵏ` either
* has `τ* > 0`, `x*/τ*` optimal for (LP) and `(y*/τ*, s*/τ*)` optimal for (LD), or
* has `τ* = 0` and indicates infeasibility: `cᵀx* < 0` and (LD) is infeasible, or
  `−bᵀy* < 0` and (LP) is infeasible. -/
theorem corollary_7 :
    ∃ C : ℝ, 0 < C ∧ ∀ (m n : ℕ), 1 ≤ n →
      ∀ (A : Matrix (Fin m) (Fin n) ℤ) (b : Fin m → ℤ) (c : Fin n → ℤ),
        ∃ (k : ℕ) (z : ℕ → HLPPoint m n),
          IsPCSequence (castMat A) (castVec b) (castVec c) z k ∧
          (k : ℝ) ≤ C * Real.sqrt (n : ℝ) * (bitLength A b c : ℝ) ∧
          (∃ u, IsTerminationOutput (castMat A) (castVec b) (castVec c) (z k) u) ∧
          ∀ u, IsTerminationOutput (castMat A) (castVec b) (castVec c) (z k) u →
            (0 < u.τ ∧ LPOptimal (castMat A) (castVec b) (castVec c) (u.τ⁻¹ • u.x) ∧
                LDOptimal (castMat A) (castVec b) (castVec c) (u.τ⁻¹ • u.y) (u.τ⁻¹ • u.s)) ∨
            (u.τ = 0 ∧
              ((castVec c ⬝ᵥ u.x < 0 ∧ ¬ LDIsFeasible (castMat A) (castVec c)) ∨
               (-(castVec b ⬝ᵥ u.y) < 0 ∧ ¬ LPIsFeasible (castMat A) (castVec b) (castVec c)))) := by sorry

end SelfDualLP.Complexity
Source
Ye, Todd, Mizuno, An O(√nL)-Iteration Homogeneous and Self-Dual Linear Programming Algorithm, Math. Oper. Res. 19(1) (1994), p. 62, Corollary 7; Theorem 6 (p. 61) and Theorem 3 (p. 58)
Human review
  • Endorsed by Shuze Chen · Oct 6, 2026

    Confirmed by the moderator at approval.

  • Endorsed by mikedeng1 · Oct 6, 2026

    Confirmed by the mission captain (proposal self-audit).

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