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

• 成果类型: Article
• 署名作者: Attouch, Hedy; Chbani, Zaki; Fadili, Jalal; Riahi, Hassan
• 署名单位: Centre National de la Recherche Scientifique (CNRS); Universite de Montpellier; Cadi Ayyad University of Marrakech; Universite de Caen Normandie; Centre National de la Recherche Scientifique (CNRS)
• 刊物名称: MATHEMATICAL PROGRAMMING
• ISSN/ISSBN: 0025-5610
• DOI: 10.1007/s10107-020-01591-1
• 发表日期: 2022
• 页码: 113-155
• 关键词: forward-backward algorithm; Gradient dynamics; CONVERGENCE

摘要

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 del(2) f (x(t)).x(t). By treating this term as the time derivative of del 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.