Fast convex optimization via a third-order in time evolution equation. (4th May 2022) - Attouch, Hedy; Chbani, Zaki; Riahi, Hassan
Abstract : In a Hilbert space H, we develop fast convex optimization methods which are based on an evolution system of the third-order in time. The function to minimize f : H → R is convex, continuously differentiable, with a r g m i n f ≠ ∅, and enters the dynamic via its gradient. On the basis of Lyapunov's analysis and temporal scaling techniques, we show a convergence rate of the values of the order 1 / t 3, and obtain the convergence of the trajectories towards optimal solutions. When f is strongly convex, an exponential rate of convergence is obtained. We complete the study of the continuous dynamic by introducing a damping term induced by the Hessian of f . This allows the oscillations to be controlled and attenuated. Then, we analyse the convergence of the proximal-based algorithms obtained by temporal discretization of this system, and obtain similar convergence rates. The algorithmic results are valid for a general convex, lower semicontinuous and proper function f : H → R ∪ { + ∞ } .