Lemma 3.2, p. 13 — for f ∈ S^{1,1}_{μ,L} the NAG flow (57) has a unique C² solution, ℒ′ ≤ −ℒ − μ/2‖x′‖² (59), and (60)
ProvedNAGFlow.Flow.lemma_3_2Let be a real Hilbert space and with : is continuously differentiable, -convex,
and is -Lipschitz with . Let be a global minimizer of , , the solution of (54) , , and .
Then the NAG flow
admits a unique solution . Moreover, with and the Lyapunov function
is differentiable on and
which implies
The lemma is the continuous model behind the accelerated methods of the paper: the NAG flow decays the Lyapunov function at the rate for every , and the discrete schemes are designed so that one step contracts by a factor , the discrete analogue of .
Formalization Note. is a real Hilbert space; the duality pairing is the inner product (Riesz). Uniqueness is equality on , because a function is unconstrained at negative times. Derivatives are relative to , so one-sided at ; "" means that has a one-sided derivative at with . The integral in (60) is an interval integral of a continuous integrand (the solution is ), so no junk value for non-integrable functions enters. The hypothesis that is a minimizer is the paper's standing assumption that is nonempty.
import Mathlib import Definitions.Def_NAGFlow_Flow_Setting
namespace NAGFlow.Flow
open Set
/-- Lemma 3.2, p. 13. Let `f ∈ S^{1,1}_{μ,L}` with `μ ≥ 0`, `γ₀ > 0`, `γ(t) = μ + (γ₀ − μ)e^{−t}`
(the solution of (54)), `x₀, v₀ ∈ V`, and `x*` a global minimizer of `f`. Then the NAG flow (57)
`γx″ + (μ + γ)x′ + ∇f(x) = 0`, `x(0) = x₀`, `x′(0) = v₀ − x₀`, admits a solution
`x ∈ C²([0, ∞); V)`, unique on `[0, ∞)`; and, with `v = x + x′` and the Lyapunov function (58)
`ℒ(t) = f(x(t)) − f(x*) + γ(t)/2 ‖v(t) − x*‖²`, `ℒ` is differentiable on `[0, ∞)` (right derivative
at `0`) with
`ℒ′(t) ≤ −ℒ(t) − μ/2 ‖x′(t)‖²` (59), and
`ℒ(t) + μ/2 ∫₀ᵗ e^{s−t} ‖x′(s)‖² ds ≤ e^{−t} ℒ(0)` for all `t ≥ 0` (60). -/
theorem lemma_3_2 {V : Type*} [NormedAddCommGroup V] [InnerProductSpace ℝ V] [CompleteSpace V]
(f : V → ℝ) (gradf : V → V) (μ L γ₀ : ℝ) (hf : NAGFlow.PredCorr.IsS11 f gradf μ L) (hγ₀ : 0 < γ₀)
(x₀ v₀ xstar : V) (hxstar : ∀ y, f xstar ≤ f y) :
∃ x : ℝ → V, IsNAGSolution2 f gradf μ γ₀ x₀ v₀ x ∧
(∀ y : ℝ → V, IsNAGSolution2 f gradf μ γ₀ x₀ v₀ y → EqOn y x (Ici 0)) ∧
(∀ t : ℝ, 0 ≤ t → ∃ dL : ℝ,
HasDerivWithinAt (lyapFlow f xstar (gammaFn μ γ₀) x (fun s => x s + dI x s)) dL
(Ici 0) t ∧
dL ≤ -lyapFlow f xstar (gammaFn μ γ₀) x (fun s => x s + dI x s) t
- μ / 2 * ‖dI x t‖ ^ 2) ∧
(∀ t : ℝ, 0 ≤ t →
lyapFlow f xstar (gammaFn μ γ₀) x (fun s => x s + dI x s) t
+ μ / 2 * ∫ s in (0 : ℝ)..t, Real.exp (s - t) * ‖dI x s‖ ^ 2
≤ Real.exp (-t) * lyapFlow f xstar (gammaFn μ γ₀) x (fun s => x s + dI x s) 0) := by sorry
end NAGFlow.Flow
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.