# Fast convex optimization via time scale and averaging of the steepest
descent

Hedy Attouch<EMAIL_ADDRESS>Radu Ioan Boţ111The research of RIB
has been supported by FWF (Austrian Science Fund), projects W 1260 and P
34922-N.222The research of DKN has been supported by FWF (Austrian Science
Fund), projects W 1260<EMAIL_ADDRESS>Dang-Khoa Nguyen333The research
of DKN has been supported by FWF (Austrian Science Fund), projects W 1260.
<EMAIL_ADDRESS>
###### Abstract

In a Hilbert setting, we develop a gradient-based dynamic approach for fast
solving convex optimization problems. By applying time scaling, averaging, and
perturbation techniques to the continuous steepest descent (SD), we obtain
high-resolution ODEs of the Nesterov and Ravine methods. These dynamics
involve asymptotically vanishing viscous damping and Hessian driven damping
(either in explicit or implicit form). Mathematical analysis does not require
developing a Lyapunov analysis for inertial systems. We simply exploit
classical convergence results for (SD) and its external perturbation version,
then use tools of differential and integral calculus, including Jensen’s
inequality. The method is flexible and by way of illustration we show how it
applies starting from other important dynamics in optimization. We consider
the case where the initial dynamics is the regularized Newton method, then the
case where the starting dynamics is the differential inclusion associated with
a convex lower semicontinuous potential, and finally we show that the
technique can be naturally extended to the case of a monotone cocoercive
operator. Our approach leads to parallel algorithmic results, which we study
in the case of fast gradient and proximal algorithms. Our averaging technique
shows new links between the Nesterov and Ravine methods.

###### keywords:

fast convex optimization , damped inertial dynamic , time scaling , averaging
, Nesterov and Ravine algorithms , Hessian driven damping , proximal
algorithms

###### MSC:

[2020] 37N40 , 46N10 , 49M30 , 65B99 , 65K05 , 65K10 , 90B50 , 90C25

[1]organization=IMAG, Univ. Montpellier, addressline=CNRS, postcode=,
city=Montpellier, country=France [2]organization=Faculty of Mathematics,
University of Vienna, addressline=Oskar-Morgenstern-Platz 1, postcode=1090
Vienna, city=Vienna, country=Austria

##  1 Introduction

In a real Hilbert space ${\mathcal{H}}$, we develop a general dynamic approach
whose objective is the rapid resolution of convex optimization problems via
first-order methods. We consider the problem

$\min\left\\{f(x):\,x\in{\mathcal{H}}\right\\},$ (1)

where, throughout the paper, we make the following assumptions on the function
$f$ to be minimized

$(\mathcal{A})\ \begin{cases}f:{\mathcal{H}}\rightarrow{\mathbb{R}}\text{ is a
convex function of class
}{\mathcal{C}}^{1};\,S=\operatorname{argmin}_{{\mathcal{H}}}f\neq\emptyset;\vspace{1mm}\\\
\nabla f\text{ is Lipschitz continuous on the bounded sets of
}{\mathcal{H}}.\end{cases}$ (2)

Our study is part of the close links between dissipative dynamical systems and
optimization algorithms, the latter being obtained by temporal discretization
of the continuous dynamics. The dynamic system approach makes it possible to
harmoniously combine the ingredients of our approach, namely time scaling,
averaging, and perturbation techniques to finally obtain inertial dynamics
with proven fast optimization properties.

Let us recall the mainstream for the study of accelerated gradient methods.
Then, in the next section, we will describe our approach, which is novel in
many aspects. The classical approach can be traced back to Gelfand and Tsetlin
[35], then Polyak [40, 41], and Attouch, Goudou and Redont [16], where fast
first-order optimization algorithms are naturally linked to damped inertial
dynamics via temporal discretization. In this approach, which is very inspired
by mechanics, PDE’s, and control theory the focus is on the design of the
damping term of the inertial dynamic, and its asymptotic stabilization effect.

In recent years, for the minimization of general convex differentiable
functions, an in-depth study has been carried out linking the accelerated
gradient method of Nesterov [38, 37] to inertial dynamics with vanishing
viscosity (the viscous damping coefficient tends to zero as $t\to+\infty$).
That is the Su-Boyd-Candès dynamical system [45]

$\ddot{x}(t)+\frac{\alpha}{t}\dot{x}(t)+\nabla f(x(t))=0,$ (3)

where fast optimization is obtained by taking $\alpha\geq 3$. In addition to
viscous damping, taking into account geometric damping (in our situation it is
driven by the Hessian of the function to be minimized) makes it possible to
improve the performance of these methods by attenuating the oscillations. That
is the dynamic

$\ddot{x}(t)+\frac{\alpha}{t}\dot{x}(t)+\beta\nabla^{2}f(x(t))\dot{x}(t)+\nabla
f(x(t))=0,$ (4)

considered by Attouch, Peypouquet, and Redont in [20]. The central role played
by these dynamics has been confirmed by their recent interpretation as the low
and high resolution of the Nesterov and Ravine accelerated gradient methods,
see Shi, Du, Jordan and Su [44], Attouch, Chbani, Fadili, and Riahi [9, 10].
The study of the fast convergence properties of these dynamics and algorithms
is based on Lyapunov analysis. But this approach does not give a simple
explanation of the choice of dynamics and algorithms. Moreover the Lyapunov
analysis is not trivial, and there is no general rule to find the Lyapunov
functions. Still, these techniques have allowed a deep understanding of
dynamics and accelerated algorithms for optimization, see [3, 4, 6, 7, 9, 11,
12, 14, 19, 26, 28, 31, 32, 33, 45, 44] for some recent contributions.

##  2 Time scaling and averaging approach

We propose a new approach to these questions which is based on a combination
of time scaling, averaging, and perturbation techniques. The basis property
which underlies our approach is the fact that by time scaling one can always
accelerate a dynamic. The kinematic interpretation is clear. By changing the
time clock the trajectories are travelled more or less quickly. The averaging
technique shifts from a dynamic of order $n$ to a dynamic of the immediately
higher order $n+1$. While preserving the asymptotic convergence properties,
this makes it possible to achieve a dynamic where the coefficient in front of
the gradient is fixed, and therefore suitable for developing an accelerated
gradient algorithm. The perturbation technique gives flexibility to these
methods, exploiting the fact that the convergence properties are preserved
when adding an external perturbation which vanishes asymptotically
sufficiently fast.

As the basic starting dynamic used in this paper, we consider the classical
continuous steepest descent

${\rm(SD)}\quad\dot{z}(t)+\nabla f(z(t))=0.$ (5)

