Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Lemma 4 — along the combined corrector direction (18) the residuals and the complementarity gap both scale by 1−α(1−γ)1-\alpha(1-\gamma)1−α(1−γ)

Proved
ExpConeIPM.Corrector.lemma_4

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

conic-optimizationinterior-point-methodsp2o-batch-pfp2bp2o-gran-per-chapterp2o-plan-paperp2o-v1

Work in the homogeneous model of a conic pair: A ⁣:Rn→RmA\colon\mathbb R^n\to\mathbb R^mA:Rn→Rm has full row rank, b∈Rmb\in\mathbb R^mb∈Rm, c∈Rnc\in\mathbb R^nc∈Rn, K^⊆Rn\hat K\subseteq\mathbb R^nK^⊆Rn is a proper cone with a ϑ^\hat\varthetaϑ^-logarithmically homogeneous self-concordant barrier F^\hat FF^, K=K^×R+K=\hat K\times\mathbb R_+K=K^×R+​, F(x^,τ)=F^(x^)−log⁡τF(\hat x,\tau)=\hat F(\hat x)-\log\tauF(x^,τ)=F^(x^)−logτ, ϑ=ϑ^+1\vartheta=\hat\vartheta+1ϑ=ϑ^+1, and GGG is the residual of the homogeneous self-dual embedding. Let z=(x,s,y)z=(x,s,y)z=(x,s,y) be an iterate with x∈int⁡Kx\in\operatorname{int}Kx∈intK, s∈int⁡K∗s\in\operatorname{int}K^*s∈intK∗, let μ=⟨x,s⟩/ϑ\mu=\langle x,s\rangle/\varthetaμ=⟨x,s⟩/ϑ, let x~=−F∗′(s)\tilde x=-F_*'(s)x~=−F∗′​(s), s~=−F′(x)\tilde s=-F'(x)s~=−F′(x) be the shadow iterates, and let WWW be a nonsingular scaling with v=Wx=W−Tsv=Wx=W^{-T}sv=Wx=W−Ts and v~=Wx~=W−Ts~\tilde v=W\tilde x=W^{-T}\tilde sv~=Wx~=W−Ts~. Let Δza\Delta z^{a}Δza solve the affine system (11), let η=−12F′′′(x)[Δxa,(F′′(x))−1Δsa]\eta=-\tfrac12F'''(x)[\Delta x^{a},(F''(x))^{-1}\Delta s^{a}]η=−21​F′′′(x)[Δxa,(F′′(x))−1Δsa] be the corrector (16), and let γ>0\gamma>0γ>0 be a centering parameter.

Then every solution Δz=(Δx,Δs,Δy)\Delta z=(\Delta x,\Delta s,\Delta y)Δz=(Δx,Δs,Δy) of the combined system (18),

G(Δz)=−(1−γ)G(z),WΔx+W−TΔs=−v+γμv~−W−Tη,G(\Delta z)=-(1-\gamma)G(z),\qquad W\Delta x+W^{-T}\Delta s=-v+\gamma\mu\tilde v-W^{-T}\eta,G(Δz)=−(1−γ)G(z),WΔx+W−TΔs=−v+γμv~−W−Tη,

satisfies

⟨s,Δx⟩+⟨x,Δs⟩=−(1−γ)⟨x,s⟩,⟨Δx,Δs⟩=0,\langle s,\Delta x\rangle+\langle x,\Delta s\rangle=-(1-\gamma)\langle x,s\rangle,\qquad\langle\Delta x,\Delta s\rangle=0,⟨s,Δx⟩+⟨x,Δs⟩=−(1−γ)⟨x,s⟩,⟨Δx,Δs⟩=0,

and for all α∈R\alpha\in\mathbb Rα∈R,

G(z+αΔz)=(1−α(1−γ)) G(z),⟨x+αΔx,s+αΔs⟩=(1−α(1−γ))⟨x,s⟩.G(z+\alpha\Delta z)=(1-\alpha(1-\gamma))\,G(z),\qquad \langle x+\alpha\Delta x,s+\alpha\Delta s\rangle=(1-\alpha(1-\gamma))\langle x,s\rangle .G(z+αΔz)=(1−α(1−γ))G(z),⟨x+αΔx,s+αΔs⟩=(1−α(1−γ))⟨x,s⟩.

So a step of length α\alphaα along the combined direction reduces the infeasibility residuals and the complementarity gap by the same factor. Iterating, G(zk)=μkG(z0)G(z^k)=\mu^kG(z^0)G(zk)=μkG(z0) and ⟨xk,sk⟩=μkϑ\langle x^k,s^k\rangle=\mu^k\vartheta⟨xk,sk⟩=μkϑ when μ0=1\mu^0=1μ0=1: the algorithm needs no merit function to balance feasibility against optimality.

Formalization Note The first identity is printed on p. 353 as ⟨s,Δx⟩+⟨x,Δs⟩=0\langle s,\Delta x\rangle+\langle x,\Delta s\rangle=0⟨s,Δx⟩+⟨x,Δs⟩=0. That is a misprint: the proof on the same page derives −(1−γ)⟨x,s⟩-(1-\gamma)\langle x,s\rangle−(1−γ)⟨x,s⟩, and together with ⟨Δx,Δs⟩=0\langle\Delta x,\Delta s\rangle=0⟨Δx,Δs⟩=0 the printed version would give ⟨x+αΔx,s+αΔs⟩=⟨x,s⟩\langle x+\alpha\Delta x,s+\alpha\Delta s\rangle=\langle x,s\rangle⟨x+αΔx,s+αΔs⟩=⟨x,s⟩, contradicting the last identity whenever γ≠1\gamma\ne1γ=1. The repaired identity is stated (compare (12) of Lemma 2, the case γ=0\gamma=0γ=0, η=0\eta=0η=0). Inner products include the homogenizing coordinates, ⟨x,s⟩=⟨x^,s^⟩+τκ\langle x,s\rangle=\langle\hat x,\hat s\rangle+\tau\kappa⟨x,s⟩=⟨x^,s^⟩+τκ. A single proper cone K^\hat KK^ stands for the paper's product of cones, and WWW is any nonsingular linear map satisfying (8), not necessarily block diagonal; both are generalizations. The identities hold for every real γ\gammaγ; the hypothesis γ>0\gamma>0γ>0 is the paper's.

Preamble
import Mathlib
import Definitions.Def_SelfScaledIPM_ShortStep_Setting
import Definitions.Def_ExpConeIPM_Corrector_HomogeneousModel
import Definitions.Def_ExpConeIPM_Corrector_SearchDirections

open scoped InnerProductSpace
Formal statement
namespace ExpConeIPM.Corrector

/-- **Lemma 4** (Dahl–Andersen, Math. Program. 194 (2022), p. 353), with the misprinted first
identity repaired. In the setting of Lemma 2, let `Δzᵃ` solve the affine system (11), let
`η := −½ F'''(x)[Δxᵃ, (F''(x))⁻¹Δsᵃ]` be the corrector (16) of the augmented barrier `F = F̂ − log τ`,
let `γ > 0`, and let `Δz` solve the combined system (18) with `μ = ⟨x, s⟩/ϑ`, `ϑ = ϑ̂ + 1`. Then
`⟨s, Δx⟩ + ⟨x, Δs⟩ = −(1 − γ)⟨x, s⟩` (printed as `= 0` on p. 353; the proof on the same page derives
`−(1 − γ)⟨x, s⟩`, and `= 0` contradicts the last identity), `⟨Δx, Δs⟩ = 0`, and for all `α ∈ ℝ`
`G(z + αΔz) = (1 − α(1 − γ)) G(z)` and `⟨x + αΔx, s + αΔs⟩ = (1 − α(1 − γ))⟨x, s⟩`. -/
theorem lemma_4 {n m : ℕ}
    (A : EuclideanSpace ℝ (Fin n) →L[ℝ] EuclideanSpace ℝ (Fin m))
    (b : EuclideanSpace ℝ (Fin m)) (c : EuclideanSpace ℝ (Fin n))
    (hA : Function.Surjective A)
    (Khat : Set (EuclideanSpace ℝ (Fin n))) (Fhat : EuclideanSpace ℝ (Fin n) → ℝ) (ϑhat : ℝ)
    (hK : SelfScaledIPM.ShortStep.IsProperCone Khat)
    (hF : SelfScaledIPM.ShortStep.IsLogHomBarrier Khat Fhat ϑhat)
    (x s : EuclideanSpace ℝ (Fin (n + 1))) (y : EuclideanSpace ℝ (Fin m))
    (hz : IsInteriorIterate Khat x s)
    (W : EuclideanSpace ℝ (Fin (n + 1)) ≃L[ℝ] EuclideanSpace ℝ (Fin (n + 1)))
    (hW : IsDoubleSecantScaling (augCone Khat) (augBarrier Fhat) x s W)
    (dxa dsa : EuclideanSpace ℝ (Fin (n + 1))) (dya : EuclideanSpace ℝ (Fin m))
    (ha : IsAffineDirection A b c x s y W dxa dsa dya)
    (γ : ℝ) (hγ : 0 < γ)
    (dx ds : EuclideanSpace ℝ (Fin (n + 1))) (dy : EuclideanSpace ℝ (Fin m))
    (hd : IsCombinedDirection A b c Khat Fhat ϑhat x s y W
      (corrector (augBarrier Fhat) x dxa dsa) γ dx ds dy) :
    ⟪s, dx⟫_ℝ + ⟪x, ds⟫_ℝ = -(1 - γ) * ⟪x, s⟫_ℝ ∧ ⟪dx, ds⟫_ℝ = 0 ∧
      ∀ α : ℝ,
        residual A b c (x + α • dx) (s + α • ds) (y + α • dy) =
            (1 - α * (1 - γ)) • residual A b c x s y ∧
          ⟪x + α • dx, s + α • ds⟫_ℝ = (1 - α * (1 - γ)) * ⟪x, s⟫_ℝ := by sorry

end ExpConeIPM.Corrector
Source
Dahl, Andersen, A primal-dual interior-point algorithm for nonsymmetric exponential-cone optimization, Math. Program. 194 (2022), p. 353, Lemma 4 (first identity repaired per the proof on the same page)
Human review
  • Endorsed by Shuze Chen · Oct 8, 2026

    Confirmed by the moderator at approval.

  • Endorsed by mikedeng1 · Oct 8, 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