(20), proof of Theorem 9, p. 24 — equivalent second-order form of (IPAHD-SC)
ProvedHessianDamping.IPAHDSC.run_satisfies_eq20convex-optimizationhessian-dampinginertial-algorithmp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1proximal-algorithmstrong-convexity
Let be convex and of class on a real Hilbert space , let , , , and let be a run of the inertial proximal algorithm (IPAHD-SC). Then for every ,
This is the "equivalent formulation" (20) that the proof of Theorem 9 works with: it exhibits the algorithm as an implicit discretization of the inertial dynamic .
Formalization Note The run is given through the minimizing property of the proximal step, so the identity is the first-order optimality condition of that step. Positivity of is implicit on the page (, the positive step size).
Preamble
import Mathlib import Definitions.Def_HessianDamping_IPAHDSC_Setting
Formal statement
namespace HessianDamping.IPAHDSC
/-- (20), proof of Theorem 9, p. 24: every run of (IPAHD-SC) satisfies, for `k ≥ 1`,
`(1/√s)(x_{k+1} - 2x_k + x_{k-1}) + 2√μ(x_{k+1} - x_k) + β(∇f(x_{k+1}) - ∇f(x_k)) + √s∇f(x_{k+1}) = 0`. -/
theorem run_satisfies_eq20 {H : Type*} [NormedAddCommGroup H] [InnerProductSpace ℝ H] [CompleteSpace H]
(f : H → ℝ) (hfconv : ConvexOn ℝ Set.univ f) (hfC1 : ContDiff ℝ 1 f)
(μ : ℝ) (hμ : 0 < μ) (β s : ℝ) (hs : 0 < s) (hβ0 : 0 ≤ β)
(x : ℕ → H) (hrun : IsIPAHDSCRun f μ β s x) (k : ℕ) (hk : 1 ≤ k) :
(1 / Real.sqrt s) • (x (k + 1) - (2 : ℝ) • x k + x (k - 1)) +
(2 * Real.sqrt μ) • (x (k + 1) - x k) +
β • (gradient f (x (k + 1)) - gradient f (x k)) +
Real.sqrt s • gradient f (x (k + 1)) = 0 := by sorry
end HessianDamping.IPAHDSC
Source
Attouch, Chbani, Fadili, Riahi, First-order optimization algorithms via inertial systems with Hessian driven damping, arXiv:1907.10536v2, p. 24, proof of Theorem 9, (20)
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.