Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Lemma 5 — with ρ = 0 the ALADIN dual iterate λ⁺ equals the dual Newton step λ⁺_DD of (A.4)

Proved
ALADIN.DualDecomp.lemma_5

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

augmented-lagrangiandistributed-optimizationdual-decompositionp2o-batch-pfp2bp2o-gran-per-chapterp2o-plan-paperp2o-v1

Let (f,h,A,b)(f,h,A,b)(f,h,A,b) be an instance of problem (1.1) in which every fif_ifi​ and hih_ihi​ is twice continuously differentiable, every fif_ifi​ is strictly convex and every component of every hih_ihi​ is convex. Consider one iteration of Algorithm 2 from (x,λ)(x,\lambda)(x,λ) with

  1. penalty parameter ρ=0\rho = 0ρ=0 and positive semidefinite scaling matrices Σi\Sigma_iΣi​ in step 1, and step-1 outputs (yi,κi)(y_i,\kappa_i)(yi​,κi​) (so yiy_iyi​ solves (A.2) with multiplier κi\kappa_iκi​);
  2. constraint Jacobian approximations Ci∈Rnh×nC_i\in\mathbb R^{n_h\times n}Ci​∈Rnh​×n of full row rank and positive definite Hessian approximations HiH_iHi​ in step 3;
  3. any μ>0\mu > 0μ>0 in step 4, with (Δy,s,λQP,ν)(\Delta y, s, \lambda_{\mathrm{QP}}, \nu)(Δy,s,λQP​,ν) solving the KKT system of the coupled QP (3.3);
  4. step sizes α3=α\alpha_3 = \alphaα3​=α with α∈(0,1]\alpha\in(0,1]α∈(0,1] in step 5.

Let MMM be given by (A.6) and ∇V(λ)=∑iAiyi−b\nabla V(\lambda) = \sum_i A_i y_i - b∇V(λ)=∑i​Ai​yi​−b by (A.3). Then M−1μIM - \frac1\mu IM−μ1​I is invertible and the step-5 iterate coincides with the (inexact) dual Newton step (A.4):

λ+=λ+α3(λQP−λ) = λ−α(M−1μI)−1∇V(λ)=λDD+,\lambda^+ = \lambda + \alpha_3(\lambda_{\mathrm{QP}} - \lambda)\ =\ \lambda - \alpha\Big(M - \frac1\mu I\Big)^{-1}\nabla V(\lambda) = \lambda^+_{\mathrm{DD}},λ+=λ+α3​(λQP​−λ) = λ−α(M−μ1​I)−1∇V(λ)=λDD+​,

where

M=−∑i=1NAi[Hi−1−Hi−1Ci⊤[CiHi−1Ci⊤]−1CiHi−1]Ai⊤.M = -\sum_{i=1}^N A_i\Big[H_i^{-1} - H_i^{-1}C_i^\top\big[C_iH_i^{-1}C_i^\top\big]^{-1}C_iH_i^{-1}\Big]A_i^\top .M=−i=1∑N​Ai​[Hi−1​−Hi−1​Ci⊤​[Ci​Hi−1​Ci⊤​]−1Ci​Hi−1​]Ai⊤​.

The lemma makes Remark 4.2 precise: with ρ=0\rho = 0ρ=0, ALADIN is a dual decomposition method whose dual update is a Levenberg–Marquardt-regularized dual Newton step, with 1/μ1/\mu1/μ as the regularization parameter.

Formalization Note (A.6) as printed has [CiHiCi⊤]†[C_iH_iC_i^\top]^\dagger[Ci​Hi​Ci⊤​]†; this is a typo for [CiHi−1Ci⊤]†[C_iH_i^{-1}C_i^\top]^\dagger[Ci​Hi−1​Ci⊤​]†, cf. (A.5); the corrected bracket is used, and since it is invertible its pseudo-inverse is written as the inverse. The invertibility of M−1μIM - \frac1\mu IM−μ1​I, taken for granted on the page, is part of the conclusion because Mathlib's matrix inverse returns 000 on singular matrices. The QP (3.3) enters through its KKT system with the sign convention of footnote 4. ∇V(λ)\nabla V(\lambda)∇V(λ) is the formula (A.3). The convexity hypotheses and α∈(0,1]\alpha\in(0,1]α∈(0,1] are kept as on the page; the identity itself does not use them.

