Proof of Theorem 3.2, p. 6 — ‖x_n − z‖² + 2λ⟨F(z), x_{n−1} − z⟩ converges for every z ∈ S
ProvedProjReflGrad.Weak.energy_convergeslyapunovp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1projection-methodvariational-inequality
Under the assumptions of Theorem 3.2, let be generated by Algorithm 3.1. Then for every the real sequence
converges.
This replaces the convergence of in the classical Opial argument: the extra term is what makes the Lyapunov quantity monotone.
Formalization Note. The sequence is indexed by , , so that no natural-number subtraction occurs; an index shift does not change convergence.
Preamble
import Mathlib import Definitions.Def_ProjReflGrad_Weak_Setting
Formal statement
namespace ProjReflGrad.Weak
/-- Proof of Theorem 3.2 (Malitsky 2015, p. 6): for every `z ∈ S` the sequence
`‖x_n - z‖² + 2λ⟨F(z), x_{n-1} - z⟩` converges (indexed here by `n + 1`). -/
theorem energy_converges {H : Type*} [NormedAddCommGroup H] [InnerProductSpace ℝ H]
[CompleteSpace H]
(C : Set H) (hCcl : IsClosed C) (hCcv : Convex ℝ C) (F : H → H) (L lam : ℝ)
(hC1 : (solSet C F).Nonempty) (hC2 : IsMonotoneMap F) (hL : 0 < L) (hC3 : IsLipschitzMap F L)
(hlam0 : 0 < lam) (hlam1 : lam < (Real.sqrt 2 - 1) / L)
(x y : ℕ → H) (hrun : IsPRGRun C F lam x y) :
∀ z ∈ solSet C F, ∃ l : ℝ,
Filter.Tendsto (fun n => ‖x (n + 1) - z‖ ^ 2 + 2 * lam * inner ℝ (F z) (x n - z))
Filter.atTop (nhds l) := by sorry
end ProjReflGrad.Weak
Source
Malitsky, Projected Reflected Gradient Methods for Monotone Variational Inequalities, arXiv:1502.04968v1, p. 6, proof of Theorem 3.2
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.