Lemma 2.1, p. 5 — the output of (2.4) satisfies the Q variational inequality
ProvedExtADMM.Orth.lemma_2_1admmconvex-optimizationp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1variational-inequality
For a three-block problem satisfying the standing assumptions, let and let be any run of the reordered ADMM scheme (2.4). At each iteration , its output lies in and, for every ,
Here and is the four-by-three block matrix in (2.9), including the coefficient in its final diagonal block. This inequality records the first-order information of one complete update cycle. The lemma itself needs no hypothesis.
Preamble
import Definitions.Def_ExtADMM_Orth_Setting set_option autoImplicit false
Formal statement
namespace ExtADMM.Orth
/-- Lemma 2.1, equation (2.8), p. 5. -/
theorem lemma_2_1 {n1 n2 n3 p : ℕ} (P : Problem n1 n2 n3 p)
(β : ℝ) (x1 : ℕ → Fin n1 → ℝ) (x2 : ℕ → Fin n2 → ℝ)
(x3 : ℕ → Fin n3 → ℝ) (lam : ℕ → Fin p → ℝ)
(hP : P.Standing) (hβ : 0 < β) (hrun : P.IsRun24 β x1 x2 x3 lam)
(k : ℕ) :
P.w x1 x2 x3 lam (k + 1) ∈ P.Omega ∧
∀ z ∈ P.Omega,
0 ≤ P.theta z - P.theta (P.w x1 x2 x3 lam (k + 1)) +
pair (z - P.w x1 x2 x3 lam (k + 1))
(P.F (P.w x1 x2 x3 lam (k + 1)) +
P.Qmul β (P.v x1 x3 lam k - P.v x1 x3 lam (k + 1))) := by sorry
end ExtADMM.Orth
Source
Chen, He, Ye & Yuan, The direct extension of ADMM for multi-block convex minimization problems is not necessarily convergent, Math. Program., DOI 10.1007/s10107-014-0826-5 (authors' version of January 22, 2014), p. 5, Lemma 2.1, (2.8)–(2.9)
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.