Proof of Theorem 4.1, third display, p. 17 — by (72), γ_k(v_{k+1} − v_k, v_{k+1} − x*) = μα_k(…) − α_k⟨∇f(x_{k+1}), v_{k+1} − x*⟩
ProvedNAGFlow.Implicit.scheme_identityconvex-optimizationimplicit-schemelyapunov-functionp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1
Let be a real Hilbert space, any map, , , sequences in and real sequences. Fix with and , and suppose the second line of the implicit scheme (72) holds at step :
Then
The identity substitutes the scheme into the cross term of the Lyapunov difference.
Formalization Note. The hypothesis is not written in the display; the page's (72) divides by , and along a run of (72)–(73) it follows from , , (Remark 4.1 records ). Without it Lean's convention would change the meaning of (72). Inner product and duality pairing are both the real inner product (Riesz).
Preamble
import Mathlib import Definitions.Def_NAGFlow_Implicit_Setting
Formal statement
namespace NAGFlow.Implicit
open scoped RealInnerProductSpace
/-- Proof of Theorem 4.1, third display, p. 17: if `α_k > 0`, `γ_k > 0` and the second line of
(72) holds at step `k`, then
`γ_k ⟪v_{k+1} - v_k, v_{k+1} - x*⟫
= μ α_k ⟪x_{k+1} - v_{k+1}, v_{k+1} - x*⟫ - α_k ⟪∇f(x_{k+1}), v_{k+1} - x*⟫`. -/
theorem scheme_identity {V : Type*} [NormedAddCommGroup V] [InnerProductSpace ℝ V]
[CompleteSpace V] (gradf : V → V) (xstar : V) (μ : ℝ) (α γ : ℕ → ℝ) (x v : ℕ → V)
(k : ℕ) (hα : 0 < α k) (hγ : 0 < γ k)
(hv : (1 / α k) • (v (k + 1) - v k)
= (μ / γ k) • (x (k + 1) - v (k + 1)) - (1 / γ k) • gradf (x (k + 1))) :
γ k * ⟪v (k + 1) - v k, v (k + 1) - xstar⟫
= μ * α k * ⟪x (k + 1) - v (k + 1), v (k + 1) - xstar⟫
- α k * ⟪gradf (x (k + 1)), v (k + 1) - xstar⟫ := by sorry
end NAGFlow.Implicit
Source
Luo & Chen, arXiv:1909.03145v4, proof of Theorem 4.1, third display ('By (72), it follows that'), p. 17; scheme (72), p. 16
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.