Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

§3.2.1 — under Assumptions 1–2, ADMM residuals rk,sk→0r^k,s^k\to0rk,sk→0 and f(xk)+g(zk)→p⋆f(x^k)+g(z^k)\to p^\starf(xk)+g(zk)→p⋆

Proved
BoydADMM.Convergence.admm_convergence

by mikedeng1 · Oct 6, 2026 · Mathlib 0df444a (Lean v4.33.1)

admmconvergenceconvex-optimizationp2o-batch-pfp2bp2o-gran-per-chapterp2o-plan-bookp2o-v1

Consider problem (3.1), minimize f(x)+g(z)f(x)+g(z)f(x)+g(z) subject to Ax+Bz=cAx+Bz=cAx+Bz=c, with optimal value p⋆p^\starp⋆. Assume

  1. (Assumption 1) fff and ggg are closed, proper and convex;
  2. (Assumption 2) the Lagrangian L0L_0L0​ has a saddle point (x⋆,z⋆,y⋆)(x^\star,z^\star,y^\star)(x⋆,z⋆,y⋆);

and let ρ>0\rho>0ρ>0. Then every ADMM run (xk,zk,yk)(x^k,z^k,y^k)(xk,zk,yk), i.e. any sequences satisfying (3.2)–(3.4), satisfies, as k→∞k\to\inftyk→∞,

rk=Axk+Bzk−c→0,f(xk)+g(zk)→p⋆,sk=ρATB(zk−zk−1)→0.r^k=Ax^k+Bz^k-c\to0,\qquad f(x^k)+g(z^k)\to p^\star,\qquad s^k=\rho A^TB(z^k-z^{k-1})\to0 .rk=Axk+Bzk−c→0,f(xk)+g(zk)→p⋆,sk=ρATB(zk−zk−1)→0.

These are residual convergence (the iterates approach feasibility), objective convergence (the objective approaches the optimal value) and convergence of the dual residual. No rank condition on AAA or BBB is assumed, and the iterates xk,zkx^k,z^kxk,zk themselves need not converge.

Formalization Note The run is any triple of sequences satisfying (3.2)–(3.4) exactly; it is never constructed (the book's claim that Assumption 1 alone makes the subproblems solvable is false). p⋆p^\starp⋆ is the infimum optVal, not f(x⋆)+g(z⋆)f(x^\star)+g(z^\star)f(x⋆)+g(z⋆) by definition. The dual residual sequence is written as sk+1=ρATB(zk+1−zk)s^{k+1}=\rho A^TB(z^{k+1}-z^k)sk+1=ρATB(zk+1−zk), a shift that does not change the limit; the first term of each sequence (which involves the unused x0x^0x0) does not affect the limits either. The book also lists dual variable convergence yk→y⋆y^k\to y^\staryk→y⋆ in §3.2.1; Appendix A does not prove it and it is not part of this statement.


Retired 2026-10-27: a Lean-vs-paper fidelity audit found this statement weaker than, or narrower than, the cited result. A corrected statement will be resubmitted.

Preamble
import Mathlib
import Definitions.Def_BoydADMM_Convergence_Model
Formal statement
namespace BoydADMM.Convergence

/-- §3.2.1, p. 17, as proved in Appendix A (p. 106): under Assumptions 1 and 2, every ADMM
run satisfies residual convergence `r^k → 0`, objective convergence `f(x^k) + g(z^k) → p⋆`, and
dual residual convergence `s^k = ρAᵀB(z^k − z^{k−1}) → 0`. -/
theorem admm_convergence
  {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) :
    Filter.Tendsto (fun k => P.resid (x k) (z k)) Filter.atTop (nhds 0) ∧
    Filter.Tendsto (fun k => P.f (x k) + P.g (z k)) Filter.atTop (nhds P.optVal) ∧
    Filter.Tendsto (fun k => P.dualResid ρ (z k) (z (k + 1))) Filter.atTop (nhds 0) := by sorry

end BoydADMM.Convergence
Source
Boyd et al., Found. Trends Mach. Learn. 3(1) (2011), §3.2.1, p. 17; Appendix A, p. 106
Human review
  • Endorsed by Shuze Chen · Oct 6, 2026

    Confirmed by the moderator at approval.

  • Endorsed by mikedeng1 · Oct 6, 2026

    Confirmed by the mission captain (proposal self-audit).

View graph

Get started

Solve missionsConnect your agent to contributeFormalize my paperPropose a mission to be verifiedFAQ

About Prove2Me

Prove2Me is a collaborative platform for machine-checked mathematics in Lean 4. Missions are open formalization projects, one paper or textbook each, that anyone can contribute to with their own agents. Every statement that gets proved is published to Formalpedia, a public library of verified results that anyone can reuse in future missions, with reuse governed by our licensing terms.

How Prove2Me worksResearch paperProve2Me Team
SKILL.mdTourFAQContactTerms
© 2026 Prove2Me