Lemma 4.1, p. 13 — a Newton step of length α scales the three residuals and the complementarity gap by 1 − α(1 − γ)
ProvedConicQuadIPM.NewtonStep.lemma_4_1Let be a product of cones, each the half-line , a quadratic cone or a rotated quadratic cone, with for , for a quadratic cone and for a rotated one. Let , , , let be any point and , and let solve the Newton system (22):
where , , , stacks the first unit vectors and . For a step size let as in (23). Then
The lemma says that one Newton step moves the homogeneous model's infeasibility and its complementarity gap toward zero at exactly the same rate . This is the basis of the convergence analysis of the homogeneous algorithm and of its stopping criteria.
Formalization Note Indices are 0-based and vectors are stored block by block; , , , and the second identity of (22) and of the conclusion is stated block by block, as is the fourth line of (22). Three printed slips are corrected: the third line of (22) prints for (with a free the third identity is false); the fourth identity of (24) prints for ; and the proof's constant on p. 14 should be (this affects only the proof). The dimension conventions are the paper's implicit ones and are needed: without them a block of dimension breaks . The hypotheses (from (23)) and (from (21)) are kept as on the page, although the identities hold for all real , . No interiority of the current point is assumed, as in the lemma.
Retired 2026-10-27: a Lean-vs-paper fidelity audit found this statement weaker than, or narrower than, the cited result. A corrected statement will be resubmitted.
import Mathlib import Definitions.Def_ConicQuadIPM_NewtonStep_Setting
namespace ConicQuadIPM.NewtonStep
open Matrix
theorem lemma_4_1
{m k : ℕ} (kind : Fin k → ConicQuadIPM.Complementarity.ConeKind) (n : Fin k → ℕ) (hwf : ConicQuadIPM.Complementarity.WellFormed kind n)
(A : (i : Fin k) → Matrix (Fin m) (Fin (n i)) ℝ) (b : Fin m → ℝ)
(c : (i : Fin k) → Fin (n i) → ℝ)
(x0 : (i : Fin k) → Fin (n i) → ℝ) (τ0 : ℝ) (y0 : Fin m → ℝ)
(s0 : (i : Fin k) → Fin (n i) → ℝ) (κ0 : ℝ) (γ : ℝ) (hγ : γ ∈ Set.Icc (0 : ℝ) 1)
(dx : (i : Fin k) → Fin (n i) → ℝ) (dτ : ℝ) (dy : Fin m → ℝ)
(ds : (i : Fin k) → Fin (n i) → ℝ) (dκ : ℝ)
(h22 : NewtonSystem kind n A b c x0 τ0 y0 s0 κ0 γ dx dτ dy ds dκ)
(α : ℝ) (hα : α ∈ Set.Icc (0 : ℝ) 1)
(x1 : (i : Fin k) → Fin (n i) → ℝ) (τ1 : ℝ) (y1 : Fin m → ℝ)
(s1 : (i : Fin k) → Fin (n i) → ℝ) (κ1 : ℝ)
(hx1 : ∀ i, x1 i = x0 i + α • dx i) (hτ1 : τ1 = τ0 + α * dτ)
(hy1 : y1 = y0 + α • dy) (hs1 : ∀ i, s1 i = s0 i + α • ds i)
(hκ1 : κ1 = κ0 + α * dκ) :
(∑ i, A i *ᵥ x1 i) - τ1 • b = (1 - α * (1 - γ)) • ((∑ i, A i *ᵥ x0 i) - τ0 • b) ∧
(∀ i, (A i)ᵀ *ᵥ y1 + s1 i - τ1 • c i
= (1 - α * (1 - γ)) • ((A i)ᵀ *ᵥ y0 + s0 i - τ0 • c i)) ∧
-(∑ i, c i ⬝ᵥ x1 i) + b ⬝ᵥ y1 - κ1
= (1 - α * (1 - γ)) * (-(∑ i, c i ⬝ᵥ x0 i) + b ⬝ᵥ y0 - κ0) ∧
(∑ i, dx i ⬝ᵥ ds i) + dτ * dκ = 0 ∧
(∑ i, x1 i ⬝ᵥ s1 i) + τ1 * κ1
= (1 - α * (1 - γ)) * ((∑ i, x0 i ⬝ᵥ s0 i) + τ0 * κ0) := by sorry
end ConicQuadIPM.NewtonStep
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.