Proof of Theorem 3.2, pp. 5–6 — the iterates are bounded and ‖x_{n+1} − x_n‖ → 0, ‖x_{n+1} − y_n‖ → 0
ProvedProjReflGrad.Weak.bounded_and_steps_vanishasymptotic-regularityp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1projection-methodvariational-inequality
Under the assumptions of Theorem 3.2 (that is, closed and convex, (C1)–(C3), ), every sequence generated by Algorithm 3.1 satisfies:
- is bounded;
- ;
- .
These asymptotic regularity properties are what allows passing to the limit along weakly convergent subsequences.
Preamble
import Mathlib import Definitions.Def_ProjReflGrad_Weak_Setting
Formal statement
namespace ProjReflGrad.Weak
/-- Proof of Theorem 3.2 (Malitsky 2015, pp. 5–6): every run of Algorithm 3.1 is bounded, and
`‖x_{n+1} - x_n‖ → 0` and `‖x_{n+1} - y_n‖ → 0`. -/
theorem bounded_and_steps_vanish {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) :
Bornology.IsBounded (Set.range x) ∧
Filter.Tendsto (fun n => ‖x (n + 1) - x n‖) Filter.atTop (nhds 0) ∧
Filter.Tendsto (fun n => ‖x (n + 1) - y n‖) Filter.atTop (nhds 0) := by sorry
end ProjReflGrad.Weak
Source
Malitsky, Projected Reflected Gradient Methods for Monotone Variational Inequalities, arXiv:1502.04968v1, pp. 5–6, proof of Theorem 3.2
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.