Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Theorem 4.1, p. 14 — with strongly convex θᵢ the direct extension of ADMM is not necessarily convergent for all β > 0 (diverges on (4.1) at β = 1)

Proved
ExtADMM.StrongCvx.theorem_4_1

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

admmcounterexampledivergencep2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1strongly-convex

Theorem 4.1. For the model (1.1) with strongly convex objective functions, the direct extension of ADMM (1.5) is not necessarily convergent for all β>0\beta>0β>0.

Precisely: the strongly convex instance (4.1),

min⁡ 0.05x12+0.05x22+0.05x32s.t.(111112122)(x1x2x3)=0,\min\ 0.05x_1^2+0.05x_2^2+0.05x_3^2\quad\text{s.t.}\quad \begin{pmatrix}1&1&1\\1&1&2\\1&2&2\end{pmatrix}\begin{pmatrix}x_1\\x_2\\x_3\end{pmatrix}=0,min 0.05x12​+0.05x22​+0.05x32​s.t.​111​112​122​​​x1​x2​x3​​​=0,

satisfies

  1. the standing assumptions of (1.1) (closed convex sets Xi=R\mathcal X_i=\mathbb RXi​=R, convex θi\theta_iθi​, nonempty solution set);
  2. each θi(x)=0.05x2\theta_i(x)=0.05x^2θi​(x)=0.05x2 is strongly convex with modulus 1/101/101/10;
  3. there is a starting point (x20,x30,λ0)∈R×R×R3(x_2^0,x_3^0,\lambda^0)\in\mathbb R\times\mathbb R\times\mathbb R^3(x20​,x30​,λ0)∈R×R×R3 such that the direct extension of ADMM (1.5) with β=1\beta=1β=1 has a run from it, and no run of (1.5) with β=1\beta=1β=1 from it converges: the sequence (x1k,x2k,x3k,λk)(x_1^k,x_2^k,x_3^k,\lambda^k)(x1k​,x2k​,x3k​,λk) has no limit.

Hence strong convexity of the objective alone does not secure convergence of (1.5); the known convergence results for strongly convex θi\theta_iθi​ need a restriction on β\betaβ that cannot simply be dropped.

Formalization Note "Not necessarily convergent for all β>0\beta>0β>0" is read as "it is not the case that (1.5) converges for every β>0\beta>0β>0", witnessed by the explicit instance (4.1) at β=1\beta=1β=1, the only value the paper computes. The stronger reading "for every β>0\beta>0β>0 there is a divergent run" is false for (4.1): the spectral radius of the iteration matrix is below 111 for small β\betaβ (about 0.860.860.86 at β=0.1\beta=0.1β=0.1). Strong convexity uses Mathlib's StrongConvexOn s m f (f−m2∥⋅∥2f-\frac m2\|\cdot\|^2f−2m​∥⋅∥2 convex), so 0.05x20.05x^20.05x2 has m=1/10m=1/10m=1/10; on Fin 1 → ℝ the norm is ∣x∣|x|∣x∣. "Converges" means convergence in the product topology; the existence of a run is asserted so that the non-convergence clause is not vacuous. The first block x10x_1^0x10​ of a run is never read by (1.5).

Preamble
import Mathlib
import Definitions.Def_ExtADMM_StrongCvx_Setting
import Definitions.Def_ExtADMM_StrongCvx_Example41
Formal statement
namespace ExtADMM.StrongCvx

open Matrix Filter Topology

/-- Theorem 4.1, p. 14: for the model (1.1) with strongly convex objective, the direct
extension of ADMM (1.5) is not necessarily convergent for all `β > 0`. Witness: the instance
(4.1), whose `θᵢ(x) = 0.05x²` are `(1/10)`-strongly convex, with `β = 1`: there is a starting
point `(x₂⁰, x₃⁰, λ⁰)` from which a run exists and no run converges. -/
theorem theorem_4_1 :
    example41.Standing ∧
    (StrongConvexOn Set.univ (1/10) example41.θ1 ∧ StrongConvexOn Set.univ (1/10) example41.θ2 ∧
      StrongConvexOn Set.univ (1/10) example41.θ3) ∧
    ∃ (x20 x30 : Fin 1 → ℝ) (lam0 : Fin 3 → ℝ),
      (∃ (x1 x2 x3 : ℕ → Fin 1 → ℝ) (lam : ℕ → Fin 3 → ℝ),
        example41.IsRun15 1 x1 x2 x3 lam ∧ x2 0 = x20 ∧ x3 0 = x30 ∧ lam 0 = lam0) ∧
      ∀ (x1 x2 x3 : ℕ → Fin 1 → ℝ) (lam : ℕ → Fin 3 → ℝ),
        example41.IsRun15 1 x1 x2 x3 lam → x2 0 = x20 → x3 0 = x30 → lam 0 = lam0 →
          ¬ ∃ w, Tendsto (fun k => (x1 k, x2 k, x3 k, lam k)) atTop (𝓝 w) := by sorry

end ExtADMM.StrongCvx
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. 14, Theorem 4.1 and (4.1)
Human review
  • Endorsed by Shuze Chen · Oct 8, 2026

    Confirmed by the moderator at approval.

  • Endorsed by mikedeng1 · Oct 8, 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