Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Theorem 8 — the proximal-type algorithm (3.1) converges strongly to Q_{T⁻¹0} x_0

Proved
ProximalBanach.Hybrid.hybrid_proximal_strong_convergence

by mikedeng1 · Sep 27, 2026 · Mathlib 0df444a (Lean v4.33.1)

maximal-monotone-operatorp2o-batch-p200ap2o-gran-per-chapterp2o-plan-paperp2o-v1proximal-point-algorithmstrong-convergence

Let EEE be a uniformly convex and uniformly smooth real Banach space with duality mapping JJJ, and let T:E→2E∗T:E\to2^{E^*}T:E→2E∗ be a maximal monotone operator with T−10≠∅T^{-1}0\neq\emptysetT−10=∅. Let (rn)⊂(0,∞)(r_n)\subset(0,\infty)(rn​)⊂(0,∞) satisfy lim inf⁡n→∞rn>0\liminf_{n\to\infty}r_n>0liminfn→∞​rn​>0. Let (xn)(x_n)(xn​) be generated by the algorithm

{x0∈E,0=vn+1rn(Jyn−Jxn),vn∈Tyn,Hn={z∈E:⟨z−yn,vn⟩≤0},Wn={z∈E:⟨z−xn,Jx0−Jxn⟩≤0},xn+1=QHn∩Wnx0,n=0,1,2,…(3.1)\begin{cases}x_0\in E,\\ 0=v_n+\frac1{r_n}(Jy_n-Jx_n),\quad v_n\in Ty_n,\\ H_n=\{z\in E:\langle z-y_n,v_n\rangle\le0\},\\ W_n=\{z\in E:\langle z-x_n,Jx_0-Jx_n\rangle\le0\},\\ x_{n+1}=Q_{H_n\cap W_n}x_0,\qquad n=0,1,2,\dots\end{cases}\tag{3.1}⎩⎨⎧​x0​∈E,0=vn​+rn​1​(Jyn​−Jxn​),vn​∈Tyn​,Hn​={z∈E:⟨z−yn​,vn​⟩≤0},Wn​={z∈E:⟨z−xn​,Jx0​−Jxn​⟩≤0},xn+1​=QHn​∩Wn​​x0​,n=0,1,2,…​(3.1)

Then (xn)(x_n)(xn​) converges strongly to QT−10x0Q_{T^{-1}0}x_0QT−10​x0​, the generalized projection of x0x_0x0​ onto the zero set of TTT:

lim⁡n→∞∥xn−QT−10x0∥=0.\lim_{n\to\infty}\|x_n-Q_{T^{-1}0}x_0\|=0 .n→∞lim​∥xn​−QT−10​x0​∥=0.

This extends Solodov and Svaiter's strongly convergent hybrid proximal point method from Hilbert spaces to spaces such as LpL^pLp, 1<p<∞1<p<\infty1<p<∞.

Formalization Note The conclusion is that there is a point zzz which is a generalized projection of x0x_0x0​ onto T−10T^{-1}0T−10 (z∈T−10z\in T^{-1}0z∈T−10 minimizes φ(⋅,x0)\varphi(\cdot,x_0)φ(⋅,x0​) there) and xn→zx_n\to zxn​→z in norm. lim inf⁡rn>0\liminf r_n>0liminfrn​>0 is encoded as "there is c>0c>0c>0 with rn≥cr_n\ge crn​≥c for all large nnn". The theorem holds for every run of (3.1) (runs exist by Proposition 7). Reflexivity, strict convexity and smoothness are not assumed: they follow from uniform convexity and uniform smoothness. T−10T^{-1}0T−10 is not assumed closed or convex.

Preamble
import Mathlib
import Definitions.Def_ProximalBanach_Hybrid_Basic
Formal statement
namespace ProximalBanach.Hybrid

open Filter Topology

variable {E : Type*} [NormedAddCommGroup E] [NormedSpace ℝ E] [CompleteSpace E]

/-- Theorem 8 (p. 942): let `E` be uniformly convex and uniformly smooth and `T` maximal
monotone with `T⁻¹0 ≠ ∅`. If `r_n > 0` and `liminf r_n > 0`, then every run `{x_n}` of (3.1)
converges strongly to `Q_{T⁻¹0} x_0`. -/
theorem hybrid_proximal_strong_convergence [UniformConvexSpace E]
    (hUS : IsUniformlySmooth E) (J : E → StrongDual ℝ E) (hJ : ∀ x, J x ∈ dualityMap x)
    (T : E → Set (StrongDual ℝ E)) (hT : IsMaximalMonotone T) (hZ : (zeros T).Nonempty)
    (r : ℕ → ℝ) (hr : ∀ n, 0 < r n) (hlim : ∃ c : ℝ, 0 < c ∧ ∀ᶠ n in atTop, c ≤ r n)
    (x y : ℕ → E) (v : ℕ → StrongDual ℝ E) (hrun : IsHybridRun T J r x y v) :
    ∃ z : E, IsGenProj J (zeros T) (x 0) z ∧ Tendsto x atTop (𝓝 z) := by sorry

end ProximalBanach.Hybrid
Source
Kamimura and Takahashi, Strong convergence of a proximal-type algorithm in a Banach space, SIAM J. Optim. 13(3), 2003, p. 942, Theorem 8 (with the standing assumption of §3 that T is maximal monotone)
Human review
  • Endorsed by Shuze Chen · Sep 27, 2026

    Confirmed by the moderator at approval.

  • Endorsed by mikedeng1 · Sep 27, 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