(8), p. 10, and (IPAHD), p. 11 — every run of (IPAHD) satisfies the implicit discretization (8)
ProvedHessianDamping.IPAHD.run_satisfies_eq8hessian-dampinginertial-algorithmp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1proximal-algorithm
Let be a real Hilbert space and a convex function of class . Let , , , and let , be non-negative sequences. If is generated by (IPAHD), i.e. for every with and , then for every
The paper obtains (IPAHD) from the implicit discretization (8) of the continuous dynamic; this statement is the converse direction, the one the proof of Theorem 4 uses.
Formalization Note. The hypotheses and are implicit on the page (the step size is positive, for the proximal step); see the Setting definition for the encoding of the proximal step.
Preamble
import Mathlib import Definitions.Def_GoldenRatioVI_Shared_IsProxPoint import Definitions.Def_HessianDamping_IPAHD_Setting
Formal statement
namespace HessianDamping.IPAHD
/-- (8), p. 10, and (IPAHD), p. 11: every run of (IPAHD) satisfies the implicit discretization (8). -/
theorem run_satisfies_eq8
{H : Type*} [NormedAddCommGroup H] [InnerProductSpace ℝ H] [CompleteSpace H]
(f : H → ℝ) (hfconv : ConvexOn ℝ Set.univ f) (hfC1 : ContDiff ℝ 1 f)
(α : ℝ) (hα : 1 ≤ α)
(h s : ℝ) (hh : 0 < h) (hs : s = h ^ 2)
(β b : ℕ → ℝ) (hβ : ∀ k, 0 ≤ β k) (hb : ∀ k, 0 ≤ b k)
(x : ℕ → H) (hx : IsIPAHDRun f α s β b x)
(k : ℕ) (hk : 1 ≤ k) :
(k : ℝ) • (x (k + 1) - (2 : ℝ) • x k + x (k - 1)) + α • (x (k + 1) - x k)
+ (β k * h * k) • (gradient f (x (k + 1)) - gradient f (x k))
+ (b k * h ^ 2 * k) • gradient f (x (k + 1)) = 0 := by sorry
end HessianDamping.IPAHD
Source
Attouch, Chbani, Fadili, Riahi, First-order optimization algorithms via inertial systems with Hessian driven damping, arXiv:1907.10536v2, §3.1.1, (8), p. 10, and (IPAHD), p. 11
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.