App. A, proof of Lemma 5 — eliminating the slack: min over s of (μ/2)‖s‖² − (λ_QP − λ)ᵀs = −‖λ_QP − λ‖²/(2μ)
ProvedALADIN.DualDecomp.slack_eliminationdual-decompositionp2o-batch-pfp2bp2o-gran-per-chapterp2o-plan-paperp2o-v1quadratic-programming
Let and . Then for every ,
and equality holds if and only if .
In the proof of Lemma 5 this is the step that removes the slack variable from the dual of the coupled QP (3.3): the inner minimum over of equals (written on the page).
Preamble
import Mathlib
Formal statement
namespace ALADIN.DualDecomp
open Matrix
/-- App. A, proof of Lemma 5, p. 1123: the minimization over the slack variable `s` in the dual of
QP (3.3). For `μ > 0` and `λ, λ_QP ∈ ℝᵐ`, every `s ∈ ℝᵐ` satisfies
`(μ/2)‖s‖²₂ − (λ_QP − λ)ᵀ s ≥ −(1/(2μ)) ‖λ_QP − λ‖²₂`, with equality iff `s = (λ_QP − λ)/μ`. -/
theorem slack_elimination {m : ℕ} (μ : ℝ) (hμ : 0 < μ) (lam lamQP : Fin m → ℝ) :
(∀ s : Fin m → ℝ,
-(1 / (2 * μ)) * ((lamQP - lam) ⬝ᵥ (lamQP - lam)) ≤
μ / 2 * (s ⬝ᵥ s) - (lamQP - lam) ⬝ᵥ s) ∧
(∀ s : Fin m → ℝ,
μ / 2 * (s ⬝ᵥ s) - (lamQP - lam) ⬝ᵥ s =
-(1 / (2 * μ)) * ((lamQP - lam) ⬝ᵥ (lamQP - lam)) ↔
s = μ⁻¹ • (lamQP - lam)) := 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, App. A, proof of Lemma 5, slack elimination
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.