(3.6), proof of Theorem 3.2, p. 5 — the Lyapunov-type inequality for z ∈ S, n ≥ 2
ProvedProjReflGrad.Weak.eq_3_6lyapunovp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1projection-methodvariational-inequality
In the setting of Lemma 3.1, assume in addition , so that . Then for every and every
With and this reads , the descent inequality the proof of Theorem 3.2 is built on.
Formalization Note. Stated for , as in the paper's proof ("For let "); see Lemma 3.1.
Preamble
import Mathlib import Definitions.Def_ProjReflGrad_Weak_Setting
Formal statement
namespace ProjReflGrad.Weak
/-- Inequality (3.6), proof of Theorem 3.2 (Malitsky 2015, p. 5), for `n ≥ 2` and `z ∈ S`:
`‖x_{n+1} - z‖² + λL‖x_{n+1} - y_n‖² + 2λ⟨F(z), x_n - z⟩
≤ ‖x_n - z‖² + λL‖x_n - y_{n-1}‖² + 2λ⟨F(z), x_{n-1} - z⟩ - (1 - λL(1 + √2))‖x_n - x_{n-1}‖²`. -/
theorem eq_3_6 {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) (hlam1 : lam < (Real.sqrt 2 - 1) / L)
(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 + lam * L * ‖x (n + 1) - y n‖ ^ 2 + 2 * lam * inner ℝ (F z) (x n - z)
≤ ‖x n - z‖ ^ 2 + lam * L * ‖x n - y (n - 1)‖ ^ 2
+ 2 * lam * inner ℝ (F z) (x (n - 1) - z)
- (1 - lam * L * (1 + Real.sqrt 2)) * ‖x n - x (n - 1)‖ ^ 2 := by sorry
end ProjReflGrad.Weak
Source
Malitsky, Projected Reflected Gradient Methods for Monotone Variational Inequalities, arXiv:1502.04968v1, p. 5, (3.6), proof of Theorem 3.2
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.