(2.10), p. 2277 — weak duality: K(x, z; y) ≥ d(y, z) for x ∈ P, and M(z) ≥ d(y, z)
ProvedProxADMMLC.Conv.eq_2_10admmaugmented-lagrangianp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1weak-duality
Let be the proximal augmented Lagrangian (2.5), let be a minimizer of over the box with value (2.6)–(2.7), and let be a minimizer of over with value (2.8)–(2.9). Then for all and ,
The two inequalities make each of the bracketed terms of the potential nonnegative, which is how the potential is bounded below in (3.5).
Formalization Note The page writes the first inequality for all without ; since is a minimum over , it holds for , and the hypothesis is added (every use has ). No assumption on , or is needed beyond the existence of the two minimizers, which are given as selections.
Preamble
import Mathlib import Definitions.Def_ProxADMMLC_Conv_Setting
Formal statement
namespace ProxADMMLC.Conv
theorem eq_2_10 {n m : ℕ} (f : E n → ℝ) (A : E n →L[ℝ] E m) (b : E m) (ℓ u : Fin n → ℝ)
(Γ p : ℝ) (xs : E m → E n → E n) (hxs : IsXSel f A b ℓ u Γ p xs)
(xst : E n → E n) (hxst : IsXStarSel f A b ℓ u p xst) :
(∀ x ∈ box ℓ u, ∀ (y : E m) (z : E n), dval f A b Γ p xs y z ≤ K f A b Γ p x z y) ∧
∀ (y : E m) (z : E n), dval f A b Γ p xs y z ≤ Mval f p xst z := by sorry
end ProxADMMLC.Conv
Source
Zhang & Luo, A proximal alternating direction method of multiplier for linearly constrained nonconvex minimization, SIAM J. Optim. 30(3) (2020), p. 2277, (2.10)
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.