Theorem 3 — the generalized proximal point algorithm converges weakly to a zero, or is unbounded
ProvedDouglasRachfordPPA.GenDR.generalized_proximal_pointLet be a real Hilbert space and a maximal monotone operator on . Let , , be real sequences and , sequences in () such that
where , , , and . Then:
- if has a zero, converges weakly to a zero of ;
- if has no zero, is unbounded.
The theorem combines Rockafellar's inexact proximal point algorithm (variable stepsizes ) with the over/under-relaxation of Gol'shtein and Tret'yakov, in a general Hilbert space and including the case without zeros. Theorem 7 is obtained by applying it to the splitting operator.
Formalization Note The printed statement has two slips, corrected here: it reads where the text before it (p. 9) and the proof (pp. 11, 14) use , and it writes where the proof uses (, p. 11). The resolvent is a map with for all (unique by Corollary 2.2). The conditions , are encoded as with , and as with for all ; these are equivalent to the page and imply the page's . Weak convergence is for all ; unboundedness is "the range of is not bounded". Sequences are indexed from .
import Mathlib import Definitions.Def_ThreeOpSplitting_Convergence_MonotoneOperators import Definitions.Def_ThreeOpSplitting_Convergence_WeakConvergence open InnerProductSpace ThreeOpSplitting.Convergence
namespace DouglasRachfordPPA.GenDR
/-- Theorem 3 (generalized proximal point algorithm), with the printed slips corrected:
`z (k+1) = (1 - ρ k) z k + ρ k w k` and `‖w k - J_{c_k T}(z k)‖ ≤ ε k`. The resolvent
`J_{c_k T}` is the map `J k` with `IsResolvent (c k) T (J k)`. -/
theorem generalized_proximal_point
{H : Type*} [NormedAddCommGroup H] [InnerProductSpace ℝ H] [CompleteSpace H]
(T : H → Set H) (hT : IsMaximalMonotone T)
(c ρ ε : ℕ → ℝ) (J : ℕ → H → H) (hJ : ∀ k, IsResolvent (c k) T (J k))
(z w : ℕ → H)
(hz : ∀ k, z (k + 1) = (1 - ρ k) • z k + ρ k • w k)
(hw : ∀ k, ‖w k - J k (z k)‖ ≤ ε k)
(hε_nonneg : ∀ k, 0 ≤ ε k) (hε_sum : Summable ε)
(hρ : ∃ ρ₁ ρ₂ : ℝ, 0 < ρ₁ ∧ ρ₂ < 2 ∧ ∀ k, ρ₁ ≤ ρ k ∧ ρ k ≤ ρ₂)
(hc : ∃ c₀ : ℝ, 0 < c₀ ∧ ∀ k, c₀ ≤ c k) :
((zer T).Nonempty → ∃ zs ∈ zer T, WeakTendsto z zs) ∧
(zer T = ∅ → ¬ Bornology.IsBounded (Set.range z)) := by sorry
end DouglasRachfordPPA.GenDR
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.