Fast convex optimization via a third-order in time evolution equation. (4th May 2022)

• Record Type: Journal Article
• Authors: Attouch, Hedy; Chbani, Zaki; Riahi, Hassan
• Is Part Of: Optimization. Volume 71:Number 5(2022)
• Page Start: 1275
• Page End: 1304
• Publication Date: 2022-05-04
• Subjects: Accelerated gradient system -- convex optimization -- Lyapunov analysis -- proximal algorithms -- time rescaling; 49M37 -- 65K05 -- 90C25; Mathematical optimization -- Periodicals; 519.7
• DOI: 10.1080/02331934.2020.1764953
• Languages: English
• ISSNs: 0233-1934

Abstract

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 ∪ { + ∞ } .