First-order optimization algorithms via inertial systems with Hessian driven damping

In a Hilbert space setting, for convex optimization, we analyze the convergence rate of a class of first-order algorithms involving inertial features. They can be interpreted as discrete time versions of inertial dynamics involving both viscous and Hessian-driven dampings. The geometrical damping dr...

Full description

Saved in:
Bibliographic Details
Published in:Mathematical programming 2022-05, Vol.193 (1), p.113-155
Main Authors: Attouch, Hedy, Chbani, Zaki, Fadili, Jalal, Riahi, Hassan
Format: Article
Language:English
Subjects:
Algorithms
Analysis
Calculus of Variations and Optimal Control
Optimization
Combinatorics
Computational geometry
Convergence
Convex analysis
Convexity
Damping
First order algorithms
Full Length Paper
Hilbert space
Inventory control
Machine Learning
Mathematical analysis
Mathematical and Computational Physics
Mathematical Methods in Physics
Mathematical optimization
Mathematics
Mathematics and Statistics
Mathematics of Computing
Numerical Analysis
Optimization
Optimization and Control
Regularization
Statistics
Theoretical
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:In a Hilbert space setting, for convex optimization, we analyze the convergence rate of a class of first-order algorithms involving inertial features. They can be interpreted as discrete time versions of inertial dynamics involving both viscous and Hessian-driven dampings. The geometrical damping driven by the Hessian intervenes in the dynamics in the form ∇ 2 f ( x ( t ) ) x ˙ ( t ) . By treating this term as the time derivative of ∇ f ( x ( t ) ) , this gives, in discretized form, first-order algorithms in time and space. In addition to the convergence properties attached to Nesterov-type accelerated gradient methods, the algorithms thus obtained are new and show a rapid convergence towards zero of the gradients. On the basis of a regularization technique using the Moreau envelope, we extend these methods to non-smooth convex functions with extended real values. The introduction of time scale factors makes it possible to further accelerate these algorithms. We also report numerical results on structured problems to support our theoretical findings.
ISSN:0025-5610
1436-4646
DOI:10.1007/s10107-020-01591-1