Fast convex optimization via inertial dynamics with Hessian driven damping

We first study the fast minimization properties of the trajectories of the second-order evolution equation ddotx(t) + fracαt dotx(t) + β nabla2 Phi (x(t))dotx (t) + nabla Phi (x(t)) = 0, where Phi:mathcal H→mathbb R is a smooth convex function acting on a real Hilbert space mathcal H, and α, β are positive parameters. This inertial system combines an isotropic viscous damping which vanishes asymptotically, and a geometrical Hessian driven damping, which makes it naturally related to Newton's and Levenberg-Marquardt methods. For α≥ 3, β >0, along any trajectory, fast convergence of the values Phi(x(t))- minmathcal HPhi =mathcal Oleft(t-2right) is obtained, together with rapid convergence of the gradients nablaPhi(x(t)) to zero. For α>3, just assuming that Phi has minimizers, we show that any trajectory converges weakly to a minimizer of Phi, and Phi(x(t))-minmathcal HPhi = o(t-2). Strong convergence is established in various practical situations. For the strongly convex case, convergence can be arbitrarily fast depending on the choice of α. More precisely, we have Phi(x(t))- minmathcal HPhi = mathcal O(t^-frac23α). We extend the results to the case of a general proper lower-semicontinuous convex function Phi : mathcal H rightarrow mathbb R cup +∞ . This is based on the fact that the inertial dynamic with Hessian driven damping can be written as a first-order system in time and space. By explicit-implicit time discretization, this opens a gate to new - possibly more rapid - inertial algorithms, expanding the field of FISTA methods for convex structured optimization problems.