Proof of Theorem 4.1, first display, p. 17 — the difference ℒ_{k+1} − ℒ_k under (73)
ProvedNAGFlow.Implicit.diff_identityconvex-optimizationimplicit-schemelyapunov-functionp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1
Let be a real Hilbert space, , , , and let be sequences in and real sequences, with as in (74). Fix and suppose and the parameter equation (73) holds at step : . Then
This is the discrete counterpart of differentiating the Lyapunov function of the NAG flow, and is the first step of the proof that the implicit scheme contracts .
Formalization Note. No assumption on is needed. The inner product is the real inner product of InnerProductSpace ℝ V, and is written .
Preamble
import Mathlib import Definitions.Def_NAGFlow_Implicit_Setting
Formal statement
namespace NAGFlow.Implicit
open scoped RealInnerProductSpace
/-- Proof of Theorem 4.1, first display, p. 17: if `α_k > 0` and `γ` satisfies (73) at step `k`,
then for any `f`, `x*` and sequences `x, v`,
`ℒ_{k+1} - ℒ_k = f(x_{k+1}) - f(x_k) + (γ_{k+1} - γ_k)/2 ‖v_{k+1} - x*‖²
+ γ_k/2 (‖v_{k+1} - x*‖² - ‖v_k - x*‖²)
= f(x_{k+1}) - f(x_k) + α_k/2 (μ - γ_{k+1}) ‖v_{k+1} - x*‖²
+ γ_k ⟪v_{k+1} - v_k, (v_{k+1} + v_k)/2 - x*⟫`. -/
theorem diff_identity {V : Type*} [NormedAddCommGroup V] [InnerProductSpace ℝ V]
[CompleteSpace V] (f : V → ℝ) (xstar : V) (μ : ℝ) (α γ : ℕ → ℝ) (x v : ℕ → V) (k : ℕ)
(hα : 0 < α k) (hγ : (γ (k + 1) - γ k) / α k = μ - γ (k + 1)) :
(lyap f xstar x v γ (k + 1) - lyap f xstar x v γ k
= f (x (k + 1)) - f (x k) + (γ (k + 1) - γ k) / 2 * ‖v (k + 1) - xstar‖ ^ 2
+ γ k / 2 * (‖v (k + 1) - xstar‖ ^ 2 - ‖v k - xstar‖ ^ 2)) ∧
(lyap f xstar x v γ (k + 1) - lyap f xstar x v γ k
= f (x (k + 1)) - f (x k) + α k / 2 * (μ - γ (k + 1)) * ‖v (k + 1) - xstar‖ ^ 2
+ γ k * ⟪v (k + 1) - v k, (1 / 2 : ℝ) • (v (k + 1) + v k) - xstar⟫) := by sorry
end NAGFlow.Implicit
Source
Luo & Chen, arXiv:1909.03145v4, proof of Theorem 4.1, first display (after (75)), p. 17
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.