In a Hilbert space, for convex optimization, we report on recent advances regarding the acceleration of first-order algorithms. We rely on inertial dynamics with damping driven by the Hessian, and the link between continuous dynamic systems and algorithms obtained by temporal discretization. We first review the classical results, from Polyak’s heavy ball with friction method to Nesterov’s accelerated gradient method. Then we introduce the damping driven by the Hessian which intervenes in the dynamic in the form D^2f(x(t))x'(t). By treating this term as the time derivative of Df(x(t)), this gives, in discretized form, first-order algorithms.As a fundamental property, this geometric damping makes it possible to attenuate the oscillations. In addition to the fast convergence of the values, the algorithms thus obtained show a rapid convergence towards zero of the gradients. The introduction of time scale factors further accelerates these algorithms. On the basis of a regularization technique using the Moreau envelope, we extend the method to non-smooth convex functions with extended real values. Numerical results for structured optimization problems support our theoretical findings. Finally, we evoke recent developement concerning the extension of these results to the case of monotone structured inclusions, inertial ADMM algorithms, dry friction, inexact/stochastic case, Tikhonov regularization, non-convex tame optimization, closed-loop adaptive damping, thus showing the versatility of the method.

Zoom meeting: Link