Lemma 5 — with ρ = 0 the ALADIN dual iterate λ⁺ equals the dual Newton step λ⁺_DD of (A.4)
ProvedALADIN.DualDecomp.lemma_5Let be an instance of problem (1.1) in which every and is twice continuously differentiable, every is strictly convex and every component of every is convex. Consider one iteration of Algorithm 2 from with
- penalty parameter and positive semidefinite scaling matrices in step 1, and step-1 outputs (so solves (A.2) with multiplier );
- constraint Jacobian approximations of full row rank and positive definite Hessian approximations in step 3;
- any in step 4, with solving the KKT system of the coupled QP (3.3);
- step sizes with in step 5.
Let be given by (A.6) and by (A.3). Then is invertible and the step-5 iterate coincides with the (inexact) dual Newton step (A.4):
where
The lemma makes Remark 4.2 precise: with , ALADIN is a dual decomposition method whose dual update is a Levenberg–Marquardt-regularized dual Newton step, with as the regularization parameter.
Formalization Note (A.6) as printed has ; this is a typo for , cf. (A.5); the corrected bracket is used, and since it is invertible its pseudo-inverse is written as the inverse. The invertibility of , taken for granted on the page, is part of the conclusion because Mathlib's matrix inverse returns on singular matrices. The QP (3.3) enters through its KKT system with the sign convention of footnote 4. is the formula (A.3). The convexity hypotheses and are kept as on the page; the identity itself does not use them.
import Mathlib import Definitions.Def_ALADIN_DualDecomp_Problem import Definitions.Def_ALADIN_DualDecomp_Step
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
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.