Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Lemma 5 — the step length of Algorithm 2 is at least θ2=min⁡{1,βγμ/∥Pq∥∞}\theta_2 = \min\{1, \beta\gamma\mu/\|Pq\|_\infty\}θ2​=min{1,βγμ/∥Pq∥∞​} (resp. θ2−\theta_2^-θ2−​)

Proved
AdaptiveStepIPM.WideNbhd.lemma_5

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

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

Let β,γ∈(0,1)\beta,\gamma\in(0,1)β,γ∈(0,1), let N\mathcal NN be N∞(β)\mathcal N_\infty(\beta)N∞​(β) or N∞−(β)\mathcal N^-_\infty(\beta)N∞−​(β), let (x,s)∈N(x,s)\in\mathcal N(x,s)∈N with μ=xTs/n\mu = x^Ts/nμ=xTs/n, let (dx,dy,ds)(d_x,d_y,d_s)(dx​,dy​,ds​) solve (2) at (x,s)(x,s)(x,s) with parameter γ\gammaγ, and let p,qp,qp,q be the scaled vectors (6). Put

θ2:=min⁡{1,βγμ∥Pq∥∞},θ2−:=min⁡{1,βγμ∥Pq∥∞−}.\theta_2 := \min\Big\{1,\frac{\beta\gamma\mu}{\|Pq\|_\infty}\Big\},\qquad \theta_2^- := \min\Big\{1,\frac{\beta\gamma\mu}{\|Pq\|^-_\infty}\Big\}.θ2​:=min{1,∥Pq∥∞​βγμ​},θ2−​:=min{1,∥Pq∥∞−​βγμ​}.
  1. If N=N∞(β)\mathcal N = \mathcal N_\infty(\beta)N=N∞​(β), then (x(θ),s(θ))=(x+θdx,s+θds)∈N∞(β)(x(\theta),s(\theta)) = (x+\theta d_x, s+\theta d_s)\in\mathcal N_\infty(\beta)(x(θ),s(θ))=(x+θdx​,s+θds​)∈N∞​(β) for every θ∈[0,θ2]\theta\in[0,\theta_2]θ∈[0,θ2​]; hence the largest admissible step θˉ\bar\thetaθˉ of Algorithm 2 satisfies θˉ≥θ2\bar\theta\ge\theta_2θˉ≥θ2​.
  2. If N=N∞−(β)\mathcal N = \mathcal N^-_\infty(\beta)N=N∞−​(β), the same holds with θ2−\theta_2^-θ2−​ in place of θ2\theta_2θ2​.

Since one iteration reduces the duality measure to (1−θˉ(1−γ))μ(1-\bar\theta(1-\gamma))\mu(1−θˉ(1−γ))μ, a lower bound on θˉ\bar\thetaθˉ is a guaranteed decrease of the duality gap.

Formalization Note When the norm in a denominator is 000, the quotient is +∞+\infty+∞ and the minimum is 111; Lean's division by zero gives 000, so this case is defined as 111 explicitly. The admissibility of every θ∈[0,θ2]\theta\in[0,\theta_2]θ∈[0,θ2​] is the statement the paper's proof establishes; the bound on θˉ\bar\thetaθˉ is stated for every greatest admissible step. The standing condition n≥1n\ge1n≥1 is a hypothesis.

Preamble
import Mathlib
import Definitions.Def_AdaptiveStepIPM_WideNbhd_Neighborhoods
import Definitions.Def_AdaptiveStepIPM_WideNbhd_Algorithm2
Formal statement
namespace AdaptiveStepIPM.WideNbhd

open Matrix

/-- Lemma 5 of Mizuno–Todd–Ye (p. 10): let `β, γ ∈ (0, 1)`, `(x, s)` in the neighbourhood `N`,
`d` a solution of (2) at `(x, s)` with `γ`, `μ = xᵀs/n` and `p, q` as in (6).
If `N = N_∞(β)`, every `θ ∈ [0, θ₂]` with `θ₂ = min{1, βγμ/‖AdaptiveStepIPM.PredCorr.Pq‖_∞}` keeps `(x(θ), s(θ)) ∈ N`, so
the largest admissible `θ̄` satisfies `θ̄ ≥ θ₂`; likewise for `N = N_∞⁻(β)` with
`θ₂⁻ = min{1, βγμ/‖AdaptiveStepIPM.PredCorr.Pq‖⁻_∞}`. (The minimum is `1` when the norm is `0`.) -/
theorem lemma_5 {n m : ℕ} (hn : 1 ≤ n) (A : Matrix (Fin m) (Fin n) ℝ) (b : Fin m → ℝ)
    (c : Fin n → ℝ) (β γ : ℝ) (hβ0 : 0 < β) (hβ1 : β < 1) (hγ0 : 0 < γ) (hγ1 : γ < 1)
    (x s : Fin n → ℝ) (dx : Fin n → ℝ) (dy : Fin m → ℝ) (ds : Fin n → ℝ)
    (hd : IsDirection A x s γ dx dy ds) :
    ((x, s) ∈ Ninf A b c β →
        (∀ θ ∈ Set.Icc (0 : ℝ) (stepBound β γ (AdaptiveStepIPM.PredCorr.mu x s) (normInf (AdaptiveStepIPM.PredCorr.Pq x s dx ds))),
            (x + θ • dx, s + θ • ds) ∈ Ninf A b c β) ∧
        ∀ θbar, IsGreatest (admissibleSteps (Ninf A b c β) x s dx ds) θbar →
          stepBound β γ (AdaptiveStepIPM.PredCorr.mu x s) (normInf (AdaptiveStepIPM.PredCorr.Pq x s dx ds)) ≤ θbar) ∧
      ((x, s) ∈ NinfMinus A b c β →
        (∀ θ ∈ Set.Icc (0 : ℝ) (stepBound β γ (AdaptiveStepIPM.PredCorr.mu x s) (normInfNeg (AdaptiveStepIPM.PredCorr.Pq x s dx ds))),
            (x + θ • dx, s + θ • ds) ∈ NinfMinus A b c β) ∧
        ∀ θbar, IsGreatest (admissibleSteps (NinfMinus A b c β) x s dx ds) θbar →
          stepBound β γ (AdaptiveStepIPM.PredCorr.mu x s) (normInfNeg (AdaptiveStepIPM.PredCorr.Pq x s dx ds)) ≤ θbar) := by sorry

end AdaptiveStepIPM.WideNbhd
Source
Mizuno, Todd, Ye, On adaptive-step primal-dual interior-point algorithms for linear programming, Cornell ORIE Technical Report No. 944 (1990, rev. 1991), p. 10, Lemma 5
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