Proof of Theorem 4.4, p. 12 — along every run 0 < λ_n ≤ λ̄ and τ_n ∈ (0, 1]
ProvedProjReflGrad.Adaptive.lam_le_lamBaradaptive-step-sizep2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1variational-inequality
Let be a real Hilbert space, closed and convex, -Lipschitz with , , and . For every run of Algorithm 4.2 and every ,
The proof of Theorem 4.4 recalls that is an upper bound of ; positivity of and are what the step rule (4.1) and Lemma 4.2 presuppose at every step.
Formalization Note This item states only the upper bound and positivity. The paper also asserts that is a lower bound of "from Lemma 4.2"; that claim is not stated here (see the mission description).
Preamble
import Mathlib import Definitions.Def_ProjReflGrad_Adaptive_Setting
Formal statement
namespace ProjReflGrad.Adaptive
/-- Proof of Theorem 4.4 (Malitsky 2015, p. 12): along every run of Algorithm 4.2 the step sizes
satisfy `0 < λ_n ≤ λ̄` and the reflection weights satisfy `τ_n ∈ (0, 1]`. -/
theorem lam_le_lamBar {H : Type*} [NormedAddCommGroup H] [InnerProductSpace ℝ H] [CompleteSpace H]
(C : Set H) (hCcl : IsClosed C) (hCcv : Convex ℝ C) (F : H → H) (L : ℝ)
(hL : 0 < L) (hC3 : ProjReflGrad.Weak.IsLipschitzMap F L)
(α lamInit lamBar : ℝ) (hα0 : 0 < α) (hα1 : α < Real.sqrt 2 - 1) (hlamInit : 0 < lamInit)
(hlamBar : 0 < lamBar) (x y : ℕ → H) (lam tau : ℕ → ℝ)
(hrun : IsAdaptiveRun C F α lamInit lamBar x y lam tau) :
∀ n, 0 < lam n ∧ lam n ≤ lamBar ∧ 0 < tau n ∧ tau n ≤ 1 := by sorry
end ProjReflGrad.Adaptive
Source
Malitsky, Projected Reflected Gradient Methods for Monotone Variational Inequalities, arXiv:1502.04968v1, p. 12, proof of Theorem 4.4
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.