Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Theorem 3.1 — for 0 < ρ < 2r, the modified dual algorithm converges strongly to (v*, Av*) and λⁿ stays bounded

Proved
GabayMercier.DualAlgorithm.theorem_3_1

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

admmaugmented-lagrangianconvergencehilbert-spacep2o-batch-pfp2bp2o-gran-per-chapterp2o-plan-paperp2o-v1

Let V,YV,YV,Y be real Hilbert spaces, A:V→YA:V\to YA:V→Y continuous linear, b∈V′b\in V'b∈V′, and f=f1+f2f=f_1+f_2f=f1​+f2​ where

  1. f1:Y→Rf_1:Y\to\mathbb Rf1​:Y→R is convex and continuously differentiable with strongly monotone gradient: (f1′(y)−f1′(z),y−z)≥γ∣y−z∣2(f_1'(y)-f_1'(z),y-z)\ge\gamma|y-z|^2(f1′​(y)−f1′​(z),y−z)≥γ∣y−z∣2 for some γ>0\gamma>0γ>0 (2.3);
  2. f2:Y→(−∞,+∞]f_2:Y\to(-\infty,+\infty]f2​:Y→(−∞,+∞] is proper, convex and lower semicontinuous;
  3. ∣Av∣2≥α2∥v∥2|Av|^2\ge\alpha^2\|v\|^2∣Av∣2≥α2∥v∥2 for some α>0\alpha>0α>0 (2.5);
  4. some Av0Av_0Av0​ lies in the interior of dom⁡f2\operatorname{dom}f_2domf2​ (qualification).

Let v∗v^*v∗ be the solution of (P)(\mathcal P)(P): inf⁡v∈V{f(Av)−⟨b,v⟩}\inf_{v\in V}\{f(Av)-\langle b,v\rangle\}infv∈V​{f(Av)−⟨b,v⟩}. Let r>0r>0r>0 and let the stepsize satisfy

0<ρ<2r.0<\rho<2r .0<ρ<2r.

