Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Theorem 8 — nonquadratic proximal methods of multipliers converge to a saddle point

Proved
BregmanPPA.ProxMult.theorem8

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

bregman-functionconvex-programmingp2o-batch-pfp2bp2o-gran-per-chapterp2o-plan-paperp2o-v1proximal-method-of-multiplierssaddle-point

Consider a problem of the form (10):

minimize f(x)such that gi(x)≤0 (i=1,…,m), x∈C,\text{minimize } f(x)\quad\text{such that } g_i(x)\le0\ (i=1,\dots,m),\ x\in C,minimize f(x)such that gi​(x)≤0 (i=1,…,m), x∈C,

with C⊆RnC\subseteq\mathbb R^nC⊆Rn closed, nonempty and convex and f,g1,…,gmf,g_1,\dots,g_mf,g1​,…,gm​ proper lower semicontinuous convex functions, finite on CCC, and let lll be its Lagrangian. Let {ck}\{c_k\}{ck​} be positive scalars bounded away from zero, hxh_xhx​ a Bregman function on Rn\mathbb R^nRn with zone Sx⊇CS_x\supseteq CSx​⊇C, and hph_php​ a Bregman function on Rm\mathbb R^mRm with zone Sp⊇Ω+‾S_p\supseteq\overline{\Omega^+}Sp​⊇Ω+ and im⁡(∇hp)=Rm\operatorname{im}(\nabla h_p)=\mathbb R^mim(∇hp​)=Rm. Suppose {(xk,pk)}k≥0⊆Rn×Rm\{(x^k,p^k)\}_{k\ge0}\subseteq\mathbb R^n\times\mathbb R^m{(xk,pk)}k≥0​⊆Rn×Rm conforms to the recursions

xk+1=arg⁡min⁡x∈C{f(x)+1ckhp∗+(∇hp(pk)+ckg(x))+1ckDhx(x,xk)},pk+1=∇hp∗+(∇hp(pk)+ckg(xk+1)).(12)\begin{aligned}x^{k+1}&=\arg\min_{x\in C}\Big\{f(x)+\frac1{c_k}h_p^{*+}\big(\nabla h_p(p^k)+c_kg(x)\big)+\frac1{c_k}D_{h_x}(x,x^k)\Big\},\\ p^{k+1}&=\nabla h_p^{*+}\big(\nabla h_p(p^k)+c_kg(x^{k+1})\big).\end{aligned}\tag{12}xk+1pk+1​=argx∈Cmin​{f(x)+ck​1​hp∗+​(∇hp​(pk)+ck​g(x))+ck​1​Dhx​​(x,xk)},=∇hp∗+​(∇hp​(pk)+ck​g(xk+1)).​(12)

Then:

  1. if (10) has an optimal solution–Lagrange multiplier pair, i.e. a saddle pair (x∗,p∗)(x^*,p^*)(x∗,p∗) with l(x∗,p)≤l(x∗,p∗)≤l(x,p∗)l(x^*,p)\le l(x^*,p^*)\le l(x,p^*)l(x∗,p)≤l(x∗,p∗)≤l(x,p∗) for all x,px,px,p, then (xk,pk)(x^k,p^k)(xk,pk) converges to one such pair;
  2. if (10) has no such pair, at least one of the sequences {xk}\{x^k\}{xk}, {pk}\{p^k\}{pk} is unbounded.

With hx=12∥⋅∥2h_x=\frac12\|\cdot\|^2hx​=21​∥⋅∥2 and hp=12∥⋅∥2h_p=\frac12\|\cdot\|^2hp​=21​∥⋅∥2 this is Rockafellar's proximal method of multipliers; other choices of hx,hph_x,h_phx​,hp​ give nonquadratic versions with the same guarantee.

Formalization Note "Optimal solution–Lagrange multiplier pair" is the saddle inequality, which the paper identifies with these pairs on p. 220 and which is exactly the zero set of KKK used in the proof. "Converges to one" means both sequences converge, to the two components of a single saddle pair. The page's "Sp⊃Ω+‾S_p\supset\overline{\Omega^+}Sp​⊃Ω+" is read as ⊇\supseteq⊇ (the paper's typography; SpS_pSp​ is open). The xxx-step uses a minimality predicate instead of arg⁡min⁡\arg\minargmin (equivalent, the minimizer being unique, p. 222); the run requires x0∈Sxx^0\in S_xx0∈Sx​ and pk∈Spp^k\in S_ppk∈Sp​; hp∗+h_p^{*+}hp∗+​ enters through toReal, exact by Lemma 3. The existence of runs is the separate item theorem8_existence. The §4.2 assumption that the dual functional is not everywhere −∞-\infty−∞ concerns the dual problem of §4.2 and is not used in §5; it is not assumed, which can only strengthen the statement.

Preamble
import Mathlib
import Definitions.Def_BregmanPPA_Convergence_Model
import Definitions.Def_BregmanPPA_IneqMult_Program
import Definitions.Def_BregmanPPA_ProxMult_Saddle

open Filter Topology
Formal statement
namespace BregmanPPA.ProxMult

/-- Theorem 8, pp. 220–221 (first two sentences): along a run of the nonquadratic proximal
method of multipliers (12), if (10) has a saddle pair (an optimal solution–Lagrange multiplier
pair), then `(x^k, p^k)` converges to one; if it has none, `{x^k}` or `{p^k}` is unbounded. -/
theorem theorem8 {n m : ℕ} (C : Set (BregmanPPA.IneqMult.E n)) (f : BregmanPPA.IneqMult.E n → EReal) (g : Fin m → BregmanPPA.IneqMult.E n → EReal)
    (Sx : Set (BregmanPPA.IneqMult.E n)) (hx : BregmanPPA.IneqMult.E n → ℝ) (Sp : Set (BregmanPPA.IneqMult.E m)) (hp : BregmanPPA.IneqMult.E m → ℝ)
    (c : ℕ → ℝ) (x : ℕ → BregmanPPA.IneqMult.E n) (p : ℕ → BregmanPPA.IneqMult.E m)
    (hP : BregmanPPA.IneqMult.IsConvexProgram C f g)
    (hc : ∀ k, 0 < c k) (hcinf : ∃ ε : ℝ, 0 < ε ∧ ∀ k, ε ≤ c k)
    (hhx : BregmanPPA.Convergence.IsBregmanFunction Sx hx) (hSx : C ⊆ Sx)
    (hhp : BregmanPPA.Convergence.IsBregmanFunction Sp hp) (hSp : BregmanPPA.IneqMult.nonnegOrthant m ⊆ Sp)
    (him : gradient hp '' Sp = Set.univ)
    (hrun : IsProxMultRun C f g Sx hx Sp hp c x p) :
    ((∃ x' p', IsSaddlePair C f g x' p') →
      ∃ x' p', IsSaddlePair C f g x' p' ∧
        Tendsto x atTop (𝓝 x') ∧ Tendsto p atTop (𝓝 p')) ∧
    ((¬ ∃ x' p', IsSaddlePair C f g x' p') →
      ¬ Bornology.IsBounded (Set.range x) ∨ ¬ Bornology.IsBounded (Set.range p)) := by sorry

end BregmanPPA.ProxMult
Source
Eckstein, Nonlinear proximal point algorithms using Bregman functions, with applications to convex programming, Math. Oper. Res. 18(1) (1993), pp. 220–221, Theorem 8 (first two sentences)
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