Appendix A, p. 107 — is bounded, so and
ProvedBoydADMM.Convergence.summed_boundadmmconvergence-prooflyapunovp2o-batch-pfp2bp2o-gran-per-chapterp2o-plan-bookp2o-v1
Under Assumptions 1 and 2, with , a saddle point of and any ADMM run, let and . Then
and consequently and as .
The vanishing of gives, after multiplication by , the convergence of the dual residual to zero.
Formalization Note The book writes the sum from bounded by , obtained by iterating (A.1); since (A.1) is proved only for (see ineq_A1), we state the sum from bounded by , which yields the same limits. The infinite sum is stated as the bound on every partial sum, for all , which for nonnegative terms is equivalent and avoids Lean's convention for non-summable series.
Preamble
import Mathlib import Definitions.Def_BoydADMM_Convergence_Model
Formal statement
namespace BoydADMM.Convergence
/-- p. 107: iterating (A.1) gives
`ρ ∑_{k ≥ 1} (‖r^{k+1}‖₂² + ‖B(z^{k+1} − z^k)‖₂²) ≤ V^1` (every partial sum is bounded by
`V^1`), which implies `r^k → 0` and `B(z^{k+1} − z^k) → 0`. -/
theorem summed_bound
{n m p : ℕ} (P : Problem n m p) (hA1 : P.Assumption1) {ρ : ℝ} (hρ : 0 < ρ)
{xs : EuclideanSpace ℝ (Fin n)} {zs : EuclideanSpace ℝ (Fin m)}
{ys : EuclideanSpace ℝ (Fin p)} (hsp : P.IsSaddlePoint xs zs ys)
{x : ℕ → EuclideanSpace ℝ (Fin n)} {z : ℕ → EuclideanSpace ℝ (Fin m)}
{y : ℕ → EuclideanSpace ℝ (Fin p)} (hrun : P.IsADMMSeq ρ x z y) :
(∀ N : ℕ, ρ * ∑ j ∈ Finset.range N,
(‖P.resid (x (j + 2)) (z (j + 2))‖ ^ 2 + ‖P.Bmul (z (j + 2) - z (j + 1))‖ ^ 2) ≤
P.lyapunov ρ zs ys (z 1) (y 1)) ∧
Filter.Tendsto (fun k => P.resid (x k) (z k)) Filter.atTop (nhds 0) ∧
Filter.Tendsto (fun k => P.Bmul (z (k + 1) - z k)) Filter.atTop (nhds 0) := by sorry
end BoydADMM.Convergence
Source
Boyd et al., Found. Trends Mach. Learn. 3(1) (2011), Appendix A, p. 107
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.