Fast convex optimization via a third-order in time evolution equation: TOGES-V an improved version of TOGES

• Published in: Optimization 2024-03, Vol.73 (3), p.575-595
• Main Authors: Attouch, Hedy, Chbani, Zaki, Riahi, Hassan
• Format: Article
• Language: English
• Subjects: Accelerated gradient system; Convergence; Convex analysis; convex optimization; Convexity; Damping; Dynamical systems; Evolution; fast convergence; Hilbert space; Lyapunov analysis; Optimization; time rescaling
• ISSN: 0233-1934; 1029-4945
• DOI: 10.1080/02331934.2022.2119084

In a Hilbert space setting $ {\mathcal H} $ H , for convex optimization, we analyse the fast convergence properties as $ t \rightarrow +\infty $ t → + ∞ of the trajectories $ t \mapsto u(t) \in {\mathcal H} $ t ↦ u ( t ) ∈ H generated by a third-order in time evolution system. The function $ f: {\mathcal H} \to {\mathbb R} $ f : H → R to minimize is supposed to be convex, continuously differentiable, with $ {\rm argmin}_{{\mathcal H}} f \neq \emptyset $ argmin H f ≠ ∅ . It enters into the dynamic through its gradient. Based on this new dynamical system, we improve the results obtained by Attouch et al. [Fast convex optimization via a third-order in time evolution equation. Optimization. 2020;71(5):1275-1304]. As a main result, when the damping parameter α satisfies $ \alpha \gt 3 $ α > 3 , we show that $ f(u(t)) - \inf _{{\mathcal H}} f = o( 1/t^3) $ f ( u ( t ) ) − inf H f = o ( 1 / t 3 ) as $ t \rightarrow +\infty $ t → + ∞ , as well as the convergence of the trajectories. We complement these results by introducing into the dynamic an Hessian-driven damping term, which reduces the oscillations. In the case of a strongly convex function f, we show an autonomous evolution system of the third-order in time with an exponential rate of convergence. All these results have natural extensions to the case of a convex lower semicontinuous function $ f: {\mathcal H} \to \mathbb R\cup \{+\infty \} $ f : H → R ∪ { + ∞ } . Just replace f with its Moreau envelope.