Theorem 1, Step 1 — decreasing Bregman distances and bounded iterates
ProvedBregmanPPA.Convergence.step1bregman-functionp2o-batch-pfp2bp2o-gran-per-chapterp2o-plan-paperp2o-v1proximal-point
Consider a Bregman proximal-point run for a maximal monotone operator with , positive step sizes bounded below by a positive constant, and a Bregman function with zone . For every zero of and every ,
Moreover, tends to a nonnegative real limit and the sequence is bounded.
This gives the distance and compactness estimates used in the convergence argument.
Formalization Note The paper's Step 1 writes ; under (C2), the stated standing assumption yields only . The inequality and boundedness use this latter inclusion, since Definition 1 defines on .
Preamble
import Mathlib import Definitions.Def_BregmanPPA_Convergence_Model open ThreeOpSplitting.Convergence Filter Topology
Formal statement
namespace BregmanPPA.Convergence
variable {H : Type*} [NormedAddCommGroup H] [InnerProductSpace ℝ H] [FiniteDimensional ℝ H]
/-- Theorem 1, proof, Step 1: decreasing Bregman distance and bounded iterates. -/
theorem step1 (T : H → Set H) (S : Set H) (h : H → ℝ) (c : ℕ → ℝ) (x : ℕ → H)
(hT : IsMaximalMonotone T) (hh : IsBregmanFunction S h)
(hdom : dom T ⊆ closure S) (hc : ∀ k, 0 < c k)
(hcinf : ∃ ε : ℝ, 0 < ε ∧ ∀ k, ε ≤ c k)
(hx : IsBregmanPPARun S h T c x) (z : H) (hz : z ∈ zer T) :
(∀ k, bregmanD h z (x (k + 1)) ≤
bregmanD h z (x k) - bregmanD h (x (k + 1)) (x k)) ∧
(∃ δ : ℝ, 0 ≤ δ ∧ Tendsto (fun k => bregmanD h z (x k)) atTop (𝓝 δ)) ∧
Bornology.IsBounded (Set.range x) := by sorry
end BregmanPPA.Convergence
Source
Eckstein, Nonlinear proximal point algorithms using Bregman functions, with applications to convex programming, Math. Oper. Res. 18(1) (1993), p. 207, Theorem 1 proof, Step 1, https://doi.org/10.1287/moor.18.1.202
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.