Preamble
import Mathlib
import Definitions.Def_ALADIN_DualDecomp_Problem
import Definitions.Def_ALADIN_DualDecomp_Step
Formal statement
namespace ALADIN.DualDecomp

open Matrix

/-- Lemma 5 (Houska–Frasch–Diehl 2016, p. 1123), with (A.6) corrected to `[Cᵢ Hᵢ⁻¹ Cᵢᵀ]⁻¹`.
Let `fᵢ`, `hᵢ` be `C²`, `fᵢ` strictly convex and every component of `hᵢ` convex. Run one iteration of
Algorithm 2 from `(x, λ)` with `ρ = 0` and PSD scaling matrices `Σᵢ`: `(yᵢ, κᵢ)` is the step-1 output,
`Cᵢ` have full row rank, `Hᵢ` are positive definite, `μ > 0`, `(Δy, s, λ_QP, ν)` solves the KKT system
of QP (3.3), and `α₃ = α` with `α ∈ (0, 1]`. Then `M − (1/μ) I` is invertible and the step-5 iterate
`λ⁺ = λ + α₃(λ_QP − λ)` equals the dual Newton step `λ⁺_DD = λ − α (M − (1/μ) I)⁻¹ ∇V(λ)` of (A.4),
with `M` from (A.6) and `∇V(λ) = ∑ᵢ Aᵢ yᵢ − b` from (A.3). -/
theorem lemma_5 {N n m nh : ℕ} (P : Problem N n m nh)
    (hf : ∀ i, ContDiff ℝ 2 (P.f i)) (hh : ∀ i, ContDiff ℝ 2 (P.h i))
    (hfconv : ∀ i, StrictConvexOn ℝ Set.univ (P.f i))
    (hhconv : ∀ i j, ConvexOn ℝ Set.univ (fun z => P.h i z j))
    (x : Fin N → Fin n → ℝ) (lam : Fin m → ℝ)
    (ρ : ℝ) (hρ : ρ = 0) (Sig : Fin N → Matrix (Fin n) (Fin n) ℝ) (hSig : ∀ i, (Sig i).PosSemidef)
    (y : Fin N → Fin n → ℝ) (κ : Fin N → Fin nh → ℝ)
    (hstep1 : ∀ i, Step1Solution P ρ (Sig i) (x i) lam i (y i) (κ i))
    (C : Fin N → Matrix (Fin nh) (Fin n) ℝ) (hC : ∀ i, (C i).rank = nh)
    (H : Fin N → Matrix (Fin n) (Fin n) ℝ) (hH : ∀ i, (H i).PosDef)
    (μ : ℝ) (hμ : 0 < μ)
    (Δy : Fin N → Fin n → ℝ) (s : Fin m → ℝ) (lamQP : Fin m → ℝ) (ν : Fin N → Fin nh → ℝ)
    (hQP : QPKKT P lam y κ C H μ Δy s lamQP ν)
    (α α₃ : ℝ) (hα : α ∈ Set.Ioc (0 : ℝ) 1) (hα₃ : α₃ = α) :
    IsUnit (Mmat P C H - μ⁻¹ • (1 : Matrix (Fin m) (Fin m) ℝ)).det ∧
    lamPlus lam α₃ lamQP = lamDD lam α μ (Mmat P C H) (gradV P y) := by sorry

end ALADIN.DualDecomp
Source
Houska, Frasch, Diehl, An augmented Lagrangian based algorithm for distributed nonconvex optimization, SIAM J. Optim. 26 (2016), p. 1123, Lemma 5
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