Proof of Theorem 4.1, fifth display, p. 17 — the gradient term split by the first line of (72)
ProvedNAGFlow.Implicit.gradient_splitconvex-optimizationimplicit-schemelyapunov-functionp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1
Let be a real Hilbert space, any map, , sequences in and a real sequence. Fix with and suppose the first line of the implicit scheme (72) holds at step :
Then, writing ,
The two terms on the right are the ones the -convexity inequality (2) bounds, at the pairs and .
Formalization Note. The duality pairing is the real inner product (Riesz). No property of is needed.
Preamble
import Mathlib import Definitions.Def_NAGFlow_Implicit_Setting
Formal statement
namespace NAGFlow.Implicit
open scoped RealInnerProductSpace
/-- Proof of Theorem 4.1, fifth display, p. 17: if `α_k > 0` and the first line of (72) holds at
step `k`, then
`-α_k ⟪∇f(x_{k+1}), v_{k+1} - x*⟫
= -⟪∇f(x_{k+1}), x_{k+1} - x_k⟫ - α_k ⟪∇f(x_{k+1}), x_{k+1} - x*⟫`. -/
theorem gradient_split {V : Type*} [NormedAddCommGroup V] [InnerProductSpace ℝ V]
[CompleteSpace V] (gradf : V → V) (xstar : V) (α : ℕ → ℝ) (x v : ℕ → V) (k : ℕ)
(hα : 0 < α k) (hx : (1 / α k) • (x (k + 1) - x k) = v (k + 1) - x (k + 1)) :
-α k * ⟪gradf (x (k + 1)), v (k + 1) - xstar⟫
= -⟪gradf (x (k + 1)), x (k + 1) - x k⟫
- α k * ⟪gradf (x (k + 1)), x (k + 1) - xstar⟫ := by sorry
end NAGFlow.Implicit
Source
Luo & Chen, arXiv:1909.03145v4, proof of Theorem 4.1, fifth display ('For the gradient term …'), p. 17
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.