Then every sequence (vn,yn,λn)n≥0(v^n,y^n,\lambda^n)_{n\ge0}(vn,yn,λn)n≥0​ produced by the modified dual algorithm (3.4), from any start (y0,λ0)∈Y×Y(y^0,\lambda^0)\in Y\times Y(y0,λ0)∈Y×Y (Step 1: r(Avn+1,Av)=(ryn−λn,Av)+⟨b,v⟩r(Av^{n+1},Av)=(ry^n-\lambda^n,Av)+\langle b,v\rangler(Avn+1,Av)=(ryn−λn,Av)+⟨b,v⟩ for all vvv; Step 2: λn+rAvn+1−ryn+1−f1′(yn+1)∈∂f2(yn+1)\lambda^n+rAv^{n+1}-ry^{n+1}-f_1'(y^{n+1})\in\partial f_2(y^{n+1})λn+rAvn+1−ryn+1−f1′​(yn+1)∈∂f2​(yn+1); Step 3: λn+1=λn+ρ(Avn+1−yn+1)\lambda^{n+1}=\lambda^n+\rho(Av^{n+1}-y^{n+1})λn+1=λn+ρ(Avn+1−yn+1)), satisfies

∥vn−v∗∥→0,∣yn−Av∗∣→0,\|v^n-v^*\|\to0,\qquad |y^n-Av^*|\to0,∥vn−v∗∥→0,∣yn−Av∗∣→0,

and the multipliers (λn)(\lambda^n)(λn) stay bounded in YYY.

This is the convergence theorem for the alternating direction method of multipliers in Hilbert space, for any stepsize below twice the penalty parameter. The solution v∗v^*v∗ exists and is unique (Proposition 2.1), so the hypothesis on v∗v^*v∗ can be met; the multipliers need not converge because the multiplier λ∗\lambda^*λ∗ need not be unique.

Formalization Note. Strong convergence in V×YV\times YV×Y is stated as the two norm limits. v∗v^*v∗ enters through the hypothesis IsSolution (finite value and minimal). The statement quantifies over every run of the algorithm; the algorithm's well-posedness (Remark 1, p. 15) is not used. Two departures from the printed text, both explained in the definition file: Step 1 carries +⟨b,v⟩+\langle b,v\rangle+⟨b,v⟩ (the paper prints −⟨b,v⟩-\langle b,v\rangle−⟨b,v⟩, which makes the algorithm solve (𝒫) with −b-b−b; for V=Y=RV=Y=\mathbb RV=Y=R, A=idA=\mathrm{id}A=id, f1(y)=y2/2f_1(y)=y^2/2f1​(y)=y2/2, f2=0f_2=0f2​=0, ⟨b,v⟩=v\langle b,v\rangle=v⟨b,v⟩=v the printed iteration converges to −1-1−1 while v∗=1v^*=1v∗=1); and the paper's qualification (2.4), int⁡dom⁡f2≠∅\operatorname{int}\operatorname{dom}f_2\ne\emptysetintdomf2​=∅, is strengthened to int⁡dom⁡f2∩R(A)≠∅\operatorname{int}\operatorname{dom}f_2\cap R(A)\ne\emptysetintdomf2​∩R(A)=∅. Under (2.4) alone the multipliers can be unbounded: in the example of Theorem 2.1 (converse) (V=RV=\mathbb RV=R, Y=R2Y=\mathbb R^2Y=R2, Av=(v,0)Av=(v,0)Av=(v,0), f2f_2f2​ the indicator of the disc of centre (0,1)(0,1)(0,1) and radius 111, ⟨b,v⟩=v\langle b,v\rangle=v⟨b,v⟩=v), no saddle point exists, and the conclusion of Theorem 3.1 fails for r=ρ=1r=\rho=1r=ρ=1: if vn→0v^n\to0vn→0 and yn→0y^n\to0yn→0, a bounded (λn)(\lambda^n)(λn) would have a weak cluster point λˉ\bar\lambdaλˉ with λˉ1=1\bar\lambda_1=1λˉ1​=1 by Step 1 and λˉ∈∂f2(0)\bar\lambda\in\partial f_2(0)λˉ∈∂f2​(0) by Step 2, which forces λˉ1=0\bar\lambda_1=0λˉ1​=0 (numerically, λ2n≈−113\lambda^n_2\approx-113λ2n​≈−113 after 10610^6106 iterations and still decreasing).

Preamble
import Mathlib
import Definitions.Def_InertialFB_IFB_ConvexAnalysis
import Definitions.Def_GabayMercier_DualAlgorithm_Model

open Filter Topology InertialFB.IFB
Formal statement
namespace GabayMercier.DualAlgorithm

variable {V Y : Type*} [NormedAddCommGroup V] [InnerProductSpace ℝ V] [CompleteSpace V]
  [NormedAddCommGroup Y] [InnerProductSpace ℝ Y] [CompleteSpace Y]

/-- Theorem 3.1, p. 19: for every stepsize `0 < ρ < 2r`, every run of the modified dual algorithm
(3.4) converges strongly in `V × Y` to `(v*, Av*)`, where `v*` is the solution of (𝒫), and the
multipliers `λⁿ` stay bounded. The qualification hypothesis strengthens the paper's (2.4). -/
theorem theorem_3_1 (A : V →L[ℝ] Y) (f₁ : Y → ℝ) (f₁' : Y → Y) (f₂ : Y → EReal)
    (b : StrongDual ℝ V) (γ α : ℝ) (h : StandingHyp A f₁ f₁' f₂ γ α)
    (hq : Qualification A f₂) (r ρ : ℝ) (hr : 0 < r) (hρ : 0 < ρ) (hρr : ρ < 2 * r)
    (v : ℕ → V) (y lam : ℕ → Y) (hrun : IsModifiedDualRun A f₁' f₂ b r ρ v y lam)
    (vs : V) (hvs : IsSolution A f₁ f₂ b vs) :
    Tendsto v atTop (𝓝 vs) ∧ Tendsto y atTop (𝓝 (A vs)) ∧
      Bornology.IsBounded (Set.range lam) := by sorry

end GabayMercier.DualAlgorithm
Source
Gabay & Mercier, IRIA RR-126 (1975), hal-04716124v1, p. 19, Theorem 3.1
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