(3.5), p. 2279 — φᵗ ≥ M(zᵗ) ≥ f̲: the potential is bounded below
ProvedProxADMMLC.Conv.eq_3_5admmp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1potential-function
Let be differentiable and , let , , , be as in (2.6)–(2.9), and let . Then for every , and for every run of Algorithm 2.2 (with any parameters) and every , the potential satisfies
Since the potential decreases by (3.37), this lower bound makes the decreases summable; it is also what bounds the iteration count in Theorem 4.2.
Formalization Note is sInf (f '' feas A b ℓ u). The feasible set is nonempty (it contains ) and compact, and is continuous, so the infimum is attained and equals the paper's minimum; it is never Lean's junk value of sInf on an empty or unbounded set.
Preamble
import Mathlib import Definitions.Def_ProxADMMLC_Conv_Setting
Formal statement
namespace ProxADMMLC.Conv
theorem eq_3_5 {n m : ℕ} (f : E n → ℝ) (A : E n →L[ℝ] E m) (b : E m) (ℓ u : Fin n → ℝ)
(hℓu : ∀ i, ℓ i < u i) (hdiff : Differentiable ℝ f) (Γ p c α β : ℝ)
(hp : 0 < 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 z : ℕ → E n) (y : ℕ → E m) (hrun : IsRun f A b ℓ u Γ p c α β x y z) :
(∀ w ∈ box ℓ u, sInf (f '' feas A b ℓ u) ≤ Mval f p xst w) ∧
∀ t, Mval f p xst (z t) ≤ phi f A b Γ p xs xst (x t) (z t) (y t) ∧
sInf (f '' feas A b ℓ u) ≤ Mval f p xst (z t) := 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. 2279, (3.5) and the definition of f̲ (§3.1.1)
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.