Lemma 4.2, p. 9 — step (4.ii) of the adaptive projected reflected gradient method is well-defined
ProvedProjReflGrad.Adaptive.lemma_4_2adaptive-step-sizep2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1variational-inequality
Let be -Lipschitz with , let , and let the previous data of Algorithm 4.2 be points , a weight and a step with . For write and let be the step rule (4.1). Then there is with
and there is with
This is Lemma 4.2: the choices required in step (4.ii) of Algorithm 4.2 are always possible. Along every run the hypotheses and hold, so the lemma applies at every step.
Formalization Note The statement does not assume or . The paper's proof takes , which lies in only when ; the statement as printed holds without that bound. It also does not assume the branch condition , which the conclusion does not need.
Preamble
import Mathlib import Definitions.Def_ProjReflGrad_Adaptive_Setting
Formal statement
namespace ProjReflGrad.Adaptive
/-- Lemma 4.2 (Malitsky 2015, p. 9): step (4.ii) of Algorithm 4.2 is well-defined. For an
`L`-Lipschitz `F`, `α > 0` and previous data `0 < λ_{n-1} ≤ λ̄`, `τ_{n-1} ≥ 0`, some
`τ'_n ∈ (0, 1]` satisfies (4.3) for `y'_n = x_n + τ'_n (x_n - x_{n-1})`, and then some
`λ'_n ∈ [τ'_n λ_{n-1}, λ(y'_n, τ'_n)]` satisfies (4.4). -/
theorem lemma_4_2 {H : Type*} [NormedAddCommGroup H] [InnerProductSpace ℝ H] (F : H → H) (L : ℝ) (hL : 0 < L)
(hC3 : ProjReflGrad.Weak.IsLipschitzMap F L) (α lamBar : ℝ) (hα : 0 < α) (xn xp yp : H) (taup lamp : ℝ)
(htaup : 0 ≤ taup) (hlamp : 0 < lamp) (hlampBar : lamp ≤ lamBar) :
∃ τ ∈ Set.Ioc (0 : ℝ) 1,
τ * lamp ≤ stepCap F α lamBar yp taup lamp (xn + τ • (xn - xp)) τ ∧
∃ l ∈ Set.Icc (τ * lamp) (stepCap F α lamBar yp taup lamp (xn + τ • (xn - xp)) τ),
‖l • F (xn + τ • (xn - xp)) - (τ * lamp) • F yp‖
≤ α * ‖(xn + τ • (xn - xp)) - yp‖ := by sorry
end ProjReflGrad.Adaptive
Source
Malitsky, Projected Reflected Gradient Methods for Monotone Variational Inequalities, arXiv:1502.04968v1, p. 9, Lemma 4.2
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.