Proof of Theorem 5.5, p. 19 — the relaxed ADMM multiplier updates give s + λ(v − u) = s⁺
ProvedNonconvexDRS.ADMM.step_identityadmmdouglas-rachfordp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1
Let , , , and . Given , , , let the multipliers be updated as in ADMM,
With , , and as in (5.2),
This is the DRS update of the governing sequence, read off the two multiplier updates of ADMM.
Formalization Note is unrestricted here; only is used, and the page's is kept.
Preamble
import Mathlib import Definitions.Def_NonconvexSplitting_Shared_LimitingSubdiff import Definitions.Def_NonconvexDRS_ADMM_Setting open NonconvexSplitting.Shared open Filter Topology open scoped InnerProductSpace
Formal statement
namespace NonconvexDRS.ADMM
/-- The first relation in the proof of Theorem 5.5, p. 19: with `s, u, v, s⁺` as in (5.2) and
`y⁺` produced from `(x, y, z, x⁺)` by the two multiplier updates of (ADMM),
`s + λ(v - u) = s⁺`. -/
theorem step_identity {m n p : ℕ}
(A : EuclideanSpace ℝ (Fin m) →L[ℝ] EuclideanSpace ℝ (Fin p))
(B : EuclideanSpace ℝ (Fin n) →L[ℝ] EuclideanSpace ℝ (Fin p)) (b : EuclideanSpace ℝ (Fin p))
(β lam : ℝ) (hβ : 0 < β)
(x xp : EuclideanSpace ℝ (Fin m)) (y yh yp : EuclideanSpace ℝ (Fin p))
(z : EuclideanSpace ℝ (Fin n))
(hyh : yh = y - (β * (1 - lam)) • (A x + B z - b))
(hyp : yp = yh + β • (A xp + B z - b)) :
A xp - (1 / β) • yp = (A x - (1 / β) • y) + lam • ((b - B z) - A x) := by sorry
end NonconvexDRS.ADMM
Source
Themelis & Patrinos, Douglas-Rachford splitting and ADMM for nonconvex optimization: tight convergence results, arXiv:1709.05747v4, p. 19, proof of Theorem 5.5 (first display)
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.