Footnote 5 — deterministic supermartingale convergence: , converges
ProvedIncProx.Cyclic.footnote5_deterministic_supermartingaleconvex-optimizationp2o-batch-pfp2bp2o-gran-per-chapterp2o-plan-paperp2o-v1real-analysissequences
Let , , , , be nonnegative real sequences such that
Then the sequence converges to a real limit.
This is the deterministic special case of the supermartingale convergence theorem that the proof of Proposition 6 applies to .
Formalization Note Since , is Mathlib's Summable W.
Preamble
import Mathlib
Formal statement
namespace IncProx.Cyclic
open Filter Topology
/-- Footnote 5 (p. 15), the deterministic special case of the supermartingale convergence theorem:
if `Y`, `Z`, `W` are nonnegative real sequences with `Y (k+1) ≤ Y k − Z k + W k` for all `k` and
`Σ W_k < ∞`, then `Y` converges. -/
theorem footnote5_deterministic_supermartingale (Y Z W : ℕ → ℝ) (hY : ∀ k, 0 ≤ Y k)
(hZ : ∀ k, 0 ≤ Z k) (hW : ∀ k, 0 ≤ W k) (hrec : ∀ k, Y (k + 1) ≤ Y k - Z k + W k)
(hsum : Summable W) : ∃ L : ℝ, Tendsto Y atTop (𝓝 L) := by sorry
end IncProx.Cyclic
Source
Bertsekas, Incremental Proximal Methods for Large Scale Convex Optimization, LIDS-P-2847 (rev. March 2011), footnote 5, p. 15 (used in the proof of Proposition 6)
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.