Proof of Theorem 4, p. 12 — under (8), v_{k+1} − v_k = h(β_{k+1} + k(β_{k+1} − β_k) − b_khk)∇f(x_{k+1})
ProvedHessianDamping.IPAHD.vK_succ_subhessian-dampinginertial-algorithmlyapunovp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1
Let be a real Hilbert space, , , , real sequences , and a sequence in . Put
If and the discretization (8) holds at ,
then
This identity drives the energy estimate of Theorem 4: the increment of is a multiple of the gradient at the new iterate.
Formalization Note. The statement is purely algebraic and assumes nothing on beyond the existence of the vectors (Mathlib's gradient f).
Preamble
import Mathlib import Definitions.Def_GoldenRatioVI_Shared_IsProxPoint import Definitions.Def_HessianDamping_IPAHD_Setting
Formal statement
namespace HessianDamping.IPAHD
/-- Proof of Theorem 4, p. 12: if (8) holds at step `k ≥ 1`, then
`v_{k+1} - v_k = h (β_{k+1} + k (β_{k+1} - β_k) - b_k h k) ∇f(x_{k+1})`. -/
theorem vK_succ_sub
{H : Type*} [NormedAddCommGroup H] [InnerProductSpace ℝ H] [CompleteSpace H]
(f : H → ℝ) (xstar : H) (α h : ℝ) (β b : ℕ → ℝ) (x : ℕ → H)
(k : ℕ) (hk : 1 ≤ k)
(h8 : (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) :
vK f α h β x xstar (k + 1) - vK f α h β x xstar k
= (h * (β (k + 1) + k * (β (k + 1) - β k) - b k * h * k)) • gradient f (x (k + 1)) := 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, proof of Theorem 4, p. 12
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.