Lemma 3.1, p. 4 — the energy inequality (3.1) for z ∈ S, n ≥ 2
ProvedProjReflGrad.Weak.lemma_3_1monotone-operatorp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1projection-methodvariational-inequality
Let be a real Hilbert space, closed and convex, and monotone and Lipschitz continuous with constant . Let , let be generated by Algorithm 3.1 (, , ), and let be a solution of the variational inequality (1.1). Then for every
This is the central estimate of the convergence proof.
Formalization Note. The paper states (3.1) without a range of ; its proof uses , which needs because may lie outside , and the proof of Theorem 3.2 uses (3.1) only for . The step bound is not needed for this inequality and is not assumed; nonemptiness of is given by .
Preamble
import Mathlib import Definitions.Def_ProjReflGrad_Weak_Setting
Formal statement
namespace ProjReflGrad.Weak
/-- Lemma 3.1, inequality (3.1) (Malitsky 2015, p. 4), for `n ≥ 2`: along a run of Algorithm 3.1
and for `z ∈ S`,
`‖x_{n+1} - z‖² ≤ ‖x_n - z‖² - (1 - λL(1 + √2))‖x_n - x_{n-1}‖² + λL‖x_n - y_{n-1}‖²
- (1 - √2λL)‖x_{n+1} - y_n‖² - 2λ⟨F(z), y_n - z⟩`. -/
theorem lemma_3_1 {H : Type*} [NormedAddCommGroup H] [InnerProductSpace ℝ H] [CompleteSpace H]
(C : Set H) (hCcl : IsClosed C) (hCcv : Convex ℝ C) (F : H → H) (L lam : ℝ)
(hC2 : IsMonotoneMap F) (hL : 0 < L) (hC3 : IsLipschitzMap F L) (hlam0 : 0 < lam)
(x y : ℕ → H) (hrun : IsPRGRun C F lam x y) (z : H) (hz : z ∈ solSet C F) :
∀ n : ℕ, 2 ≤ n →
‖x (n + 1) - z‖ ^ 2 ≤ ‖x n - z‖ ^ 2
- (1 - lam * L * (1 + Real.sqrt 2)) * ‖x n - x (n - 1)‖ ^ 2
+ lam * L * ‖x n - y (n - 1)‖ ^ 2
- (1 - Real.sqrt 2 * lam * L) * ‖x (n + 1) - y n‖ ^ 2
- 2 * lam * inner ℝ (F z) (y n - z) := by sorry
end ProjReflGrad.Weak
Source
Malitsky, Projected Reflected Gradient Methods for Monotone Variational Inequalities, arXiv:1502.04968v1, p. 4, Lemma 3.1, (3.1)
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.