(117), proof of Theorem 7.2, p. 31 — ℒ̂_k − ℒ_k ≤ −α_kℒ̂_k + (1 + α_k)(f(y_k) − f(x_{k+1})) + (α_k²/(2γ_k) − (1 + α_k)/(2L))‖G_f(y_k)‖²
ProvedNAGFlow.APGM.eq_117Let be a real Hilbert space, with () and proper, closed and convex, and let minimise . Let be a run of the semi-implicit scheme (115) with and arbitrary step sizes , started at . With
and , for every
With the step size the last two terms cancel, and the identity turns (117) into the contraction (116).
Formalization Note. No step-size rule is assumed: (117) holds for every . The point may lie outside ; there the page's is . In the encoding is a real number, and it enters both sides with total coefficient , so the inequality does not depend on the value takes at ; no hypothesis is added. The hypothesis is added: without it the page's is and the case is void ( for follows from the prox step). minimises over (argmin nonempty, p. 2).
import Mathlib import Definitions.Def_NAGFlow_APGM_Setting
namespace NAGFlow.APGM
/-- Inequality (117) (Luo & Chen, arXiv:1909.03145v4, proof of Theorem 7.2, p. 31). Let
`h ∈ S^{1,1}_{μ,L}` with `0 ≤ μ ≤ L < ∞`, `g : V → ℝ ∪ {+∞}` proper, closed and convex (encoded by
`(g, D)`), `f = h + g`, and `x* ∈ dom g` a minimiser of `f`. Let `(x, y, v)` be a run of the
semi-implicit scheme (115) with `γ₀ > 0` and any step sizes `α_k > 0`, started at `x₀ ∈ dom g`. With
`ℒ_k = f(x_k) − f(x*) + (γ_k/2)‖v_k − x*‖²`, `ℒ̂_k = f(y_k) − f(x*) + (γ_{k+1}/2)‖v_{k+1} − x*‖²` (84)
and `G_f(y_k) = L(y_k − x_{k+1})`, for every `k`
`ℒ̂_k − ℒ_k ≤ −α_kℒ̂_k + (1 + α_k)(f(y_k) − f(x_{k+1})) + (α_k²/(2γ_k))‖G_f(y_k)‖² − ((1 + α_k)/(2L))‖G_f(y_k)‖²`. -/
theorem eq_117 {V : Type*} [NormedAddCommGroup V] [InnerProductSpace ℝ V] [CompleteSpace V]
(h : V → ℝ) (gradh : V → V) (μ L : ℝ) (hh : NAGFlow.PredCorr.IsS11 h gradh μ L)
(g : V → ℝ) (D : Set V) (hg : IsProperClosedConvex g D)
(xstar : V) (hxstar : xstar ∈ D) (hmin : ∀ z ∈ D, (h + g) xstar ≤ (h + g) z)
(α γ : ℕ → ℝ) (x y v : ℕ → V) (hrun : IsSemiImplicitRun gradh g D μ L α γ x y v)
(hx0 : x 0 ∈ D) (k : ℕ) :
NAGFlow.PredCorr.lyapHat (h + g) xstar y v γ k - NAGFlow.PredCorr.lyap (h + g) xstar x v γ k ≤
-α k * NAGFlow.PredCorr.lyapHat (h + g) xstar y v γ k + (1 + α k) * ((h + g) (y k) - (h + g) (x (k + 1)))
+ α k ^ 2 / (2 * γ k) * ‖gradMap (1 / L) (y k) (x (k + 1))‖ ^ 2
- (1 + α k) / (2 * L) * ‖gradMap (1 / L) (y k) (x (k + 1))‖ ^ 2 := by sorry
end NAGFlow.APGM
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.