Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Theorem 6 — a strictly self-complementary solution of (HLP) in O(nL)O(\sqrt n L)O(n​L) predictor–corrector iterations

Disproved
SelfDualLP.Complexity.theorem_6

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) and (LD) 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 at zkz^kzk, rescaled to the normalization (9), is a strictly self-complementary solution of (HLP).

That is, the predictor–corrector algorithm, coupled with the termination technique, generates a strictly self-complementary solution for (HLP) in O(nL)O(\sqrt nL)O(n​L) iterations.

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. 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 theorem remains substantive when an infinite run cannot be extended. The hypothesis n≥1n\ge1n≥1 is implicit in the paper. The rescaling by (n+1)/(eTx∗+eTs∗+τ∗+κ∗)(n+1)/(e^Tx^*+e^Ts^*+\tau^*+\kappa^*)(n+1)/(eTx∗+eTs∗+τ∗+κ∗) is needed because the projection imposes only the homogeneous rows of (HLP).

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

/-- Theorem 6 (p. 61), 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 sequence of
iterates of the predictor–corrector algorithm applied to (HLP) under (7), there is a finite
run ending at iteration `k ≤ C√n L` at which the termination projection has an output, and every termination
output at `zᵏ`, rescaled to (9), is a strictly self-complementary solution of (HLP). -/
theorem theorem_6 :
    ∃ 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 →
            StrictlySelfComplementary7 (castMat A) (castVec b) (castVec c) (rescaleOutput u) := 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. 61, Theorem 6; proof on pp. 61–62
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