Under the standing assumption $(\mathcal{A})$ on $f$ we know that, for any
$z_{0}\in{\mathcal{H}}$, there exists a unique classical global solution
$z\in\mathcal{C}^{1}([t_{0},+\infty[:{\mathcal{H}})$ of (SD) satisfying
$z(t_{0})=z_{0}$, see [5, Theorem 17.1.1]. We fix $t_{0}>0$ as the origin of
time (because of the singularity at the origin of coefficient
$\frac{\alpha}{t}$ which enter into our analysis).

###  2.1 Classical facts concerning the continuous steepest descent

We will have to consider the gradient system with an external perturbation.
The following theorem investigates its asymptotic properties under appropriate
conditions on the perturbation term. The proof is provided in the Appendix.

######  Theorem 1.

Suppose that $f\colon{\mathcal{H}}\to{\mathbb{R}}$ satisfies $(\mathcal{A})$.
Let $z\colon\left[t_{0},+\infty\right[\to{\mathcal{H}}$ be a solution
trajectory of

$\dot{z}(t)+\nabla f(z(t))=g(t),$ (6)

where $g\colon\left[t_{0},+\infty\right[\to{\mathcal{H}}$ is such that

$\int_{t_{0}}^{+\infty}\left\lVert g\left(t\right)\right\rVert
dt<+\infty\textrm{ and }\int_{t_{0}}^{+\infty}t\left\lVert
g\left(t\right)\right\rVert^{2}dt<+\infty.$ (7)

Then the following statements are true:

  1. $\rm{(i)}$

(integral estimate of the velocities)
$\int_{t_{0}}^{+\infty}t\left\lVert\dot{z}\left(t\right)\right\rVert^{2}dt<+\infty;$

  2. $\rm{(ii)}$

(integral estimate of the gradients) $\int_{t_{0}}^{+\infty}t\left\lVert\nabla
f\left(z\left(t\right)\right)\right\rVert^{2}dt<+\infty;$

  3. $\rm{(iii)}$

(integral estimate of the values)
$\int_{t_{0}}^{+\infty}\left(f\left(z\left(t\right)\right)-\inf_{{\mathcal{H}}}f\right)dt<+\infty;$

  4. $\rm{(iv)}$

(convergence of values towards minimal value)
$f\left(z\left(t\right)\right)-\inf_{{\mathcal{H}}}f=o\left(\frac{1}{t}\right)\textrm{
as }t\to+\infty;$

  5. $\rm{(v)}$

the solution trajectory $z(t)$ converges weakly as $t\to+\infty$, and its
limit belongs to $S=\operatorname{argmin}f$.

If

$\int_{t_{0}}^{+\infty}t^{2}\left\lVert
g\left(t\right)\right\rVert^{2}dt<+\infty,$

then

  6. $\rm{(vi)}$

(convergence of gradients towards zero) $\left\lVert\nabla
f\left(z\left(t\right)\right)\right\rVert=o\left(\frac{1}{t}\right)\textrm{ as
}t\to+\infty.$

###  2.2 General time scaling and averaging

Let us make the change of time variable $t=\tau(s)$ in the dynamic (SD),

${\rm(SD)}\qquad\dot{z}(t)+\nabla f(z(t))=0,$ (8)

where $\tau(\cdot)$ is an increasing function from $\mathbb{R}^{+}$ to
$\mathbb{R}^{+}$, which is continuously differentiable and satisfies
$\lim_{s\to+\infty}\tau(s)=+\infty$. Set $y(s):=z(\tau(s))$ and $s_{0}$ be
such that $t_{0}=\tau\left(s_{0}\right)$. On the one hand, by the derivation
chain rule, we have

$\dot{y}(s)=\dot{\tau}(s)\dot{z}(\tau(s)).$ (9)

On the other hand, setting $t=\tau(s)$ in (SD) gives

$\dot{z}(\tau(s))+\nabla f(z(\tau(s)))=0.$ (10)

According to (9) and (10), we obtain

$\dot{y}(s)+\dot{\tau}(s)\nabla f(y(s))=0.$ (11)

The convergence rate becomes (take $t=\tau(s)$ in $\rm{(iv)}$ of Theorem 1
with $g\equiv 0$)

$f(y(s))-\inf_{{\mathcal{H}}}f=o\left(\dfrac{1}{\tau(s)}\right)\textrm{ as
}s\to+\infty.$ (12)

By introducing a function $\tau(s)$ that grows faster than the identity
(namely $\tau(s)\geq s$), we have accelerated the dynamic, passing from the
asymptotic convergence rate $1/t$ for (SD) to $1/\tau(s)$ for (11). The price
to pay is that we no longer have an autonomous dynamic in (11), with as major
drawback the fact that the coefficient in front of the gradient term tends to
infinity as $s\to+\infty$. This prevents from using gradient methods to
discretize it. Recall that for gradient methods the step size has to be less
than or equal to twice the inverse of the Lipschitz constant of the gradient.
To overcome this we come with the second step of our method which is
averaging.

Several recent papers have been devoted to the role of the averaging
techniques in the acceleration of optimization algorithms. In [39] Nesterov
designed an algorithm that makes use of an averaging step for the gradients of
the generated sequence. In [43] Scieur, D’Aspremont, and Bach developed a
universal acceleration method based on averaging via polynomial techniques. In
[42] Poveda and Li developed another universal acceleration method via
averaging technique for singularly perturbed hybrid dynamical systems with
restarting mechanisms. Let us explain some simple and, as far as we know, new
ideas concerning the averaging methods based on differential equations. The
use of differential equations allows us to use differential and integral
calculus, which turns out to be a flexible approach.

Let us attach to $y(\cdot)$ the new function
$x:[s_{0},+\infty[\to{\mathcal{H}}$ defined by

$\dot{x}(s)+\frac{1}{\dot{\tau}(s)}(x(s)-y(s))=0,$ (13)

with $x(s_{0})=x_{0}$ given in ${\mathcal{H}}$. Equivalently

$y(s)=x(s)+\dot{\tau}(s)\dot{x}(s).$ (14)

By temporal derivation of (14) we get

$\dot{y}(s)=\dot{x}(s)+\ddot{\tau}(s)\dot{x}(s)+\dot{\tau}(s)\ddot{x}(s).$
(15)

Replacing $\dot{y}(s)$ as given by (15) in (11) we get

$\dot{\tau}(s)\ddot{x}(s)+(1+\ddot{\tau}(s))\dot{x}(s)+\dot{\tau}(s)\nabla
f(y(s))=0.$ (16)

After simplification we obtain

$\ddot{x}(s)+\dfrac{1+\ddot{\tau}(s)}{\dot{\tau}(s)}\dot{x}(s)+\nabla
f\Big{(}x(s)+\dot{\tau}(s)\dot{x}(s)\Big{)}=0.$ (17)

In doing so, we passed from the first-order differential equation (11) to the
second-order differential equation (17), with the advantage that now the
coefficient in front of the gradient is fixed. Let us now particularize the
time scale $\tau(\cdot)$.

#### Open loop control: link with Nesterov method

According to the Su, Boyd and Candès [45] model for the Nesterov method we
consider the case where the viscous damping coefficient in (17) satisfies

$\dfrac{1+\ddot{\tau}(s)}{\dot{\tau}(s)}=\dfrac{\alpha}{s}.$ (18)

Set $\theta(s)=\dot{\tau}(s)$. We are led to solve the fist-order linear
differential equation

$\dot{\theta}(s)-\dfrac{\alpha}{s}\theta(s)=-1.$ (19)

After multiplication by $s^{-\alpha}$, we get equivalently

$\dfrac{d}{ds}\left(s^{-\alpha}\theta(s)\right)=-s^{-\alpha}.$ (20)

By integrating we get

$s^{-\alpha}\theta(s)=-\dfrac{1}{-\alpha+1}s^{-\alpha+1}+C_{0},$ (21)

which gives

$\theta(s)=\dfrac{s}{\alpha-1}+C_{0}s^{\alpha}.$ (22)

According to $\theta(s)=\dot{\tau}(s)$, we finally get

$\tau(s)=\dfrac{s^{2}}{2(\alpha-1)}+{C_{1}}s^{\alpha+1}+{C_{2}},$ (23)

for ${C_{1},C_{2}}$ real constants. This leads to the choice $\alpha>1$. A
particular and relatively simple situation is to take $C_{1}=C_{2}=0$, which
gives

$\tau(s)=\dfrac{s^{2}}{2(\alpha-1)}.$ (24)

Equation (11) becomes

$\dot{y}(s)+\frac{s}{\alpha-1}\nabla f(y(s))=0,$ (25)

and (12) gives

$f(y(s))-\inf_{{\mathcal{H}}}f=o\left(\dfrac{1}{s^{2}}\right)\textrm{ as
}s\to+\infty.$ (26)

From (17) we obtain

$\ddot{x}(s)+\frac{\alpha}{s}\dot{x}(s)+\nabla
f\left(x(s)+\frac{s}{\alpha-1}\dot{x}(s)\right)=0.$ (27)

In doing so, we passed from the first-order differential equation

$\dot{y}(s)+\frac{s}{\alpha-1}\nabla f(y(s))=0$ (28)

to the second-order differential equation (27), with the advantage that now
the coefficient in front of the gradient is fixed. Of course, we have to prove
that the fast convergence rates are preserved.

The above dynamic (27) is a particular case of the Inertial System with
Implicit Hessian Damping

${\rm(ISIHD)}\quad\ddot{x}(s)+\frac{\alpha}{s}\dot{x}(s)+\nabla
f\Big{(}x(s)+\beta(s)\dot{x}(s)\Big{)}=0,$ (29)

considered by Alecsa, László, and Pinţa in [2], see also Attouch, Fadili, and
Kungurtsev [15] in the perturbed case. The rationale justifying the use of the
term “implicit” comes from the observation that by Taylor expansion (as
$s\to+\infty$ we have $\dot{x}(s)\to 0$) one has

$\nabla f\Big{(}x(s)+\beta(s)\dot{x}(s)\Big{)}\approx\nabla
f(x(s))+\beta(s)\nabla^{2}f(x(s))\dot{x}(s),$

hence making the Hessian damping appear indirectly. We can therefore expect
the dynamic (27) to have an asymptotic behavior similar to that of

$\ddot{x}(s)+\frac{\alpha}{s}\dot{x}(s)+\frac{s}{\alpha-1}\nabla^{2}f(x(s))\dot{x}(s)+\nabla
f\left(x(s)\right)=0.$ (30)

#### Closed loop control

The continuous steepest descent system (SD) provides several quantities which
are strictly increasing and converge to $+\infty$, so they are eligible for
time scaling. Since $\|\nabla f(z(t))\|$ is monotonically decreasing to zero,
taking

$t=\tau(s)=\dfrac{1}{\|\nabla f(z(s))\|^{p}},$

is eligible for any $p>0$. According to (SD) we have that the same holds true
for

$t=\tau(s)=\dfrac{1}{\|\dot{z}(s)\|^{p}}.$

Since $\tau$ comes into the scaling technique via its derivative, we can also
consider for $p>0$

$t=\dot{\tau}(s)=\dfrac{1}{\|\dot{z}(s)\|^{p}}.$

Alternatively, we may also consider building $\tau$ with the help of the
function values since $f(z(\cdot))$ is decreasing.

All these choices will lead to closed-loop dynamical systems which have
attracted of many researchers recently, see for instance [4, 36].

###  2.3 Convergence rates

The above results suggest that similar results are valid for (17). We will
examine the convergence rates satisfied by the trajectories of (17) simply by
using time scale and averaging arguments. We do not make any other Lyapunov
analysis, we just use the Lyapunov analysis of the steepest descent, which was
recalled in Subsection 2.1. Let us state our first result which concerns the
implicit Hessian driven damping dynamics.

######  Theorem 2.

Suppose that $f\colon{\mathcal{H}}\to{\mathbb{R}}$ satisfies $(\mathcal{A})$.
Let $x:[s_{0},+\infty[\to{\mathcal{H}}$ be a solution trajectory of

$\ddot{x}(s)+\frac{\alpha}{s}\dot{x}(s)+\nabla
f\left(x(s)+\frac{s}{\alpha-1}\dot{x}(s)\right)=0.$ (31)

Assume that $\alpha>1$. Then the following statements are true:

  1. $\rm{(i)}$

(integral estimate of the gradients)
$\int_{s_{0}}^{+\infty}s^{3}\left\lVert\nabla
f\left(x(s)+\frac{s}{\alpha-1}\dot{x}(s)\right)\right\rVert^{2}ds<+\infty;$

  2. $\rm{(ii)}$

(convergence of gradients towards zero) $\left\lVert\nabla
f\left(x(s)+\frac{s}{\alpha-1}\dot{x}(s)\right)\right\rVert=o\left(\frac{1}{s^{2}}\right)\textrm{
as }s\to+\infty;$

  3. $\rm{(iii)}$

(convergence of velocities towards zero)
$\left\lVert\dot{x}\left(s\right)\right\rVert=o\left(\frac{1}{s}\right)\textrm{
as }s\to+\infty;$

  4. $\rm{(iv)}$

the solution trajectory $x(s)$ converges weakly as $s\to+\infty$, and its
limit belongs to $S=\operatorname{argmin}f$.

If $\alpha>3$, then

  5. $\rm{(v)}$

(convergence of values towards minimal value)
$f(x(s))-\inf_{{\mathcal{H}}}f=o\left(\frac{1}{s^{2}}\right)\textrm{ as
}s\to+\infty.$

###### Proof.

First observe that the time scaling and averaging operations allow us to
obtain any solution trajectory of (31). To this end we need to choose
adequately the initial data in the first order evolution equations (28) and
(13) which are respectively attached to the scaling and averaging operations.
So let us give a solution trajectory $x(\cdot)$ of (31) which satisfies the
Cauchy data $x(s_{0})=x_{0}$ and $\dot{x}(s_{0})=x_{1}$. Let us verify that
this solution is reached by taking successively

$\begin{cases}\dot{y}(s)+\frac{s}{\alpha-1}\nabla f(y(s))=0\hskip
19.91692pt\vspace{2mm}\\\
y(s_{0})=x_{0}+\frac{s_{0}}{\alpha-1}x_{1},\end{cases}$ (32)

then

$\begin{cases}\dot{x}(s)+\frac{\alpha-1}{s}(x(s)-y(s))=0\vspace{2mm}\\\
x(s_{0})=x_{0}.\end{cases}$ (33)

Indeed, (33) gives $\dot{x}(s_{0})=\frac{\alpha-1}{s_{0}}(y(s_{0})-x(s_{0}))$,
which, by the second equation of (32), leads to $\dot{x}(s_{0})=x_{1}$.

Let us first interpret the passage from $y$ to $x$ as an averaging process. To
this end rewrite (33) as

$s\dot{x}(s)+(\alpha-1)x(s)=(\alpha-1)y(s).$ (34)

After multiplication of (34) by $s^{\alpha-2}$, we get equivalently

$s^{\alpha-1}\dot{x}(s)+(\alpha-1)s^{\alpha-2}x(s)=(\alpha-1)s^{\alpha-2}y(s),$
(35)

that is

$\frac{d}{ds}\left(s^{\alpha-1}x(s)\right)=(\alpha-1)s^{\alpha-2}y(s).$ (36)

By integrating (36) from $s_{0}$ to $s$, and according to $x(s_{0})=x_{0}$, we
obtain

$\displaystyle x(s)$ $\displaystyle=$
$\displaystyle\frac{s_{0}^{\alpha-1}}{s^{\alpha-1}}x_{0}+\frac{\alpha-1}{s^{\alpha-1}}\int_{s_{0}}^{s}u^{\alpha-2}y(u)du$
(37) $\displaystyle=$
$\displaystyle\frac{s_{0}^{\alpha-1}}{s^{\alpha-1}}y(s_{0})+\frac{\alpha-1}{s^{\alpha-1}}\int_{s_{0}}^{s}u^{\alpha-2}y(u)du-\frac{{s_{0}}^{\alpha}}{(\alpha-1)s^{\alpha-1}}x_{1}$
(38)

where the last equality follows from the choice of $y(s_{0})$ as given by
(32). Then, observe that $x(s)$ can be simply written as follows

$x(s)=\int_{s_{0}}^{s}y(u)\,d\mu_{s}(u)+\xi(s),$ (39)

where $\mu_{s}$ is the positive Radon measure on $[s_{0},s]$ defined by

$\mu_{s}=\frac{s_{0}^{\alpha-1}}{s^{\alpha-1}}\delta_{s_{0}}+(\alpha-1)\frac{u^{\alpha-2}}{s^{\alpha-1}}du,$

where $\delta_{s_{0}}$ is the Dirac measure at $s_{0}$, and

$\xi(s):=-\frac{{s_{0}}^{\alpha}}{(\alpha-1)s^{\alpha-1}}x_{1}$

is considered as a small perturbation for large values of $s$.

$\rm{(i)}$ $\&$ $\rm{(ii)}$ According to the energy estimates for the
continuous steepest descent system, see Theorem 1, we have that for any
solution trajectory of

${\rm(SD)}\quad\dot{z}(t)+\nabla f(z(t))=0$ (40)

it holds

${\int_{t_{0}}^{+\infty}t\left\lVert\dot{z}\left(t\right)\right\rVert^{2}dt<+\infty,\quad}\int_{t_{0}}^{+\infty}t\|\nabla
f(z(t)\|^{2}dt<+\infty,{\quad\textrm{ and }\quad\left\lVert\nabla
f\left(z\left(t\right)\right)\right\rVert=o\left(\frac{1}{t}\right)\textrm{ as
}t\to+\infty}.$ (41)

Notice that from the unperturbed (SD) we also have

$\left\lVert\dot{z}\left(t\right)\right\rVert=o\left(\frac{1}{t}\right)\textrm{
as }t\to+\infty.$ (42)

After making the change of time variable

$t=u(s)=\frac{s^{2}}{2(\alpha-1)},$

and setting $z(u(s))=y(s)$, the second integral estimate above becomes

$\int_{s_{0}}^{+\infty}u(s)\|\nabla f(z(u(s))\|^{2}\dot{u}(s)ds<+\infty,$ (43)

that is

$\int_{s_{0}}^{+\infty}s^{3}\|\nabla f(y(s))\|^{2}ds<+\infty.$ (44)

Replacing $y$ by its equivalent formulation
$y(s)=x(s)+\frac{s}{\alpha-1}\dot{x}(s)$ in (41) and (44) gives the claims.

$\rm{(iii)}$ From (42) we have that there exists a positive function
$\varepsilon_{0}(\cdot)$ which satisfies
$\lim_{s\to+\infty}\varepsilon_{0}(s)=0$ such that

$\|\dot{z}(\tau(s))\|=\frac{\varepsilon_{0}(\tau(s))}{\tau(s)},$ (45)

and since $\dot{y}(s)=\dot{\tau}(s)\dot{z}(\tau(s))$ we get

$\|\dot{y}(s)\|=\frac{\varepsilon_{0}(\tau(s))\dot{\tau}(s)}{\tau(s)}.$ (46)

From $\tau(s)=\frac{s^{2}}{2(\alpha-1)}$, we get

$\|\dot{y}(s)\|=\frac{\varepsilon_{1}(s)}{s},$ (47)

with $\varepsilon_{1}(s)=2\varepsilon_{0}(\tau(s))$ which tends to zero as
$s\to+\infty$. Let us now establish a similar estimate for $\|\dot{x}(s)\|$.
According to (37)

$\displaystyle x(s)$ $\displaystyle=$
$\displaystyle\frac{s_{0}^{\alpha-1}}{s^{\alpha-1}}x_{0}+\frac{\alpha-1}{s^{\alpha-1}}\int_{s_{0}}^{s}u^{\alpha-2}y(u)du.$
(48)

Let us derivate this expression. We get

$\displaystyle\dot{x}(s)$ $\displaystyle=$
$\displaystyle-\frac{(\alpha-1)s_{0}^{\alpha-1}}{s^{\alpha}}x_{0}-\frac{(\alpha-1)^{2}}{s^{\alpha}}\int_{s_{0}}^{s}u^{\alpha-2}y(u)du+(\alpha-1)\frac{1}{s}y(s).$
(49)

Let us reformulate this expression in terms of $\dot{y}(s)$, which is the
quantity whose speed of convergence is known by (47). Indeed, by integration
by parts we have

$\displaystyle\int_{s_{0}}^{s}u^{\alpha-1}\dot{y}(u)du$ $\displaystyle=$
$\displaystyle
s^{\alpha-1}y(s)-s_{0}^{\alpha-1}y(s_{0})-(\alpha-1)\int_{s_{0}}^{s}u^{\alpha-2}y(u)du.$

After multiplication of the above expression by $\frac{\alpha-1}{s^{\alpha}}$,
and according to $y(s_{0})=x_{0}{+\frac{s_{0}}{\alpha-1}x_{1}}$, we get

$\displaystyle\frac{\alpha-1}{s^{\alpha}}\int_{s_{0}}^{s}u^{\alpha-1}\dot{y}(u)du$
$\displaystyle=$
$\displaystyle(\alpha-1)\frac{1}{s}y(s)-\frac{(\alpha-1)s_{0}^{\alpha-1}}{s^{\alpha}}x_{0}{-\frac{s_{0}^{\alpha}}{s^{\alpha}}x_{1}}-\frac{(\alpha-1)^{2}}{s^{\alpha}}\int_{s_{0}}^{s}u^{\alpha-2}y(u)du.$
(50)

Comparing (49) and (50) we get

$\displaystyle\dot{x}(s)$ $\displaystyle=$
$\displaystyle\frac{\alpha-1}{s^{\alpha}}\int_{s_{0}}^{s}u^{\alpha-1}\dot{y}(u)du{+\frac{s_{0}^{\alpha}}{s^{\alpha}}x_{1}}.$

According to (47), we obtain successively

$\displaystyle\|\dot{x}(s)\|$ $\displaystyle\leq$
$\displaystyle\frac{\alpha-1}{s^{\alpha}}\int_{s_{0}}^{s}u^{\alpha-1}\left\lVert\dot{y}(u)\right\rVert
du{+\frac{s_{0}^{\alpha}}{s^{\alpha}}\left\lVert x_{1}\right\rVert}$ (51)
$\displaystyle=$
$\displaystyle\frac{\alpha-1}{s^{\alpha}}\int_{s_{0}}^{s}u^{\alpha-2}\varepsilon_{1}(u)du{+\frac{s_{0}^{\alpha}}{s^{\alpha}}\left\lVert
x_{1}\right\rVert}.$

After multiplication of (51) by $s$, we obtain

$\displaystyle s\|\dot{x}(s)\|$ $\displaystyle\leq$
$\displaystyle\frac{\alpha-1}{s^{\alpha-1}}\int_{s_{0}}^{s}u^{\alpha-2}\varepsilon_{1}(u)du+\frac{s_{0}^{\alpha}}{s^{\alpha-1}}\left\lVert
x_{1}\right\rVert,$

and Lemma 4 gives us $\lim_{s\to+\infty}\|s\dot{x}(s)\|=0$.

$\rm{(iv)}$ For trajectory convergence, following the approach of the paper,
we do not perform a Lyapunov analysis, but take advantage of the fact that the
trajectory $z\left(s\right)$ of the steepest descent dynamics converges weakly
towards a solution $x_{*}\in S$ as $s\to+\infty$. This immediately implies
that $y(s)=z(u(s))$ converges weakly to $x_{*}$ as $s\to+\infty$. In other
words, for each $v\in{\mathcal{H}}$

$\left\langle y\left(s\right),v\right\rangle\to\left\langle
x_{*},v\right\rangle\textrm{ as }s\to+\infty.$

To pass from the convergence of $y$ to that of $x$, we use the interpretation
of $x$ as an average of $y$ plus a negligeable term. The convergence then
results from the general property which says that convergence entails ergodic
convergence. Let us make this precise. Since the perturbation term $\xi$ is
negligible as $s\to+\infty$, we have by definition of $x(s)$

$x(s)\sim\frac{s_{0}^{\alpha-1}}{s^{\alpha-1}}y(s_{0})+\frac{\alpha-1}{s^{\alpha-1}}\int_{s_{0}}^{s}u^{\alpha-2}y(u)du.$

After elementary calculus, we just need to prove that for $a(\cdot)$ be a
positive real valued function which verifies $\lim_{s\to+\infty}a(s)=0$, then
$\lim_{s\to+\infty}A(s)=0$, where

$A(s)=\frac{1}{s^{\alpha-1}}\int_{s_{0}}^{s}u^{\alpha-2}a(u)du,$

which is true according to Lemma 4.

$\rm{(v)}$ First, let us get rid of the perturbation term. From $\rm{(iv)}$ we
deduce that $x(\cdot)$ is also bounded. Since $\nabla f$ is Lipschitz
continuous on the bounded sets, it follows that $\nabla f$ is bounded on the
bounded sets, which immediately implies that $f$ is also Lipschitz continuous
on the bounded sets. Therefore there exists $L_{f}>0$ such that

$f(x(s))-f\left(\int_{s_{0}}^{s}y(u)\,d\mu_{s}(u)\right)\leq
L_{f}\|\xi(s)\|\leq\frac{{C_{f}}}{s^{\alpha-1}}\quad\forall s\geq s_{0},$

for $C_{f}:=\frac{L_{f}{s_{0}}^{\alpha}}{\alpha-1}\left\lVert
x_{1}\right\rVert$, which leads to

$f(x(s))-\inf_{{\mathcal{H}}}f\leq
f\left(\int_{s_{0}}^{s}y(u)\,d\mu_{s}(u)\right)-\inf_{{\mathcal{H}}}f+\frac{C_{f}}{s^{\alpha-1}}\quad\forall
s\geq s_{0}.$ (52)

We are therefore reduced to examining the convergence rate of
$f\left(\int_{s_{0}}^{s}y(u)d\mu_{s}(u)\right)-\inf f$ towards zero as
$s\to+\infty$. We have that $\mu_{s}$ is a positive Radon measure on
$[s_{0},s]$ whose total mass is equal to $1$. It is therefore a probability
measure, and $\int_{s_{0}}^{s}y(u)\,d\mu_{s}(u)$ is obtained by averaging the
trajectory $y(\cdot)$ on $[s_{0},s]$ with respect to $\mu_{s}$. From there, we
can deduce fast convergence properties for the solution trajectories of (31).
According to the convexity of $f$, and Jensen’s inequality, we obtain that

$f\left(\int_{s_{0}}^{s}y(u)\,d\mu_{s}(u)\right)-\inf_{{\mathcal{H}}}f\leq\int_{s_{0}}^{s}\left(f(y(u))-\inf_{{\mathcal{H}}}f\right)d\mu_{s}(u).$
(53)

It follows from (26) that there exists a positive function
$\varepsilon(\cdot)$ which satisfies $\lim_{s\to+\infty}\varepsilon(s)=0$ such
that

$f\left(y\left(s\right)\right)-\inf_{{\mathcal{H}}}f=\frac{\varepsilon(s)}{s^{2}}.$
(54)

According to the definition of $\mu_{s}$, it yields for all $s\geq s_{0}$

$f\left(\int_{s_{0}}^{s}y(u)\,d\mu_{s}(u)\right)-\inf_{{\mathcal{H}}}f\leq\int_{s_{0}}^{s}\frac{\varepsilon(u)}{u^{2}}d\mu_{s}(u)=\frac{s_{0}^{\alpha-3}}{s^{\alpha-1}}+\dfrac{\alpha-1}{s^{\alpha-1}}\int_{s_{0}}^{s}\varepsilon(u)u^{\alpha-4}du.$

By making use of (52), we deduce

$s^{2}\left(f(x(s))-\inf_{{\mathcal{H}}}f\right)\leq\frac{C_{f}+s_{0}^{\alpha-3}}{s^{\alpha-3}}+\dfrac{\alpha-1}{s^{\alpha-3}}\int_{s_{0}}^{s}\varepsilon(u)u^{\alpha-4}du.$

Therefore, for $\alpha>3$ we get

$\displaystyle\limsup_{s\to+\infty}s^{2}(f\left(x(s)\right)-\inf_{{\mathcal{H}}}f)$
$\displaystyle\leq$
$\displaystyle\left(\alpha-1\right)\limsup_{s\to+\infty}\dfrac{1}{s^{\alpha-3}}\int_{s_{0}}^{s}\varepsilon(u)u^{\alpha-4}du.$

Finally, we just need to apply Lemma 4 to prove the claim. ∎

######  Remark 1.

Let us emphasize the fact that the convergence of the solution trajectories of
the damped inertial system (31) is valid under the condition $\alpha>1$. This
contrasts with the stronger condition $\alpha>3$ which is required to obtain
the convergence of the trajectories for the system without Hessian driven
damping

$\ddot{x}(s)+\frac{\alpha}{s}\dot{x}(s)+\nabla f\left(x(s)\right)=0,$ (55)

and which is the low-resolution ODE of Nesterov’s accelerated gradient method.
This property is related to the presence of the Hessian driven damping and the
particular form of the corresponding coefficient $\frac{s}{\alpha-1}.$
Moreover, it has been established in [11, 19] that the choice $\alpha>3$
provides a convergence rate of the values of $o\left(1/s^{2}\right)$ as
$s\rightarrow+\infty$, and therefore it improves the convergence rate of
Nesterov’s accelrated gradient method of ${\mathcal{O}}\left(1/s^{2}\right)$
as $s\rightarrow+\infty$. As seen, the time scale and averaging approach is
flexible enough to also provide the convergence rate $o\left(1/s^{2}\right)$
as $s\rightarrow+\infty$, in the case $\alpha>3$.

######  Remark 2.

The time scale and averaging technique provides a new approach which allows to
transfer the convergence rate of the function value along the trajectory
$y(s)$ obtained via the time scaling of (SD) to the function value along the
trajectory $x(s)$ that can be seen as the average of the initial one. This
phenomenon can be seen in analogy with the manner the Nesterov method and the
Ravine method behave to each other.

Recall that the Nesterov’acceleration gradient [38, 37] reads

$(\forall k\geq
1)\quad\begin{cases}y_{k}&:=x_{k}+\alpha_{k}\left(x_{k}-x_{k-1}\right)\vspace{1mm}\\\
x_{k+1}&:=y_{k}-\lambda\nabla f\left(y_{k}\right)\end{cases},$ (56)

where $x_{0}=x_{1}\in{\mathcal{H}}$, $0<\lambda\leq\frac{1}{L}$ and

$\alpha_{k}:=\dfrac{t_{k}-1}{t_{k+1}}\quad\textrm{ with
}\quad\begin{cases}t_{1}:=1\\\ t_{k+1}^{2}-t_{k+1}\leq t_{k}^{2}\quad\forall
k\geq 1\end{cases}.$

The so-called Ravine sequence $(y_{k})_{k\geq 1}$ is the one generated by the
Ravine method introduced by Gelfand and Tsetlin [35, 14]. We will show that
the values of $f$ along the Ravine sequence converge fast towards
$\inf_{{\mathcal{H}}}$ and that the convergence rate can be transferred to the
values of $f$ along $(x_{k})_{k\geq 0}$, which is an average sequence of
$(y_{k})_{k\geq 1}$. Indeed, by induction arguments, we have for every $k\geq
1$

$\displaystyle
x_{k+1}=\dfrac{1}{1+\alpha_{k+1}}y_{k+1}+\dfrac{\alpha_{k+1}}{1+\alpha_{k+1}}x_{k}$
$\displaystyle=\dfrac{1}{1+\alpha_{k+1}}y_{k+1}+\dfrac{\alpha_{k+1}}{1+\alpha_{k+1}}\left(\dfrac{1}{1+\alpha_{k}}y_{k}+\dfrac{\alpha_{k}}{1+\alpha_{k}}x_{k-1}\right)$
$\displaystyle=\cdots=\sum_{i=1}^{k+1}\theta_{k+1,i}y_{i},$

where the nonnegative weights $\left(\theta_{k+1,i}\right)_{1\leq i\leq k+1}$
defined by

$\theta_{k+1,i}:=\dfrac{1}{1+\alpha_{k+1}}\prod_{j=1}^{k+1-i}\dfrac{\alpha_{k+2-j}}{1+\alpha_{k+1-j}}\quad\forall
1\leq i\leq k\quad\mbox{and}\ \theta_{k+1,k+1}:=\dfrac{1}{1+\alpha_{k+1}}$

fulfill $\sum_{i=1}^{k+1}\theta_{k+1,i}=1$.

In the following we give a direct proof for the fast convergence rate of the
Ravine method, which can be seen as an alternative approach to [14]. Let
$z_{*}\in S$. We define for every $k\geq 2$ the discrete energy function

$E_{k}:=t_{k}^{2}\left(f\left(y_{k-1}\right)-\inf_{{\mathcal{H}}}f-\lambda\left(1-\dfrac{L\lambda}{2}\right)\left\lVert\nabla
f\left(y_{k-1}\right)\right\rVert^{2}\right)+\dfrac{1}{2\lambda}\left\lVert\left(t_{k}-1\right)\left(x_{k}-x_{k-1}\right)+x_{k}-z_{*}\right\rVert^{2}\geq
0.$

Let $k\geq 2$. By the convexity of $f$, it yields

$\displaystyle f\left(x_{k}\right)\geq f\left(y_{k}\right)+\left\langle\nabla
f\left(y_{k}\right),x_{k}-y_{k}\right\rangle\quad\mbox{and}\quad\inf_{{\mathcal{H}}}f\geq
f\left(y_{k}\right)+\left\langle\nabla
f\left(y_{k}\right),z_{*}-y_{k}\right\rangle.$

By multiplying the first inequality by $t_{k+1}^{2}-t_{k+1}>0$ and the second
one by $t_{k+1}>0$ and summing the resulting inequalities, it yields

$\displaystyle\left(t_{k+1}^{2}-t_{k+1}\right)\left(f\left(x_{k}\right)-\inf_{{\mathcal{H}}}f\right)$
$\displaystyle\geq
t_{k+1}^{2}\left(f\left(y_{k}\right)-\inf_{{\mathcal{H}}}f\right)-t_{k+1}\left\langle\nabla
f\left(y_{k}\right),\left(t_{k+1}-1\right)\left(y_{k}-x_{k}\right)+y_{k}-z_{*}\right\rangle.$
(57)

Since
$t_{k+1}y_{k}=t_{k+1}x_{k}+\left(t_{k}-1\right)\left(x_{k}-x_{k-1}\right)$, by
denoting

$\displaystyle
u_{k}:=\left(t_{k+1}-1\right)\left(y_{k}-x_{k}\right)+y_{k}-z_{*}=t_{k+1}\left(y_{k}-x_{k}\right)+x_{k}-z_{*}=\left(t_{k}-1\right)\left(x_{k}-x_{k-1}\right)+x_{k}-z_{*},$

we have

$\displaystyle-\lambda t_{k+1}\nabla
f\left(y_{k}\right)=t_{k+1}\left(x_{k+1}-y_{k}\right)=t_{k+1}\left(x_{k+1}-x_{k}\right)-\left(t_{k}-1\right)\left(x_{k}-x_{k-1}\right)=u_{k+1}-u_{k}.$

Therefore

$\displaystyle\ -t_{k+1}\left\langle\nabla
f\left(y_{k}\right),\left(t_{k+1}-1\right)\left(y_{k}-x_{k}\right)+y_{k}-z_{*}\right\rangle$
$\displaystyle=$ $\displaystyle\ \dfrac{1}{\lambda}\left\langle
u_{k+1}-u_{k},u_{k}\right\rangle=\dfrac{1}{2\lambda}\left(\left\lVert
u_{k+1}\right\rVert^{2}-\left\lVert u_{k+1}-u_{k}\right\rVert^{2}-\left\lVert
u_{k}\right\rVert^{2}\right)$ $\displaystyle=$ $\displaystyle\
\dfrac{1}{2\lambda}\left(\left\lVert\left(t_{k+1}-1\right)\left(x_{k+1}-x_{k}\right)+x_{k+1}-z_{*}\right\rVert^{2}-\left\lVert\left(t_{k}-1\right)\left(x_{k}-x_{k-1}\right)+x_{k}-z_{*}\right\rVert^{2}\right)-\dfrac{1}{2}\lambda
t_{k+1}^{2}\left\lVert\nabla f\left(y_{k}\right)\right\rVert^{2}.$

Replacing this expression into (57), after some rearrangements we obtain

$\displaystyle
E_{k+1}\leq\dfrac{1}{2\lambda}\left\lVert\left(t_{k}-1\right)\left(x_{k}-x_{k-1}\right)+x_{k}-z_{*}\right\rVert^{2}+\left(t_{k+1}^{2}-t_{k+1}\right)\left(f\left(x_{k}\right)-\inf_{{\mathcal{H}}}f\right)-\dfrac{1}{2}\lambda\left(1-L\lambda\right)t_{k+1}^{2}\left\lVert\nabla
f\left(y_{k}\right)\right\rVert^{2}.$

In addition, the Descent Lemma gives

$\displaystyle f\left(x_{k}\right)-\inf_{{\mathcal{H}}}f$ $\displaystyle\leq
f\left(y_{k-1}\right)-\inf_{{\mathcal{H}}}f+\left\langle\nabla
f\left(y_{k-1}\right),x_{k}-y_{k-1}\right\rangle+\dfrac{L}{2}\left\lVert
x_{k}-y_{k-1}\right\rVert^{2}$
$\displaystyle=f\left(y_{k-1}\right)-\inf_{{\mathcal{H}}}f-\lambda\left(1-\dfrac{L\lambda}{2}\right)\left\lVert\nabla
f\left(y_{k-1}\right)\right\rVert^{2},$ (58)

which further leads to the inequality

$\displaystyle E_{k+1}\leq$ $\displaystyle\
E_{k}-\dfrac{1}{2}\lambda\left(1-L\lambda\right)t_{k+1}^{2}\left\lVert\nabla
f\left(y_{k}\right)\right\rVert^{2}$ $\displaystyle\
+\left(t_{k+1}^{2}-t_{k+1}-t_{k}^{2}\right)\left(f\left(y_{k-1}\right)-\inf_{{\mathcal{H}}}f-\lambda\left(1-\dfrac{L\lambda}{2}\right)\left\lVert\nabla
f\left(y_{k-1}\right)\right\rVert^{2}\right),$

and it also proves that $E_{k}\geq 0$ for every $k\geq 2$. Therefore, when
$0<\lambda<\frac{1}{L}$, we can deduce

$f\left(y_{k}\right)-\inf_{{\mathcal{H}}}f=\mathcal{O}\left(\dfrac{1}{t_{k+1}^{2}}\right)=\mathcal{O}\left(\dfrac{1}{(k+1)^{2}}\right),$

which immediately transfers to

$f\left(x_{k}\right)-\inf_{{\mathcal{H}}}f=\mathcal{O}\left(\dfrac{1}{t_{k+1}^{2}}\right)=\mathcal{O}\left(\dfrac{1}{(k+1)^{2}}\right).$

##  3 Applications to other continuous dynamics

In this section we will show that the proposed approach which combines time
scaling with averaging can be successfully applied beyond the classical
steepest descent dynamical system.

###  3.1 Explicit Hessian damping

We consider an explicit Hessian driven damping version of the Su-Boyd-Candés
dynamical system (3). As explained in (30) the following dynamic

$\ddot{y}\left(s\right)+\dfrac{\alpha}{s}\dot{y}\left(s\right)+\dfrac{s}{\alpha+1}\dfrac{d}{ds}\left(\nabla
f\left(y\left(s\right)\right)\right)+\nabla f\left(y\left(s\right)\right)=0$
(59)

comes naturally by performing a Taylor expansion in (31). Just note that to
match the general writing of inertial dynamics for optimization, the above
formula is obtained by taking $\alpha+1$ instead of $\alpha-1$.

The above dynamic (59) is a particular case of the general dynamic on
$[s_{0},+\infty[$

${\rm\mbox{(DIN-
AVD)}}_{\alpha,\beta,b}\quad\ddot{y}(s)+\displaystyle{\frac{\alpha}{s}}\dot{y}(s)+\beta(s)\nabla^{2}f(y(s))\dot{y}(s)+b(s)\nabla
f(y(s))=0,$

studied by Attouch, Chbani, Fadili, Riahi in [9, 10]. Let us recall the
convergence results obtained in [9, 10] by performing a Lyapunov analysis for
${\rm(DIN-AVD)}_{\alpha,\beta,b}$. They will serve as a comparison with our
results.

######  Theorem 3.

Assume that $\alpha\geq 1$. Set
$w(s):=b(s)-\left(\dot{\beta}(s)+\dfrac{\beta(s)}{s}\right)$ and suppose that
the following conditions are satisfied for every $s\geq s_{0}$

$\displaystyle(\mathcal{G}_{2})\quad b(s)>\dot{\beta}(s)+\dfrac{\beta(s)}{s};$
$\displaystyle(\mathcal{G}_{3})\quad s\dot{w}(s)\leq(\alpha-3)w(s).\hskip
85.35826pt$

Then, for every solution trajectory
$y:[s_{0},+\infty[\rightarrow{\mathcal{H}}$ of ${\rm(DIN-
AVD)}_{\alpha,\beta,b}$, the following statements are true:

$\displaystyle
i)\,\,f(y(s))-\inf_{{\mathcal{H}}}f={\mathcal{O}}\left(\dfrac{1}{s^{2}w(s)}\right)\,\mbox{
as }\,s\to+\infty;$ $\displaystyle
ii)\,\int_{s_{0}}^{+\infty}s^{2}\beta(s)w(s)\|\nabla f(y(s))\|^{2}ds<+\infty;$
$\displaystyle
iii)\,\int_{s_{0}}^{+\infty}s\Big{(}(\alpha-3)w(s)-s\dot{w}(s)\Big{)}(f(y(s))-\inf_{{\mathcal{H}}}f)ds<+\infty.$

Let us specialize the above result to (31) by taking $b(s)=1$ and
$\beta(s)=\frac{s}{\alpha-1}$ for every $s\geq s_{0}$. We get
$w(\cdot)\equiv\frac{\alpha-3}{\alpha-1}$. Thus $(\mathcal{G}_{2})$ is
satisfied for $\alpha>3$, while $(\mathcal{G}_{3})$ reduces to
$0\leq\frac{{(\alpha-3)}^{2}}{\alpha-1}$, which is also satisfied. We thus get
the convergence rates for the trajectories of (31)

$f(y(s))-\min_{{\mathcal{H}}}f={\mathcal{O}}\left(\dfrac{1}{s^{2}}\right)\,\mbox{
as }\,s\to+\infty;\,\int_{s_{0}}^{+\infty}s^{3}\|\nabla
f(y(s))\|^{2}ds<+\infty;\,\int_{s_{0}}^{+\infty}s(f(y(s))-\inf_{{\mathcal{H}}}f)ds<+\infty.$

In this particular setting we can deduce further (see [10, Theorem 2.1])

$\int_{s_{0}}^{+\infty}s\|\dot{y}(s)\|^{2}ds<+\infty;\quad
f(y(s))-\min_{{\mathcal{H}}}f=o\left(\dfrac{1}{s^{2}}\right)\,\mbox{ and
}\|\dot{y}(s)\|=o\left(\dfrac{1}{s}\right)\,\mbox{ as }\,s\to+\infty.$

Let us show that this dynamic can be reached by time scaling of a perturbed
version of the continuous steepest descent dynamical system. As for the
implicit case, we make in the latter the change of time variable

$\tau(s)=\frac{s^{2}}{2(\alpha+1)}.$

Thus we obtain the rescaled steepest descent

$\dot{y}(s)+\frac{s}{\alpha+1}\nabla f(y(s))=0,$ (60)

with the convergence rate

$f(y(s))-\inf_{{\mathcal{H}}}f{=o\left(\dfrac{1}{s^{2}}\right)\mbox{ as
}\,s\to+\infty.}$ (61)

To obtain an explicit Hessian driven damping term, we take the derivative with
respect to $s$ in (60)

$\ddot{y}\left(s\right)+\dfrac{1}{\alpha+1}\nabla
f\left(y\left(s\right)\right)+\dfrac{s}{\alpha+1}\dfrac{d}{ds}\left(\nabla
f\left(y\left(s\right)\right)\right)=0.$

On the other hand, for every $s\geq\sigma_{0}$, by multiplying both sides of
(60) by $\frac{\alpha}{s}>0$, we get

$\dfrac{\alpha}{s}\dot{y}\left(s\right)+\dfrac{\alpha}{\alpha+1}\nabla
f\left(y\left(s\right)\right)=0.$

Summing up the two above equations above yields

$\ddot{y}\left(s\right)+\dfrac{\alpha}{s}\dot{y}\left(s\right)+\dfrac{s}{\alpha+1}\dfrac{d}{ds}\left(\nabla
f\left(y\left(s\right)\right)\right)+\nabla f\left(y\left(s\right)\right)=0,$

which is precisely (59).

######  Theorem 4.

Suppose that $f\colon{\mathcal{H}}\to{\mathbb{R}}$ satisfies $(\mathcal{A})$.
Let $y:[s_{0},+\infty[\to{\mathcal{H}}$ be a solution trajectory of

$\ddot{y}\left(s\right)+\dfrac{\alpha}{s}\dot{y}\left(s\right)+\dfrac{s}{\alpha+1}\dfrac{d}{ds}\left(\nabla
f\left(y\left(s\right)\right)\right)+\nabla f\left(y\left(s\right)\right)=0.$
(62)

Assume that $\alpha>1$. Then the following statements are true:

  1. $\rm{(i)}$

(integral estimate of the velocities)
$\int_{s_{0}}^{+\infty}s\left\lVert\dot{y}\left(s\right)\right\rVert^{2}ds<+\infty;$

  2. $\rm{(ii)}$

(integral estimate of the values)
$\int_{s_{0}}^{+\infty}s\left(f\left(y\left(s\right)\right)-\inf_{{\mathcal{H}}}f\right)ds<+\infty;$

  3. $\rm{(iii)}$

(integral estimate of the gradients)
$\int_{s_{0}}^{+\infty}s^{3}\left\lVert\nabla
f\left(y\left(s\right)\right)\right\rVert^{2}ds<+\infty;$

  4. $\rm{(iv)}$

(convergence of values towards minimal value)
$f\left(y\left(s\right)\right)-\inf_{{\mathcal{H}}}f=o\left(\frac{1}{s^{2}}\right)\textrm{
as }s\to+\infty;$

  5. $\rm{(v)}$

the solution trajectory $y(s)$ converges weakly as $s\to+\infty$, and its
limit belongs to $S=\operatorname{argmin}f$.

If $\alpha>2$, then

  6. $\rm{(vi)}$

(convergence of gradients towards zero)
$\left\lVert\dot{y}\left(s\right)\right\rVert=o\left(\frac{1}{s}\right)\textrm{
as }s\to+\infty;$

  7. $\rm{(vii)}$

(convergence of gradients towards zero) $\left\lVert\nabla
f\left(y\left(s\right)\right)\right\rVert=o\left(\frac{1}{s^{2}}\right)\textrm{
as }s\to+\infty.$

###### Proof.

The proof consists in reversing the process described above which has
permitted us to pass from (SD) to the damped inertial dynamic with explicit
Hessian driven damping (62). Let $y$ be an arbitrary solution trajectory of
(62) which satisfies the Cauchy data $y\left(s_{0}\right):=y_{0}$ and
$\dot{y}\left(s_{0}\right):=y_{1}$. Observe that

$\displaystyle\dfrac{d}{ds}\left(s^{\alpha}\dot{y}\left(s\right)\right)$
$\displaystyle=s^{\alpha}\ddot{y}\left(s\right)+\alpha
s^{\alpha-1}\dot{y}\left(s\right)$
$\displaystyle\dfrac{d}{ds}\left(\dfrac{s^{\alpha+1}}{\alpha+1}\nabla
f\left(y\left(s\right)\right)\right)$
$\displaystyle=\dfrac{s^{\alpha+1}}{\alpha+1}\dfrac{d}{ds}\nabla
f\left(y\left(s\right)\right)+s^{\alpha}\nabla f\left(y\left(s\right)\right).$

Hence, by multiplying both sides of (62) by $s^{\alpha}>0$, we deduce that

$\dfrac{d}{ds}\left(s^{\alpha}\dot{y}\left(s\right)+\dfrac{s^{\alpha+1}}{\alpha+1}\nabla
f\left(y\left(s\right)\right)\right)=0.$

This gives, equivalently

$\dot{y}\left(s\right)+\dfrac{s}{\alpha+1}\nabla
f\left(y\left(s\right)\right)=\dfrac{c_{0}}{s^{\alpha}},$ (63)

where $c_{0}\in{\mathcal{H}}$ is a constant that can be determined from the
Cauchy condition. Precisely, taking $s:=s_{0}$ in (63) it yields

$c_{0}=s_{0}^{\alpha}y_{1}+\frac{s_{0}^{\alpha+1}}{\alpha+1}\nabla
f\left(y_{0}\right).$ (64)

Next we show that time scaling makes it possible to link the solution
trajectory $y(\cdot)$ of (62) to the solution trajectory of a perturbation of
(SD). Set $z\left(t\right)=y\left(\sigma\left(t\right)\right)$, where

$\sigma\left(t\right)=\sqrt{2\left(\alpha+1\right)t}.$

Therefore,

$\dot{\sigma}\left(t\right)=\sqrt{\dfrac{\alpha+1}{2t}}\quad\textrm{ and
}\quad\dot{z}\left(t\right)=\dot{\sigma}\left(t\right)\dot{y}\left(\sigma\left(t\right)\right).$

Moreover, notice that (63) can be equivalently written as

$\dfrac{\alpha+1}{s}\dot{y}\left(s\right)+\nabla
f\left(y\left(s\right)\right)=\dfrac{c_{0}(\alpha+1)}{s^{\alpha+1}}.$

Setting $s=\sigma\left(t\right)$ gives with
$c:=c_{0}(\alpha+1)\in{\mathcal{H}}$

$\frac{\alpha+1}{\sigma\left(t\right)}\frac{1}{\dot{\sigma}\left(t\right)}\dot{z}\left(t\right)+\nabla
f\left(z\left(t\right)\right)=\frac{c}{\sigma\left(t\right)^{\alpha+1}}$

or, equivalently,

$\dot{z}\left(t\right)+\nabla
f\left(z\left(t\right)\right)=\frac{c}{t^{\frac{\alpha+1}{2}}}.$

This is nothing else than the perturbed continuous steepest descent system
with perturbation function
$g\colon\left[t_{0},+\infty\right[\to{\mathcal{H}},g(t)=\frac{c}{t^{\frac{\alpha+1}{2}}},$
which obviously fulfills

$\int_{t_{0}}^{+\infty}\left\lVert g\left(t\right)\right\rVert
dt<+\infty\textrm{ and }\int_{t_{0}}^{+\infty}t\left\lVert
g\left(t\right)\right\rVert^{2}dt<+\infty,$

for every $\alpha>1$.

Furthermore,

$\int_{t_{0}}^{+\infty}t^{2}\left\lVert
g\left(t\right)\right\rVert^{2}dt=\int_{t_{0}}^{+\infty}\dfrac{\left\lVert
c\right\rVert^{2}}{t^{\alpha-1}}dt<+\infty,$

whenever $\alpha>2$. All statements excepting $\rm{(vi)}$ follow from Theorem
1.

Going back to the perturbed continuous steepest descent (6), we see that

$\left\lVert\dot{z}\left(t\right)\right\rVert\leq\left\lVert\nabla
f\left(z\left(t\right)\right)\right\rVert+\left\lVert
g\left(t\right)\right\rVert=o\left(\dfrac{1}{t}\right)+o\left(\dfrac{1}{t^{\frac{\alpha+1}{2}}}\right)=o\left(\dfrac{1}{t}\right)\textrm{
as }t\to+\infty.$

Taking $t=\tau\left(s\right)=\frac{s^{2}}{2(\alpha+1)}$, it yields

$\left\lVert\dot{z}\left(\tau\left(s\right)\right)\right\rVert=o\left(\dfrac{1}{s^{2}}\right)\textrm{
as }s\to+\infty,$

which gives $\rm{(vi)}$, since
$\dot{y}(s)=\dot{\tau}(s)\dot{z}(\tau(s))=\frac{s}{\alpha+1}\dot{z}(\tau(s))$.
∎

######  Remark 3.

As in in Theorem 2, we see that the convergence of trajectory can be
guaranteed for $\alpha>1$, which is less restrictive than for the Su-Boyd-
Candés system, the trajectory of which is known to convergence for $\alpha>3$.
This is another positive effect of the approach that combines time scaling and
averaging.

###  3.2 Combining implicit and explicit Hessian driven damping

As a starting dynamic we consider the regularized Newton dynamical system

$\begin{cases}\lambda\dot{z}(t)+\dot{v}(t)+v(t)=0\vspace{1mm}\\\ v(t)=\nabla
f(z(t))\end{cases}.$ (65)

It is a special case of the regularized Newton dynamic

$\lambda(t)\dot{z}(t)+\nabla^{2}f(z(t))\dot{z}(t)+\nabla f(z(t))=0.$ (66)

This system has been studied by Attouch and Svaiter [22], Attouch, Redont, and
Svaiter [21], Attouch, Marques Alves, and Svaiter [17] to solve monotone
inclusions (that is, with a general maximally monotone operator $A$ instead of
$\nabla f$). In this approach, the central question is the adjustment of the
Levenberg-Marquardt regularization parameter $\lambda(\cdot)$ in front of the
velocity term. Indeed, taking $\lim_{t\to+\infty}\lambda(t)=0$ allows to be
asymptotically close to the Newton method. Our situation concerns the simpler
case $\lambda(t)\equiv\lambda>0$ constant, which fits with the convergence
properties proved in these papers, and the fact that this dynamic is well-
posed. For precise statements concerning the asymptotic behavior of this
system see [22, Theorem 4.1, Remark 4.2] and [22, Theorem 3.9]. For the sake
of completeness, we provide below its convergence properties, that shows some
improvements compared to the results in [22]. The proof of Theorem 5 is
provided in the Appendix.

######  Theorem 5.

Suppose that $f\colon{\mathcal{H}}\to{\mathbb{R}}$ satisfies $(\mathcal{A})$.
Let $z:[t_{0},+\infty[\to{\mathcal{H}}$ be a solution trajectory of the
dynamical system (65). Then the following statements are true:

  1. $\rm{(i)}$

(integral estimate of the values)
$\int_{t_{0}}^{+\infty}\left(f\left(z\left(t\right)\right)-\inf_{{\mathcal{H}}}f\right)dt<+\infty;$

  2. $\rm{(ii)}$

(convergence of values towards minimal value)
$f\left(z\left(t\right)\right)-\inf_{{\mathcal{H}}}f=o\left(\frac{1}{t}\right)\textrm{
as }t\to+\infty;$

  3. $\rm{(iii)}$

(integral estimates of velocities and gradients)
$\int_{t_{0}}^{+\infty}t\left\lVert\dot{z}\left(t\right)\right\rVert^{2}dt<+\infty$
and
$\int_{t_{0}}^{+\infty}t\left\lVert\dot{v}\left(t\right)\right\rVert^{2}dt<+\infty,$
which lead to $\int_{t_{0}}^{+\infty}t\left\lVert
v\left(t\right)\right\rVert^{2}dt=\int_{t_{0}}^{+\infty}t\left\lVert\nabla
f\left(z\left(t\right)\right)\right\rVert^{2}dt<+\infty;$

  4. $\rm{(iv)}$

(convergence of velocities and gradients towards zero) $\left\lVert
v\left(t\right)\right\rVert=\left\lVert\nabla
f\left(z\left(t\right)\right)\right\rVert=o\left(\frac{1}{t}\right)\textrm{ as
}t\to+\infty,$ which lead to
$\left\lVert\dot{z}\left(t\right)\right\rVert=\left\lVert\dot{v}\left(t\right)\right\rVert=o\left(\frac{1}{t}\right)\textrm{
as }t\to+\infty;$

  5. $\rm{(v)}$

the solution trajectory $z(t)$ converges weakly as $t\to+\infty$, and its
limit belongs to $S=\operatorname{argmin}f$.

######  Remark 4.

In [22, Theorem 4.1], the authors show that both $\dot{z}\left(\cdot\right)$
and $\dot{v}\left(\cdot\right)$, and consequently $v\left(\cdot\right)$,
belong to $\mathbb{L}^{2}\left(\left[t_{0},+\infty\right[\right)$. Since
$t\mapsto\left\lVert v\left(t\right)\right\rVert$ is nonincreasing, in [22,
Theorem 3.9] it is shown that $\left\lVert
v\left(t\right)\right\rVert=o\left(\frac{1}{\sqrt{t}}\right)$ as
$t\to+\infty$. By improving some integral estimates for the velocity and the
gradient, we can provide a faster convergence rate, namely of
$o\left(\frac{1}{t}\right)$ as $t\to+\infty$.

Let us make the change of time variable $t=\tau(s)=\frac{1}{2}\gamma s^{2}$ in
the dynamic (65), where $\gamma$ is a positive constant to be adjusted later.
Set $y(s):=z(\tau(s))$, $w(s):=v(\tau(s))=\nabla f(y(s))$, and $s_{0}>0$ be
such that $t_{0}=\tau\left(s_{0}\right)$. On the one hand, by the derivation
chain rule, we have for every $s\geq s_{0}$

$\dot{y}(s)=\dot{\tau}(s)\dot{z}(\tau(s)),\quad\dot{w}(s)=\dot{\tau}(s)\dot{v}(\tau(s)).$
(67)

On the other hand, setting $t=\tau(s)$ in (65) gives

$\begin{cases}\lambda\dot{z}(\tau(s))+\dot{v}(\tau(s))+v(\tau(s))=0\vspace{1mm}\\\
v(\tau(s))=\nabla f(z(\tau(s))).\end{cases}$ (68)

According to (67), (68), and $\dot{\tau}(s)=\gamma s$, we obtain

$\begin{cases}\frac{\lambda}{cs}\dot{y}(s)+\frac{1}{\gamma
s}\dot{w}(s)+w(s)=0\vspace{1mm}\\\ w(s)=\nabla f(y(s))\end{cases}$ (69)

or, equivalently,

$\begin{cases}\lambda\dot{y}(s)+\dot{w}(s)+\gamma sw(s)=0\vspace{1mm}\\\
w(s)=\nabla f(y(s)).\end{cases}$ (70)

The convergence rate becomes

$f(y(s))-\inf_{{\mathcal{H}}}f=o\left(\frac{1}{s^{2}}\right)\textrm{ as
}s\to+\infty.$ (71)

So, we have accelerated the dynamic for the values, passing from the
convergence rate $1/t$ to $1/s^{2}$. Moreover, by proceeding as in Subsection
3.1, we can return from (70) to the dynamics (68).

Let us now come with the averaging process. Given $s_{0}>0$, we attach to
$y(\cdot)$ the new function $x:[s_{0},+\infty[\to{\mathcal{H}}$ defined by

$\dot{x}(s)+\dfrac{\delta}{s}(x(s)-y(s))=0,$ (72)

with $x(s_{0})=x_{0}$ given in ${\mathcal{H}}$, and where $\delta$ is a
positive coefficient to adjust. Equivalently

$y(s)=x(s)+\dfrac{s}{\delta}\dot{x}(s).$ (73)

Let us formulate (70) in terms of $x$ by eliminating $y$. We first obtain

$\begin{cases}\lambda\left(\dot{x}(s)+\frac{s}{\delta}\ddot{x}(s)+\frac{1}{\delta}\dot{x}(s)\right)+\dot{w}(s)+\gamma
sw(s)=0\vspace{1mm}\\\ w(s)=\nabla
f\left(x(s)+\frac{s}{\delta}\dot{x}(s)\right).\end{cases}$ (74)

After reduction we obtain

$\begin{cases}\ddot{x}(s)+\frac{\delta+1}{s}\dot{x}(s)+\frac{\delta}{\lambda
s}\dot{w}(s)+\frac{\delta\gamma}{\lambda}w(s)=0\vspace{1mm}\\\ w(s)=\nabla
f\left(x(s)+\frac{s}{\delta}\dot{x}(s)\right).\end{cases}$ (75)

Take $\delta=\alpha-1$, $\gamma=\frac{\lambda}{\alpha-1}$ in (75). We have
$\delta\gamma=\lambda$, which gives

$\begin{cases}\ddot{x}(s)+\frac{\alpha}{s}\dot{x}(s)+\frac{\alpha-1}{\lambda
s}\dot{w}(s)+w(s)=0\vspace{1mm}\\\ w(s)=\nabla
f\left(x(s)+\frac{s}{\alpha-1}\dot{x}(s)\right).\end{cases}$ (76)

According to the general properties of the averaging process

$y(s)=x(s)+\frac{s}{\alpha-1}\dot{x}(s),$ (77)

which has been already studied, see (33), we obtain the following theorem for
a dynamics which combines explicit and implicit Hessian driven damping in a
new way.

######  Theorem 6.

Suppose that $f\colon{\mathcal{H}}\to{\mathbb{R}}$ satisfies $(\mathcal{A})$.
Let $x:[s_{0},+\infty[\to{\mathcal{H}}$ be a solution trajectory of

$\begin{cases}\ddot{x}(s)+\dfrac{\alpha}{s}\dot{x}(s)+\dfrac{\alpha-1}{\lambda
s}\dot{w}(s)+w(s)=0\vspace{1mm}\\\ w(s)=\nabla
f\left(x(s)+\dfrac{s}{\alpha-1}\dot{x}(s)\right).\end{cases}$ (78)

Assume that $\alpha>1$. Then the following statements are true:

  1. $\rm{(i)}$

(integral estimate of the gradients) $\int_{s_{0}}^{+\infty}s^{3}\left\lVert
w\left(s\right)\right\rVert^{2}ds<+\infty;$

  2. $\rm{(ii)}$

(convergence of gradients towards zero) $\left\lVert
w\left(s\right)\right\rVert=o\left(\frac{1}{s^{2}}\right)\textrm{ as
}s\to+\infty;$

  3. $\rm{(iii)}$

(convergence of velocities towards zero)
$\left\lVert\dot{x}\left(s\right)\right\rVert=o\left(\frac{1}{s}\right)\textrm{
as }s\to+\infty;$

  4. $\rm{(iv)}$

the solution trajectory $x(s)$ converges weakly as $s\to+\infty$, and its
limit belongs to $S=\operatorname{argmin}f$.

If $\alpha>3$, then

  5. $\rm{(v)}$

(convergence of values towards minimal value)
$f(x(s))-\inf_{{\mathcal{H}}}f=o\left(\frac{1}{s^{2}}\right)\textrm{ as
}s\to+\infty.$

###### Proof.

Let $x(\cdot)$ be a solution trajectory of (78) which satisfies the Cauchy
data $x(s_{0})=x_{0},\dot{x}(s_{0})=x_{1}$, and $w\left(s_{0}\right):=\nabla
f\left(x_{0}+\frac{s_{0}}{\alpha-1}x_{1}\right)$. In the same way as in the
proof of Theorem 2, we first show that such a solution is reached by
considering first the solution $y(\cdot)$ of the system

$\begin{cases}\lambda\dot{y}(s)+\dot{w}(s)+\frac{\lambda
s}{\alpha-1}w(s)=0\vspace{1mm}\\\ w(s)=\nabla f(y(s))\\\
y(s_{0})=x_{0}+\frac{s_{0}}{\alpha-1}x_{1},\end{cases}$ (79)

and then

$\begin{cases}\dot{x}(s)+\frac{\alpha-1}{s}(x(s)-y(s))=0\vspace{2mm}\\\
x(t_{0})=x_{0}.\end{cases}$ (80)

Indeed, (80) gives $\dot{x}(s_{0})=\frac{\alpha-1}{s_{0}}(y(s_{0})-x(s_{0}))$,
which, by the second equation of (79), equals to $x_{1}$. We have already seen
that $x$ can be seen as an averaging process (80) of $y$ as follows

$x(s)=\int_{s_{0}}^{s}y(u)\,d\mu_{s}(u)+\xi(s),$ (81)

where $\mu_{s}$ is the measure on $[s_{0},s]$ defined by

$\mu_{s}=\frac{s_{0}^{\alpha-1}}{s^{\alpha-1}}\delta_{s_{0}}+(\alpha-1)\frac{u^{\alpha-2}}{s^{\alpha-1}}du,$

where $\delta_{s_{0}}$ is the Dirac measure at $s_{0}$ and

$\xi(s):=-\frac{{s_{0}}^{\alpha}}{(\alpha-1)s^{\alpha-1}}x_{1}.$

The statements $\rm{(i)}$ and $\rm{(ii)}$ follow from Theorem 5 after time
rescaling and integration by substitution. In order to show $\rm{(iv)}$, we
need to pass from the convergence of $y$ to that of $x$ by using the
interpretation of $x$ as an average of $y$ plus a negligible term. Moreover,
we know that $y$ converges weakly to an element in $S$ thanks to Theorem 5.
The convergence of $x$ follows from similar arguments as in Theorem 2.

Finally, since the averaging process is the same as in Theorem 2, the
convergence rate of $1/s^{2}$ for the values $\rm{(v)}$ follows by the same
arguments. ∎

###  3.3 General Hessian damping coefficient: extension to bilevel convex
optimization

Given $\beta_{0}$ a positive damping coefficient, consider the more general
form of the dynamic

$\ddot{x}(s)+\frac{\alpha}{s}\dot{x}(s)+\nabla
f\left(x(s)+\beta_{0}\frac{s}{\alpha-1}\dot{x}(s)\right)=0.$ (82)

Our study in the previous subsections concerned the case $\beta_{0}=1$. This
section shows that the time rescaling and averaging technique links the
dynamical system (82) with a bilevel convex optimization problem and thus
emphasizes the versatility of the approach proposed in this paper.

Let us introduce

$y(s):=x(s)+\beta_{0}\frac{s}{\alpha-1}\dot{x}(s),$ (83)

so that (82) is written equivalently

$\ddot{x}(s)+\frac{\alpha}{s}\dot{x}(s)+\nabla f\left(y(s)\right)=0.$ (84)

Let us reformulate (84) as a differential equation with $y(s)$ as the state
variable. According to (83) we have

$\dot{x}(s)=\dfrac{\alpha-1}{\beta_{0}s}(y(s)-x(s)),$ (85)

which after derivation gives

$\ddot{x}(s)=\dfrac{\alpha-1}{\beta_{0}s}(\dot{y}(s)-\dot{x}(s))-\dfrac{\alpha-1}{\beta_{0}s^{2}}(y(s)-x(s)).$
(86)

Combining (84) and (86) we obtain

$\dfrac{\alpha-1}{\beta_{0}s}(\dot{y}(s)-\dot{x}(s))-\dfrac{\alpha-1}{\beta_{0}s^{2}}(y(s)-x(s))+\frac{\alpha}{s}\dot{x}(s)+\nabla
f\left(y(s)\right)=0.$ (87)

By replacing $\dot{x}(s)$ by its formulation given in (85) we obtain

$\dfrac{\alpha-1}{\beta_{0}s}\dot{y}(s)+\left(\frac{\alpha}{s}-\dfrac{\alpha-1}{\beta_{0}s}\right)\dfrac{\alpha-1}{\beta_{0}s}(y(s)-x(s))-\frac{\alpha-1}{\beta_{0}s^{2}}(y(s)-x(s))+\nabla
f\left(y(s)\right)=0.$

After reduction we get

$\dfrac{\alpha-1}{\beta_{0}s}\dot{y}(s)+\frac{(\alpha-1)^{2}(\beta_{0}-1)}{\beta_{0}^{2}s^{2}}(y(s)-x(s))+\nabla
f\left(y(s)\right)=0.$ (88)

Equivalently

$\dot{y}(s)+\dfrac{\beta_{0}s}{\alpha-1}\nabla
f\left(y(s)\right)+\frac{(\alpha-1)(\beta_{0}-1)}{\beta_{0}s}(y(s)-x(s))=0.$
(89)

Putting together (85) and (89) we obtain the system

$\begin{cases}\dot{y}(s)+\dfrac{\beta_{0}s}{\alpha-1}\nabla
f\left(y(s)\right)+\dfrac{(\alpha-1)(\beta_{0}-1)}{\beta_{0}s}(y(s)-x(s))=0\vspace{2mm}\\\
\dot{x}(s)+\dfrac{\alpha-1}{\beta_{0}s}(x(s)-y(s))=0.\end{cases}$ (90)

Let us now consider time scaling of the above system as in (24). Set

$s=\sqrt{2(\alpha-1)t}\,\mbox{ and
}\,y(\sqrt{2(\alpha-1)t})=Y(t),\,x(\sqrt{2(\alpha-1)t})=X(t).$

A similar calculation as in Subsection 2.2 gives

$\begin{cases}\dot{Y}(t)+\beta_{0}\nabla
f\left(Y(t)\right)+\dfrac{(\alpha-1)(\beta_{0}-1)}{2\beta_{0}t}(Y(t)-X(t))=0\vspace{2mm}\\\
\dot{X}(t)+\dfrac{\alpha-1}{2\beta_{0}t}(X(t)-Y(t))=0.\end{cases}$ (91)

This is a perturbation of the steepest descent dynamical system in the product
space ${\mathcal{H}}\times{\mathcal{H}}$. Precisely, setting
$Z(t)=(Y(t),X(t))\in{\mathcal{H}}\times{\mathcal{H}}$, we have

$\dot{Z}(t)+\beta_{0}\nabla\Psi\left(Z(t)\right)+\frac{(\alpha-1)}{2\beta_{0}t}A(Z(t))=0,$
(92)

where $\Psi(Z)=f(Y)$ and
$A:{\mathcal{H}}\times{\mathcal{H}}\to{\mathcal{H}}\times{\mathcal{H}}$ is the
linear operator whose matrix is given by

$A=$$\begin{pmatrix}\beta_{0}-1&-(\beta_{0}-1)\\\ -1&+1\end{pmatrix}$

The case $\beta_{0}=2$ is of particular interest since then $A$ is a symmetric
operator which is positive semidefinite. The study of this system then follows
from classical results concerning gradient dynamical systems with multiscale
aspects, see for example the work of Attouch and Czarnecki [13].

The dynamical system (92) for $\beta_{0}=2$ fits in the dynamics

$\dot{Z}(t)+\beta_{0}\nabla\Psi\left(Z(t)\right)+\varepsilon\left(t\right)\nabla\Phi\left(Z(t)\right)=0,$
(93)

with $\varepsilon\left(t\right):=\frac{(\alpha-1)}{2\beta_{0}t}$ and
$\Phi\left(\cdot\right)=\frac{1}{2}\left\lVert\cdot\right\rVert_{A}^{2}$,
where $\left\lVert\cdot\right\rVert_{A}$ is the seminorm induced by the
symmetric and positive semidefinite operator $A$. The differential equation
(93) can be seen as a continuous time approach of the bilevel optimization
problem

$\min_{{\mathcal{H}}\times{\mathcal{H}}}\left\\{\Phi\left(Z\right)\ |\ Z\in
D:=\operatorname{argmin}_{{\mathcal{H}}\times{\mathcal{H}}}\Psi\right\\}.$
(94)

Let $Z_{*}$ be a solution of (94), meaning that
$\Phi\left(Z_{*}\right)=\inf_{D}\Phi$ and
$\Psi\left(Z_{*}\right)=\inf_{{\mathcal{H}}\times{\mathcal{H}}}\Psi$. Define
for $t\geq t_{0}$

$\Psi_{\Phi}\left(t\right):=\beta_{0}\left(\Psi\left(Z(t)\right)-\inf\nolimits_{{\mathcal{H}}\times{\mathcal{H}}}\Psi\right)+\varepsilon\left(t\right)\left(\Phi\left(Z(t)\right)-\inf\nolimits_{D}\Phi\right)\geq
0.$

Indeed the above quantity is nonnegative because we are in the particular
simple case where $\Phi(Y,X)=\frac{1}{2}\|Y-X\|^{2}$ is nonnegative,
$D=\operatorname{argmin}_{{\mathcal{H}}}f\times{\mathcal{H}}$ and hence
$\inf_{D}\Phi=0$. Let us compute

$\displaystyle\dfrac{d}{dt}\left(\dfrac{1}{2}\left\lVert
Z\left(t\right)-Z_{*}\right\rVert^{2}\right)$ $\displaystyle=\left\langle
Z\left(t\right)-Z_{*},\dot{Z}\left(t\right)\right\rangle=-\beta_{0}\left\langle
Z\left(t\right)-Z_{*},\nabla\Psi\left(Z(t)\right)\right\rangle-\varepsilon\left(t\right)\left\langle
Z\left(t\right)-Z_{*},\nabla\Phi\left(Z(t)\right)\right\rangle$
$\displaystyle\leq-\beta_{0}\left(\Psi\left(Z(t)\right)-\inf\nolimits_{{\mathcal{H}}\times{\mathcal{H}}}\Psi\right)-\varepsilon\left(t\right)\left(\Phi\left(Z(t)\right)-\inf\nolimits_{D}\Phi\right)=-\Psi_{\Phi}\left(t\right).$

This shows that $\lim_{t\to+\infty}\left\lVert
Z\left(t\right)-Z_{*}\right\rVert\in{\mathbb{R}}$ exists and that

$\int_{t_{0}}^{+\infty}\Psi_{\Phi}\left(t\right)dt<+\infty.$

This yields $\liminf_{t\rightarrow+\infty}t\Psi_{\Phi}\left(t\right)=0$. On
the other hand, we have

$\displaystyle\dfrac{d}{dt}\Psi_{\Phi}\left(t\right)$
$\displaystyle=\beta_{0}\left\langle\nabla\Psi\left(Z\left(t\right)\right),\dot{Z}\left(t\right)\right\rangle+\varepsilon\left(t\right)\left\langle\nabla\Phi\left(Z\left(t\right)\right),\dot{Z}\left(t\right)\right\rangle+\dot{\varepsilon}\left(t\right)\left(\Phi\left(Z(t)\right)-\inf_{D}\Phi\right)\leq-\left\lVert\dot{Z}\left(t\right)\right\rVert^{2}.$

This means that $\Psi_{\Phi}$ is decreasing and furthermore

$\dfrac{d}{dt}\left(t\Psi_{\Phi}\left(t\right)\right)=\Psi_{\Phi}\left(t\right)+t\dfrac{d}{dt}\Psi_{\Phi}\left(t\right)\leq\Psi_{\Phi}\left(t\right)-t\left\lVert\dot{Z}\left(t\right)\right\rVert^{2}.$

Since $\Psi_{\Phi}\in\mathbb{L}^{1}\left(\left[t_{0},+\infty\right[\right)$,
we conclude that
$t\|\dot{Z}\left(t\right)\|^{2}\in\mathbb{L}^{1}\left(\left[t_{0},+\infty\right[\right)$
and furthermore $\lim_{t\to+\infty}t\Psi_{\Phi}\left(t\right)=0$.
Consequently,

$\lim_{t\to+\infty}t\left(\Psi\left(Z(t)\right)-\inf\nolimits_{{\mathcal{H}}\times{\mathcal{H}}}\Psi\right)=0\textrm{
and
}\lim_{t\to+\infty}\left(\Phi\left(Z(t)\right)-\inf\nolimits_{D}\Phi\right)=0.$

Since $\Psi$ and $\Phi$ are convex and lower semicontinuous, the second
condition of Opial’s lemma is fulfilled. Thus $Z(t)$ converges weakly to a
solution of (94) as $t\rightarrow+\infty$.

Moreover, according to the definition of $\Phi$ and $A$, it holds

$\Phi\left(Z(t)\right)=\dfrac{1}{2}\left\langle
Z(t),A\left(Z\left(t\right)\right)\right\rangle=\dfrac{1}{2}\left\lVert
X(t)-Y(t)\right\rVert^{2}=\dfrac{2\beta_{0}^{2}}{\left(\alpha-1\right)^{2}}t^{2}\left\lVert\dot{X}(t)\right\rVert^{2}\to
0\ \mbox{as}\ t\rightarrow+\infty.$

According to the definitions of $\Psi$ and $\Phi$ we conclude that there
exists $x_{*}\in\operatorname{argmin}_{{\mathcal{H}}}f$ such that
$(Y(t),X(t))$ converges weakly to $(x_{*},x_{*})$ as $t\rightarrow+\infty$,

$f(Y(t))-\inf\nolimits_{{\mathcal{H}}}f=o\left(\frac{1}{t}\right)\ \mbox{and}\
\lim_{t\rightarrow+\infty}\|X(t)-Y(t)\|=\lim_{t\rightarrow+\infty}t\|\dot{X}(t)\|=0.$

This means that $x(s)$ converges weakly to $x_{*}$ as $s\rightarrow+\infty$,

$f\left(x(s)+\frac{2s}{\alpha-1}\dot{x}(s)\right)-\inf\nolimits_{{\mathcal{H}}}f=o\left(\frac{1}{s^{2}}\right)\
\mbox{and}\ \lim_{s\rightarrow+\infty}s\|\dot{x}(s)\|=0.$

In the following theorem we collect the convergence properties of the
trajectory of the dynamical system (82) in case $\beta_{0}=2$.

######  Theorem 7.

Suppose that $f\colon{\mathcal{H}}\to{\mathbb{R}}$ satisfies $(\mathcal{A})$.
Let $x:[s_{0},+\infty[\to{\mathcal{H}}$ be a solution trajectory of

$\ddot{x}(s)+\frac{\alpha}{s}\dot{x}(s)+\nabla
f\left(x(s)+\frac{2s}{\alpha-1}\dot{x}(s)\right)=0.$

Assume that $\alpha>1$. Then the following statements are true:

  1. $\rm{(i)}$

(convergence of values towards minimal value)
$f\left(x(s)+\frac{2s}{\alpha-1}\dot{x}(s)\right)-\inf_{{\mathcal{H}}}f=o\left(\frac{1}{s^{2}}\right)\textrm{
as }s\to+\infty;$

  2. $\rm{(ii)}$

(convergence of velocities towards zero)
$\left\lVert\dot{x}\left(s\right)\right\rVert=o\left(\frac{1}{s}\right)\textrm{
as }s\to+\infty;$

  3. $\rm{(iii)}$

the solution trajectory $x(s)$ converges weakly as $s\to+\infty$, and its
limit belongs to $S=\operatorname{argmin}f$.

##  4 Nonsmooth case

In this section, we show that the approach proposed in this paper extends to
the case when $f:{\mathcal{H}}\to{\mathbb{R}}\cup\\{+\infty\\}$ is assumed to
be a (possibly nonsmooth) proper, convex and lower semicontinuous function.

###  4.1 The continuous dynamics

As a basic property of the dynamical system (31), the couple of variables
$(x,y)$ defined in Subsection 2.3 satisfies the following differential system,
which involves only first-order derivatives in time and space

$\begin{cases}\dot{y}(s)+\frac{s}{\alpha-1}\nabla f(y(s))&=0\vspace{2mm}\\\
\dot{x}(s)+\frac{\alpha-1}{s}(x(s)-y(s))&=0.\end{cases}$ (95)

This naturally suggests the extension of the above results to the nonsmooth
case (replace the gradient of $f$ by its subdifferential). We thus get the
differential inclusion system

$\begin{cases}\dot{y}(s)+\frac{s}{\alpha-1}\partial f(y(s))&\ni
0\vspace{2mm}\\\ \dot{x}(s)+\frac{\alpha-1}{s}(x(s)-y(s))&=0.\end{cases}$ (96)

Solving this system gives generalized solutions to the second-order
differential inclusion

$\ddot{x}(s)+\frac{\alpha}{s}\dot{x}(s)+\partial
f\left(x(s)+\frac{s}{\alpha-1}\dot{x}(s)\right)\ni 0$ (97)

whose direct study raises several difficulties, recalling that
$x(s_{0})=x_{0}$ and $\dot{x}(s_{0})=x_{1}$. To extend the results of the
previous section to this nonsmooth case, we need to avoid the arguments using
the Lipschitz continuity of $\nabla f$. So, we are led to consider the Cauchy
problem for (97) with initial data $x_{0}\in\operatorname{dom}f$ and
$x_{1}=0$, that is with initial velocity equal to zero. So doing we have
$y({s_{0}})=x({s_{0}})=x_{0}$, which allows to interpret $x$ as an average of
$y$ without correcting term ($\xi=0$ with the notations of Subsection 2.6).

The existence and uniqueness of a strong solution to the associated Cauchy
problem relies on the equivalent formulation of (96) as a perturbation of the
generalized steepest descent dynamical system in the product space
${\mathcal{H}}\times{\mathcal{H}}$. Precisely, define
$F:{\mathcal{H}}\times{\mathcal{H}}\to{\mathbb{R}}\cup\\{+\infty\\}$, for any
$Z=(y,x)\in{\mathcal{H}}\times{\mathcal{H}}$ by

$F(Z)=f(y),$

and let
$G:{\mathcal{H}}\times{\mathcal{H}}\to{\mathcal{H}}\times{\mathcal{H}}$ be the
operator defined by

$G(Z)=(0,x-y).$ (98)

Then (96) is written equivalently as

$\dot{Z}(s)+\frac{s}{\alpha-1}\partial F(Z(s))+\frac{\alpha-1}{s}G(Z(s))\ni
0.$ (99)

The initial condition becomes $Z(t_{0})=(x_{0},x_{0})$ which belongs to
$\operatorname{dom}F=\operatorname{dom}f\times{\mathcal{H}}$. According to the
classical results concerning the Lipschitz perturbation of evolution equations
governed by subdifferentials of convex functions, see [29, Proposition 3.12],
we obtain the existence and uniqueness of a global strong solution of the
Cauchy problem associated with (96). As a major advantage of the time scaling
and averaging techniques, the arguments used in the previous section still
work in this more general nonsmooth situation. The rules of differential
calculus are still valid for strong solutions, see [30, chapter VIII.2], and
Jensen’s inequality is still valid for a nonsmooth function $f$ (see e.g. [25,
Proposition 9.24]). Indeed Jensen’s inequality is classical for a smooth
convex function $f$. Its extension to the nonsmooth convex case can be
obtained by first writing it for the Moreau-Yosida regularization
$f_{\lambda}$ of $f$, then passing to the limit when $\lambda\downarrow 0$.
According to the monotone convergence of $f_{\lambda}$ towards $f$, we can
pass to the limit in the integral term thanks to the Beppo Levi monotone
convergence theorem. Therefore we obtain the following theorem.

######  Theorem 8.

Let $f:{\mathcal{H}}\to{\mathbb{R}}\cup\\{+\infty\\}$ be a proper, lower
semicontinuous, and convex function such that
$S=\operatorname{argmin}f\neq\emptyset$. Let
$x:[s_{0},+\infty[\to{\mathcal{H}}$ be a solution trajectory of

$\ddot{x}(s)+\frac{\alpha}{s}\dot{x}(s)+\partial
f\left(x(s)+\frac{s}{\alpha-1}\dot{x}(s)\right)\ni 0,$ (100)

which satisfies the initial conditions $x(s_{0})\in\operatorname{dom}f$ and
$\dot{x}(s_{0})=0$. Assume that $\alpha>1$. Then

  1. $\rm{(i)}$

the solution trajectory $x(s)$ converges weakly as $s\to+\infty$, and its
limit belongs to $S=\operatorname{argmin}f$.

If $\alpha>3$, then

  2. $\rm{(ii)}$

(convergence of values towards minimal value)
$f\left(y\left(s\right)\right)-\inf_{{\mathcal{H}}}f=o\left(\frac{1}{s^{2}}\right)\textrm{
as }s\to+\infty.$

######  Remark 5.

As a consequence of $ii)$, we have that $x(s)$ remains in the domain of $f$
for all $s\geq t_{0}$. This viability property strongly depends on the fact
that the initial position belongs to the domain of $f$, and that the initial
velocity has been taken equal to zero.

######  Remark 6.

The above theorem is valid in an infinite dimensional setting, which makes it
applicable to nonlinear PDEs. According to the classical theory for the
steepest descent dynamic in the nonsmooth convex case, we have that at each
$s>s_{0}$ the right derivative of $y(s)$ exists and satisfies

$-\left(\dfrac{dy}{ds}\right)^{+}(s)=\frac{s}{\alpha-1}\left(\partial
f(y(s))\right)^{0}$

where $\left(\partial f(y(s))\right)^{0}$ is the element of minimum norm of
$\partial f(y(s))$. Thus, $y$ may exhibit shocks. By contrast, $x$, which is
an average of $y$, has a continuous derivative, hence does not exhibit shocks.
Still $x$ is not twice differentiable.

###  4.2 A proximal type algorithm for nonsmooth minimization

Recall the second-order differential inclusion (97) associated with (1) in
Section 4

$\ddot{x}(s)+\frac{\alpha}{s}\dot{x}(s)+\partial
f\left(x(s)+\frac{s}{\alpha-1}\dot{x}(s)\right)\ni 0,$ (101)

or equivalently formulated as a first order system (see (96))

$\begin{cases}\dot{y}(s)+\frac{s}{\alpha-1}\partial f(y(s))&\ni
0\vspace{2mm}\\\ \dot{x}(s)+\frac{\alpha-1}{s}(x(s)-y(s))&=0.\end{cases}$
(102)

We consider the following implicit discretization in time of (102), written
for every $k\geq 0$ as

$\begin{cases}y_{k+1}-y_{k}+\frac{s_{k+1}}{\alpha-1}\partial
f\left(y_{k+1}\right)&\ni 0\vspace{2mm}\\\
x_{k+1}-x_{k}+\frac{\alpha-1}{s_{k+1}}\left(x_{k}-y_{k+1}\right)&=0.\end{cases}$
(103)

This gives rise to the following numerical algorithm

$(\forall k\geq
0)\quad\begin{cases}y_{k+1}&:=\operatorname{prox}_{\frac{s_{k+1}}{\alpha-1}f}\left(y_{k}\right)\vspace{1mm}\\\
x_{k+1}&:=\left(1-\frac{\alpha-1}{s_{k+1}}\right)x_{k}+\frac{\alpha-1}{s_{k+1}}y_{k+1},\end{cases}$
(104)

where $y_{0},x_{0}\in{\mathcal{H}}$ are arbitrary initial points. This
algorithm has some analogy with the relaxed inertial proximal algorithm for
maximally monotone operators in [8].

For the step size sequence $\left(s_{k}\right)_{k\geq 0}$ we impose the
following recurrence condition

$s_{0}:=0\qquad\textrm{ and }\qquad
s_{k+1}^{2}-\left(\alpha-1\right)s_{k+1}=s_{k}^{2}\quad\forall k\geq 0,$ (105)

which relates to the Nesterov step size rule. Indeed, by denoting
$t_{k}:=\frac{s_{k}}{\alpha-1}$, we have for every $k\geq 0$

$s_{k+1}:=\dfrac{\alpha-1+\sqrt{\left(\alpha-1\right)^{2}+4s_{k}^{2}}}{2}\
\mbox{or, equivalently,}\ t_{k+1}:=\dfrac{1+\sqrt{1+4t_{k}^{2}}}{2},$

which is nothing but the classic step size rule of Nesterov’s accelerated
gradient method [38, 37, 24].

We will nevertheless continue to work with the sequence
$\left(s_{k}\right)_{k\geq 0}$ in order to emphasize that all the convergence
statements provided in this section are valid for $\alpha>1$, contrary to the
stronger condition $\alpha>3$ for the low resolution case (see Remark 1). We
have that $s_{k}\sim k$, precisely,
$s_{k}\geq\left(k+1\right)\left(\alpha-1\right)/2$ for every $k\geq 0$ (cf.
[24, Lemma 4.3]). Furthermore, by a telescoping sum argument, we have from
(105)

$s_{k+1}^{2}-\left(\alpha-1\right)\sum_{i=0}^{k}s_{i+1}=s_{0}^{2}.$

Since $s_{0}=0$, we can conclude that for every $k\geq 0$

$s_{k}^{2}=\left(\alpha-1\right)\sum_{i=0}^{k}s_{i}.$ (106)

Let us also notice that (104) can be written only in terms of the sequence
$\left(x_{k}\right)_{k\geq 0}$

$x_{k+1}-x_{k}-\dfrac{s_{k}-\left(\alpha-1\right)}{s_{k+1}}\left(x_{k}-x_{k-1}\right)+\partial
f\left(x_{k}+\dfrac{s_{k+1}}{\alpha-1}\left(x_{k+1}-x_{k}\right)\right)\ni
0\quad\forall k\geq 1,$

which can be seen as a direct discretization of (101).

In the following we first analyze the convergence properties of the sequence
$\left(y_{k}\right)_{k\geq 0}$ generated by (104). Then, we transfer these to
the sequence $\left(x_{k}\right)_{k\geq 0}$. One can easily observe the
similarity between this approach and the continuous time one, where we
transferred the converge properties of the trajectory $y(\cdot)$ generated by
the continuous steepest descent system after time scaling to the averaged
trajectory $x(\cdot)$.

######  Theorem 9.

Let $\left(y_{k}\right)_{k\geq 0}$ be the sequence generated by (104). The
following statements are true:

  1. $\rm{(i)}$

(summability of function values) $\sum_{k\geq
0}s_{k}\left(f\left(y_{k}\right)-\inf_{{\mathcal{H}}}f\right)<+\infty;$

  2. $\rm{(ii)}$

(summability of subgradients) there exists a sequence
$\left(\eta_{k}\right)_{k\geq 0}\subseteq{\mathcal{H}}$ such that
$\eta_{k}\in\partial f\left(y_{k}\right)$ for every $k\geq 0$ and $\sum_{k\geq
0}s_{k}^{2}\left\lVert\eta_{k}\right\rVert^{2}$ $<+\infty.$

In particular, if $f$ is differentiable, then $\left\lVert\nabla
f\left(y_{k}\right)\right\rVert={o\left(\frac{1}{\sqrt{\sum_{i=0}^{k}s_{i}^{2}}}\right)=o\left(\frac{1}{k\sqrt{k}}\right)}\textrm{
as }k\to+\infty;$

  3. $\rm{(iii)}$

(convergence of values towards minimal value)
$f\left(y_{k}\right)-\inf_{{\mathcal{H}}}f=\mathcal{O}\left(\frac{1}{\sum_{i=0}^{k}s_{i}}\right)=o\left(\frac{1}{s_{k}^{2}}\right)=o\left(\frac{1}{\left(k+1\right)^{2}}\right)$
as $k\to+\infty;$

  4. $\rm{(iv)}$

the sequence of iterates $\left(y_{k}\right)_{k\geq 0}$ converges weakly as
$k\to+\infty$, and its limit belongs to
$S=\operatorname{argmin}_{{\mathcal{H}}}f$.

###### Proof.

Let $k\geq 0$ be fixed. Take $z_{*}\in S=\operatorname{argmin}f$. According to
(104) there exists $\eta_{k+1}\in\partial f\left(y_{k+1}\right)$ such that
$y_{k+1}-y_{k}+\frac{s_{k+1}}{\alpha-1}\eta_{k+1}=0$. By convexity of $f$ we
deduce that

$\displaystyle\dfrac{1}{2}\left\lVert y_{k+1}-z_{*}\right\rVert^{2}$
$\displaystyle=\dfrac{1}{2}\left\lVert
y_{k}-z_{*}\right\rVert^{2}+\left\langle
y_{k+1}-z_{*},y_{k+1}-y_{k}\right\rangle-\dfrac{1}{2}\left\lVert
y_{k+1}-y_{k}\right\rVert^{2}$ $\displaystyle=\dfrac{1}{2}\left\lVert
y_{k}-z_{*}\right\rVert^{2}-\dfrac{s_{k+1}}{\alpha-1}\left\langle
y_{k+1}-z_{*},\eta_{k+1}\right\rangle-\dfrac{1}{2}\dfrac{s_{k+1}^{2}}{\left(\alpha-1\right)^{2}}\left\lVert\eta_{k+1}\right\rVert^{2}$
$\displaystyle\leq\dfrac{1}{2}\left\lVert
y_{k}-z_{*}\right\rVert^{2}-\dfrac{s_{k+1}}{\alpha-1}\left(f\left(y_{k+1}\right)-\inf_{{\mathcal{H}}}f\right)-\dfrac{1}{2}\dfrac{s_{k+1}^{2}}{\left(\alpha-1\right)^{2}}\left\lVert\eta_{k+1}\right\rVert^{2}.$
(107)

The statements $i)$ and $ii)$ follow from [23, Lemma 5.31]. In addition, the
limit $\lim_{k\to+\infty}\left\lVert y_{k}-z_{*}\right\rVert\in{\mathbb{R}}$
exists, which means that the first condition of the discrete Opial’s lemma is
fulfilled.

The convergence rate in $ii)$ follows from the fact that sequence
$\left(\eta_{k}\right)_{k\geq 0}$ is nonincreasing. Indeed, we have from the
monotonicity of $\partial f$

$\displaystyle\left\lVert\eta_{k}\right\rVert^{2}-\left\lVert\eta_{k+1}\right\rVert^{2}$
$\displaystyle=-2\left\langle\eta_{k+1},\eta_{k+1}-\eta_{k}\right\rangle+\left\lVert\eta_{k+1}-\eta_{k}\right\rVert^{2}=\dfrac{\alpha-1}{s_{k+1}}\left\langle
y_{k+1}-y_{k},\eta_{k+1}-\eta_{k}\right\rangle+\left\lVert\eta_{k+1}-\eta_{k}\right\rVert^{2}\geq
0,$

and the rate follows from [7, Lemma 22]. Similarly, we notice that  the
sequence $\left(f\left(y_{k}\right)-\inf_{{\mathcal{H}}}f\right)_{k\geq 0}$ is
nonincreasing as well. Precisely, for every $k\geq 0$ we have

$\left(f\left(y_{k}\right)-\inf_{{\mathcal{H}}}f\right)-\left(f\left(y_{k+1}\right)-\inf_{{\mathcal{H}}}f\right)\geq\langle\eta_{k+1},y_{k}-y_{k+1}\rangle=\dfrac{\alpha-1}{s_{k+1}}\left\lVert
y_{k+1}-y_{k}\right\rVert^{2}\geq 0.$

According to [7, Lemma 22] we get

$f\left(y_{k}\right)-\inf_{{\mathcal{H}}}f=o\left(\dfrac{1}{\sum_{i=0}^{k}s_{i}}\right),$

which proves $iii)$, thanks to (106). Finally, since
$\lim_{k\to+\infty}f\left(y_{k}\right)=\inf_{{\mathcal{H}}}f$ and $f$ is
convex and lower semicontinuous, the second condition of Opial’s lemma is also
fulfilled. This gives the weak convergence of the sequence
$\left(y_{k}\right)_{k\geq 0}$ to an element in $S=\operatorname{argmin}f$. ∎

Let us consider the convergence properties of $(x_{k})_{k\geq 0}$ which are
associated with the averaging process.

######  Theorem 10.

Let $\left(x_{k}\right)_{k\geq 0}$ be the sequence generated by (104). The
following statements are true:

  1. $\rm{(i)}$

(convergence of values)
$f\left(x_{k}\right)-\inf_{{\mathcal{H}}}f=\mathcal{O}\left(\frac{1}{\sum_{i=0}^{k}s_{i}}\right)=\mathcal{O}\left(\frac{1}{s_{k}^{2}}\right)=\mathcal{O}\left(\frac{1}{\left(k+1\right)^{2}}\right)$
as $k\to+\infty;$

  2. $\rm{(ii)}$

the sequence of iterates $\left(x_{k}\right)_{k\geq 0}$ converges weakly as
$k\to+\infty$, and its limit belongs to
$S=\operatorname{argmin}_{{\mathcal{H}}}f$.

###### Proof.

We begin by interpreting $\left(x_{k}\right)_{k\geq 0}$ as an average of
$\left(y_{k}\right)_{k\geq 0}$. Multiplying the second equation in (104) by
$s_{k+1}^{2}$ and using (105), we obtain for every $k\geq 0$

$s_{k+1}^{2}x_{k+1}=\left(s_{k+1}^{2}-\left(\alpha-1\right)s_{k+1}\right)x_{k}+\left(\alpha-1\right)s_{k+1}y_{k+1}=s_{k}^{2}x_{k}+\left(\alpha-1\right)s_{k+1}y_{k+1}.$

By a telescopic sum argument and using (106), we obtain from here the
following expression for each $k\geq 0$

$x_{k+1}=\dfrac{1}{s_{k+1}^{2}}\sum_{i=0}^{k+1}\left(\alpha-1\right)s_{i}y_{i}=\dfrac{1}{\sum_{i=0}^{k+1}s_{i}}\sum_{i=0}^{k+1}s_{i}y_{i}.$

Then, Jensen’s inequality gives for every $k\geq 0$

$\displaystyle f\left(x_{k+1}\right)-\inf_{{\mathcal{H}}}f$
$\displaystyle=\left(f-\inf_{{\mathcal{H}}}f\right)\left(\dfrac{1}{\sum_{i=0}^{k+1}s_{i}}\sum_{i=0}^{k+1}s_{i}y_{i}\right)$
$\displaystyle\leq\dfrac{1}{\sum_{i=0}^{k+1}s_{i}}\sum_{i=0}^{k+1}s_{i}\left(f\left(y_{i}\right)-\inf_{{\mathcal{H}}}f\right)\leq\dfrac{\alpha-1}{s_{k+1}^{2}}\sum_{i\geq
0}s_{i}\left(f\left(y_{i}\right)-\inf_{{\mathcal{H}}}f\right),$ (108)

where in the last equation we use (106). In Theorem 9 we have shown
$\sum_{i\geq
0}s_{i}\left(f\left(y_{i}\right)-\inf_{{\mathcal{H}}}f\right)<+\infty$, which
gives the announced convergence rates. The fact that
$\left(x_{k}\right)_{k\geq 0}$ converges weakly to an element in
$S=\operatorname{argmin}f$ as $k\to+\infty$ follows from the fact that
convergence entails ergodic convergence. ∎

##  5 Operator case

What underlies our study is the first-order in time evolution system taken as
a starting point and its convergence properties. In this regard, it is natural
to consider also the evolution equation governed by a cocoercive operator.
Indeed, gradients of convex functions and cocoercive operators are the two
basic examples of monotone operators ensuring the convergence of the
associated semi-groups of contractions. We will successively examine a general
cocoercive operator, then the additively structured case. For monotone
operators, the convergence rates are expressed in terms of velocities and
residuals.

###  5.1 General cocoercive case

Recall that a single-valued operator $M:{\mathcal{H}}\rightarrow{\mathcal{H}}$
is called $\rho$-cocoercive (with $\rho>0$) if

$\langle
M(x)-M(y),x-y\rangle\geq\rho\left\|{M(x)-M(y)}\right\|^{2}\quad\forall
x,y\in{\mathcal{H}}.$

We mention the following classical properties of cocoercive operators:

a) If $M$ is $\rho$-cocoercive, then it is monotone and
$\frac{1}{\rho}$-Lipschitz continuous, and hence maximally monotone.

b) If $f$ is a convex differentiable function whose gradient is $L$-Lipschitz
continuous, then the operator $\nabla f$ is $1/L$-cocoercive (Baillon-Haddad
theorem).

Let us come to our study. Given $M\colon{\mathcal{H}}\to{\mathcal{H}}$ a
$\rho$-cocoercive operator, consider the monotone equation

$M\left(x\right)=0,$ (109)

and the associated evolution equation

$\dot{z}\left(t\right)+M\left(z\left(t\right)\right)=0.$ (110)

We denote the solution set of (109) by $S$, which we assume to be nonempty. We
recall the results in [25, Theorems 11 and 16] which state that
$z\left(t\right)$ converges weakly to a point in $S$. In addition

$\int_{t_{0}}^{+\infty}\left\lVert\dot{z}\left(t\right)\right\rVert^{2}dt=\int_{t_{0}}^{+\infty}\left\lVert
M\left(z\left(t\right)\right)\right\rVert^{2}dt<+\infty\textrm{ and
}\left\lVert
M\left(z\left(t\right)\right)\right\rVert=o\left(\dfrac{1}{\sqrt{t}}\right)\textrm{
as }t\to+\infty.$ (111)

Further we develop an analysis similar to the one in Subsection 3.1 in the
case of a gradient operator. Set
$y\left(s\right):=z\left(\tau\left(s\right)\right)$, where
$\tau\colon\left[t_{0},+\infty\right[\to\mathbb{R}^{+}$ is a continuously
differentiable increasing function satisfying
$\lim_{s\to+\infty}\tau\left(s\right)=+\infty$. According to the derivation
chain rule, we have

$\dot{y}\left(s\right)=\dot{\tau}\left(s\right)\dot{z}\left(\tau\left(s\right)\right)$

which, by setting $t:=\tau\left(s\right)$ in (110), gives

$\dot{z}\left(\tau\left(s\right)\right)+M\left(z\left(\tau\left(s\right)\right)\right)=0.$

Combining the two relations above gives

$\dot{y}\left(s\right)+\dot{\tau}\left(s\right)M\left(y\left(s\right)\right)=0.$
(112)

Taking the derivative with respect to $s$ of the above equation gives

$\ddot{y}\left(s\right)+\ddot{\tau}\left(s\right)M\left(y\left(s\right)\right)+\dot{\tau}\left(s\right)\dfrac{d}{ds}\left(M\left(y\left(s\right)\right)\right)=0.$
(113)

Multiplying both sides of (112) by $\frac{\alpha}{s}$, then adding the result
to (113), we obtain

$\ddot{y}\left(s\right)+\dfrac{\alpha}{s}\dot{y}\left(s\right)+\dot{\tau}\left(s\right)\dfrac{d}{ds}\left(M\left(y\left(s\right)\right)\right)+\left(\ddot{\tau}\left(s\right)+\dfrac{\alpha}{s}\dot{\tau}\left(s\right)\right)M\left(y\left(s\right)\right)=0.$
(114)

As a subsequent result of (111) we have

$\left\lVert
M\left(y\left(s\right)\right)\right\rVert=o\left(\dfrac{1}{\sqrt{\tau\left(s\right)}}\right)\textrm{
as }s\to+\infty.$

Taking

$\tau\left(s\right)=\dfrac{s^{2}}{2\left(\alpha+1\right)},$

then (114) becomes

$\ddot{y}\left(s\right)+\dfrac{\alpha}{s}\dot{y}\left(s\right)+\dfrac{s}{\alpha+1}\dfrac{d}{ds}\left(M\left(y\left(s\right)\right)\right)+M\left(y\left(s\right)\right)=0.$
(115)

We obtain the rate

$\left\lVert
M\left(y\left(s\right)\right)\right\rVert=o\left(\dfrac{1}{s}\right)\textrm{
as }s\to+\infty.$

Moreover, it holds

$\int_{\tau\left(t_{0}\right)}^{+\infty}s\left\lVert
M\left(y\left(s\right)\right)\right\rVert^{2}ds<+\infty.$

Now let us do the reverse, and start from a solution trajectory $y(\cdot)$ of
(114) satisfying $y\left({s_{0}}\right):=y_{0}$ and
$\dot{y}\left({s_{0}}\right):=y_{1}$. Using similar arguments as in Theorem 4,
we multiply both sides of (115) by $s^{\alpha}>0$ and get

$\dfrac{d}{ds}\left(s^{\alpha}\dot{y}\left(s\right)+\dfrac{s^{\alpha+1}}{\alpha+1}M\left(y\left(s\right)\right)\right)=0.$

This leads to

$\dot{y}\left(s\right)+\dfrac{s}{\alpha+1}M\left(y\left(s\right)\right)=\dfrac{c_{0}}{s^{\alpha}},$
(116)

where $c_{0}\in{\mathcal{H}}$ is a constant that can be determined from the
Cauchy condition. Set $z\left(t\right):=y\left(\sigma\left(t\right)\right)$,
where

$\sigma\left(t\right)=\sqrt{2\left(\alpha+1\right)t}.$ (117)

After calculations similar to those made previously, we arrive at

$\dot{z}\left(t\right)+M\left(z\left(t\right)\right)=\dfrac{c}{t^{\frac{\alpha+1}{2}}},$

where $c\in{\mathcal{H}}$ is a constant. Our study therefore falls within the
properties of the perturbed system

$\dot{z}\left(t\right)+M\left(z\left(t\right)\right)=g(t),$ (118)

where, as $\alpha>1$, the external perturbation
$g\colon\left[t_{0},+\infty\right[\to{\mathcal{H}},g(t)=\frac{c}{t^{\frac{\alpha+1}{2}}}$,
is such that

$\int_{t_{0}}^{+\infty}\left\lVert g\left(t\right)\right\rVert
dt<+\infty\,\textrm{ and }\int_{t_{0}}^{+\infty}t\left\lVert
g\left(t\right)\right\rVert^{2}dt<+\infty.$ (119)

We have the following result.

######  Theorem 11.

Let $z\colon\left[t_{0},+\infty\right[\to{\mathcal{H}}$ be a solution
trajectory of

$\dot{z}\left(t\right)+M\left(z\left(t\right)\right)=g(t),$ (120)

where $g$ fulfils (119). Then the following statements are true:

  1. $\rm{(i)}$

(convergence rate of the operator norm) $\left\lVert
M\left(z\left(t\right)\right)\right\rVert=o\left(\frac{1}{\sqrt{t}}\right)\textrm{
as }t\to+\infty;$

  2. $\rm{(ii)}$

(integral estimate of the operator norm) $\int_{t_{0}}^{+\infty}\left\lVert
M\left(z\left(t\right)\right)\right\rVert^{2}dt<+\infty;$

  3. $\rm{(iii)}$

the solution trajectory $z(t)$ converges weakly as $t\to+\infty$, and its
limit belongs to $S=\operatorname{Zer}M$.

Combining the above theorem with the time scaling defined in (117) gives the
following result.

######  Theorem 12.

Let $M:{\mathcal{H}}\rightarrow{\mathcal{H}}$ be a cocoercive operator and
$y:[s_{0},+\infty[\to{\mathcal{H}}$ be a solution trajectory of

$\ddot{y}\left(s\right)+\dfrac{\alpha}{s}\dot{y}\left(s\right)+\dfrac{s}{\alpha+1}\dfrac{d}{ds}\left(M\left(y\left(s\right)\right)\right)+M\left(y\left(s\right)\right)=0,$
(121)

where $\alpha>1$. Then the following statements are true:

  1. $\rm{(i)}$

(convergence rate of the operator norm) $\left\lVert
M\left(y\left(s\right)\right)\right\rVert=o\left(\frac{1}{s}\right)\textrm{ as
}s\to+\infty;$

  2. $\rm{(ii)}$

(integral estimate of the gradients) $\int_{s_{0}}^{+\infty}s\left\lVert
M\left(y\left(s\right)\right)\right\rVert^{2}ds<+\infty;$

  3. $\rm{(iii)}$

the solution trajectory $y(s)$ converges weakly as $s\to+\infty$, and its
limit belongs to $S=\operatorname{Zer}M$.

######  Remark 7.

Theorem 12 is valid for an arbitrary cocoercive operator. By contrast, the
corresponding result without the Newton correction term requires that the
coefficient of the cocoercive operator asymptotically tends to infinity, see
Attouch and Peypouquet [18].

######  Remark 8.

Recently, in [27] the closely related dynamics

$\ddot{y}\left(s\right)+\dfrac{\alpha}{s}\dot{y}\left(s\right)+\dfrac{2s}{\alpha+1}\dfrac{d}{ds}\left(M\left(y\left(s\right)\right)\right)+M\left(y\left(s\right)\right)=0$
(122)

has been considered. Compared to (115), the difference lies in the coefficient
of $\frac{d}{ds}\left(M\left(y\left(s\right)\right)\right)$. According to [27,
Theorem 4 and Theorem 7], the solution trajectory of (122) verifies

$\int_{t_{0}}^{+\infty}s^{3}\left\lVert
M\left(y\left(s\right)\right)\right\rVert^{2}ds<+\infty,\,\mbox{ and
}\,\left\lVert
M\left(y\left(s\right)\right)\right\rVert=o\left(\dfrac{1}{s^{2}}\right)\textrm{
as }s\to+\infty.$

It would be interesting to know if we can achieve the same convergence rate
using time scaling and perturbation techniques.

###  5.2 Additively structured monotone inclusions

Our interest now is to solve the structured monotone inclusion problem

$0\in A(x)+B(x),$

where $A$ is maximally monotone, and $B$ is cocoercive with
$(A+B)^{-1}(0)\neq\emptyset$. A favorable situation occurs when one can
compute the resolvent operator of $A$

$J_{\mu A}=(I+\mu A)^{-1},\quad\mu>0.$

In this case, we can develop a strategy parallel to the one which consists in
replacing a maximally monotone operator by its Yosida approximation. Indeed,
given $\mu>0$, we have

$(A+B)(x)\ni 0\iff x-J_{\mu A}(x-\mu B(x))=0\iff M_{A,B,\mu}(x)=0,$ (123)

where $M_{A,B,\mu}:{\mathcal{H}}\to{\mathcal{H}}$ is the single-valued
operator defined by

$M_{A,B,\mu}(x)=\frac{1}{\mu}\left({x-J_{\mu A}(x-\mu B(x))}\right).$ (124)

The operator $M_{A,B,\mu}$ is closely tied to the well-known forward-backward
fixed point operator. Moreover, when $B=0$,
$M_{A,B,\mu}=\frac{1}{\mu}\left({I-J_{\mu A}}\right)$ which is nothing but the
Yosida regularization of $A$ with index $\mu$. As a remarkable property, for
the paremeter $\mu$ properly set, the operator $M_{A,B,\mu}$ is cocoercive.
This is made precise in the following result, whose proof relies on the
relation between cocoercivity and averaged property.

######  Proposition 1.

([34, Proposition 4.4]) Let $A:{\mathcal{H}}\to 2^{{\mathcal{H}}}$ be a
general maximally monotone operator, and $B:{\mathcal{H}}\to{\mathcal{H}}$ a
monotone operator which is $\lambda$-cocoercive. Assume that
$\mu\in]0,2\lambda[$. Then $M_{A,B,\mu}$ is $\rho$-cocoercive with

$\rho=\mu\left({1-\frac{\mu}{4\lambda}}\right).$

Therefore, we can develop a strategy parallel to that developed in [18], which
consists in replacing a maximally monotone operator by its Yosida
approximation. This leads to the inertial dynamics

$\ddot{y}\left(s\right)+\dfrac{\alpha}{s}\dot{y}\left(s\right)+\dfrac{s}{\alpha+1}\dfrac{d}{ds}\left(M_{A,B,\mu}\left(y\left(s\right)\right)\right)+M_{A,B,\mu}\left(y\left(s\right)\right)=0.$
(125)

It is immediate to apply Theorem 12 to (125). This open new perspectives for
forward-backward accelerated regularized Newton methods.

Let us illustrate our results by considering the following composite
optimization problem

$\min_{y\in{\mathbb{R}}^{n}}\left\\{f\left(y\right):=\dfrac{1}{2}\left\lVert
Ay-b\right\rVert^{2}+g\left(y\right)\right\\},$

where $A$ is a linear operator from ${\mathbb{R}}^{n}$ to ${\mathbb{R}}^{m}$,
$g\colon{\mathbb{R}}^{n}\to{\mathbb{R}}\cup\left\\{+\infty\right\\}$ is a
proper, convex and lower semicontinuous function which acts as a regularizer.
This class of problems covers many interesting situations arising in the
signal and image processing such as the LASSO problem. We are in the setting
of (124) with

$M_{A,B,\mu}\left(y\right):=\dfrac{1}{\mu}\left(y-\operatorname{prox}_{\mu
g}\left(y+\mu A^{*}\left(b-Ay\right)\right)\right),$

where $0<\mu<\frac{1}{\left\lVert A\right\rVert^{2}}$. Following [9], we can
also interpret our problem as minimizing the Moreau envelope of $f$ computed
for an ad hoc metric. Precisely, if $W:=\frac{1}{\mu}\mathbb{I}-A^{*}A$ and
$f_{W}\left(y\right):=\operatorname{argmin}_{u\in{\mathbb{R}}^{n}}\left\\{f\left(u\right)+\frac{1}{2}\left\lVert
y-u\right\rVert_{W}^{2}\right\\}$, then $\nabla
f_{W}\left(y\right)=M_{A,B,\mu}\left(y\right)$ and
$\inf_{{\mathcal{H}}}f=\inf_{{\mathcal{H}}}f_{W}$. So, we can use this example
to illustrate also the convergence properties of the dynamic with explicit
Hessian damping considered in Subsection 3.1. Thus, we can expect a
convergence rate of $1/s^{2}$ for
$f\left(y_{W}(s)\right)-\inf_{{\mathcal{H}}}f$, where
$y_{W}\left(s\right):=\operatorname{prox}_{\mu g}\left(y\left(s\right)+\mu
A^{*}\left(b-Ay\left(s\right)\right)\right)$.

We conduct the experiment for a randomly generated matrix $A$ and by taking
$g$ to be the $\ell_{1}$ norm with various choices for
$\alpha\in\left\\{1.001,2,3,5\right\\}$. Notice that we do not need need to
solve (125) directly but rather exploit the fact that it can be rewritten as
the first order equation

$\dot{y}\left(s\right)+\dfrac{s}{\alpha+1}M_{A,B,\mu}\left(y\left(s\right)\right)=\dfrac{s_{0}^{\alpha}}{s^{\alpha}}\left(y_{1}+\dfrac{s_{0}}{\alpha+1}y_{0}\right),$

as shown previously. We then use the Runge-Kutta method to solve this equation
numerically. Below we plot for the different choices of $\alpha$ the values of
$f$ at $y_{W}\left(s\right)$ and of the norm of the operator at
$y\left(s\right)$, respectively.

Figure 1: Convergence of funtion values in logarithmic scale.

Figure 2: Convergence of operator values in logarithmic scale.

##  6 Conclusion and perspectives

Our study has shed new light on the acceleration of gradient methods for
general convex differentiable optimization. Based on a dynamical approach, and
using relatively elementary tools, namely time scaling and time averaging, we
were able to introduce a large class of damped inertial dynamics with proven
fast convergence rates. The method is very flexible and can be adapted to
various initial start-up dynamics. We paid particular attention to the
steepest continuous descent and the regularized Newton method. Our approach
confirms the important role played by the Hessian driven damping role in these
questions. Our results open the door to a systematic study of the
corresponding fast proximal and gradient methods. Importantly, our approach
also works when we take a cocoercive operator instead of a gradient operator.
Applications to inertial forward-backward methods, ADMM, can therefore be
expected, to cite some of the most popular algorithms for convex structured
optimization. Application to stochastic differential equations can be
considered as well.

##  7 Appendix

###  7.1 Auxiliary results

Opial’s lemma in continuous form is a basic ingredient of the asymptotic
analysis of dynamical systems.

######  Lemma 1.

(Opial) Let $S$ be a nonempty subset of $\mathcal{H}$ and let
$x:[t_{0},+\infty[\to\mathcal{H}$. Assume that

  * (i)

for every $z\in S$, $\lim_{t\to\infty}\|x(t)-z\|$ exists;

  * (ii)

every weak sequential limit point of $x(t)$, as $t\to\infty$, belongs to $S$.

Then $x(t)$ converges weakly as $t\to+\infty$, and its limit belongs to $S$.

In the analysis of the perturbed dynamical systems Gronwall-Bellman’s lemma
(see [29, Lemme A.5]) plays an important role.

######  Lemma 2.

Let $T\geq\delta\geq 0$ and $g\colon\left[\delta,T\right]\to\mathbb{R}^{+}$ be
integrable, and let $c\geq 0$. Suppose that
$h\colon\left[\delta,T\right]\to\mathbb{R}$ is continuous and

$\dfrac{1}{2}h^{2}\left(t\right)\leq\dfrac{1}{2}c^{2}+\int_{\delta}^{t}h\left(t\right)g\left(t\right)dt$

for every $t\in\left[\delta,T\right]$. Then $\left\lvert
h\left(t\right)\right\rvert\leq c+\int_{\delta}^{t}g\left(u\right)du$ for
every $t\in\left[\delta,T\right]$.

######  Lemma 3.

Let $\delta\geq 0$ and $h\colon\left[\delta,+\infty\right]\to{\mathbb{R}}^{+}$
be a nonincreasing function belonging to
$\mathbb{L}^{1}\left(\left[\delta,+\infty\right]\right)$. It holds
$\lim_{t\to+\infty}th\left(t\right)=0$.

###### Proof.

The nonincreasing property of $h$ implies that
$\frac{d}{dt}\left(th\left(t\right)\right)=h\left(t\right)+t\dot{h}\left(t\right)\leq
h\left(t\right)$ for every $t\geq t_{0}$. Since
$h\in\mathbb{L}^{1}\left(\left[\delta,+\infty\right]\right)$, the result
follows from [1, Lemma 5.2]. ∎

######  Lemma 4.

Let $\delta\geq 0$ and $a\colon\left[\delta,+\infty\right]\to{\mathbb{R}}^{+}$
be a positive real valued function such that $\lim_{s\to+\infty}a(s)=0$. Then
$\lim_{s\to+\infty}A(s)=0$, where for $p>0$

$A(s)=\frac{1}{s^{p}}\int_{s_{0}}^{s}u^{p-1}a(u)du.$

###### Proof.

Given $\epsilon>0$, let $T_{\epsilon}$ such that $s_{0}<T_{\epsilon}$ and
$a(u)\leq\epsilon$ for $t\geq T_{\epsilon}$. For $s>T_{\epsilon}$, we have

$\displaystyle
A(s)=\frac{1}{s^{p}}\int_{s_{0}}^{T_{\epsilon}}u^{p-1}a(u)du+\frac{1}{s^{p}}\int_{T_{\epsilon}}^{s}u^{p-1}a(u)du\leq\frac{1}{s^{p}}\int_{s_{0}}^{T_{\epsilon}}u^{p-1}a(u)du+\epsilon.$

Letting $s$ converge to $+\infty$, it yields

$\limsup_{s\to+\infty}A(s)\leq\epsilon.$

This being true for any $\epsilon>0$, we infer that
$\lim_{s\to+\infty}A(s)=0$, which gives the claim. ∎

###  7.2 Missing proofs

###### Proof of Theorem 1.

For sake of completeness, let us recall some of the arguments used in the
asymptotic analysis of the perturbed steepest descent system when the
perturbation $g$ satisfies (7). Given $z_{*}\in S$, let $T>t_{0}$ be fixed and
for every $T\geq t\geq t_{0}$ consider

${\mathcal{E}}_{T}\left(t\right):=t\left(f\left(z\left(t\right)\right)-\inf_{{\mathcal{H}}}f\right)+\dfrac{1}{2}\left\lVert
z\left(t\right)-z_{*}\right\rVert^{2}+\int_{t}^{T}\left\langle
z\left(u\right)-z_{*}+\tau\dot{z}\left(u\right),g\left(u\right)\right\rangle
du.$

Differentiating ${\mathcal{E}}_{T}$ gives for every $T\geq t\geq t_{0}$

$\displaystyle\dfrac{d}{dt}{\mathcal{E}}_{T}\left(t\right)$
$\displaystyle=f\left(z\left(t\right)\right)-\inf_{{\mathcal{H}}}f+t\left\langle\nabla
f\left(z\left(t\right)\right),\dot{z}\left(t\right)\right\rangle+\left\langle
z\left(t\right)-z_{*},\dot{z}\left(t\right)-g\left(t\right)\right\rangle-t\left\langle\dot{z}\left(t\right),g\left(t\right)\right\rangle$
$\displaystyle=f\left(z\left(t\right)\right)-\inf_{{\mathcal{H}}}f-t\left\lVert\dot{z}\left(t\right)\right\rVert^{2}-\left\langle
z\left(t\right)-z_{*},\nabla f\left(z\left(t\right)\right)\right\rangle$
$\displaystyle\leq-t\left\lVert\dot{z}\left(t\right)\right\rVert^{2},$

where the second equality comes from (6) and the last inequality follows from
the convexity of $f$. By integration from $t_{0}$ to $t$ and by denoting
${C_{3}}:=t_{0}\left(f\left(z\left(t_{0}\right)\right)-\inf_{{\mathcal{H}}}f\right)+\dfrac{1}{2}\left\lVert
z\left(t_{o}\right)-z_{*}\right\rVert^{2}\geq 0$ we deduce that

$\displaystyle
t\left(f\left(z\left(t\right)\right)-\inf_{{\mathcal{H}}}f\right)+\dfrac{1}{2}\left\lVert
z\left(t\right)-z_{*}\right\rVert^{2}$ $\displaystyle\leq\ $
$\displaystyle{C_{3}}+\int_{t_{0}}^{t}\left\langle
z\left(u\right)-z_{*},g\left(u\right)\right\rangle
du+\int_{t_{0}}^{t}\tau\left\langle\dot{z}\left(u\right),g\left(u\right)\right\rangle
du-\int_{t_{0}}^{t}\tau\left\lVert\dot{z}\left(u\right)\right\rVert^{2}du$
$\displaystyle\leq\ $ $\displaystyle{C_{3}}+\int_{t_{0}}^{t}\left\lVert
z\left(u\right)-z_{*}\right\rVert\left\lVert g\left(u\right)\right\rVert
du+\dfrac{1}{2}\int_{t_{0}}^{+\infty}\tau\left\lVert
g\left(u\right)\right\rVert^{2}du-\dfrac{1}{2}\int_{t_{0}}^{t}\tau\left\lVert\dot{z}\left(u\right)\right\rVert^{2}du.$
(126)

We obtain that there exists ${C_{4}}\geq 0$ such that the following estimate
is true for every $t\geq t_{0}$

$\dfrac{1}{2}\left\lVert
z\left(t\right)-z_{*}\right\rVert^{2}\leq{C_{4}}+\int_{t_{0}}^{t}\left\lVert
z\left(u\right)-z_{*}\right\rVert\left\lVert g\left(u\right)\right\rVert du.$

According to Gronwall’s lemma (see Lemma 2 in the Appendix), we conclude that
for every $t\geq t_{0}$

$\left\lVert
z\left(t\right)-z_{*}\right\rVert\leq\sqrt{2{C_{4}}}+\int_{t_{0}}^{t}\left\lVert
g\left(u\right)\right\rVert
du\leq\sqrt{2{C_{4}}}+\int_{t_{0}}^{+\infty}\left\lVert
g\left(u\right)\right\rVert du<+\infty.$

The trajectory is therefore bounded. Using this property and condition (7)
allow us to assert from (126) that there exists ${C_{5}}\geq 0$ such that for
every $t\geq t_{0}$

$t\left(f\left(z\left(t\right)\right)-\inf_{{\mathcal{H}}}f\right)+\dfrac{1}{2}\left\lVert
z\left(t\right)-z_{*}\right\rVert^{2}+\dfrac{1}{2}\int_{t_{0}}^{t}\tau\left\lVert\dot{z}\left(u\right)\right\rVert^{2}du\leq{C_{5}}.$
(127)

Since
$t\left(f\left(z\left(t\right)\right)-\inf_{{\mathcal{H}}}f\right)+\frac{1}{2}\left\lVert
z\left(t\right)-z_{*}\right\rVert^{2}\geq 0$ for every $t\geq t_{0}$, letting
$t$ tend to $+\infty$ in (127) we deduce that

$\int_{t_{0}}^{+\infty}t\left\lVert\dot{z}\left(t\right)\right\rVert^{2}dt<+\infty.$

According to the constitutive equation (6) we get item $\rm{(ii)}$

$\int_{t_{0}}^{+\infty}t\left\lVert\nabla f(z(t)\right\rVert^{2}dt\leq
2\int_{t_{0}}^{+\infty}t\left\lVert\dot{z}\left(t\right)\right\rVert^{2}dt+2\int_{t_{0}}^{+\infty}t\left\lVert
g\left(t\right)\right\rVert^{2}dt<+\infty.$

Differentiate the anchor function, it yields for every $t\geq t_{0}$

$\displaystyle\dfrac{d}{dt}\left(\dfrac{1}{2}\left\lVert
z\left(t\right)-z_{*}\right\rVert^{2}\right)$ $\displaystyle=\left\langle
z\left(t\right)-z_{*},\dot{z}\left(t\right)\right\rangle$
$\displaystyle=-\left\langle z\left(t\right)-z_{*},\nabla
f\left(z\left(t\right)\right)\right\rangle-\left\langle
z\left(t\right)-z_{*},g\left(t\right)\right\rangle$
$\displaystyle\leq-\left(f\left(z\left(t\right)\right)-\inf_{{\mathcal{H}}}f\right)+\sup_{{u}\geq
t_{0}}\left\lVert z\left({u}\right)-z_{*}\right\rVert\cdot\left\lVert
g\left(t\right)\right\rVert$ (128) $\displaystyle\leq\sup_{{u}\geq
t_{0}}\left\lVert z\left({u}\right)-z_{*}\right\rVert\cdot\left\lVert
g\left(t\right)\right\rVert.$ (129)

Recall that the trajectory $z(\cdot)$ is bounded. Now let us show that in fact

$\lim_{t\to+\infty}t\left(f\left(z\left(t\right)\right)-\inf_{{\mathcal{H}}}f\right)=0,$

meaning that the convergence rate of
$f\left(z\left(t\right)\right)-\inf_{{\mathcal{H}}}f$ is actually
$o\left(1/t\right)$. To this end we integrate (128) from $t_{0}$ to $t>t_{0}$
and let then $t$ converge to $+\infty$. This yields $\rm{(iii)}$

$\int_{t_{0}}^{+\infty}\left(f\left(z\left(t\right)\right)-\inf_{{\mathcal{H}}}f\right)dt=\int_{t_{0}}^{+\infty}\dfrac{1}{t}t\left(f\left(z\left(t\right)\right)-\inf_{{\mathcal{H}}}f\right)dt<+\infty$
(130)

and thus
$\liminf_{t\to+\infty}t\left(f\left(z\left(t\right)\right)-\inf_{{\mathcal{H}}}f\right)=0$.
It remains to show that the limit exists. To this end we compute the time
derivative of
$t\left(f\left(z\left(t\right)\right)-\inf_{{\mathcal{H}}}f\right)$ for every
$t\geq t_{0}$

$\displaystyle\dfrac{d}{dt}\left(t\left(f\left(z\left(t\right)\right)-\inf_{{\mathcal{H}}}f\right)\right)$
$\displaystyle=f\left(z\left(t\right)\right)-\inf_{{\mathcal{H}}}f+t\left\langle\nabla
f\left(z\left(t\right)\right),\dot{z}\left(t\right)\right\rangle$
$\displaystyle=f\left(z\left(t\right)\right)-\inf_{{\mathcal{H}}}f-t\left\lVert\dot{z}\left(t\right)\right\rVert^{2}-t\left\langle
g\left(t\right),\dot{z}\left(t\right)\right\rangle\leq
f\left(z\left(t\right)\right)-\inf_{{\mathcal{H}}}f+\dfrac{1}{4}t\left\lVert
g\left(t\right)\right\rVert^{2}$

and apply once again [1, Lemma 5.1]. Statement $\rm{(iv)}$ follows from
assumption (7) and (130).

According to assumption (7), we deduce that the right hand side of (129)
belongs to $\mathbb{L}^{1}\left(\left[t_{0},+\infty\right[\right)$. Therefore,
from [1, Lemma 5.1] we obtain that $\lim_{t\to+\infty}\left\lVert
z\left(t\right)-z_{*}\right\rVert^{2}\in\mathbb{R}$ exists, and so
$\lim_{t\to+\infty}\left\lVert z\left(t\right)-z_{*}\right\rVert\in\mathbb{R}$
does. In other words, the first condition of Opial’s lemma (see Lemma 1 in the
Appendix) is fulfilled. Furthermore, since
$\lim_{t\to+\infty}f\left(z\left(t\right)\right)=\inf_{{\mathcal{H}}}f$ and
$f$ is convex and weakly lower semicontinuous, the second condition of Opial’s
lemma is also fulfilled. This gives the weak convergence of the trajectory
$z(t)$ as $t\to+\infty$ to an element in $S=\operatorname{argmin}f$.

The proof of $\rm{(vi)}$ follows similarly. First, the assertion $\rm{(ii)}$
gives $\liminf_{t\to+\infty}t^{2}\left\lVert\nabla
f\left(z\left(t\right)\right)\right\rVert^{2}=0$. Let $L$ be the Lipschitz
constant of $\nabla f$ on a ball containing the trajectory $z(\cdot)$. We have
for almost every $t\geq t_{0}$

$\displaystyle\dfrac{d}{dt}\left(t^{2}\left\lVert\nabla
f\left(z\left(t\right)\right)\right\rVert^{2}\right)$
$\displaystyle=2t\left\lVert\nabla
f\left(z\left(t\right)\right)\right\rVert^{2}+t^{2}\left\langle\nabla
f\left(z\left(t\right)\right),\dfrac{d}{dt}\nabla
f\left(z\left(t\right)\right)\right\rangle$ $\displaystyle=2t\left\lVert\nabla
f\left(z\left(t\right)\right)\right\rVert^{2}-t^{2}\left\langle\dot{z}\left(t\right),\dfrac{d}{dt}\nabla
f\left(z\left(t\right)\right)\right\rangle+t^{2}\left\langle
g\left(t\right),\dfrac{d}{dt}\nabla
f\left(z\left(t\right)\right)\right\rangle$ $\displaystyle\leq
2t\left\lVert\nabla
f\left(z\left(t\right)\right)\right\rVert^{2}-\dfrac{t^{2}}{L}\left\lVert\dfrac{d}{dt}\nabla
f\left(z\left(t\right)\right)\right\rVert^{2}+4Lt^{2}\left\lVert
g\left(t\right)\right\rVert^{2}+\dfrac{t^{2}}{L}\left\lVert\dfrac{d}{dt}\nabla
f\left(z\left(t\right)\right)\right\rVert^{2}$
$\displaystyle=2t\left\lVert\nabla
f\left(z\left(t\right)\right)\right\rVert^{2}+4Lt^{2}\left\lVert
g\left(t\right)\right\rVert^{2}.$

The convergence rate follows by applying once again [1, Lemma 5.1] and by
using that $t\mapsto
tg(t)\in\mathbb{L}^{2}\left(\left[t_{0},+\infty\right[\right)$. ∎

###### Proof of Theorem 5.

Given $z_{*}\in S$, we define the following function for every $t\geq t_{0}$,
which is nonnegative due to the convexity of $f$ and the fact that
$v\left(t\right)=\nabla f\left(z\left(t\right)\right)$

$\phi\left(t\right):=\left[f\left(z_{*}\right)-f\left(z\left(t\right)\right)-\left\langle
v\left(t\right),z_{*}-z\left(t\right)\right\rangle\right]+\dfrac{\lambda}{2}\left\lVert
z_{*}-z\left(t\right)\right\rVert^{2}.$

According to (65) and the convexity of $f$ we have for every $t\geq t_{0}$

$\displaystyle\dfrac{d}{dt}\phi\left(t\right)$ $\displaystyle=-\left\langle
v\left(t\right),\dot{z}\left(t\right)\right\rangle-\left\langle\dot{v}\left(t\right),z_{*}-z\left(t\right)\right\rangle+\left\langle
v\left(t\right),\dot{z}\left(t\right)\right\rangle-\lambda\left\langle
z_{*}-z\left(t\right),\dot{z}\left(t\right)\right\rangle$
$\displaystyle=\left\langle
v\left(t\right),z_{*}-z\left(t\right)\right\rangle\leq\inf_{{\mathcal{H}}}f-f\left(z\left(t\right)\right)\leq
0.$

We integrate from $t_{0}$ to $t>t_{0}$ and let $t$ tend to $+\infty$, and
obtain $\rm{(i)}$.

The inequality above also implies that the function $\phi$ is nonincreasing on
$\left[t_{0},+\infty\right[$, from which we deduce that $\phi(t)$ converges as
$t\to+\infty$, and that the trajectory $z(\cdot)$ is bounded. Let $L>0$ be the
Lipschitz constant of $\nabla f$ on a ball that contains the trajectory
$z(\cdot)$. It follows from (65) that for every $t\geq t_{0}$

$\displaystyle\dfrac{d}{dt}\left(f\left(z\left(t\right)\right)-\inf_{{\mathcal{H}}}f\right)$
$\displaystyle=\left\langle
v\left(t\right),\dot{z}\left(t\right)\right\rangle=-\lambda\left\lVert\dot{z}\left(t\right)\right\rVert^{2}-\left\langle\dot{v}\left(t\right),\dot{z}\left(t\right)\right\rangle=-\lambda\left\lVert\dot{z}\left(t\right)\right\rVert^{2}-\left\langle\dfrac{d}{dt}\left(\nabla
f\left(z\left(t\right)\right)\right),\dot{z}\left(t\right)\right\rangle$
$\displaystyle\leq-\lambda\left\lVert\dot{z}\left(t\right)\right\rVert^{2}-\dfrac{1}{L}\left\lVert\dfrac{d}{dt}\left(\nabla
f\left(z\left(t\right)\right)\right)\right\rVert^{2}=-\lambda\left\lVert\dot{z}\left(t\right)\right\rVert^{2}-\dfrac{1}{L}\left\lVert\dot{v}\left(t\right)\right\rVert^{2}\leq
0.$

Since $t\mapsto f\left(z\left(t\right)\right)-\inf_{{\mathcal{H}}}f$ is
nonincreasing, by applying Lemma 3 in the Appendix we obtain $\rm{(ii)}$.

In addition, we derive that

$\displaystyle\dfrac{d}{dt}\left(t\left(f\left(z\left(t\right)\right)-\inf_{{\mathcal{H}}}f\right)\right)$
$\displaystyle=f\left(z\left(t\right)\right)-\inf_{{\mathcal{H}}}f+\dfrac{d}{dt}\left(f\left(z\left(t\right)\right)-\inf_{{\mathcal{H}}}f\right)$
$\displaystyle\leq f\left(z\left(t\right)\right)-\inf_{{\mathcal{H}}}f-\lambda
t\left\lVert\dot{z}\left(t\right)\right\rVert^{2}-\dfrac{1}{L}t\left\lVert\dot{v}\left(t\right)\right\rVert^{2}$

Integrating again from $t_{0}$ to $t>t_{0}$ and letting $t$ tend to $+\infty$,
we obtain $\rm{(iii)}$. Indeed, for every $t\geq t_{0}$ we have $\left\lVert
v\left(t\right)\right\rVert^{2}\leq
2\lambda^{2}\left\lVert\dot{z}\left(t\right)\right\rVert^{2}+2\left\lVert\dot{v}\left(t\right)\right\rVert^{2}$,
therefore

$\int_{t_{0}}^{+\infty}t\left\lVert
v\left(t\right)\right\rVert^{2}dt=\int_{t_{0}}^{+\infty}t\left\lVert\nabla
f\left(z\left(t\right)\right)\right\rVert^{2}dt<+\infty.$ (131)

Consequently, for item $iv)$ we can use again Lemma 3. Precisely, observe that
for every $t\geq t_{0}$

$\dfrac{d}{dt}\left(\dfrac{1}{2}\left\lVert
v\left(t\right)\right\rVert^{2}\right)=\left\langle
v\left(t\right),\dot{v}\left(t\right)\right\rangle=-\lambda\left\langle\dot{{z}}\left(t\right),\dot{v}\left(t\right)\right\rangle-\left\lVert\dot{v}\left(t\right)\right\rVert^{2}\leq
0,$

which means $t\mapsto\frac{1}{2}\left\lVert v\left(t\right)\right\rVert^{2}$
is nonincreasing. The conclusion follows by using (131) and by noticing that

$\left\lVert
v\left(t\right)\right\rVert^{2}=\left\lVert\lambda\dot{z}\left(t\right)+\dot{v}\left(t\right)\right\rVert^{2}=\lambda^{2}\left\lVert\dot{z}\left(t\right)\right\rVert^{2}+\left\lVert\dot{v}\left(t\right)\right\rVert^{2}+2\lambda\left\langle\dot{z}\left(t\right),\dot{v}\left(t\right)\right\rangle\geq\lambda^{2}\left\lVert\dot{z}\left(t\right)\right\rVert^{2}+\left\lVert\dot{v}\left(t\right)\right\rVert^{2}.$

Finally, let us recall that
$\lim_{t\to+\infty}\phi\left(t\right)\in{\mathbb{R}}$ exists. Moreover,
according to $\rm{(ii)}$, $\rm{(iv)}$, and the fact that the trajectory
$z(\cdot)$ is bounded, we conclude that

$\lim_{t\to+\infty}\dfrac{\lambda}{2}\left\lVert
z_{*}-z\left(t\right)\right\rVert^{2}=\lim_{t\to+\infty}\phi\left(t\right)\in{\mathbb{R}}.$

This yields the first condition of Opial’s lemma. Now let $\widehat{z}$ be a
weak sequential cluster point of the trajectory. Since $v\left(t\right)=\nabla
f\left(z\left(t\right)\right)$ for every $t\geq t_{0}$, it follows from the
sequential closedness property of $\nabla f$ in the weak $\times$ strong
topology on ${\mathcal{H}}\times{\mathcal{H}}$ that $\widehat{z}\in S$, which
proves that the second condition of Opial’s lemma is also satisfied. This
completes the proof. ∎

###### Proof of Theorem 11.

For the sake of completeness, we briefly sketch the Lyapunov analysis of
(118). Given $z_{*}\in S$, let us first fix $T>t_{0}$, and for every $T\geq
t\geq t_{0}$ consider

${\mathcal{E}}_{T}\left(t\right):=\dfrac{1}{2}\left\lVert
z\left(t\right)-z_{*}\right\rVert^{2}+\int_{t}^{T}\left\langle
z\left(u\right)-z_{*},g\left(u\right)\right\rangle du.$

For every $T\geq t\geq t_{0}$ it holds

$\displaystyle\dfrac{d}{dt}{\mathcal{E}}_{T}\left(t\right)$
$\displaystyle=\left\langle
z\left(t\right)-z_{*},\dot{z}\left(t\right)\right\rangle-\left\langle
z\left(t\right)-z_{*},g\left(t\right)\right\rangle=-\left\langle
z\left(t\right)-z_{*},M\left(z\left(t\right)\right)\right\rangle.$

By integration from $t_{0}$ to $t$, we get for $C_{6}:=\dfrac{1}{2}\left\lVert
z\left(t_{0}\right)-z_{*}\right\rVert^{2}$

$\displaystyle\dfrac{1}{2}\left\lVert
z\left(t\right)-z_{*}\right\rVert^{2}+\int_{t_{0}}^{t}\left\langle
z\left(t\right)-z_{*},M\left(z\left(t\right)\right)\right\rangle du$
$\displaystyle\leq C_{6}+\int_{t_{0}}^{t}\left\langle
z\left(u\right)-z_{*},g\left(u\right)\right\rangle du$ $\displaystyle\leq
C_{6}+\int_{t_{0}}^{t}\left\lVert z\left(u\right)-z_{*}\right\rVert\left\lVert
g\left(u\right)\right\rVert du.$ (132)

By Gronwall’s lemma (see Lemma 2 in the Appendix), we conclude that for every
$t\geq t_{0}$

$\left\lVert
z\left(t\right)-z_{*}\right\rVert\leq\sqrt{2C_{6}}+\int_{t_{0}}^{t}\left\lVert
g\left(u\right)\right\rVert
du\leq\sqrt{2C_{6}}+\int_{t_{0}}^{+\infty}\left\lVert
g\left(u\right)\right\rVert du<+\infty.$

This gives the boundedness of the trajectory. Using this assertion in (132),
we deduce that for every $t\geq t_{0}$

$\displaystyle\int_{t_{0}}^{t}\left\langle
z\left(u\right)-z_{*},M\left(z\left(u\right)\right)\right\rangle du$
$\displaystyle\leq C_{6}+\sup_{t\geq t_{0}}\left\lVert
z\left(u\right)-z_{*}\right\rVert\int_{t_{0}}^{t}\left\lVert
g\left(u\right)\right\rVert du$ $\displaystyle\leq C_{6}+\sup_{t\geq
t_{0}}\left\lVert
z\left(u\right)-z_{*}\right\rVert\int_{t_{0}}^{+\infty}\left\lVert
g\left(u\right)\right\rVert du<+\infty.$

According to the $\rho$-cocoercivity of $M$, and by letting $t$ go to
infinity, we obtain

$\rho\int_{t_{0}}^{+\infty}\left\lVert
M\left(z\left(t\right)\right)\right\rVert^{2}dt\leq\int_{t_{0}}^{+\infty}\left\langle
z\left(t\right)-z_{*},M\left(z\left(t\right)\right)\right\rangle dt<+\infty.$
(133)

Therefore, $\liminf_{t\to+\infty}t\left\lVert
M\left(z\left(t\right)\right)\right\rVert^{2}=0$. Let us now compute the time
derivative for every $t\geq t_{0}$

$\displaystyle\dfrac{d}{dt}\left(\dfrac{1}{2}t\left\lVert
M\left(z\left(t\right)\right)\right\rVert^{2}\right)$
$\displaystyle=\dfrac{1}{2}\left\lVert
M\left(z\left(t\right)\right)\right\rVert^{2}+t\left\langle
M\left(z\left(t\right)\right),\dfrac{d}{dt}\left(M\left(z\left(t\right)\right)\right)\right\rangle$
$\displaystyle=\dfrac{1}{2}\left\lVert
M\left(z\left(t\right)\right)\right\rVert^{2}-t\left\langle\dot{z}\left(t\right),\dfrac{d}{dt}\left(M\left(z\left(t\right)\right)\right)\right\rangle+t\left\langle
g\left(t\right),\dfrac{d}{dt}\left(M\left(z\left(t\right)\right)\right)\right\rangle.$

Using the cocoercivity of $M$ and the Cauchy-Schwarz inequality, we deduce
that

$\displaystyle-t\left\langle\dot{z}\left(t\right),\dfrac{d}{dt}\left(M\left(z\left(t\right)\right)\right)\right\rangle+t\left\langle
g\left(t\right),\dfrac{d}{dt}\left(M\left(z\left(t\right)\right)\right)\right\rangle$
$\displaystyle\leq-\rho
t\left\lVert\dfrac{d}{dt}\left(M\left(z\left(t\right)\right)\right)\right\rVert^{2}+t\left\lVert
g\left(t\right)\right\rVert\left\lVert\dfrac{d}{dt}\left(M\left(z\left(t\right)\right)\right)\right\rVert$
$\displaystyle\leq\dfrac{1}{4\rho}t\left\lVert
g\left(t\right)\right\rVert^{2}.$

The right hand side of the above inequality belongs to
$\mathbb{L}^{1}\left(\left[t_{0},+\infty\right[\right)$ thanks to (119) and
(133). According to [1, Lemma 5.1] we have that
$\lim_{t\to+\infty}t\left\lVert
M\left(z\left(t\right)\right)\right\rVert^{2}\in\mathbb{R}$ exists, and
therefore it must be equal to $0$

$\left\lVert
M\left(z\left(t\right)\right)\right\rVert=o\left(\dfrac{1}{\sqrt{t}}\right)\textrm{
as }t\to+\infty.$

This also means that $\lim_{t\to+\infty}M\left(z\left(t\right)\right)=0$.
According to the sequential closedness property of the graph of $M$ in the
weak $\times$ strong topology on ${\mathcal{H}}\times{\mathcal{H}}$, every
weak limit point of the trajectory $z$ belongs to $S$. It remains to verify
the first condition of Opial’s lemma. Given $z_{*}\in S$, observe that for
every $t\geq t_{0}$ it holds

$\displaystyle\dfrac{d}{dt}\left(\dfrac{1}{2}\left\lVert
z\left(t\right)-z_{*}\right\rVert^{2}\right)$ $\displaystyle=\left\langle
z\left(t\right)-z_{*},\dot{z}\left(t\right)\right\rangle=-\left\langle
z\left(t\right)-z_{*},M\left(z\left(t\right)\right)\right\rangle+\left\langle
z\left(t\right)-z_{*},g\left(t\right)\right\rangle$
$\displaystyle\leq\sup_{t\geq t_{0}}\left\lVert
z\left(t\right)-z_{*}\right\rVert\cdot\left\lVert
g\left(t\right)\right\rVert.$

This shows that the limit $\lim_{t\to+\infty}\left\lVert
z\left(t\right)-z_{*}\right\rVert\in\mathbb{R}$ thanks to (119) and [1, Lemma
5.1]. ∎

## References

  * Abbas et al. [2014] Abbas, B., Attouch, H., Svaiter, B., 2014.  Newton-like dynamics and forward–backward methods for structured monotone inclusions in hilbert spaces.  J. Optim. Theory Appl. 161, 331–360.  doi:10.1007/s10957-013-0414-5.
  * Alecsa et al. [2021] Alecsa, C., László, S., Pinta, T., 2021.  An extension of the second order dynamical system that models Nesterov’s convex gradient method.  Appl. Math. Optim. 84, 1687–1716.  doi:10.1007/s00245-020-09692-1.
  * Attouch et al. [2022a] Attouch, H., Balhag, A., Chbani, Z., Riahi, H., 2022a.  Fast convex optimization via inertial dynamics combining viscous and Hessian-driven damping with time rescaling.  Evol. Equ. Control Theory 11, 487–514.  doi:10.3934/eect.2021010.
  * Attouch et al. [2022b] Attouch, H., Boţ, R., Csetnek, E., 2022b.  Fast optimization via inertial dynamics with closed-loop damping.  J. Eur. Math. Soc. doi:10.4171/JEMS/1231.
  * Attouch et al. [2014] Attouch, H., Buttazzo, G., Michaille, G., 2014.  Variational analysis in Sobolev and BV spaces. Applications to PDE’s and optimization.  MOS/SIAM Series on Optimization, MO 17. 2nd ed., Society for Industrial and Applied Mathematics (SIAM), Philadelphia.
  * Attouch and Cabot [2017] Attouch, H., Cabot, A., 2017\.  Asymptotic stabilization of inertial gradient dynamics with time-dependent viscosity.  J. Differential Equation 263, 5412–5458.  doi:10.1016/j.jde.2017.06.024.
  * Attouch and Cabot [2018] Attouch, H., Cabot, A., 2018\.  Convergence rates of inertial forward-backward algorithms.  SIAM J. Optim. 28, 849–874.  doi:10.1137/17M1114739.
  * Attouch and Cabot [2020] Attouch, H., Cabot, A., 2020\.  Convergence of a relaxed inertial proximal algorithm for maximally monotone operators.  Math. Program. 184, 243–287.  doi:10.1007/s10957-013-0414-5.
  * Attouch et al. [2022c] Attouch, H., Chbani, Z., Fadili, J., Riahi, H., 2022c.  First-order algorithms via inertial systems with hessian driven damping.  Math. Program. 193, 113–155.  doi:10.1007/s10107-020-01591-1.
  * Attouch et al. [2023] Attouch, H., Chbani, Z., Fadili, J., Riahi, H., 2023\.  Convergence of iterates for first-order optimization algorithms with inertia and Hessian driven damping.  Optimization 72, 1199–1238.  doi:10.1080/02331934.2021.2009828.
  * Attouch et al. [2018] Attouch, H., Chbani, Z., Peypouquet, J., Redont, P., 2018\.  Fast convergence of inertial dynamics and algorithms with asymptotic vanishing viscosity.  Math. Program. Ser. B 168, 123–175.  doi:10.1007/s10107-016-0992-8.
  * Attouch et al. [2019] Attouch, H., Chbani, Z., Riahi, H., 2019.  Fast proximal methods via time scaling of damped inertial dynamics.  SIAM J. Optim. 29, 2227–2256.  doi:10.1137/18M1230207.
  * Attouch and Czarnecki [2010] Attouch, H., Czarnecki, M.O., 2010\.  Asymptotic behavior of coupled dynamical systems with multiscale aspects.  J. Differential Equations 248, 1315–1344.  doi:10.1007/s10957-013-0414-5.
  * Attouch and Fadili [2022] Attouch, H., Fadili, J., 2022\.  From the Ravine method to the Nesterov method and vice versa: A dynamical system perspective.  SIAM J. Optim. 32, 2074–2101.  doi:10.1137/22M1474357.
  * Attouch et al. [2022d] Attouch, H., Fadili, J., Kungurtsev, V., 2022d.  On the effect of perturbations, errors in first-order optimization methods with inertia and hessian driven damping.  Evol. Equ. Control Theory doi:10.3934/eect.2022022.
  * Attouch et al. [2000] Attouch, H., Goudou, X., Redont, P., 2000.  The heavy ball with friction method. the continuous dynamical system, global exploration of the local minima of a real-valued function by asymptotical analysis of a dissipative dynamical system.  Commun. Contemp. Math. 2, 1–34.  doi:10.1142/S0219199700000025.
  * Attouch et al. [2016a] Attouch, H., Marques-Alves, M., Svaiter, B.F., 2016a.  A dynamic approach to a proximal-Newton method for monotone inclusions in Hilbert spaces, with complexity $\mathcal{O}(1/n^{2})$.  J. Convex Anal. 23, 139–180.
  * [18] Attouch, H., Peypouquet, J., .  Convergence of inertial dynamics and proximal algorithms governed by maximal monotone operators.  Math. Program. doi:10.1007/s10107-018-1252-x.
  * Attouch and Peypouquet [2016] Attouch, H., Peypouquet, J., 2016\.  The rate of convergence of nesterov’s accelerated forward-backward method is actually faster than $1/k^{2}$.  SIAM J. Optim. 26, 1824–1834.  doi:10.1137/15M1046095.
  * Attouch et al. [2016b] Attouch, H., Peypouquet, J., Redont, P., 2016b.  Fast convex optimization via inertial dynamics with hessian driven damping.  J. Diff. Equ. 261, 5734–5783.  doi:10.1016/j.jde.2016.08.020.
  * Attouch et al. [2013] Attouch, H., Redont, P., Svaiter, B.F., 2013.  Global convergence of a closed-loop regularized Newton method for solving monotone inclusions in Hilbert spaces.  J. Optim. Theory Appl. 157, 624–650.  doi:10.1007/s10957-012-0222-3.
  * Attouch and Svaiter [2011] Attouch, H., Svaiter, B.F., 2011\.  A continuous dynamical Newton-like approach to solving monotone inclusions.  SIAM J. Control Optim. 49, 574–598.  doi:10.1137/100784114.
  * Bauschke and Combettes [2017] Bauschke, H., Combettes, P.L., 2017\.  Convex Analysis and Monotone Operator Theory in Hilbert Spaces.  CSM Books in Mathematics. 2nd ed., Springer.
  * Beck and Teboulle [2009] Beck, A., Teboulle, M., 2009\.  A fast iterative shrinkage-thresholding algorithm for linear inverse problems.  SIAM J. Imaging Sci. 2, 183–202.  doi:10.1137/080716542.
  * Boţ and Csetnek [2017] Boţ, R.I., Csetnek, E.R., 2017\.  A dynamical system associated with the fixed points set of a nonexpansive operator.  J. Dyn. Diff. Equ. 29, 155–168.  doi:10.1007/s10884-015-9438-x.
  * Boţ et al. [2021] Boţ, R.I., Csetnek, E.R., László, S., 2021.  Tikhonov regularization of a second order dynamical system with Hessian driven damping.  Math. Program. 189, 151–186.  doi:10.1007/s10957-013-0414-5.
  * Boţ et al. [2022] Boţ, R.I., Csetnek, E.R., Nguyen, D.K., 2022.  Fast OGDA in continuous and discrete time arXiv:arXiv:2203.10947.
  * Boţ and Nguyen [2021] Boţ, R.I., Nguyen, D.K., 2021\.  Improved convergence rates and trajectory convergence for primal-dual dynamical systems with vanishing damping.  J. Differ. Equ. 303, 369–406.  doi:10.1016/j.jde.2021.09.021.
  * Brézis [1972] Brézis, H., 1972.  Opérateurs maximaux monotones dans les espaces de Hilbert et équations d’évolution.  Lecture Notes 5, North Holland.
  * Brézis [1983] Brézis, H., 1983.  Analyse fonctionnelle, Théorie et applications.  North Holland.
  * Cabot et al. [2009] Cabot, A., Engler, H., Gadat, S., 2009.  On the long time behavior of second order differential equations with asymptotically small dissipation.  Trans. Amer. Math. Soc. 361, 5983–6017.  URL: http://www.jstor.org/stable/40302945.
  * Castera et al. [2021] Castera, C., Bolte, J., Févotte, C., Pauwels, E., 2021\.  Newton-like dynamics and forward–backward methods for structured monotone inclusions in hilbert spaces.  J. Mach. Learn. Res. 22, 1–31.  URL: http://jmlr.org/papers/v22/19-1024.html.
  * Chambolle and Dossal [2015] Chambolle, A., Dossal, C., 2015\.  On the convergence of the iterates of the Fast Iterative Shrinkage Thresholding Algorithm.  J. Optim. Theory Appl. 166, 968–982.  doi:10.1007/s10957-015-0746-4.
  * Combettes and Yamada [2015] Combettes, P., Yamada, I., 2015\.  Compositions and convex combinations of averaged nonexpansive operators.  J. Math. Anal. Appl. 425, 55–70.  doi:10.1016/j.jmaa.2014.11.044.
  * Gelfand and Tsetlin [1963] Gelfand, I., Tsetlin, M., 1963\.  Printszip nelokalnogo poiska v sistemah avtomatich.  Optimizatsii, Dokl. AN SSSR 137, 295–298.  doi:10.1007/s10957-013-0414-5.
  * Lin and Jordan [2021] Lin, T., Jordan, M., 2021.  On monotone inclusions, acceleration and closed-loop control arXiv:arXiv:2111.08093.
  * [37] Nesterov, Y., .  Introductory Lectures on Convex Optimization: A Basic Course.  Applied Optimization.
  * Nesterov [1983] Nesterov, Y., 1983.  A method of solving a convex programming problem with convergence rate $\mathcal{O}(1/k^{2})$.  Soviet Mathematics Doklady 27, 372–376.
  * Nesterov [2005] Nesterov, Y., 2005.  Smooth minimization of non-smooth functions.  Math. Program. 103, 127–152.
  * Polyak [1964] Polyak, B., 1964.  Some methods of speeding up the convergence of iteration methods.  U.S.S.R. Comput. Math. Math. Phys. 4, 1–17.  doi:10.1016/0041-5553(64)90137-5.
  * Polyak [1987] Polyak, B., 1987.  Introduction to Optimization.  Optimization Software, New York.
  * Poveda and Li [2021] Poveda, J.I., Li, N., 2021.  Robust hybrid zero-order optimization algorithms with acceleration via averaging in time.  Automatica 123, 109361\.  doi:10.1016/j.automatica.2020.109361.
  * Scieur et al. [2020] Scieur, D., D’Aspremont, A., Bach, F., 2020.  Regularized nonlinear acceleration.  Math. Program. 179, 47–83.  doi:10.1007/s10107-018-1319-8.
  * Shi et al. [2021] Shi, B., Du, S.S., Jordan, M.I., Su, W.J., 2021.  Understanding the acceleration phenomenon via high-resolution differential equations.  Math. Program. doi:10.1007/s10107-021-01681-8.
  * Su et al. [2016] Su, W.J., Boyd, S., Candès, E.J., 2016.  A differential equation for modeling Nesterov’s accelerated gradient method: theory and insights.  J. Mach. Learn. Res. 17, 1–43.  URL: http://jmlr.org/papers/v17/15-084.html.