App. A, proof of Lemma 5 — λ − (M − I/μ)⁻¹g is the unique maximizer of ½(ν−λ)ᵀM(ν−λ) + νᵀg − ‖ν−λ‖²/(2μ)
ProvedALADIN.DualDecomp.argmax_displaydual-decompositionp2o-batch-pfp2bp2o-gran-per-chapterp2o-plan-paperp2o-v1quadratic-programming
Let be symmetric negative semidefinite, , and . Define
Then is invertible and
is the unique maximizer of over .
In the proof of Lemma 5, with and from (A.6), is the dual objective of the QP (3.3) after the slack and have been eliminated, and the display identifies its maximizer with the Levenberg–Marquardt dual Newton direction.
Preamble
import Mathlib
Formal statement
namespace ALADIN.DualDecomp
open Matrix
/-- App. A, proof of Lemma 5, p. 1124 (the argmax display): let `M ∈ ℝ^{m×m}` be symmetric and negative
semidefinite, `μ > 0`, `λ ∈ ℝᵐ` and `g ∈ ℝᵐ` (in the paper `g = ∇V(λ)`). Then `M − (1/μ) I` is invertible
and `ν⋆ = λ − (M − (1/μ) I)⁻¹ g` is the unique maximizer over `ℝᵐ` of
`ν ↦ ½ (ν − λ)ᵀ M (ν − λ) + νᵀ g − (1/(2μ)) ‖ν − λ‖²₂`. -/
theorem argmax_display {m : ℕ} (M : Matrix (Fin m) (Fin m) ℝ) (hM : (-M).PosSemidef)
(μ : ℝ) (hμ : 0 < μ) (lam g : Fin m → ℝ) :
let φ : (Fin m → ℝ) → ℝ := fun ν =>
1 / 2 * ((ν - lam) ⬝ᵥ (M *ᵥ (ν - lam))) + ν ⬝ᵥ g - 1 / (2 * μ) * ((ν - lam) ⬝ᵥ (ν - lam))
let νstar := lam - (M - μ⁻¹ • (1 : Matrix (Fin m) (Fin m) ℝ))⁻¹ *ᵥ g
IsUnit (M - μ⁻¹ • (1 : Matrix (Fin m) (Fin m) ℝ)).det ∧
IsMaxOn φ Set.univ νstar ∧
∀ ν, φ ν = φ νstar → ν = νstar := by sorry
end ALADIN.DualDecomp
Source
Houska, Frasch, Diehl, An augmented Lagrangian based algorithm for distributed nonconvex optimization, SIAM J. Optim. 26 (2016), p. 1124, App. A, proof of Lemma 5, argmax display
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.