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

Abstract

In a Hilbert space setting $\mathcal{H}$, for convex optimization, we analyse the fast convergence properties as $t\to +\mathrm{\infty }$ of the trajectories $t\mapsto u(t)\in \mathcal{H}$ generated by a third-order in time evolution system. The function $f:\mathcal{H}\to \mathbb{R}$ to minimize is supposed to be convex, continuously differentiable, with ${\mathrm{argmin}}_{\mathcal{H}}f\ne \mathrm{\varnothing }$. 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 >3$, we show that $f(u(t))-\underset{\mathcal{H}}{inf}f=o(1/t^3)$ as $t\to +\mathrm{\infty }$, 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 \{+\mathrm{\infty }\}$. Just replace f with its Moreau envelope.

Keywords:

• Accelerated gradient system
• convex optimization
• time rescaling
• fast convergence
• Lyapunov analysis

1991 Mathematics Subject Classifications:

• 49M37
• 65K05
• 90C25

Disclosure statement

No potential conflict of interest was reported by the author(s).

Notes

${}^{\ast }$Throughout the paper, $\mathcal{H}$ is a real Hilbert space, endowed with the scalar product $⟨\cdot ,\cdot ⟩$ and the associated norm $\Vert \cdot \Vert$. Unless specified, $f:\mathcal{H}\to \mathbb{R}$ is a ${\mathcal{C}}^1$ convex function with ${\mathrm{argmin}}_{\mathcal{H}}f\ne \mathrm{\varnothing }$. We take $t_0>0$ as the origin of time (this is justified by the singularity at the origin of the damping coefficient $\gamma (t)=\frac{\alpha }{t}$ which is used in the paper).