∎

11institutetext:  Hedy Attouch 22institutetext: IMAG, Univ. Montpellier, CNRS,
Montpellier, France
22email<EMAIL_ADDRESS>33institutetext: Radu Ioan Boţ
44institutetext: Faculty of Mathematics, University of Vienna, Oskar-
Morgenstern-Platz 1, 1090 Vienna, Austria,
44email<EMAIL_ADDRESS>Dang-Khoa Nguyen
66institutetext: Faculty of Mathematics, University of Vienna, Oskar-
Morgenstern-Platz 1, 1090 Vienna, Austria,
66email<EMAIL_ADDRESS>
# Fast convex optimization via closed-loop time scaling of gradient dynamics

Hedy Attouch  Radu Ioan Boţ  Dang-Khoa Nguyen

###### Abstract

In a Hilbert setting, for convex differentiable optimization, we develop a
general framework for adaptive accelerated gradient methods. They are based on
damped inertial dynamics where the coefficients are designed in a closed-loop
way. Specifically, the damping is a feedback control of the velocity, or of
the gradient of the objective function. For this, we develop a closed-loop
version of the time scaling and averaging technique introduced by the authors.
We thus obtain autonomous inertial dynamics which involve vanishing viscous
damping and implicit Hessian driven damping. By simply using the convergence
rates for the continuous steepest descent and Jensen’s inequality, without the
need for further Lyapunov analysis, we show that the trajectories have several
remarkable properties at once: they ensure fast convergence of values, fast
convergence of the gradients towards zero, and they converge to optimal
solutions. Our approach leads to parallel algorithmic results, that we study
in the case of proximal algorithms. These are among the very first general
results of this type obtained using autonomous dynamics.

###### Keywords:

fast convex optimization; damped inertial dynamic; time scaling; averaging;
closed-loop control; Nesterov and Ravine algorithms; Hessian driven damping;
proximal algorithms

AMS subject classification 37N40, 46N10, 49M30, 65B99, 65K05, 65K10, 90B50,
90C25

##  1 Introduction

In a real Hilbert space ${\mathcal{H}}$, we develop a dynamic approach to the
rapid resolution of convex optimization problems which relies on inertial
dynamics whose damping is designed as a closed-loop control. We consider the
minimization 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. Our study comes as a natural extension of the
authors’ previous work ABN  where the technique of time scaling and averaging
was used in an open-loop way, giving rise to non-autonomous damped inertial
dynamics with fast convergence properties. In the present paper, we take
advantage of the simplicity and flexibility of this technique to develop it in
a closed-loop way. This will give rise to autonomous damped inertial dynamics
with fast convergence properties. Recall that the low-resolution ODE obtained
by Su, Boyd, and Candès SBC  of the accelerated gradient method of Nesterov,
together with the corresponding high-resolution ODE ACFR , SDJS  (which
involves an additional Hessian driven damping term) are non-autonomous
dynamics, the coefficient of viscous friction being of the form $\alpha/t$.
Our study therefore opens a new path in the field of first-order adaptive
optimization methods.

###  1.1 Time scale and averaging: the open-loop approach

Let us first briefly explain the time scaling and averaging method in the
open-loop case on a model example (see ABN  for more details). Then we will
look at how to develop a corresponding closed-loop approach. As the basic
starting dynamic, we consider the continuous steepest descent

${\rm(SD)}\quad\dot{z}(s)+\nabla f(z(s))=0,$ (3)

for which we have the classical convergence result

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

Then, we make the change of time variable $s=\tau(t)$ in (SD), where
$\tau(\cdot)$ is an increasing function from $\mathbb{R}_{+}$ to
$\mathbb{R}_{+}$, continuously differentiable, and satisfying
$\lim_{t\to+\infty}\tau(t)=+\infty$. Setting $y(t):=z(\tau(t))$, we get

$\dot{y}(t)+\dot{\tau}(t)\nabla f(y(t))=0.$ (4)

The convergence rate becomes

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

Taking $\tau(\cdot)$ which grows faster than the identity, makes the solution
trajectories unchanged but travelled faster. The price to pay is that (4) is a
non-autonomous dynamic in which the coefficient in front of the gradient term
tends to infinity as $t\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 difficulty we come with the second step of our
method which is averaging. Let us attach to $y(\cdot)$ the new function
$x:[t_{0},+\infty[\to{\mathcal{H}}$ defined by

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

with $x(t_{0})=x_{0}$ given in ${\mathcal{H}}$. We shall explain further the
averaging interpretation. Equivalently

$y(t)=x(t)+\dot{\tau}(t)\dot{x}(t).$ (7)

By temporal derivation of (7) we get

$\dot{y}(t)=\dot{x}(t)+\ddot{\tau}(t)\dot{x}(t)+\dot{\tau}(t)\ddot{x}(t).$ (8)

Replacing $y(t)$ and $\dot{y}(t)$ as given by (7) and (8) in (4), we get

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

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

$\tau(t)=\dfrac{t^{2}}{2(\alpha-1)},$ (10)

gives $\frac{1+\ddot{\tau}(t)}{\dot{\tau}(t)}=\frac{\alpha}{t}$, and the
corresponding dynamic with implicit Hessian driven damping

$\ddot{x}(t)+\frac{\alpha}{t}\dot{x}(t)+\nabla
f\Big{(}x(t)+\dfrac{t}{\alpha-1}\dot{x}(t)\Big{)}=0.$ (11)

In this dynamic, the Hessian driven damping appears in an implicit form. This
type of dynamic was initiated in ALP , see also MJ  for a related autonomous
system in the case of a strongly convex function $f$. The rationale justifying
the use of the term “implicit” comes from the observation that by a Taylor
expansion (as $t\to+\infty$ we have $t\dot{x}(t)\to 0$ which justifies the use
of Taylor expansion), we have

$\nabla f\Big{(}{x(t)+\dfrac{t}{\alpha-1}\dot{x}(t)}\Big{)}\approx\nabla
f(x(t))+\dfrac{t}{\alpha-1}\nabla^{2}f(x(t))\dot{x}(t),$

thus making the Hessian damping appear indirectly in (11). Because of its
important role in attenuating the oscillations, several recent studies have
been devoted to inertial dynamics combining the asymptotic vanishing damping
with the geometric Hessian-driven damping (coined sometimes Newton-type
inertial dynamics); see e.g., ABCR ; APR2 ; ACFR ; ACFR-Opti ; AFK ; BCL ;
CBFP ; ML1 ; SDJS . In turn, the corresponding algorithms, among which IGAHD
enjoys several favorable properties, introduce a correction term in the
Nesterov accelerated gradient method (see Nest1 ; Nest2 ) which reduces the
oscillatory aspects.

Note that in (11) the coefficient of the Hessian damping is proportional to
the inverse of the viscosity damping. Thus asymptotically when the viscous
damping tends towards zero, and therefore can cause many small oscillations to
appear, the coefficient of the Hessian driven damping tends towards infinity,
and therefore has an effective effect on the attenuation of the oscillations.
This is the situation considered by Attouch-Boţ-Nguyen ABN , who obtained
convergence rates comparable to those associated with the Nesterov accelerated
gradient method. A major advantage of this approach is that there is no need
to do a Lyapunov analysis, we only use the classical convergence rate for the
continuous steepest descent. Moreover, the convergence of the trajectories is
a direct consequence of the known results for the steepest descent.

###  1.2 Closed-loop control

The idea is to exploit the time scaling and averaging method and the fact that
(SD) provides several quantities which are increasing and converge to
$+\infty$ as $t\to+\infty$, so which are eligible for time scaling. This will
enable us to perform time scaling and averaging in a closed-loop way. Indeed,
in (SD), the velocity and the norm of the gradient are monotonically
decreasing to zero. So, the idea is to use their inverse for defining the time
scaling. Specifically, in a first result we are going to define the derivative
of the time scaling $\tau(\cdot)$ as a function of the inverse of the speed.
This means acceleration of the time scaling when the speed decreases.
Following this approach, we will obtain in Theorem 3.2 the following model
result.

###### Theorem 1.1

Suppose that $f\colon{\mathcal{H}}\to{\mathbb{R}}$ satisfies $(\mathcal{A})$.
Let us choose the positive parameters according to $q>0$, $p\geq 1$, and
$\gamma>1$. Let $x\colon\left[t_{0},+\infty\right[\to{\mathcal{H}}$ be a
solution trajectory of the following system

$\begin{cases}\ddot{x}(t)+\dfrac{(1+\gamma)\dot{\tau}(t)^{2}-\tau(t)\ddot{\tau}(t)}{\tau(t)\dot{\tau}(t)}\dot{x}(t)+\gamma\frac{\dot{\tau}(t)^{2}}{\tau(t)}\nabla
f\left(x(t)+\dfrac{1}{\gamma}\dfrac{\tau(t)}{\dot{\tau}(t)}\dot{x}(t)\right)&=0\vspace{2mm}\\\
\tau\left(t\right)-\dfrac{1}{q^{q}}\left(t_{0}+\displaystyle\int_{t_{0}}^{t}\left[\lambda\left(r\right)\right]^{\frac{1}{q}}dr\right)^{q}&=0\vspace{2mm}\\\
\left[\lambda\left(t\right)\right]^{p}\left\lvert\dot{\tau}\left(t\right)\right\rvert^{p-1}\left\lVert\nabla
f\left(x\left(t\right)+\dfrac{1}{\gamma}\dfrac{\tau(t)}{\dot{\tau}(t)}\dot{x}\left(t\right)\right)\right\rVert^{p-1}&=1.\end{cases}$
(12)

Then we have the fast convergence of values: as $t\to+\infty$

$f(x(t))-\inf_{{\mathcal{H}}}f=o\left(\dfrac{1}{t^{1+q-\frac{1}{p}}}\right).$
(13)

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

As a special case, take $p=1$, $q=2$. Then, the last equation of (12) gives
$\lambda(t)\equiv 1$. According to this, the second equation of (12) gives
$\tau(t)={\frac{t^{2}}{4}}$, and we find a case with time scaling in an open-
loop form. After elementary calculation, the first equation of (12) is written
as

$\ddot{x}(t)+\dfrac{\alpha}{t}\dot{x}(t)+\dfrac{\alpha-1}{2}\nabla
f\left(x(t)+\dfrac{t}{\alpha-1}\dot{x}(t)\right)=0,$

with $\alpha=2\gamma+1>3$, and the convergence rate of the values becomes

$f(x(t))-\inf_{{\mathcal{H}}}f=o\left(\dfrac{1}{t^{2}}\right).$ (14)

We therefore recover the results obtained by the authors in the case of the
open loop, giving the optimal convergence rates for general convex
differentiable optimization. This inertial formulation may seem at first
glance complicated. Indeed it is equivalent to the first-order system in time
and space

$\begin{cases}\dot{y}\left(t\right)+\dot{\tau}\left(t\right)\nabla
f\left(y\left(t\right)\right)&=0\vspace{1mm}\\\
\dot{x}(t)+\gamma\dfrac{\dot{\tau}(t)}{\tau(t)}x(t)-\gamma\dfrac{\dot{\tau}(t)}{\tau(t)}y(t)&=0\vspace{1mm}\\\
\tau\left(t\right)-\dfrac{1}{q^{q}}\left(t_{0}+\displaystyle\int_{t_{0}}^{t}\left[\lambda\left(r\right)\right]^{\frac{1}{q}}dr\right)^{q}&=0\vspace{1mm}\\\
\left[\lambda\left(t\right)\right]^{p}\left\lVert\dot{y}\left(t\right)\right\rVert^{p-1}&=1,\end{cases}$
(15)

whose temporal discretization provides corresponding optimization algorithms,
see Theorem 5.1.

###  1.3 Link with the existing literature

Contrary to the rich literature that has been devoted to non-autonomous damped
inertial methods and their links with the fast first-order optimization
algorithms for general convex optimization (in particular the Nesterov
accelerated gradient method), only a small number of papers have been devoted
to these questions, based on autonomous methods. Indeed the heavy ball method
of Polyak only provides the asymptotic convergence rate $1/t$ for general
convex functions. The idea is therefore to see if we can mimic the fast
convergence properties of the Su, Boyd, and Candès dynamic model (see SBC ) of
the Nesterov accelerated gradient method, using autonomous dynamics. A natural
idea is to design the damping term, on which is based the optimization
properties of the system, in a closed-loop way. In this direction, we can
mention the following contributions.

a) Our study has a natural link with works devoted to regularized Newton
methods for solving monotone inclusions (and (1) in particular). Given a
general maximally monotone operator
$A:{\mathcal{H}}\rightrightarrows{\mathcal{H}}$, to overcome the ill-posed
character of the continuous Newton method, in line with ASv , Attouch, Redont
and Svaiter have studied in ARS  the following closed-loop dynamic version of
the Levenberg-Marquardt method

$\displaystyle\left\\{\begin{array}[]{rcl}v(t)\in A(x(t))\\\
\rule{0.0pt}{12.0pt}\|v(t)\|^{\gamma}\dot{x}(t)+\beta\dot{v}(t)+v(t)=0.\end{array}\right.$

When $\gamma>1$, they showed the well-posedness of the above system, and
analyzed its convergence properties. When $A=\nabla f$ this system writes

$\|\nabla f(x(t))\|^{\gamma}\dot{x}(t)+\beta\nabla^{2}f(x(t))\dot{x}(t)+\nabla
f(x(t))=0.$

Thus, its inertial version

$\ddot{x}(t)+\|\nabla
f(x(t))\|^{\gamma}\dot{x}(t)+\beta\nabla^{2}f(x(t))\dot{x}(t)+\nabla
f(x(t))=0$

falls within the framework of our study with the damping equal to a closed-
loop control of the norm of the gradient. The techniques developed in ARS  are
particularly useful for studying the well-posedness of dynamics with implicit
features.

b) Although significantly different, our approach has several points in common
with the article by Lin and Jordan LJ . In this article, the authors study the
closed-loop dynamical system

$\begin{cases}\dot{y}\left(t\right)+\dot{\tau}\left(t\right)\nabla
f\left(x\left(t\right)\right)&=0\vspace{1mm}\\\
\dot{x}\left(t\right)+\frac{\dot{\tau}\left(t\right)}{\tau\left(t\right)}\left(x\left(t\right)-y\left(t\right)\right)+\frac{\left[\dot{\tau}\left(t\right)\right]^{2}}{\tau\left(t\right)}\nabla
f\left(x\left(t\right)\right)&=0\vspace{1mm}\\\
\tau\left(t\right)-\dfrac{1}{4}\left(\int_{0}^{t}\sqrt{\lambda\left(r\right)}dr+c\right)^{2}&=0\vspace{1mm}\\\
\left[\lambda\left(t\right)\right]^{p}\left\lVert\nabla
f\left(x\left(t\right)\right)\right\rVert^{p-1}&=\theta,\end{cases}$ (17)

where $c>0$ and $0<\theta<1$. The corresponding second-order in time damped
inertial system writes as follows

$\ddot{x}(t)+\dfrac{2\left[\dot{\tau}(t)\right]^{2}-\tau(t)\ddot{\tau}(t)}{\tau(t)\dot{\tau}(t)}\dot{x}(t)+\dfrac{\left[\dot{\tau}(t)\right]^{2}}{\tau(t)}\nabla^{2}f\left(x(t)\right)\dot{x}(t)+\frac{\dot{\tau}(t)(\dot{\tau}(t)+\ddot{\tau}(t))}{\tau(t)}\nabla
f\left(x(t)\right)=0.$ (18)

In the above system, the Hessian driven damping comes in an explicit way
because of the structure of the first equation which differs from the
structure of the continuous steepest descent. In contrast, in our approach,
the first equation is the rescaled continuous steepest descent, and the
Hessian driven damping comes implicitly. Let us highlight some advantages of
our approach.

$\bullet$ Our system is introduced in a natural way by using the time scaling
and averaging method. This makes unnecessary to perform a Lyapunov analysis
for the inertial system. It has already been done for the continuous steepest
descent. This results in a significantly simplified mathematical analysis.

$\bullet$ Our dynamic model contains an additional parameter $q$ which, when
$q=2$, gives the setting of Lin and Jordan, and which, when judiciously tuned,
gives better convergence rates.

$\bullet$ Our approach provides the weak convergence of the trajectories to
optimal solutions.

We shall return later to the precise comparison between the two systems.

c) In ABC , Attouch, Boţ and Csetnek study the convergence properties of the
Autonomous Damped Inertial Gradient Equation

$\mbox{\rm(ADIGE)}\qquad\ddot{x}(t)+\mathcal{G}\Big{(}\dot{x}(t),\nabla
f({x}(t)),\nabla^{2}f({x}(t))\Big{)}+\nabla f(x(t))=0,$

where the damping term $\mathcal{G}\Big{(}\dot{x}(t),\nabla
f(x(t)),\nabla^{2}f({x}(t))\Big{)}$ acts as a closed-loop control. They pay
particular attention to the role played by the parameter $r>1$ in the
asymptotic convergence analysis of the dynamic

$\ddot{x}(t)+\|\dot{x}(t)\|^{r-2}\dot{x}(t)+\nabla f(x(t))=0.$

They show that the case $r=2$ separates the weak damping ($r>2$) from the
strong damping ($r<2$), hence the importance of this case. These questions
have also been considered by Haraux and Jendoubi in HJ .

d) In Song , Song, Jiang, and Ma develop an interesting technique for
accelerating high-order algorithms under general Hölder continuity assumption.
Their continuous-time framework reduces to an inertial system without Hessian-
driven damping in the first-order setting, which has been proven to be an
inaccurate surrogate. Although underlying their approach, the acceleration via
time scaling, the averaging technique, and the closed-loop tuning of the
coefficients are not clearly identified.

###  1.4 Organization of the paper

After a general presentation of the article in the introduction, we provide in
Section 2 a general estimate of the time scaling for the continuous steepest
descent when it is defined in a closed-loop way. This is crucial for the rest
of the paper. Then we specialize these results to situations of particular
interest, and examine in details the case of closed-loop systems induced
respectively by velocities, and then by gradients. In Section 3, which is the
main part of the paper, we develop the next important step in our approach,
which is the averaging operation. This provides accelerated damped inertial
dynamics that are autonomous and with fast convergence properties. Finally, in
Section 4 we analyze the fast convergence properties of proximal algorithms
which come naturally from the temporal discretization of the continuous
dynamics.

##  2 Closed-loop time scaling of the steepest descent

###  2.1 Formulation of the closed-loop time scaling

Given $t_{0}\geq 0,\,q>0$, and $p\geq 1$, the time scale function
$\tau\colon\left[t_{0},+\infty\right[\to{\mathbb{R}}_{++}$ is defined by

$\begin{cases}\dot{y}\left(t\right)+\dot{\tau}\left(t\right)\nabla
f\left(y\left(t\right)\right)&=0\vspace{1mm}\\\
\tau\left(t\right)-\dfrac{1}{q^{q}}\left(t_{0}+\displaystyle\int_{t_{0}}^{t}\left[\lambda\left(r\right)\right]^{\frac{1}{q}}dr\right)^{q}&=0\vspace{1mm}\\\
\left[\lambda\left(t\right)\right]^{p}\left[{\mathcal{G}}\left(y\left(t\right)\right)\right]^{p-1}&=1,\end{cases}$
(19)

where ${\mathcal{G}}(\cdot)$ is a given positive, continuous function that
depends on the information of the trajectory $y(\cdot)$. This general
formalism allows us to unify the various situations coming from different
choices of the time scaling as a feedback control of the state of the system.
For example ${\mathcal{G}}$ may be a function of
$y,\dot{y},f\left(y\right),\nabla f\left(y\right)$ and/or any mixture
combination of them. Then the function $\lambda(\cdot)$ is continuous and it
links the coefficient of $\nabla f$, namely $\dot{\tau}(\cdot)$, with the
solution trajectory $y(\cdot)$.
As a useful result, note that for every $t\geq t_{0}$, it holds

$\displaystyle\dot{\tau}\left(t\right)$ $\displaystyle=$
$\displaystyle\dfrac{1}{q^{q-1}}\left(\displaystyle\int_{t_{0}}^{t}\left[\lambda\left(r\right)\right]^{\frac{1}{q}}dr+t_{0}\right)^{q-1}\left[\lambda\left(t\right)\right]^{\frac{1}{q}}$
(20) $\displaystyle=$
$\displaystyle\left[\tau\left(t\right)\right]^{\frac{q-1}{q}}\left[\lambda\left(t\right)\right]^{\frac{1}{q}}>0.$

Moreover, the relations (19) allow us to cover the open-loop case. In
particular, when $p=1$ it holds $\lambda\left(t\right)=1$ for every $t\geq
t_{0}$. This yields for every $q>0$

$\tau\left(t\right)=\left(\dfrac{t}{q}\right)^{q}.$

Taking further $q:=1$, then $\tau\left(t\right)$ becomes the _regular time_ in
variable $t$, namely $\tau\left(t\right)=t$ for every $t\geq t_{0}$.
Let us specify the interpretation of (19) as a steepest descent dynamic which
is rescaled in time in a closed-loop way.

###### Proposition 1

Suppose that $f\colon{\mathcal{H}}\to{\mathbb{R}}$ satisfies $(\mathcal{A})$.
Let $t_{0}\geq 0,\,q>0$, $p\geq 1$ and
$y\colon\left[t_{0},+\infty\right[\to{\mathcal{H}}$ be a solution trajectory
of the system (19). Suppose that

$\lim_{s\to+\infty}\tau\left(s\right)=+\infty.$

Then $y(\cdot)$ is a solution trajectory of a time rescaled continuous
steepest descent (SD), as described below:
Let $s_{0}=\tau\left(t_{0}\right)$ and
$z\colon\left[s_{0},+\infty\right[\to{\mathcal{H}}$ be a solution trajectory
of the following system

$\dot{z}\left(s\right)+\nabla f\left(z\left(s\right)\right)=0.$ (21)

Then we have

$y\left(t\right)=z\left(\tau\left(t\right)\right)\qquad\forall t\geq t_{0},$

and there exists a continuously differentiable function
$\sigma\colon\left[s_{0},+\infty\right[\to{\mathbb{R}}_{++}$ such that

$z\left(s\right)=y\left(\sigma\left(s\right)\right)\qquad\forall s\geq s_{0}.$

###### Proof

We already interpreted how to go from a solution trajectory $z(\cdot)$ of (SD)
to the closed-loop system above via the time scaling function $\tau(\cdot)$.
Let us now show the reverse direction. Let
$y\colon\left[t_{0},+\infty\right[\to{\mathcal{H}}$ be a solution trajectory
of (19). We have that $\lambda$ is continuous and positive on
$\left[t_{0},+\infty\right[$, therefore $\tau$ is a monotonically increasing
function, hence injective. On the other hand, we have
$t_{0}=\tau\left(t_{0}\right)=\left(\frac{t_{0}}{q}\right)^{q}$. Since by
assumption $\lim_{t\to+\infty}\tau\left(t\right)=+\infty$, this means $\tau$
is a continuous function whose image contains $\left[s_{0},+\infty\right[$,
hence surjective. Combining these premises, we have shown that $\tau$ is a
bijection, which means it is invertible.

Set $\sigma\equiv\tau^{-1}$ and make the change of time variable
$t:=\sigma\left(s\right)$ in (19). Let us define

$z\left(s\right)=y\left(\sigma\left(s\right)\right)=y\left(\tau^{-1}\left(s\right)\right).$

Then by the chain rule, we have

$\dot{z}\left(s\right)=\dot{y}\left(\tau^{-1}\left(s\right)\right)\dfrac{1}{\dot{\tau}\left(\tau^{-1}\left(s\right)\right)}=\dot{y}\left(\sigma\left(s\right)\right)\dfrac{1}{\dot{\tau}\left(\sigma\left(s\right)\right)}.$

This leads to

$\dot{z}\left(s\right)+\nabla f\left(z\left(s\right)\right)=0.$

In other words, $z\colon\left[s_{0},+\infty\right[\to{\mathcal{H}}$ is a
solution trajectory of (SD). ∎

The above assertion allows us to transfer the convergence results of (SD) to
some closed-loop systems. In particular, given a time scaling function
$\tau(\cdot)$ as described above, by making the change of time variable
$s:=\tau\left(t\right)$, we obtain the following results from Theorem 7.1 in
the appendix applied to the unperturbed continuous steepest descent system.

$\displaystyle\displaystyle{\int_{t_{0}}^{+\infty}}\dfrac{\tau\left(t\right)}{\dot{\tau}\left(t\right)}\left\lVert\dot{y}\left(t\right)\right\rVert^{2}dt<+\infty,$
(22)
$\displaystyle\displaystyle{\int_{t_{0}}^{+\infty}}\tau\left(t\right)\dot{\tau}\left(t\right)\left\lVert\nabla
f\left(y\left(t\right)\right)\right\rVert^{2}dt<+\infty,$ (23) $\displaystyle
f(y(t))-\inf_{{\mathcal{H}}}f=o\left(\dfrac{1}{\tau(t)}\right)\textrm{ as
}t\to+\infty,$ (24) $\displaystyle\left\lVert\nabla
f\left(y\left(t\right)\right)\right\rVert=o\left(\dfrac{1}{\tau(t)}\right)\textrm{
as }t\to+\infty.$ (25)

###  2.2 Lower bound estimate of the time scaling $\tau(t)$

As key ingredient of our approach, the next step is to establish a lower bound
for $\tau(t)$ in terms of $t$. This will reflect the acceleration of our
dynamic via time scaling and allow us to achieve fast convergence rates. For
this, we will need the following technical lemma, which can be seen as a
nonlinear Gronwall result.

###### Lemma 1

Suppose that there exists $C_{0}>0$ and $b>a\geq 0$ such that

$\int_{t_{0}}^{t}\left[\tau\left(r\right)\right]^{a}\left[\lambda\left(r\right)\right]^{-b}dr\leq
C_{0}<+\infty\quad\forall t\geq t_{0}.$ (26)

Then there exists $C_{1}>0$ such that

$\tau\left(t\right)\geq
C_{1}\left(t-t_{0}\right)^{\frac{qb+1}{b-a}}\quad\forall t\geq t_{0}.$ (27)

###### Proof

Let $t\geq t_{0}$ be fixed. By applying the Hölder inequality, we get

$\displaystyle\int_{t_{0}}^{t}\left[\tau\left(r\right)\right]^{\frac{a}{qb+1}}dr$
$\displaystyle\leq\left(\int_{t_{0}}^{t}\left[\tau\left(r\right)\right]^{a}\left[\lambda\left(r\right)\right]^{-b}dr\right)^{\frac{1}{qb+1}}\left(\int_{t_{0}}^{t}\left[\lambda\left(r\right)\right]^{\frac{1}{q}}dr\right)^{\frac{qb}{qb+1}}$
$\displaystyle\leq
C_{0}^{\frac{1}{qb+1}}\left(t_{0}+\int_{t_{0}}^{t}\left[\lambda\left(r\right)\right]^{\frac{1}{q}}dr\right)^{\frac{qb}{qb+1}}=\left(C_{0}q^{qb}\right)^{\frac{1}{qb+1}}\left[\tau\left(t\right)\right]^{\frac{b}{qb+1}}.$
(28)

If $a=0$ then (27) follows immediately. From now on suppose that $a>0$, so
that the inequality (28) can be rewritten as

$\int_{t_{0}}^{t}\left[\tau\left(r\right)\right]^{\frac{a}{qb+1}}dr\leq\left(C_{0}q^{qb}\right)^{\frac{1}{qb+1}}\left(\left[\tau\left(t\right)\right]^{\frac{a}{qb+1}}\right)^{\frac{b}{a}}$
(29)

The arguments are now adapted from LJ , which is inspired by the proof of
Bihari-LaSalle inequality. Let

$C_{q,b}:=\left(C_{0}q^{qb}\right)^{\frac{1}{qb+1}}>0\qquad\textrm{ and
}\qquad
A\left(t\right):=\int_{t_{0}}^{t}\left[\tau\left(r\right)\right]^{\frac{a}{qb+1}}dr\qquad\forall
t\geq t_{0},$

so that (29) becomes

$A\left(t\right)\leq
C_{q,b}\left[\dot{A}\left(t\right)\right]^{\frac{b}{a}}\quad\forall t\geq
t_{0}$

or, equivalently,

$C_{q,b}^{-\frac{a}{b}}\leq\left[A\left(t\right)\right]^{-\frac{a}{b}}\dot{A}\left(t\right)\quad\forall
t\geq t_{0}.$

Integrating from $t_{0}$ to $t$, we obtain

$\displaystyle C_{q,b}^{-\frac{a}{b}}\left(t-t_{0}\right)$
$\displaystyle\leq\left(1-\dfrac{a}{b}\right)\left[\left[A\left(t\right)\right]^{1-\frac{a}{b}}-\left[A\left(t_{0}\right)\right]^{1-\frac{1}{b}}\right]$
$\displaystyle\leq\left[A\left(t\right)\right]^{1-\frac{a}{b}}\leq\left[C_{q,b}\left[\tau\left(t\right)\right]^{\frac{b}{qb+1}}\right]^{1-\frac{a}{b}}$
$\displaystyle=C_{q,b}^{\frac{b-a}{b}}\left[\tau\left(t\right)\right]^{\frac{b-a}{qb+1}},$

where the last inequality comes from (28). Since $b>a$, the conclusion
follows. ∎

Let us now particularize our results to some model situations.

###  2.3 Closed-loop control of (SD) via the velocity

###### Theorem 2.1

Suppose that $f\colon{\mathcal{H}}\to{\mathbb{R}}$ satisfies $(\mathcal{A})$.
Let $q>0$, $p\geq 1$ and $y\colon\left[t_{0},+\infty\right[\to{\mathcal{H}}$
be a solution trajectory of the following system

$\begin{cases}\dot{y}\left(t\right)+\dot{\tau}\left(t\right)\nabla
f\left(y\left(t\right)\right)&=0\vspace{1mm}\\\
\tau\left(t\right)-\dfrac{1}{q^{q}}\left(t_{0}+\displaystyle\int_{t_{0}}^{t}\left[\lambda\left(r\right)\right]^{\frac{1}{q}}dr\right)^{q}&=0\vspace{1mm}\\\
\left[\lambda\left(t\right)\right]^{p}\left\lVert\dot{y}\left(t\right)\right\rVert^{p-1}&=1.\end{cases}$
(30)

Then the following statements are satisfied:

  1. $(i)$

(convergence of values)
$f\left(y\left(t\right)\right)-\inf_{{\mathcal{H}}}f=o\left(t^{-\left(1+q-\frac{1}{p}\right)}\right)\textrm{
as }t\to+\infty.$

  2. $(ii)$

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

  3. $(iii)$

(integral estimate of the velocities)
$\displaystyle{\int_{t_{0}}^{+\infty}}t^{\left(1+\frac{1}{q}-\frac{1}{pq}\right)}\left\lVert\dot{y}\left(t\right)\right\rVert^{2+\frac{p-1}{pq}}dt<+\infty.$

  4. $(iv)$

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

###### Proof

When $p=1$, we recover the open loop case with the time scaling function
$\tau(t)=\left(\frac{t}{q}\right)^{q}$. The result is a direct consequence of
Theorem 7.1. Therefore, from now on we only consider the case $p>1$. Recall
that from (22) we have

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

By using successively the definition of $\lambda$, and relation (20), we
obtain

$\dfrac{\tau\left(t\right)}{\dot{\tau}\left(t\right)}\left\lVert\dot{y}\left(t\right)\right\rVert^{2}=\dfrac{\tau\left(t\right)}{\dot{\tau}\left(t\right)}\left[\lambda\left(t\right)\right]^{-\frac{2p}{p-1}}=\left[\tau\left(t\right)\right]^{\frac{1}{q}}\left[\lambda\left(t\right)\right]^{-\frac{1}{q}-\frac{2p}{p-1}}\quad\forall
t\geq t_{0}.$

According to the two above results we get

$\int_{t_{0}}^{+\infty}\left[\tau\left(r\right)\right]^{\frac{1}{q}}\left[\lambda\left(r\right)\right]^{-\frac{1}{q}-\frac{2p}{p-1}}dr<+\infty.$

We are now in position to apply Lemma 1 with $p>1$, $a:=\frac{1}{q}$ and
$b:=\frac{1}{q}+\frac{2p}{p-1}$. We have

$\dfrac{qb+1}{b-a}=\dfrac{2+\frac{2pq}{p-1}}{\frac{2p}{p-1}}=\dfrac{p-1+pq}{p}=1+q-\dfrac{1}{p},$

and therefore there exists some constant $C_{1}>0$ such that

$\tau\left(t\right)\geq
C_{1}\left(t-t_{0}\right)^{1+q-\frac{1}{p}}\quad\forall t\geq t_{0}.$ (32)

This leads to $\lim_{t\to+\infty}\tau\left(t\right)=+\infty$. Therefore,
according to Proposition 1, we can extract the results from Theorem 7.1 and
the corresponding formulas (22), (23), (24). Specifically, we obtain

$(i)$ for the values

$\displaystyle f\left(y\left(t\right)\right)-\inf_{{\mathcal{H}}}f$
$\displaystyle=$ $\displaystyle
o\left(\frac{1}{\tau(t)}\right)=o\left(\frac{1}{t^{1+q-\frac{1}{p}}}\right),$

$(ii)$ for the gradients

$\displaystyle\left\lVert\nabla f\left(y\left(t\right)\right)\right\rVert$
$\displaystyle=$ $\displaystyle
o\left(\dfrac{1}{\tau(t)}\right)=o\left(\frac{1}{t^{1+q-\frac{1}{p}}}\right).$

$(iii)$ for the velocities: we start from (31), i.e.
$\int_{t_{0}}^{+\infty}\dfrac{\tau\left(t\right)}{\dot{\tau}\left(t\right)}\left\lVert\dot{y}\left(t\right)\right\rVert^{2}dt<+\infty,$
that we evaluate as follows:

$\displaystyle\dfrac{\tau\left(t\right)}{\dot{\tau}\left(t\right)}\left\lVert\dot{y}\left(t\right)\right\rVert^{2}$
$\displaystyle=$
$\displaystyle\frac{\tau(t)}{\tau(t)^{\frac{q-1}{q}}\lambda(t)^{\frac{1}{q}}}\left\lVert\dot{y}\left(t\right)\right\rVert^{2}$
$\displaystyle=$
$\displaystyle\frac{\tau(t)^{\frac{1}{q}}}{\lambda(t)^{\frac{1}{q}}}\left\lVert\dot{y}\left(t\right)\right\rVert^{2}$
$\displaystyle=$
$\displaystyle\tau(t)^{\frac{1}{q}}\left\lVert\dot{y}\left(t\right)\right\rVert^{2+\frac{p-1}{pq}}\quad\forall
t\geq t_{0}.$

According to (32) we deduce that

$\displaystyle{\int_{t_{0}}^{+\infty}}t^{\left(1+\frac{1}{q}-\frac{1}{pq}\right)}\left\lVert\dot{y}\left(t\right)\right\rVert^{2+\frac{p-1}{pq}}dt<+\infty.$

$(iv)$ Let us finally examine the convergence of the solution trajectories. We
know that the solution trajectory of the continuous steepest descent converges
weakly when $t\to+\infty$, and its limit belong to
$S=\operatorname{argmin}_{{\mathcal{H}}}f\neq\emptyset$; see Theorem 7.1 in
appendix. With our notation we therefore have that $z(s)$ converges weakly
when $s\to+\infty$. Since $\tau(t)\to+\infty$ as $t\to+\infty$, we immediately
deduce that $y(t)=z(\tau(t)$ converges weakly as $t\to+\infty$, and its limit
belong to $S=\operatorname{argmin}_{{\mathcal{H}}}f\neq\emptyset$. This
completes the proof. ∎

###  2.4 Closed-loop control of (SD) via the norm of gradient

We develop an analysis parallel to that of the previous section, replacing
speed control with gradient control.

###### Theorem 2.2

Suppose that $f\colon{\mathcal{H}}\to{\mathbb{R}}$ satisfies $(\mathcal{A})$.
Let $q\geq\frac{1}{2}$, $p\geq 1$ and
$y\colon\left[t_{0},+\infty\right[\to{\mathcal{H}}$ be a solution trajectory
of the following system

$\begin{cases}\dot{y}\left(t\right)+\dot{\tau}\left(t\right)\nabla
f\left(y\left(t\right)\right)&=0\vspace{1mm}\\\
\tau\left(t\right)-\dfrac{1}{q^{q}}\left(t_{0}+\displaystyle\int_{t_{0}}^{t}\left[\lambda\left(r\right)\right]^{\frac{1}{q}}dr\right)^{q}&=0\vspace{1mm}\\\
\left[\lambda\left(t\right)\right]^{p}\left\lVert\nabla
f\left(y\left(t\right)\right)\right\rVert^{p-1}&=1.\end{cases}$ (33)

Then the following statements are satisfied:

  1. $(i)$

(convergence of values)
$f\left(y\left(t\right)\right)-\inf_{{\mathcal{H}}}f=o\left(t^{-pq}\right)\textrm{
as }t\to+\infty.$

  2. $(ii)$

(convergence of gradients towards zero) $\left\lVert\nabla
f\left(y\left(t\right)\right)\right\rVert=o\left(t^{-pq}\right)\textrm{ as
}t\to+\infty.$

  3. $(iii)$

(integral estimate of the gradients)
$\displaystyle{\int_{t_{0}}^{+\infty}}t^{pq\left(2-\frac{1}{q}\right)}\left\lVert\nabla
f\left(y\left(t\right)\right)\right\rVert^{2+\frac{p-1}{pq}}dt<+\infty.$

  4. $(iv)$

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

###### Proof

Again, we only consider the case $p>1$. We know from (23) that

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

By using successively the definition of $\lambda$, and the relation (20), we
obtain

$\tau\left(t\right)\dot{\tau}\left(t\right)\left\lVert\nabla
f\left(y\left(t\right)\right)\right\rVert^{2}=\tau\left(t\right)\dot{\tau}\left(t\right)\left[\lambda\left(t\right)\right]^{-\frac{2p}{p-1}}=\left[\tau\left(t\right)\right]^{2-\frac{1}{q}}\left[\lambda\left(t\right)\right]^{\frac{1}{q}-\frac{2p}{p-1}}\quad\forall
t\geq t_{0}.$

Therefore

$\int_{t_{0}}^{+\infty}\left[\tau\left(t\right)\right]^{2-\frac{1}{q}}\left[\lambda\left(t\right)\right]^{\frac{1}{q}-\frac{2p}{p-1}}dt<+\infty.$

Let us apply Lemma 1 with $a:=2-\frac{1}{q}$ and
$b=\frac{2p}{p-1}-\frac{1}{q}$. We have $b>a$, $a\geq 0$ for
$q\geq\frac{1}{2}$, and

$\dfrac{qb+1}{b-a}=\dfrac{\frac{2pq}{p-1}}{\frac{2p}{p-1}-2}=pq.$

Therefore

$\tau\left(t\right)\geq C_{1}\left(t-t_{0}\right)^{pq}\quad\forall t\geq
t_{0}.$ (34)

This gives $\lim_{t\to+\infty}\tau\left(t\right)=+\infty$. According to
Proposition 1, we can extract the results from Theorem 7.1 and the
corresponding formulas (22), (23), (24). Specifically, we obtain

$(i)$ for the values

$\displaystyle f\left(y\left(t\right)\right)-\inf_{{\mathcal{H}}}f$
$\displaystyle=$ $\displaystyle
o\left(\frac{1}{\tau(t)}\right)=o\left(\frac{1}{t^{pq}}\right);$

$(ii)$ for the gradients

$\displaystyle\left\lVert\nabla f\left(y\left(t\right)\right)\right\rVert$
$\displaystyle=$ $\displaystyle
o\left(\dfrac{1}{\tau(t)}\right)=o\left(t^{-pq}\right);$

$(iii)$ for the integral estimate of the gradients: we start from (31)

$\int_{t_{0}}^{+\infty}\tau\left(t\right)\dot{\tau}\left(t\right)\left\lVert\nabla
f\left(y\left(t\right)\right)\right\rVert^{2}dt<+\infty,$

that we evaluate as follows:

$\displaystyle\tau\left(t\right)\dot{\tau}\left(t\right)\left\lVert\nabla
f\left(y\left(t\right)\right)\right\rVert^{2}$ $\displaystyle=$
$\displaystyle\tau\left(t\right)\left[\tau\left(t\right)\right]^{\frac{q-1}{q}}\left[\lambda\left(t\right)\right]^{\frac{1}{q}}\left\lVert\nabla
f\left(y\left(t\right)\right)\right\rVert^{2}$ $\displaystyle=$
$\displaystyle\tau(t)^{2-\frac{1}{q}}\lambda(t)^{\frac{1}{q}}\left\lVert\nabla
f\left(y\left(t\right)\right)\right\rVert^{2}$ $\displaystyle=$
$\displaystyle\tau(t)^{2-\frac{1}{q}}\left\lVert\nabla
f(y(t))\right\rVert^{2-\frac{p-1}{pq}}\quad\forall t\geq t_{0}.$

According to (34) we deduce that

$\displaystyle{\int_{t_{0}}^{+\infty}}t^{pq\left(2-\frac{1}{q}\right)}\left\lVert\nabla
f\left(y\left(t\right)\right)\right\rVert^{2+\frac{p-1}{pq}}dt<+\infty.$

$(iv)$ The convergence of the solution trajectory follows from an argument
similar to that of the previous section. This completes the proof. ∎

###### Remark 1

a) We thus achieved our first goal which was to accelerate the convergence
properties of the continuous steepest descent using closed-loop time scaling.
For example, concerning the convergence rate of the values, we passed from the
convergence rate $1/t$ for the steepest descent to
$1/t^{\left(1+q-\frac{1}{p}\right)}$ when the closed-loop control acts on the
velocity, and $1/t^{pq}$ in the case of the gradient. Clearly, by playing with
the parameters $p$ and $q$ we can get arbitrary fast convergence results. The
same observation holds for the convergence of the gradients towards zero.

b) By introducing a time scale function $\tau(\cdot)$ which grows faster than
the identity (i.e. $\tau(t)\geq t$) either in open-loop or closed-loop, we
have thus accelerated the continuous steepest descent dynamic. The price to
pay is that we no longer have an autonomous dynamic in (4), with as major
drawback the fact that the coefficient in front of the gradient term tends
towards infinity as $t\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.

##  3 Accelerated gradient systems with closed-loop control of the damping

###  3.1 General results concerning time scale and averaging

We will prove the following general result which puts forward a damped
inertial dynamics which comes by time scale and averaging of the continuous
steepest descent. Then we will specialize it and consider time scale obtained
in a closed-loop way, and thus cover the two model situations.

###### Theorem 3.1

Suppose that $f\colon{\mathcal{H}}\to{\mathbb{R}}$ satisfies $(\mathcal{A})$.
Let $\gamma>1$, and let $\tau:[t_{0},+\infty[\to\mathbb{R}_{++}$ be an
increasing function, continuously differentiable, such that
$\lim_{t\to+\infty}\tau(t)=+\infty$. Let
$x\colon\left[t_{0},+\infty\right[\to{\mathcal{H}}$ be a solution trajectory
of the following second-order differential equation

$\ddot{x}(t)+\frac{(1+\gamma)\dot{\tau}(t)^{2}-\tau(t)\ddot{\tau}(t)}{\tau(t)\dot{\tau}(t)}\dot{x}(t)+\gamma\frac{\dot{\tau}(t)^{2}}{\tau(t)}\nabla
f\left(x(t)+\dfrac{1}{\gamma}\frac{\tau(t)}{\dot{\tau}(t)}\dot{x}(t)\right)=0.$
(35)

Then we have the convergence rate of the values: as $t\to+\infty$

$f\left(x(t)\right)-\inf_{{\mathcal{H}}}f=o\left(\dfrac{1}{\tau\left(t\right)}\right),$
(36)

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

###### Proof

a) We first interpret $x$ as coming from the time scale and averaging of the
continuous steepest descent. We start from $y(\cdot)$ solution of

$\dot{y}\left(t\right)+\dot{\tau}\left(t\right)\nabla
f\left(y\left(t\right)\right)=0.$ (37)

According to the time scale analysis developed in (5) we have

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

This means there exists a positive function $\varepsilon$ which satisfies
$\lim_{t\to+\infty}\varepsilon\left(t\right)=0$ and

$f\left(y\left(t\right)\right)-\inf_{{\mathcal{H}}}f=\dfrac{\varepsilon\left(t\right)}{\tau\left(t\right)}\quad\forall
t\geq t_{0}.$ (38)

Let us define the time averaging process as the transformation from $y$ to $x$
according to the formula

$\dot{x}(t)+\gamma\frac{\dot{\tau}(t)}{\tau(t)}x(t)=\gamma\frac{\dot{\tau}(t)}{\tau(t)}y(t),$
(39)

where $\gamma>1$. Equivalently

$y(t)=x(t)+\dfrac{1}{\gamma}\frac{\tau(t)}{\dot{\tau}(t)}\dot{x}(t).$ (40)

By derivating $y(\cdot)$ we get

$\dot{y}\left(t\right)=\dot{x}\left(t\right)+\dfrac{1}{\gamma}\frac{\tau(t)}{\dot{\tau}(t)}\ddot{x}(t)+\dfrac{1}{\gamma}\frac{\dot{\tau}(t)^{2}-\tau(t)\ddot{\tau}(t)}{\dot{\tau}(t)^{2}}\dot{x}(t).$
(41)

Replacing $\dot{y}\left(t\right)$ by this expression in the constitutive
rescaled steepest descent equation (37), we get

$\dot{x}\left(t\right)+\dfrac{1}{\gamma}\frac{\tau(t)}{\dot{\tau}(t)}\ddot{x}(t)+\dfrac{1}{\gamma}\frac{\dot{\tau}(t)^{2}-\tau(t)\ddot{\tau}(t)}{\dot{\tau}(t)^{2}}\dot{x}(t)+\dot{\tau}\left(t\right)\nabla
f\left(x(t)+\dfrac{1}{\gamma}\frac{\tau(t)}{\dot{\tau}(t)}\dot{x}(t)\right)=0.$

Equivalently

$\dfrac{1}{\gamma}\frac{\tau(t)}{\dot{\tau}(t)}\ddot{x}(t)+\frac{(1+\gamma)\dot{\tau}(t)^{2}-\tau(t)\ddot{\tau}(t)}{\gamma\dot{\tau}(t)^{2}}\dot{x}(t)+\dot{\tau}\left(t\right)\nabla
f\left(x(t)+\dfrac{1}{\gamma}\frac{\tau(t)}{\dot{\tau}(t)}\dot{x}(t)\right)=0.$

After multiplication by $\gamma\frac{\dot{\tau}(t)}{\tau(t)}$ we get

$\ddot{x}(t)+\frac{(1+\gamma)\dot{\tau}(t)^{2}-\tau(t)\ddot{\tau}(t)}{\tau(t)\dot{\tau}(t)}\dot{x}(t)+\gamma\frac{\dot{\tau}(t)^{2}}{\tau(t)}\nabla
f\left(x(t)+\dfrac{1}{\gamma}\frac{\tau(t)}{\dot{\tau}(t)}\dot{x}(t)\right)=0.$
(42)

b) Let us now come to the corresponding estimate of the convergence rates with
$x(t)$ instead of $y(t)$. The idea is to express $x$ as an average of $y$, and
then conclude thanks to Jensen’s inequality. Set

$\displaystyle b(t)$ $\displaystyle=$
$\displaystyle\frac{\dot{\tau}(t)}{\tau(t)}\geq 0$ (43) $\displaystyle B(t)$
$\displaystyle=$
$\displaystyle\int_{t_{0}}^{t}b(u)du=\int_{t_{0}}^{t}\frac{\dot{\tau}(u)}{\tau(u)}du=\ln\left(\frac{\tau(t)}{\tau(t_{0})}\right).$
(44)

Therefore

$e^{B(t)}=\frac{\tau(t)}{\tau(t_{0})}.$ (45)

In order to express $x$ in terms of $y$, we need to integrate the first-order
linear differential equation (39) which is written equivalently as follows

$\dot{x}(t)+\gamma b(t)x(t)=\gamma b(t)y(t).$

After multiplying by $e^{\gamma B(t)}$, we get equivalently

$e^{\gamma B(t)}\dot{x}(t)+\gamma b(t)e^{\gamma B(t)}x(t)=\gamma b(t)e^{\gamma
B(t)}y(t),$

that is,

$\dfrac{d}{dt}\left(e^{\gamma B(t)}x(t)\right)=\gamma b(t)e^{\gamma
B(t)}y(t).$

After integration we get

$e^{\gamma B(t)}x(t)=e^{\gamma
B(t_{0})}x(t_{0})+\gamma\int_{t_{0}}^{t}b(u)e^{\gamma B(u)}y(u)du.$

According to $e^{\gamma B(t_{0})}=e^{0}=1$ we get

$\displaystyle x(t)$ $\displaystyle=$ $\displaystyle e^{-\gamma
B(t)}x(t_{0})+\gamma e^{-\gamma B(t)}\int_{t_{0}}^{t}b(u)e^{\gamma
B(u)}y(u))du$ (46) $\displaystyle=$ $\displaystyle e^{-\gamma
B(t)}y(t_{0})+\gamma e^{-\gamma B(t)}\int_{t_{0}}^{t}b(u)e^{\gamma
B(u)}y(u)du,$

where the last equality follows from the choice of the Cauchy data
$y(t_{0})=x(t_{0})$. Then, observe that $x(t)$ can be simply written as
follows

$x(t)=\int_{t_{0}}^{t}y(u)\,d\mu_{t}(u),$ (47)

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

$\mu_{t}=e^{-\gamma B(t)}\delta_{t_{0}}+\gamma
b(u)e^{\gamma\left(B(u)-B(t)\right)}du.$ (48)

Precisely, in (48), $\delta_{t_{0}}$ is the Dirac measure at $t_{0}$, and
$b(u)e^{B(u)-B(t)}du$ is the measure with density $b(u)e^{B(u)-B(t)}$ with
respect to the Lebesgue measure on $[t_{0},t]$. According to

$\gamma e^{-\gamma B(t)}\int_{t_{0}}^{t}b(u)e^{\gamma B(u)}du=1-e^{-\gamma
B(t)},$

we have that $\mu_{t}$ is a positive Radon measure on $[t_{0},t]$ whose total
mass is equal to $1$. It is therefore a probability measure, and $x(t)$ is
obtained by averaging the trajectory $y(\cdot)$ on $[t_{0},t]$ with respect to
$\mu_{t}$. From there, let us show how to deduce fast convergence properties
for the so defined trajectory $x(\cdot)$. According to the convexity of $f$,
and Jensen’s inequality, we deduce that

$\displaystyle
f\left(\int_{t_{0}}^{t}y(u)\,d\mu_{t}(u)\right)-\inf_{{\mathcal{H}}}f$
$\displaystyle=$
$\displaystyle(f-\inf_{{\mathcal{H}}}f)\left(\int_{t_{0}}^{t}y(u)d\mu_{t}(u)\right)$
$\displaystyle\leq$
$\displaystyle\int_{t_{0}}^{t}\left(f(y(u))-\inf_{{\mathcal{H}}}f\right)d\mu_{t}(u)$
$\displaystyle=$
$\displaystyle\int_{t_{0}}^{t}\dfrac{\varepsilon\left(u\right)}{\tau\left(u\right)}d\mu_{t}(u),$

where the last inequality above comes from (38). According to the definition
of $\mu_{t}$ (see (48)) and the formulation of $x(t)$ (see (47)), we deduce
that

$\displaystyle f\left(x(t)\right)-\inf_{{\mathcal{H}}}f$ $\displaystyle\leq$
$\displaystyle\dfrac{\varepsilon\left(t_{0}\right)}{\tau\left(t_{0}\right)}e^{-\gamma
B(t)}+\gamma e^{-\gamma
B(t)}\int_{t_{0}}^{t}\dfrac{\varepsilon\left(u\right)}{\tau\left(u\right)}b(u)e^{\gamma
B(u)}du.$

Equivalently,

$\tau\left(t\right)\left(f\left(x(t)\right)-\inf_{{\mathcal{H}}}f\right)\leq\varepsilon\left(t_{0}\right)\left(\dfrac{\tau\left(t\right)}{\tau\left(t_{0}\right)}\right)^{1-\gamma}+\gamma\tau\left(t\right)e^{-\gamma
B(t)}\int_{t_{0}}^{t}\dfrac{\varepsilon\left(u\right)}{\tau\left(u\right)}b(u)e^{\gamma
B(u)}du.$ (49)

Since $\gamma>1$ and $\lim_{t\to+\infty}\tau(t)=+\infty$, it holds

$\limsup_{t\to+\infty}\tau\left(t\right)\left(f\left(x(t)\right)-\inf_{{\mathcal{H}}}f\right)\leq\gamma\limsup_{t\to+\infty}\tau\left(t\right)e^{-\gamma
B(t)}\int_{t_{0}}^{t}\dfrac{\varepsilon\left(u\right)}{\tau\left(u\right)}b(u)e^{\gamma
B(u)}du.$

It is therefore enough to show that

$\limsup_{t\to+\infty}\left(\gamma\tau\left(t\right)e^{-\gamma
B(t)}\int_{t_{0}}^{t}\dfrac{\varepsilon\left(u\right)}{\tau\left(u\right)}b(u)e^{\gamma
B(u)}du\right)\leq 0.$

In order to prepare for integration by parts, note that

$\gamma b(u)e^{\gamma B(u)}=\frac{d}{du}\left(e^{\gamma B(u)}\right)\textrm{
and
}\dfrac{\dot{\tau}\left(u\right)}{\left[\tau\left(u\right)\right]^{2-\gamma}}=\dfrac{d}{du}\left(\dfrac{1}{\gamma-1}\dfrac{1}{\left[\tau\left(t\right)\right]^{1-\gamma}}\right).$

Given an arbitrary $\eta>0$ we consider $T_{\eta}>t_{0}$ such that
$\varepsilon\left(u\right)\leq\eta$ for every $u\geq T_{\eta}$. Therefore, for
every $t\geq T_{\eta}$, by integration by parts and by taking into
consideration the relations (43)-(45), we get

$\displaystyle\gamma\tau\left(t\right)e^{-\gamma
B(t)}\int_{t_{0}}^{t}\dfrac{\varepsilon\left(u\right)}{\tau\left(u\right)}b(u)e^{\gamma
B(u)}du$ $\displaystyle=\ $ $\displaystyle\gamma\tau\left(t\right)e^{-\gamma
B(t)}\left(\int_{t_{0}}^{T_{\eta}}\dfrac{\varepsilon\left(u\right)}{\tau\left(u\right)}b(u)e^{\gamma
B(u)}du+\int_{T_{\eta}}^{t}\dfrac{\varepsilon\left(u\right)}{\tau\left(u\right)}b(u)e^{\gamma
B(u)}du\right)$ $\displaystyle\leq\ $
$\displaystyle\tau\left(t\right)e^{-\gamma
B(t)}\left(\gamma\int_{t_{0}}^{T_{\eta}}\dfrac{\varepsilon\left(u\right)}{\tau\left(u\right)}b(u)e^{\gamma
B(u)}du+\eta\gamma\int_{T_{\eta}}^{t}\dfrac{1}{\tau\left(u\right)}b(u)e^{\gamma
B(u)}du\right)$ $\displaystyle=\ $ $\displaystyle\tau\left(t\right)e^{-\gamma
B(t)}\left(\gamma\int_{t_{0}}^{T_{\eta}}\dfrac{\varepsilon\left(u\right)}{\tau\left(u\right)}b(u)e^{\gamma
B(u)}du+\dfrac{\eta}{\tau\left(t\right)}e^{\gamma
B(t)}-\dfrac{\eta}{\tau\left(T_{\eta}\right)}e^{\gamma
B(T_{\eta})}+\eta\int_{T_{\eta}}^{t}\dfrac{\dot{\tau}\left(u\right)}{\left[\tau\left(u\right)\right]^{2}}e^{\gamma
B(u)}du\right)$ $\displaystyle=\ $ $\displaystyle\tau\left(t\right)e^{-\gamma
B(t)}\left(\gamma\int_{t_{0}}^{T_{\eta}}\dfrac{\varepsilon\left(u\right)}{\tau\left(u\right)}b(u)e^{\gamma
B(u)}du+\dfrac{\eta}{\tau\left(t\right)}e^{\gamma
B(t)}-\dfrac{\eta}{\tau\left(T_{\eta}\right)}e^{\gamma
B(T_{\eta})}+\dfrac{\eta}{\left[\tau\left(t_{0}\right)\right]^{\gamma}}\int_{T_{\eta}}^{t}\dfrac{\dot{\tau}\left(u\right)}{\left[\tau\left(u\right)\right]^{2-\gamma}}du\right)$
$\displaystyle=\ $ $\displaystyle\tau\left(t\right)e^{-\gamma
B(t)}\left(\gamma\int_{t_{0}}^{T_{\eta}}\dfrac{\varepsilon\left(u\right)}{\tau\left(u\right)}b(u)e^{\gamma
B(u)}du+\dfrac{\eta}{\tau\left(t\right)}e^{\gamma
B(t)}-\dfrac{\eta}{\tau\left(T_{\eta}\right)}e^{\gamma
B(T_{\eta})}+\dfrac{\eta\left[\tau\left(t_{0}\right)\right]^{-\gamma}}{\gamma-1}\left(\dfrac{1}{\left[\tau\left(t\right)\right]^{1-\gamma}}-\dfrac{1}{\left[\tau\left(T_{\eta}\right)\right]^{1-\gamma}}\right)\right)$
$\displaystyle\leq\ $
$\displaystyle\left(\gamma\int_{t_{0}}^{T_{\eta}}\dfrac{\varepsilon\left(u\right)}{\tau\left(u\right)}b(u)e^{\gamma
B(u)}du\right)\tau\left(t\right)e^{-\gamma B(t)}+\eta+\dfrac{\eta}{\gamma-1}$
$\displaystyle\leq\ $ $\displaystyle
C\left[\tau\left(t\right)\right]^{1-\gamma}+\dfrac{\eta\gamma}{\gamma-1}.$

Since $\lim_{t\to+\infty}\tau(t)=+\infty$, and $\gamma>1$, we obtain

$\limsup_{t\to+\infty}\left(\gamma\tau\left(t\right)e^{-\gamma
B(t)}\int_{t_{0}}^{t}\dfrac{\varepsilon\left(u\right)}{\tau\left(u\right)}b(u)e^{\gamma
B(u)}du\right)\leq\dfrac{\eta\gamma}{\gamma-1}.$ (50)

This being true for every $\eta>0$, we infer

$f\left(x(t)\right)-\inf_{{\mathcal{H}}}f=o\left(\dfrac{1}{\tau\left(t\right)}\right).$
(51)

c) For trajectories convergence, we take advantage of the fact that the
solution trajectory $z\left(\cdot\right)$ of the continuous steepest descent
converges weakly towards a solution $x_{*}\in S$. Since
$\lim_{t\to+\infty}\tau(t)=+\infty$, this immediately implies that
$y(t)=z(\tau(t))$ converges weakly to $x_{*}$ as $s\to+\infty$. In other
words, for each $v\in{\mathcal{H}}$

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

To pass from the convergence of $y$ to that of $x$, we use the interpretation
of $x$ as an average of $y$. The convergence then results from the general
property which says that convergence entails ergodic convergence. Let us make
this precise. Using again that $\lim_{t\to+\infty}\tau(t)=+\infty$, we have

$x(t)\sim\gamma e^{-\gamma
B\left(t\right)}\int_{t_{0}}^{t}b\left(u\right)e^{\gamma
B\left(u\right)}y\left(u\right)du=\frac{\gamma}{\left[\tau(t)\right]^{\gamma}}\int_{t_{0}}^{t}\dot{\tau}\left(u\right)\left[\tau(u)\right]^{\gamma-1}y(u)du.$

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

$A(t)=\frac{\gamma}{\left[\tau(t)\right]^{\gamma}}\int_{t_{0}}^{t}\dot{\tau}\left(u\right)\left[\tau(u)\right]^{\gamma-1}a(u)du.$

Given an arbitrary $\eta>0$, let us take $T_{\eta}$ such that $t_{0}<T_{\eta}$
and $a(u)\leq\eta$ for $u\geq T_{\eta}$. For $t>T_{\eta}$, we have

$\displaystyle A(t)$ $\displaystyle=$
$\displaystyle\frac{\gamma}{\left[\tau(t)\right]^{\gamma}}\int_{t_{0}}^{T_{\eta}}\dot{\tau}\left(u\right)\left[\tau(u)\right]^{\gamma-1}a(u)du+\frac{\gamma}{\left[\tau(t)\right]^{\gamma}}\int_{T_{\eta}}^{t}\dot{\tau}\left(u\right)\left[\tau(u)\right]^{\gamma-1}a(u)du$
$\displaystyle\leq$
$\displaystyle\frac{\gamma}{\left[\tau(t)\right]^{\gamma}}\int_{t_{0}}^{T_{\eta}}\dot{\tau}\left(u\right)\left[\tau(u)\right]^{\gamma-1}a(u)du+\eta\tau(t_{0}).$

Letting $t$ converge to $+\infty$ we get

$\limsup_{t\to+\infty}A(t)\leq\eta\tau(t_{0}).$

This being true for any $\eta>0$, we infer that $\lim_{t\to+\infty}A(t)=0$,
which completes the proof. ∎

###### Remark 2

By taking $\gamma:=\frac{\alpha-1}{2}$ and
$\tau\left(t\right):=\frac{t^{2}}{2\left(\alpha-1\right)}$, equation (42)
becomes (see ABN )

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

We have $\gamma>1\Longleftrightarrow\alpha>3$, which is in accordance with the
convergence results attached to Nesterov method.

###  3.2 Damped inertial system via closed-loop control of the velocity

Let us now examine the model situation where the time scaling is defined in a
closed-loop way as a feedback control of the velocity. Completing this
construction with the averaging process, as described as above, we get that
$(x,y)\colon\left[t_{0},+\infty\right[\to{\mathcal{H}}\times{\mathcal{H}}$ is
a solution trajectory of the following algebraic-differential system

$\begin{cases}\dot{y}\left(t\right)+\dot{\tau}\left(t\right)\nabla
f\left(y\left(t\right)\right)&=0\vspace{2mm}\\\
\dot{x}(t)+\gamma\dfrac{\dot{\tau}(t)}{\tau(t)}x(t)-\gamma\dfrac{\dot{\tau}(t)}{\tau(t)}y(t)&=0\vspace{2mm}\\\
\tau\left(t\right)-\dfrac{1}{q^{q}}\left(t_{0}+\displaystyle\int_{t_{0}}^{t}\left[\lambda\left(r\right)\right]^{\frac{1}{q}}dr\right)^{q}&=0\vspace{2mm}\\\
\left[\lambda\left(t\right)\right]^{p}\left\lVert\dot{y}\left(t\right)\right\rVert^{p-1}&=1.\end{cases}$
(52)

By specializing Theorem 3.1 to this situation we get the following result.

###### Theorem 3.2

Suppose that $f\colon{\mathcal{H}}\to{\mathbb{R}}$ satisfies $(\mathcal{A})$.
Let $q>0$, $p\geq 1$, $\gamma>1$ and
$x\colon\left[t_{0},+\infty\right[\to{\mathcal{H}}$ be a solution trajectory
of the following system

$\begin{cases}\ddot{x}(t)+\dfrac{(1+\gamma)\dot{\tau}(t)^{2}-\tau(t)\ddot{\tau}(t)}{\tau(t)\dot{\tau}(t)}\dot{x}(t)+\gamma\frac{\dot{\tau}(t)^{2}}{\tau(t)}\nabla
f\left(x(t)+\dfrac{1}{\gamma}\dfrac{\tau(t)}{\dot{\tau}(t)}\dot{x}(t)\right)&=0\vspace{2mm}\\\
\tau\left(t\right)-\dfrac{1}{q^{q}}\left(t_{0}+\displaystyle\int_{t_{0}}^{t}\left[\lambda\left(r\right)\right]^{\frac{1}{q}}dr\right)^{q}&=0\vspace{2mm}\\\
\left[\lambda\left(t\right)\right]^{p}\left\lvert\dot{\tau}\left(t\right)\right\rvert^{p-1}\left\lVert\nabla
f\left(x\left(t\right)+\dfrac{1}{\gamma}\dfrac{\tau(t)}{\dot{\tau}(t)}\dot{x}\left(t\right)\right)\right\rVert^{p-1}&=1.\end{cases}$
(53)

Then we have the fast convergence of values: as $t\to+\infty$

$f(x(t))-\inf_{{\mathcal{H}}}f=o\left(\dfrac{1}{t^{1+q-\frac{1}{p}}}\right).$
(54)

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

###### Proof

We showed in the proof of Theorem 3.1 how to pass from (52) to (53).
Conversely, let $x(\cdot)$ be a solution trajectory of the damped inertial
dynamic (53). Let us show that by setting

$y\left(t\right)=\dfrac{1}{\gamma}\dfrac{\tau\left(t\right)}{\dot{\tau}\left(t\right)}\dot{x}\left(t\right)+x\left(t\right),$

then
$(x,y)\colon\left[t_{0},+\infty\right[\to{\mathcal{H}}\times{\mathcal{H}}$ is
a solution trajectory of

$\begin{cases}\dot{y}\left(t\right)+\dot{\tau}\left(t\right)\nabla
f\left(y\left(t\right)\right)&=0\vspace{2mm}\\\
\dot{x}(t)+\gamma\dfrac{\dot{\tau}(t)}{\tau(t)}x(t)-\gamma\dfrac{\dot{\tau}(t)}{\tau(t)}y(t)&=0\vspace{2mm}\\\
\tau\left(t\right)-\dfrac{1}{q^{q}}\left(t_{0}+\displaystyle\int_{t_{0}}^{t}\left[\lambda\left(r\right)\right]^{\frac{1}{q}}dr\right)^{q}&=0\vspace{2mm}\\\
\left[\lambda\left(t\right)\right]^{p}\left\lVert\dot{y}\left(t\right)\right\rVert^{p-1}&=1.\end{cases}$
(55)

Indeed, by taking the time derivative of $y(\cdot)$, as given by the second
equation of (55), we get

$\displaystyle\dot{y}\left(t\right)$
$\displaystyle=\dfrac{1}{\gamma}\dfrac{\tau\left(t\right)}{\dot{\tau}\left(t\right)}\ddot{x}\left(t\right)+\dfrac{1}{\gamma}\left(1+\gamma-\dfrac{\tau\left(t\right)\ddot{\tau}\left(t\right)}{\left[\dot{\tau}\left(t\right)\right]^{2}}\right)\dot{x}\left(t\right)$
$\displaystyle=\dfrac{1}{\gamma}\dfrac{\tau\left(t\right)}{\dot{\tau}\left(t\right)}\left(\ddot{x}\left(t\right)+\dfrac{\left(1+\gamma\right)\left[\dot{\tau}(t)\right]^{2}-\tau(t)\ddot{\tau}(t)}{\tau(t)\dot{\tau}(t)}\dot{x}(t)\right)$
$\displaystyle=-\dot{\tau}\left(t\right)\nabla
f\left(x\left(t\right)+\dfrac{1}{\gamma}\dfrac{\tau\left(t\right)}{\dot{\tau}\left(t\right)}\dot{x}\left(t\right)\right)=-\dot{\tau}\left(t\right)\nabla
f\left(y\left(t\right)\right).$

This gives the first equation in (55) and

$\left[\lambda\left(t\right)\right]^{p}\left\lVert\dot{y}\left(t\right)\right\rVert^{p-1}=\left[\lambda\left(t\right)\right]^{p}\left\lvert\dot{\tau}\left(t\right)\right\rvert^{p-1}\left\lVert\nabla
f\left(x\left(t\right)+\dfrac{1}{\gamma}\dfrac{\tau\left(t\right)}{\dot{\tau}\left(t\right)}\dot{x}\left(t\right)\right)\right\rVert^{p-1}=1.$

This shows the equivalence of the two systems. According to Theorem 2.1, and
formula (32), there exists a constant $C_{1}>0$ such that

$\tau\left(t\right)\geq C_{1}\left(t-t_{0}\right)^{1+q-\frac{1}{p}}.$ (56)

Therefore $\lim_{t\to+\infty}\tau(t)=+\infty$. According to Theorem 3.1 we
deduce

$f\left(x(t)\right)-\inf_{{\mathcal{H}}}f=o\left(\dfrac{1}{t^{1+q-\frac{1}{p}}}\right),$
(57)

and the convergence of the trajectory. ∎

###  3.3 Damped inertial system via closed-loop control of the gradient

We proceed in parallel to the previous section to obtain the following result.

###### Theorem 3.3

Suppose that $f\colon{\mathcal{H}}\to{\mathbb{R}}$ satisfies $(\mathcal{A})$.
Let $q>0$, $p\geq 1$, $\gamma>1$, and
$x\colon\left[t_{0},+\infty\right[\to{\mathcal{H}}$ be a solution trajectory
of the following system

$\begin{cases}\ddot{x}(t)+\dfrac{(1+\gamma)\dot{\tau}(t)^{2}-\tau(t)\ddot{\tau}(t)}{\tau(t)\dot{\tau}(t)}\dot{x}(t)+\gamma\frac{\dot{\tau}(t)^{2}}{\tau(t)}\nabla
f\left(x(t)+\dfrac{1}{\gamma}\frac{\tau(t)}{\dot{\tau}(t)}\dot{x}(t)\right)&=0\vspace{2mm}\\\
\tau\left(t\right)-\dfrac{1}{q^{q}}\left(t_{0}+\displaystyle\int_{t_{0}}^{t}\left[\lambda\left(r\right)\right]^{\frac{1}{q}}dr\right)^{q}&=0\vspace{2mm}\\\
\left[\lambda\left(t\right)\right]^{p}\left\lVert\nabla
f\left(x\left(t\right)+\dfrac{1}{\gamma}\dfrac{\tau\left(t\right)}{\dot{\tau}\left(t\right)}\dot{x}\left(t\right)\right)\right\rVert^{p-1}&=1.\end{cases}$
(58)

Then we have the fast convergence of values: as $t\to+\infty$

$f(x(t))-\inf_{{\mathcal{H}}}f=o\left(\dfrac{1}{t^{pq}}\right).$ (59)

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

###### Proof

Let $x(\cdot)$ be a solution trajectory of the damped inertial dynamic (58).
Let us show show that by setting

$y\left(t\right)=\dfrac{1}{\gamma}\dfrac{\tau\left(t\right)}{\dot{\tau}\left(t\right)}\dot{x}\left(t\right)+x\left(t\right),$

then
$(x,y)\colon\left[t_{0},+\infty\right[\to{\mathcal{H}}\times{\mathcal{H}}$ is
a solution trajectory of

$\begin{cases}\dot{y}\left(t\right)+\dot{\tau}\left(t\right)\nabla
f\left(y\left(t\right)\right)&=0\vspace{2mm}\\\
\dot{x}(t)+\gamma\dfrac{\dot{\tau}(t)}{\tau(t)}x(t)-\gamma\dfrac{\dot{\tau}(t)}{\tau(t)}y(t)&=0\vspace{2mm}\\\
\tau\left(t\right)-\dfrac{1}{q^{q}}\left(t_{0}+\displaystyle\int_{t_{0}}^{t}\left[\lambda\left(r\right)\right]^{\frac{1}{q}}dr\right)^{q}&=0\vspace{2mm}\\\
\left[\lambda\left(t\right)\right]^{p}\left\lVert\nabla
f\left(y\left(t\right)\right)\right\rVert^{p-1}&=1.\end{cases}$ (60)

Indeed, by the same argument as for the velocity case, we get

$\dot{y}\left(t\right)=-\dot{\tau}\left(t\right)\nabla
f\left(y\left(t\right)\right).$

This gives the first equation in (60) and

$\left[\lambda\left(t\right)\right]^{p}\left\lVert\nabla
f({y}\left(t\right))\right\rVert^{p-1}=\left[\lambda\left(t\right)\right]^{p}\left\lVert\nabla
f\left(x\left(t\right)+\dfrac{1}{\gamma}\dfrac{\tau\left(t\right)}{\dot{\tau}\left(t\right)}\dot{x}\left(t\right)\right)\right\rVert^{p-1}=1.$

This shows the equivalence of the two systems. According to Theorem 2.2, and
formula (34), there exists a constant $C_{1}>0$ such that

$\tau\left(t\right)\geq C_{1}\left(t-t_{0}\right)^{pq}.$ (61)

Therefore from Theorem 3.1 we deduce, as $t\to+\infty$

$f\left(x(t)\right)-\inf_{{\mathcal{H}}}f=o\left(\dfrac{1}{t^{pq}}\right),$
(62)

and the convergence of the trajectory. ∎

###  3.4 Comparison with the Lin-Jordan approach

In LJ , the authors study the second-order closed-loop dynamical system

$\begin{cases}\ddot{x}\left(t\right)+\left(\dfrac{2\dot{\tau}\left(t\right)}{\tau\left(t\right)}-\dfrac{\ddot{\tau}\left(t\right)}{\dot{\tau}\left(t\right)}\right)\dot{x}\left(t\right)+\dfrac{\left[\dot{\tau}\left(t\right)\right]^{2}}{\tau\left(t\right)}\nabla^{2}f\left(x\left(t\right)\right)\dot{x}\left(t\right)+\dfrac{\dot{\tau}\left(t\right)\left[\dot{\tau}\left(t\right)+\ddot{\tau}\left(t\right)\right]}{\tau\left(t\right)}\nabla
f\left(x\left(t\right)\right)&=0\vspace{2mm}\\\
\tau\left(t\right)-\dfrac{1}{4}\left(\int_{0}^{t}\sqrt{\lambda\left(t\right)}dr+c\right)^{2}&=0\vspace{2mm}\\\
\left[\lambda\left(t\right)\right]^{p}\left\lVert\nabla
f\left(x\left(t\right)\right)\right\rVert^{p-1}&=\theta,\end{cases}$ (63)

whose first-order reformulation reads

$\begin{cases}\dot{y}\left(t\right)+\dot{\tau}\left(t\right)\nabla
f\left(x\left(t\right)\right)&=0\vspace{1mm}\\\
\dot{x}\left(t\right)+\frac{\dot{\tau}\left(t\right)}{\tau\left(t\right)}\left(x\left(t\right)-y\left(t\right)\right)+\frac{\left[\dot{\tau}\left(t\right)\right]^{2}}{\tau\left(t\right)}\nabla
f\left(x\left(t\right)\right)&=0\vspace{1mm}\\\
\tau\left(t\right)-\dfrac{1}{4}\left(\int_{0}^{t}\sqrt{\lambda\left(t\right)}dr+c\right)^{2}&=0\vspace{1mm}\\\
\left[\lambda\left(t\right)\right]^{p}\left\lVert\nabla
f\left(x\left(t\right)\right)\right\rVert^{p-1}&=\theta,\end{cases}$ (64)

where $c>0$ and $0<\theta<1$ are given parameters. See also LJ-MOR  for some
extensions to monotone inclusions.

a) In LJ , the authors obtained the following convergence rate of function
values

$f\left(x\left(t\right)\right)-\inf_{{\mathcal{H}}}f={\mathcal{O}}\left(\frac{1}{t^{\frac{3p+1}{2}}}\right)\textrm{
as }t\to+\infty.$

Note that the last two equations in (64) are nothing else than those in (33)
with $q:=2$.
For comparison, in our approach the convergence rate of the values obtained in
Theorem 3.3 when $q=2$ is

$f\left(x\left(t\right)\right)-\inf_{{\mathcal{H}}}f=o\left(\frac{1}{t^{2p}}\right)$

which is better for every $p>1$.

b) Let us now compare the convergence estimates of the gradients. In LJ , the
authors obtain the integral estimate

$\displaystyle{\int_{t_{0}}^{+\infty}}t^{\frac{3p+1}{2}}\left\lVert\nabla
f\left(x\left(t\right)\right)\right\rVert^{\frac{p+1}{p}}dt<+\infty,$

which leads to

$\inf_{t_{0}\leq\sigma\leq t}\left\lVert\nabla
f\left(x\left(\sigma\right)\right)\right\rVert={\mathcal{O}}\left(t^{-\frac{3p}{2}}\right)\textrm{
as }t\to+\infty.$

In our approach, the right variable to consider is $y(t)$, instead of $x(t)$.
According to (23) we have

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

Since $q=2$, according to (20) we have

$\dot{\tau}\left(t\right)=\left[\tau\left(t\right)\right]^{\frac{1}{2}}\left[\lambda\left(t\right)\right]^{\frac{1}{2}}.$

Therefore

$\displaystyle\tau\left(t\right)\dot{\tau}\left(t\right)\left\lVert\nabla
f\left(y\left(t\right)\right)\right\rVert^{2}$ $\displaystyle=$
$\displaystyle\tau\left(t\right)^{\frac{3}{2}}\left[\lambda\left(t\right)\right]^{\frac{1}{2}}\left\lVert\nabla
f\left(y\left(t\right)\right)\right\rVert^{2}=\tau\left(t\right)^{\frac{3}{2}}\left\lVert\nabla
f\left(y\left(t\right)\right)\right\rVert^{2-\frac{p-1}{2p}}.$

Since $\tau(t)\geq Ct^{2p}$, we deduce that

$\int_{t_{0}}^{+\infty}t^{3p}\left\lVert\nabla
f\left(y\left(t\right)\right)\right\rVert^{\frac{3p+1}{2p}}dt<+\infty.$

which leads to

$\inf_{t_{0}\leq\sigma\leq t}\left\lVert\nabla
f\left(y\left(\sigma\right)\right)\right\rVert={\mathcal{O}}\left(t^{-2p}\right)\textrm{
as }t\to+\infty.$

Again, our approach gives a better convergence rate than LJ . Let us also
specify that our analysis provides the convergence of the trajectories, which
is an open question for LJ . Moreover, since our approach is consistent with
the steepest continuous descent, it can naturally be extended to the non-
smooth case, and to the case of cocoercive operators, as it was done in the
open-loop case in ABN .

###  3.5 The limiting case $\gamma=1$

Our previous results are valid under the assumption $\gamma>1$. It is a
natural question to examine the limiting case $\gamma=1$. Close examination of
the proof of the theorem reveals a slight change in the integration procedure
and a logarithm factor appears. The corresponding result obtained is written
as follows.

###### Theorem 3.4

Suppose that $f\colon{\mathcal{H}}\to{\mathbb{R}}$ satisfies $(\mathcal{A})$.
Let $x\colon\left[t_{0},+\infty\right[\to{\mathcal{H}}$ be a solution
trajectory of the following second-order differential equation

$\ddot{x}(t)+\dfrac{2\left[\dot{\tau}(t)\right]^{2}-\tau(t)\ddot{\tau}(t)}{\tau(t)\dot{\tau}(t)}\dot{x}(t)+\dfrac{\left[\dot{\tau}(t)\right]^{2}}{\tau(t)}\nabla
f\left(x(t)+\dfrac{\tau(t)}{\dot{\tau}(t)}\dot{x}(t)\right)=0$ (65)

where $\tau:\left[t_{0},+\infty\right[\to\mathbb{R}_{++}$ is an increasing
function, continuously differentiable, and satisfying
$\lim_{t\to+\infty}\tau(t)=+\infty$. Then we have the convergence rate of the
values: as $t\to+\infty$

$f\left(x(t)\right)-\inf_{{\mathcal{H}}}f=o\left(\dfrac{\ln\left(\tau\left(t\right)\right)}{\tau\left(t\right)}\right),$
(66)

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

Suppose moreover that there exists some $\theta>0$ and $C_{1}>0$ such that for
$t$ sufficiently large

$(\mathcal{A})_{\rm asymp}\qquad\tau(t)\geq
C_{1}\left(t-t_{0}\right)^{\theta}.$ (67)

Then we have the fast convergence of values: as $t\to+\infty$

$f\left(x(t)\right)-\inf_{{\mathcal{H}}}f=o\left(\dfrac{\ln\left(t\right)}{t^{\theta}}\right).$
(68)

When specialized to the closed-loop control of the velocity, we obtain

$f\left(x(t)\right)-\inf_{{\mathcal{H}}}f=o\left(\dfrac{\ln\left(t\right)}{t^{1+q-\frac{1}{p}}}\right),$
(69)

and in the case of the closed-loop control of the gradient

$f\left(x(t)\right)-\inf_{{\mathcal{H}}}f=o\left(\dfrac{\ln\left(t\right)}{t^{pq}}\right).$
(70)

So, the convergence rates are a little less good because of the logarithm
term.

##  4 Associated proximal algorithms

###  4.1 A proximal-explicit discretization

In the following, we present a numerical approach based on a _proximal-
explicit_ temporal discretization of the closed-loop systems investigated in
this paper. By proximal-explicit we mean that the function $f$ is evaluated
using a proximal step while the step size sequence
$\left(\lambda_{k}\right)_{k\geq 0}$ and the time scaling sequence
$\left(\tau_{k}\right)_{k\geq 0}$ are computed explicitly. This makes our
numerical scheme much easier implementable than the numerical algorithm
proposed in LJ  as well as the large-step A HPE approach by Monteiro and
Svaiter MS  which are in fact approximations of a _proximal-implicit_ discrete
time method. We restrict ourselves to the case $q=1$, which gives
$\dot{\tau}\left(t\right)=\lambda\left(t\right)$. In this case, the continuous
time closed-loop dynamical system is written as follows

$\begin{cases}\dot{y}\left(t\right)+\lambda\left(t\right)\nabla
f\left(y\left(t\right)\right)&=0\vspace{2mm}\\\
\left[\lambda\left(t\right)\right]^{p}\left[{\mathcal{G}}\left(y\left(t\right)\right)\right]^{p-1}&=1.\end{cases}$
(71)

Let us describe the general structure of the algorithm which is obtained by a
proximal-explicit discretization of the continuous system (71).

Given $y_{k},y_{k-1}$ in ${\mathcal{H}}$, we first define $\lambda_{k}$ by

$\left[\lambda_{k}\right]^{p}\left[{\mathcal{G}}\left(y_{k},y_{k-1}\right)\right]^{p-1}=1.$

and consider then an implicit finite difference scheme for the first equation
of (71)

$y_{k+1}-y_{k}+\lambda_{k}\nabla f\left(y_{k+1}\right)=0.$ (72)

This gives the following algorithm, called PEAS for Proximal Explicit
Algorithm with Adaptive Step Size.

1

Input: $y_{0}\neq y_{-1}\in{\mathcal{H}}$

2 for  _$k=0,1,\cdots$_ do

3
$\lambda_{k}:=\left[{\mathcal{G}}\left(y_{k},y_{k-1}\right)\right]^{-\frac{p-1}{p}}$

4 $y_{k+1}:=\operatorname{prox}_{\lambda_{k}f}\left(y_{k}\right)$

5 end for

Algorithm 1 Proximal-explicit algorithm with adaptive step size (PEAS)

Note that $\left(\lambda_{k}\right)_{k\geq 0}$ is computed explicitly in terms
of $\left(y_{k}\right)_{k\geq 0}$. In other words, the definition of the
sequence $\left(\lambda_{k}\right)_{k\geq 0}$ is decoupled from the
computation of $\left(y_{k}\right)_{k\geq 0}$. This is different from the
method in LJ , which ultimately leads to the large-step A HPE approach by
Monteiro and Svaiter in MS .

Let us now specify the link between $\lambda_{k}$ and $\tau_{k}$. We start
from the relation (recall that we take $q=1$)

$\dot{\tau}\left(t\right)=\lambda\left(t\right).$ (73)

Then, for every $k\geq 0$ we discretize (73) as follows

$\tau_{k+1}-\tau_{k}=\lambda_{k}\Longleftrightarrow\tau_{k+1}=\lambda_{k}+\tau_{k}$
(74)

with the convention $\lambda_{0}:=t_{0}$ and $\tau_{0}:=0$, which then yields
$\tau_{k}=\sum_{i=0}^{k-1}\lambda_{i}.$

Drawing inspiration from continuous analysis, we will first show that the
function value $f\left(y_{k}\right)-\inf_{{\mathcal{H}}}f$ attains the
$o\left(\frac{1}{\tau_{k+1}}\right)$ rate of convergence, and the sequence
$\left(y_{k}\right)_{k\geq 0}$ converges weakly to a solution. Then, as a
crucial result, we will derive a lower bound of $\tau_{k+1}$ in terms of $k$.

The following result emphasizes that the rate of convergence and summability
results holds for $\left(y_{k}\right)_{k\geq 0}$ for arbitrary step sizes
$\lambda_{k}$ that satisfy $\sum_{k\geq 0}\lambda_{k}=+\infty$. The proof is
an adaptation of (ABN, , Theorem 4.1).

###### Theorem 4.1

Let $y_{0}\in{\mathcal{H}}$, $\left(\lambda_{k}\right)_{k\geq 0}$ be a given
positive sequence satisfying $\displaystyle{\sum_{k\geq
0}\lambda_{k}=+\infty}$, $\tau_{0}=0$ and
$\tau_{k}=\sum_{i=0}^{k-1}\lambda_{i}$ for every $k\geq 1$. Then for any
sequence $\left(y_{k}\right)_{k\geq 0}$ generated by the proximal algorithm

$y_{k+1}:=\operatorname{prox}_{\lambda_{k}f}\left(y_{k}\right)\quad\forall
k\geq 0,$ (75)

the following properties are satisfied:

  1. $(i)$

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

  2. $(ii)$

(summability of gradients) $\displaystyle{\sum_{k\geq
0}\tau_{k}\lambda_{k}\left\lVert\nabla
f\left(y_{k+1}\right)\right\rVert^{2}<+\infty};$

  3. $(iii)$

(summability of velocities) $\displaystyle{\sum_{k\geq
0}\dfrac{\tau_{k}}{\lambda_{k}}\left\lVert
y_{k+1}-y_{k}\right\rVert^{2}<+\infty};$

  4. $(iv)$

(convergence of function values)
$\displaystyle{f\left(y_{k+1}\right)-\inf_{{\mathcal{H}}}f=o\left(\frac{1}{\tau_{k+1}}\right)}$
as $k\to+\infty;$

  5. $(v)$

(convergence of gradient) $\displaystyle{\left\lVert\nabla
f\left(y_{k+1}\right)\right\rVert=o\left(\frac{1}{\sqrt{\sum_{l=0}^{k}\tau_{l}\lambda_{l}}}\right)}$
as $k\to+\infty;$

  6. $(vi)$

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
(72) and the 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}-\lambda_{k}\left\langle y_{k+1}-z_{*},\nabla
f\left(y_{k+1}\right)\right\rangle-\dfrac{1}{2}\lambda_{k}^{2}\left\lVert\nabla
f\left(y_{k+1}\right)\right\rVert^{2}$
$\displaystyle\leq\dfrac{1}{2}\left\lVert
y_{k}-z_{*}\right\rVert^{2}-\lambda_{k}\left(f\left(y_{k+1}\right)-\inf_{{\mathcal{H}}}f\right)-\dfrac{1}{2}\lambda_{k}^{2}\left\lVert\nabla
f\left(y_{k+1}\right)\right\rVert^{2}.$ (76)

Statement $(i)$ follows from (BaCo, , 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.

On the other hand, the sequence
$\left(f\left(y_{k}\right)-\inf_{{\mathcal{H}}}f\right)_{k\geq 0}$ is
nonincreasing. Precisely, we have for every $k\geq 0$

$\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\nabla
f\left(y_{k+1}\right),y_{k}-y_{k+1}\rangle=\lambda_{k}\left\lVert\nabla
f\left(y_{k+1}\right)\right\rVert^{2}\geq 0.$ (77)

According to (AC2, , Lemma 22) we get

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

which proves $(iv)$.

Let $k\geq 1$. Multiplying both sides of (77) by
$\tau_{k}=\sum_{i=0}^{k-1}\lambda_{i}>0$, then adding the result into (76), we
get

$\displaystyle\tau_{k+1}\left(f\left(y_{k+1}\right)-\inf_{{\mathcal{H}}}f\right)+\dfrac{1}{2}\left\lVert
y_{k+1}-z_{*}\right\rVert^{2}$
$\displaystyle\leq\tau_{k}\left(f\left(y_{k}\right)-\inf_{{\mathcal{H}}}f\right)+\dfrac{1}{2}\left\lVert
y_{k}-z_{*}\right\rVert^{2}$
$\displaystyle\qquad-\dfrac{1}{2}\lambda_{k}^{2}\left\lVert\nabla
f\left(y_{k+1}\right)\right\rVert^{2}-\tau_{k}\lambda_{k}\left\lVert\nabla
f\left(y_{k+1}\right)\right\rVert^{2}.$

This implies

$\sum_{k\geq 0}\lambda_{k}^{2}\left\lVert\nabla
f\left(y_{k+1}\right)\right\rVert^{2}<+\infty\quad\textrm{ and
}\quad\sum_{k\geq 1}\tau_{k}\lambda_{k}\left\lVert\nabla
f\left(y_{k+1}\right)\right\rVert^{2}<+\infty,$

which yields $(ii)$. From (72), we infer $(iii)$. To deduce $(v)$, it suffices
to show that the sequence $\left(\|\nabla f\left(y_{k}\right)\|\right)_{k\geq
0}$ is nonincreasing. Indeed, it follows from (75) and the cocoercivity of
$\nabla f$ that

$\displaystyle\dfrac{1}{2}\left\lVert\nabla
f\left(y_{k+1}\right)\right\rVert^{2}$
$\displaystyle=\dfrac{1}{2}\left\lVert\nabla
f\left(y_{k}\right)\right\rVert^{2}+\left\langle\nabla
f\left(y_{k+1}\right),\nabla f\left(y_{k+1}\right)-\nabla
f\left(y_{k}\right)\right\rangle-\dfrac{1}{2}\left\lVert\nabla
f\left(y_{k+1}\right)-\nabla f\left(y_{k}\right)\right\rVert^{2}$
$\displaystyle=\dfrac{1}{2}\left\lVert\nabla
f\left(y_{k}\right)\right\rVert^{2}-\dfrac{1}{\lambda_{k}}\left\langle
y_{k+1}-y_{k},\nabla f\left(y_{k+1}\right)-\nabla
f\left(y_{k}\right)\right\rangle-\dfrac{1}{2}\left\lVert\nabla
f\left(y_{k+1}\right)-\nabla f\left(y_{k}\right)\right\rVert^{2}$
$\displaystyle\leq\dfrac{1}{2}\left\lVert\nabla
f\left(y_{k}\right)\right\rVert^{2}.$

Taking into account also $(ii)$, we obtain $(v)$.

Finally, according to the assumption $\sum_{k\geq 0}\lambda_{k}=+\infty$, and
$(iv)$, we have that
$\lim_{k\to+\infty}f\left(y_{k}\right)=\inf_{{\mathcal{H}}}f$. Since $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$. ∎

Then, we give a statement which can be seen as a discrete counterpart of Lemma
1. The result is more complex not only because we are in the discrete setting,
but also because it allows an explicit choice of the stepsize, as we will see
later.

###### Lemma 2

Let $\left(\lambda_{k}\right)_{k\geq 0}$ be a positive sequence and
$\left(\tau_{k}\right)_{k\geq 0}$ such that $\tau_{0}=0$ and
$\tau_{k}=\sum_{i=0}^{k-1}\lambda_{i}$ for all $k\geq 1$. Suppose that there
exist $C_{2}>0$ and $a,b,c\geq 0$ such that $b+c>a$ and

$\sum_{k\geq 0}\tau_{k}^{a}\lambda_{k}^{-b}\lambda_{k+1}^{-c}\leq
C_{2}<+\infty$

Then there exists $C_{3}>0$ such that for every $k\geq 1$ it holds

$\tau_{k+1}\geq C_{3}k^{\frac{b+c+1}{b+c-a}}.$ (78)

###### Proof

By applying the Hölder inequality twice we get for all $k\geq 0$

$\displaystyle\sum_{i=0}^{k}\tau_{i}^{\frac{a}{b+c+1}}$
$\displaystyle\leq\left(\sum_{i=0}^{k}\tau_{i}^{a}\lambda_{i}^{-b}\lambda_{i+1}^{-c}\right)^{\frac{1}{b+c+1}}\left(\sum_{i=0}^{k}\lambda_{i}\right)^{\frac{b}{b+c+1}}\left(\sum_{i=0}^{k}\lambda_{i+1}\right)^{\frac{c}{b+c+1}}$
$\displaystyle\leq
C_{2}^{\frac{1}{b+c+1}}\left(\sum_{i=0}^{k+1}\lambda_{i}\right)^{\frac{b+c}{b+c+1}}=C_{2}^{\frac{1}{b+c+1}}\tau_{k+2}^{\frac{b+c}{b+c+1}}.$
(79)

If $a=0$ then (78) follows immediately. From now on we suppose that $a>0$.
Inequality (79) becomes

$\sum_{i=0}^{k}\tau_{i}^{\frac{a}{b+c+1}}\leq
C_{2}^{\frac{1}{b+c+1}}\left(\tau_{k+2}^{\frac{a}{b+c+1}}\right)^{\frac{b+c}{a}}\quad\forall
k\geq 0.$ (80)

Following the continuous counterpart, let us define

$C_{b+c}:=C_{2}^{\frac{1}{b+c+1}}>0\qquad\textrm{ and }\qquad
A_{k}:=\sum_{i=0}^{k}\tau_{i}^{\frac{a}{b+c+1}}\qquad\forall k\geq 0$

so that (80) becomes

$A_{k}\leq C_{b+c}\left(A_{k+2}-A_{k+1}\right)^{\frac{b+c}{a}}\quad\forall
k\geq 0.$

From here,

$C_{b+c}^{-\frac{a}{b+c}}\leq
A_{k}^{-\frac{a}{b+c}}\left(A_{k+2}-A_{k+1}\right)\quad\forall k\geq 1.$ (81)

For convenience, we define the following function
$\psi\colon{\mathbb{R}}_{++}\to{\mathbb{R}}_{++}$ as
$\psi\left(r\right):=r^{-\frac{a}{b+c}}$. It is clear that

$\dfrac{d}{dr}\left(\dfrac{b+c}{b+c-a}r^{1-\frac{a}{b+c}}\right)=\psi\left(r\right)\qquad\textrm{
and }\qquad\dot{\psi}\left(r\right)=-\dfrac{a}{b+c}r^{-\frac{a}{b+c}-1}<0.$

Since $\left(A_{k}\right)_{k\geq 0}$ is increasing, this means
$\psi\left(A_{k+2}\right)\leq\psi\left(r\right)\leq\psi(A_{k})$ for every
$A_{k}\leq r\leq A_{k+2}$.

Let $k\geq 1$ fixed. We consider two separate cases.

Then (81) leads to

$\displaystyle C_{b+c}^{-\frac{a}{b+c}}$ $\displaystyle\leq
A_{k}^{-\frac{a}{b+c}}\left(A_{k+2}-A_{k}\right)=\psi\left(A_{k}\right)\left(A_{k+2}-A_{k}\right)$
$\displaystyle\leq
2\psi\left(A_{k+2}\right)\left(A_{k+2}-A_{k}\right)=2\psi\left(A_{k+2}\right)\int_{A_{k}}^{A_{k+2}}1dr$
$\displaystyle\leq
2\int_{A_{k}}^{A_{k+2}}\psi\left(r\right)dr=2\dfrac{b+c}{b+c-a}\left(A_{k+2}^{1-\frac{a}{b+c}}-A_{k}^{1-\frac{a}{b+c}}\right).$

This is equivalent to $A_{k+2}>2^{\frac{b+c}{a}}A_{k}$. Since $b+c>a$, we can
deduce further

$A_{k+2}^{1-\frac{a}{b+c}}>2^{\frac{b+c}{a}-1}A_{k}^{1-\frac{a}{b+c}}.$

Consequently,

$A_{k+2}^{1-\frac{a}{b+c}}-A_{k}^{1-\frac{a}{b+c}}>\left(2^{\frac{b+c}{a}-1}-1\right)A_{k}^{1-\frac{a}{b+c}}\geq\left(2^{\frac{b+c}{a}-1}-1\right)A_{1}^{1-\frac{a}{b+c}},$

recall that the last inequality follows from the increasing property of
$\left(A_{k}\right)_{k\geq 1}$.

In conclusion, for every $k\geq 0$ we have

$A_{k+2}^{1-\frac{a}{b+c}}-A_{k}^{1-\frac{a}{b+c}}\geq
C_{4}:=\min\left\\{\frac{1}{2}\left(1-\dfrac{a}{b+c}\right)C_{b+c}^{-\frac{a}{b+c}},\left(2^{\frac{b+c}{a}-1}-1\right)A_{1}^{1-\frac{a}{b+c}},A_{2}^{1-\frac{a}{b+c}}\right\\}>0.$

Telescoping sum arguments combined with (80) imply for every $k\geq 1$

$C_{4}k\leq A_{2k}^{1-\frac{a}{b+c}}-A_{0}^{1-\frac{a}{b+c}}\leq
A_{2k}^{1-\frac{a}{b+c}}\leq
C_{2}^{\frac{b+c-a}{(b+c)(b+c+1)}}\tau_{2k+2}^{\frac{b+c-a}{b+c+1}}.$

This gives for every $k\geq 1$

$\tau_{2k+3}\geq\tau_{2k+2}\geq\widetilde{C}_{3}k^{\frac{b+c+1}{b+c-a}},$

where $\widetilde{C}_{3}>0$. We therefore deduce that there exists $C_{3}>0$
such that

$\tau_{k+1}\geq C_{3}k^{\frac{b+c+1}{b+c-a}}\quad\forall k\geq 1,$

which gives (78). ∎

Following a plan identical to the continuous case, we successively consider
the case where the control by feedback is formulated in terms of speed, then
of gradient.

###  4.2 Adaptive stepsize rules resulting from the discretization of the
velocity based system

In this subsection we specialize the algorithm PEAS to the case where
$G(y_{k},y_{k-1})=\left\lVert y_{k}-y_{k-1}\right\rVert$.

1

Input: $y_{0}\neq y_{-1}\in{\mathcal{H}}$

2 for  _$k=0,1,\cdots$_ do

3 if  _$\nabla f\left(y_{k}\right)=0$_ then

4 stop

5

6 else

7 $\lambda_{k}:=\left\lVert y_{k}-y_{k-1}\right\rVert^{-\frac{p-1}{p}}$

8 $y_{k+1}:=\operatorname{prox}_{\lambda_{k}f}\left(y_{k}\right)$

9

10 end if

11

12 end for

Algorithm 2 Proximal algorithm with adaptive step size defined via velocity

###### Theorem 4.2

Let $\left(y_{k}\right)_{k\geq 0}$ be the sequence generated by Algorithm 2.
Then it holds

$f\left(y_{k}\right)-\inf_{{\mathcal{H}}}f=o\left(\dfrac{1}{k^{2-\frac{1}{p}}}\right)\textrm{
as }k\to+\infty,$

and 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

By the choice of the step size, we have from Theorem 4.1 $(iii)$ that

$\sum_{k\geq 0}\dfrac{\tau_{k}}{\lambda_{k}}\left\lVert
y_{k+1}-y_{k}\right\rVert^{2}=\sum_{k\geq
0}\tau_{k}\lambda_{k}^{-1}\lambda_{k+1}^{-\frac{2p}{p-1}}<+\infty,$

where $\tau_{0}=0$ and $\tau_{k}:=\sum_{i=0}^{k-1}\lambda_{i}$ for every
$k\geq 1$. We are in position to apply Lemma 2 with
$\left(a,b,c\right):=\left(1,1,\frac{2p}{p-1}\right)$. We get

$\tau_{k+1}\geq C_{3}k^{2-\frac{1}{p}}\quad\forall k\geq 1.$ (82)

Therefore $\sum_{k\geq
0}\lambda_{k}=\lim_{k\rightarrow+\infty}\tau_{k}=+\infty$, and we can apply
Theorem 4.1 to obtain the conclusion. ∎

###  4.3 Adaptive stepsize resulting from the discretization of the gradient
based system

Now let us specialize the algorithm PEAS to the case where
$G(y_{k},y_{k-1})=\left\lVert\nabla f(y_{k})\right\rVert$.

Input: $y_{0}\in{\mathcal{H}}$

1 for  _$k=0,1,\cdots$_ do

2 if  _$\nabla f\left(y_{k}\right)=0$_ then

3 stop

4

5 else

6 $\lambda_{k}:=\left\lVert\nabla
f\left(y_{k}\right)\right\rVert^{-\frac{p-1}{p}}$

7 $y_{k+1}:=\operatorname{prox}_{\lambda_{k}f}\left(y_{k}\right)$

8

9 end if

10

11 end for

Algorithm 3 Proximal algorithm with adaptive step size defined via gradient

###### Theorem 4.3

Let $\left(y_{k}\right)_{k\geq 0}$ be the sequence generated by Algorithm 3.
Then it holds

$f\left(y_{k+1}\right)-\inf_{{\mathcal{H}}}f=o\left(\frac{1}{k^{2-\frac{1}{p}}}\right)\textrm{
as }k\to+\infty$

and 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

In this case we have from Theorem 4.1 $(ii)$

$\sum_{k\geq 0}\tau_{k}\lambda_{k}\left\lVert\nabla
f\left(y_{k+1}\right)\right\rVert^{2}=\sum_{k\geq
0}\tau_{k}\lambda_{k}\lambda_{k+1}^{-\frac{2p}{p-1}}<+\infty,$ (83)

where $\tau_{0}=0$ and $\tau_{k}:=\sum_{i=0}^{k-1}\lambda_{i}$ for every
$k\geq 1$.

Let us establish an inequality of the type

$\left\lVert\nabla f\left(y_{k}\right)\right\rVert\leq C_{k}\left\lVert\nabla
f\left(y_{k+1}\right)\right\rVert,$

for some sequence $C_{k}>0$ which is to be precised. We have for all $k\geq 0$

$\displaystyle\left\lVert\nabla f\left(y_{k}\right)\right\rVert^{2}$
$\displaystyle=\left\lVert\nabla
f\left(y_{k+1}\right)\right\rVert^{2}-2\left\langle\nabla
f\left(y_{k+1}\right),\nabla f\left(y_{k+1}\right)-\nabla
f\left(y_{k}\right)\right\rangle+\left\lVert\nabla
f\left(y_{k+1}\right)-\nabla f\left(y_{k}\right)\right\rVert^{2}$
$\displaystyle=\left\lVert\nabla
f\left(y_{k+1}\right)\right\rVert^{2}+\dfrac{2}{\lambda_{k}}\left\langle
y_{k+1}-y_{k},\nabla f\left(y_{k+1}\right)-\nabla
f\left(y_{k}\right)\right\rangle+\left\lVert\nabla
f\left(y_{k+1}\right)-\nabla f\left(y_{k}\right)\right\rVert^{2}$
$\displaystyle\leq\left\lVert\nabla
f\left(y_{k+1}\right)\right\rVert^{2}+\left(\dfrac{2L}{\lambda_{k}}+L^{2}\right)\left\lVert
y_{k+1}-y_{k}\right\rVert^{2}=\left(1+L\lambda_{k}\right)^{2}\left\lVert\nabla
f\left(y_{k+1}\right)\right\rVert^{2}$
$\displaystyle\leq\left(1+L\lambda_{k+1}\right)^{2}\left\lVert\nabla
f\left(y_{k+1}\right)\right\rVert^{2}$ (84)

where $L>0$ denotes the Lipschitz constant of $\nabla f$ on a bounded set
containing the sequence $\left(y_{k}\right)_{k\geq 0}$.

Combining (83) and (84), we get

$\sum_{k\geq
0}\tau_{k}\lambda_{k}\frac{1}{\left(1+L\lambda_{k+1}\right)^{2}}\left\lVert\nabla
f\left(y_{k}\right)\right\rVert^{2}=\sum_{k\geq
0}\tau_{k}\lambda_{k}\frac{1}{\left(1+L\lambda_{k+1}\right)^{2}}\lambda_{k}^{-\frac{2p}{p-1}}<+\infty.$
(85)

Let us now show that $\lim_{k\rightarrow+\infty}\lambda_{k}=+\infty$.
According to the decreasing property of the sequence
$\left(f\left(y_{k}\right)-\inf_{{\mathcal{H}}}f\right)_{k\geq 0}$, by summing
inequalities (77) we get

$\sum_{k\geq 0}\lambda_{k}\left\lVert\nabla
f\left(y_{k+1}\right)\right\rVert^{2}<+\infty.$ (86)

From the closed-loop rule we deduce that

$\sum_{k\geq 0}\lambda_{k}\lambda_{k+1}^{-\frac{2p}{p-1}}<+\infty.$ (87)

Therefore

$\lim_{k\rightarrow+\infty}\lambda_{k}\lambda_{k+1}^{-\frac{2p}{p-1}}=0.$

Since $(\lambda_{k})_{k\geq 0}$ is increasing, let us denote by $l>0$ its
limit. If $l$ is finite then, by passing to the limit on the above inequality
we get $l^{1-\frac{2p}{p-1}}=0$, a clear contradiction with $l>0$. Therefore

$\lim_{k\rightarrow+\infty}\lambda_{k}=+\infty.$

In this case
$\frac{1}{\left(1+L\lambda_{k+1}\right)^{2}}\sim\left(L\lambda_{k+1}\right)^{-2}$,
which gives

$\sum_{k\geq
0}\tau_{k}\lambda_{k}^{1-\frac{2p}{p-1}}{\lambda_{k+1}}^{-2}<+\infty.$ (88)

We are in position to apply Lemma 2 with
$\left(a,b,c\right):=\left(1,\frac{2p}{p-1}-1,2\right)$. We get

$\tau_{k+1}\geq C_{3}k^{2-\frac{1}{p}}\quad\forall k\geq 1.$

We have $\sum_{k\geq
0}\lambda_{k}=\lim_{k\rightarrow+\infty}\tau_{k}=+\infty$, and we can apply
Theorem 4.1 to obtain, as $k\to+\infty$

$f\left(y_{k+1}\right)-\inf_{{\mathcal{H}}}f=o\left(\frac{1}{k^{2-\frac{1}{p}}}\right).$

This completes the proof. ∎

###### Remark 3

Note that the closed-loop control of the velocity and the closed-loop control
of the gradient give the same convergence rate of the values. Clearly, we have
obtained a faster convergence result.

##  5 Inertial proximal algorithms obtained by closed-loop damping

Let us now consider the convergence properties of the sequences
$(x_{k})_{k\geq 0}$ which are obtained by applying the averaging process to
the sequences generated by Algorithm 2. Indeed, we limit our investigation to
the closed loop control of the velocity, the case of the closed loop control
of the gradient is very similar. Let us discretize the continuous averaging
relation

$\dot{x}(t)+\dfrac{\dot{\tau}(t)}{\tau(t)}\left(x(t)-y(t)\right)=0$

as follows (recall that, because of the choice $q=1$, we have
$\dot{\tau}(t)=\lambda(t)$)

$x_{k+1}-x_{k}+\frac{\lambda_{k}}{\tau_{k+1}}\left(x_{k}-y_{k+1}\right)=0.$

Equivalently

$x_{k+1}=\left(1-\frac{\lambda_{k}}{\tau_{k+1}}\right)x_{k}+\frac{\lambda_{k}}{\tau_{k+1}}y_{k+1}.$

This gives the following proximal inertial algorithm:

Input: $\tau_{0}:=0$ and $x_{0},y_{0}\neq y_{-1}\in{\mathcal{H}}$

1 for  _$k=0,1,\cdots$_ do

2 if  _$\nabla f\left(y_{k}\right)=0$_ then

3 stop

4

5 else

6 $\displaystyle{\lambda_{k}:=\left\lVert
y_{k}-y_{k-1}\right\rVert^{-\frac{p-1}{p}}}$

7
$\displaystyle{y_{k+1}:=\operatorname{prox}_{\lambda_{k}f}\left(y_{k}\right)}$

8 $\displaystyle{\tau_{k+1}:=\tau_{k}+\lambda_{k}}$

9
$\displaystyle{x_{k+1}:=\left(1-\frac{\lambda_{k}}{\tau_{k+1}}\right)x_{k}+\frac{\lambda_{k}}{\tau_{k+1}}y_{k+1}.}$

10 end if

11

12 end for

Algorithm 4 Proximal inertial algorithm with adaptive step size defined via
velocity

###### Theorem 5.1

Let $\left(x_{k}\right)_{k\geq 0}$ be the sequence generated by Algorithm 4.
Then it holds

$f\left(x_{k}\right)-\inf_{{\mathcal{H}}}f=\mathcal{O}\left(\frac{1}{k^{2-\frac{1}{p}}}\right)\textrm{
as }k\to+\infty$

and 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

Let $k\geq 0$. By definition of $x_{k+1}$ we have

$\tau_{k+1}x_{k+1}=(\tau_{k+1}-\lambda_{k})x_{k}+\lambda_{k}y_{k+1}$

which gives (recall that $\tau_{k+1}=\sum_{i=0}^{k}\lambda_{i}$)

$\tau_{k+1}x_{k+1}-\tau_{k}x_{k}=(\tau_{k+1}-\lambda_{k})x_{k}+\lambda_{k}y_{k+1}-\tau_{k}x_{k}=(\tau_{k+1}-\tau_{k}-\lambda_{k})x_{k}+\lambda_{k}y_{k+1}=\lambda_{k}y_{k+1}.$

Therefore, by telescoping arguments we obtain

$x_{k+1}=\frac{\sum_{i=0}^{k}\lambda_{i}y_{i+1}}{\tau_{k+1}}\quad\forall k\geq
0.$ (89)

By convexity of $f$ we infer

$\displaystyle f\left(x_{k+1}\right)-\inf_{{\mathcal{H}}}f$
$\displaystyle=\left(f-\inf_{{\mathcal{H}}}f\right)\left(x_{k+1}\right)=\left(f-\inf_{{\mathcal{H}}}f\right)\left(\frac{\sum_{i=0}^{k}\lambda_{i}y_{i+1}}{\tau_{k+1}}\right)$
$\displaystyle\leq\dfrac{1}{\tau_{k+1}}\sum_{i=0}^{k}\lambda_{i}\left(f-\inf_{{\mathcal{H}}}f\right)\left(y_{i+1}\right)=\dfrac{1}{\tau_{k+1}}\sum_{i=0}^{k}\lambda_{i}\left(f\left(y_{i+1}\right)-\inf_{{\mathcal{H}}}f\right),$

By Theorem 4.1 $(i)$, we have $\sum_{k\geq
0}\lambda_{k}\left(f\left(y_{k+1}\right)-\inf_{{\mathcal{H}}}f\right)<+\infty,$
and by (82) we have $\tau_{k+1}\geq k^{2-\frac{1}{p}}$, which gives the claim.
The weak convergence of $\left(x_{k}\right)_{k\geq 0}$ to an element in
$S=\operatorname{argmin}_{{\mathcal{H}}}f$ follows from the weak convergence
of $\left(y_{k}\right)_{k\geq 0}$ and the Stolz-Cesáro Theorem. ∎

###  5.1 Geometric interpretation of PEAS

First note that (PEAS) can be equivalently written as follows

$x_{k+1}=\left(1-\frac{\lambda_{k}}{\tau_{k+1}}\right)x_{k}+\frac{\lambda_{k}}{\tau_{k+1}}\operatorname{prox}_{\lambda_{k}f}\left(x_{k-1}+\frac{\tau_{k}}{\lambda_{k-1}}(x_{k}-x_{k-1}\right).$
(90)

Since $\frac{\tau_{k}}{\lambda_{k-1}}>1$, the algorithm first involves an
extrapolation step (this is the inertial aspect), then a proximal step, and
finally a relaxation step which balances the inertia effect and dampens the
oscillations. This is shown in the figure below. We set
$\theta_{k}=\frac{\lambda_{k}}{\tau_{k+1}}\in]0,1[$.

$y_{k}=x_{k-1}+\frac{1}{\theta_{k-1}}(x_{k}-x_{k-1})$$\bullet$$x_{k}$$\bullet$$x_{k-1}$$\bullet$$\bullet$$x_{k+1}=\left(1-\theta_{k}\right)x_{k}+\theta_{k}\operatorname{prox}_{\lambda_{k}f}\left(y_{k}\right)$$\operatorname{prox}_{\lambda_{k}f}(y_{k})$$S$Fig.1
A geometrical illustration of algorithm PEAS

Despite some analogies, (PEAS) is different from the relaxed inertial proximal
algorithm (RIPA) considered by Attouch and Cabot in AC-RIPA , and which writes

$\begin{cases}y_{k}&=x_{k}+\alpha_{k}(x_{k}-x_{k-1})\vspace{1mm}\\\
x_{k+1}&=(1-\rho_{k})y_{k}+\rho_{k}\operatorname{prox}_{\lambda_{k}f}(y_{k})\end{cases}$
(91)

As main difference, in (PEAS) relaxation is taken between $x_{k}$ and
$\operatorname{prox}_{\lambda_{k}f}(y_{k})$, while in (RIPA) it is taken
between $y_{k}$ and $\operatorname{prox}_{\lambda_{k}f}(y_{k})$. Consequently
(PEAS) involves a Hessian damping effect which is not present in (RIPA). Note
in (PEAS) the balance between the extrapolation (inertial, acceleration)
effect and the relaxation effect. Moreover, our construction provides
coefficients which are generated automatically in closed loop way, whereas in
(RIPA) they require subtle adjustment. The importance of the relaxation
technique when combined with inertia has been put to the fore in IH .
According to (89), $x_{k+1}$ can be interpreted as an average of the
$\\{y_{n}:0\leq n\leq k+1\\}$, which makes our approach somewhat analogous to
the nonlinear averaging technique developed in SAB , where it is assumed that
there is a unique minimizer. Averaging techniques have also been used in PL
in the context of hybrid systems. Indeed, adjusting the damping in a closed-
loop ad hoc manner bears some analogy to restarting methods.

##  6 Conclusion, perspective

Our study proposes new fast adaptive optimization methods for convex
optimization. We have shown that the time scaling and averaging technique,
previously developed by the authors in the context of non-autonomous systems,
can be developed by taking closed-loop time parameterization, giving rise to
autonomous dynamics. The method turns out to be flexible, because it is based
on elementary mathematical tools, namely the dynamics of the steepest descent,
and the operations of temporal parameterization and averaging. It is therefore
not necessary to redo a Lyapunov analysis, one relies on the classic results
for the steepest descent. The results obtained for the continuous dynamics
pass quite naturally to the corresponding proximal algorithms, where the
iterates are expressed in a direct way according to the proximal terms. This
study is one of the very first to develop an algorithmic framework based on
autonomous dynamics and which, when specialized, provides the convergence
rates of the dynamical surrogate of the Nesterov acceleration gradient method.
Another important aspect of our analysis is that it exhibits Hessian-driven
damping, which plays a key role in damping oscillations. Our work opens up
many perspectives, our method naturally extending to gradient algorithms,
proximal-gradient algorithms for composite optimization, cocercive monotone
operators, and the study of the stochastic version, to name only a few.

##  7 Appendix

###  7.1 Classical facts concerning the continuous steepest descent

Consider the classical continuous steepest descent

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

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 (ABM_book, , Theorem 17.1.1). We fix $t_{0}$ as the
origin of time. Recall classical facts concerning the continuous steepest
descent.

###### Theorem 7.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)$ (93)

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.$ (94)

Then the following statements are satisfied:

  1. $(i)$

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

  2. $(ii)$

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

  3. $(iii)$

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

  4. $(iv)$

(convergence of values)
$f\left(z\left(t\right)\right)-\inf_{{\mathcal{H}}}f=o\left(\dfrac{1}{t}\right)\textrm{
as }t\to+\infty.$

  5. $(v)$

(improved convergence rates of gradients) if $g(t)\equiv 0$, then
$\left\lVert\nabla
f\left(z\left(t\right)\right)\right\rVert=o\left(\dfrac{1}{t}\right)\textrm{
as }t\to+\infty.$

  6. $(vi)$

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

If $g(t)\equiv 0$ we have that $t\mapsto\left\lVert\nabla
f\left(z\left(t\right)\right)\right\rVert$ is nonincreasing since in this case

$\frac{d}{dt}\left\lVert\nabla
f\left(z\left(t\right)\right)\right\rVert^{2}=2\left\langle\nabla
f\left(z\left(t\right)\right),\frac{d}{dt}\nabla
f\left(z\left(t\right)\right)\right\rangle=-2\left\langle\dot{z}\left(t\right),\frac{d}{dt}\nabla
f\left(z\left(t\right)\right)\right\rangle\leq 0\quad\forall t\geq t_{0}.$

Therefore, from the integral estimate of the gradients we deduce that
$\left\lVert\nabla
f\left(z\left(t\right)\right)\right\rVert=o\left(\frac{1}{t}\right)$.

###  7.2 Auxiliary result

Opial’s Lemma is a basic ingredient of the convergence analysis.

###### Lemma 3

(Opial) Let $S$ be a nonempty subset of ${\mathcal{H}}$ and let
$\left(x_{k}\right)_{k\geq 0}$ be a sequence in ${\mathcal{H}}$. Assume that

  1. $(i)$

for every $z\in S$, $\lim_{k\to+\infty}\left\lVert x_{k}-z\right\rVert$
exists;

  2. $(ii)$

every weak sequential limit point of $\left(x_{k}\right)_{k\geq 0}$, as
$k\to+\infty$, belongs to $S$.

Then $\left(x_{k}\right)_{k\geq 0}$ converges weakly as $k\to+\infty$, and its
limit belongs to $S$.

## Funding

The research of RIB and DKN has been supported by FWF (Austrian Science Fund),
projects W 1260 and P 34922-N, respectively.

## References

  * (1) C.D. Alecsa, S. László, T. Pinta, An extension of the second order dynamical system that models Nesterov’s convex gradient method, Applied Mathematics and Optimization, 84 (2021), 1687–1716.
  * (2) H. Attouch, A. Balhag, Z. Chbani, H. Riahi, Fast convex optimization via inertial dynamics combining viscous and Hessian-driven damping with time rescaling, Evolution Equations and Control Theory, 11 (2) (2022), 487–514.
  * (3) H. Attouch, R.I. Boţ, E.R. Csetnek, Fast optimization via inertial dynamics with closed-loop damping. J. Eur. Math. Soc. (2022), DOI 10.4171/JEMS/1231
  * (4) H. Attouch, R.I. Boţ, D.-K. Nguyen, Fast convex optimization via time scale and averaging of the steepest descent, arXiv:2208.08260v1 [math.OC] Aug 2022.
  * (5) H. Attouch, G. Buttazzo, G. Michaille, Variational analysis in Sobolev and BV spaces. Applications to PDE’s and optimization, Second Edition MOS/SIAM Series on Optimization, MO 17, Society for Industrial and Applied Mathematics (SIAM), Philadelphia, PA, (2014), 793 pages.
  * (6) H. Attouch, A. Cabot, Convergence rates of inertial forward-backward algorithms, SIAM J. Optim., 28 (1) (2018), 849–874.
  * (7) H. Attouch, A. Cabot, Convergence of a relaxed inertial proximal algorithm for maximally monotone operators, Math. Program., 184 (2020), 243–287.
  * (8) H. Attouch, Z. Chbani, J. Fadili, H. Riahi, First-order algorithms via inertial systems with Hessian driven damping, Math. Program., 193 (2022), 113–155.
  * (9) H. Attouch, Z. Chbani, J. Fadili, H. Riahi, Convergence of iterates for first-order optimization algorithms with inertia and Hessian driven damping, Optimization, 2021, published online, https://doi.org/10.1080/02331934.2021.2009828.
  * (10) H. Attouch, J. Fadili, V. Kungurtsev, On the effect of perturbations, errors in first-order optimization methods with inertia and Hessian driven damping, Evolution Equations and Control Theory, 12 (1) (2023), 71–117, doi:10.3934/eect.2022022
  * (11) H. Attouch, J. Peypouquet, P. Redont, Fast convex minimization via inertial dynamics with Hessian driven damping, J. Differential Equations, 261 (2016), 5734–5783.
  * (12) H. Attouch, P. Redont, B. F. Svaiter, Global convergence of a closed-loop regularized Newton method for solving monotone inclusions in Hilbert spaces, J. Optim. Theory Appl., 157 (3) (2013), 624–650.
  * (13) H. Attouch, B. F. Svaiter, A continuous dynamical Newton-Like approach to solving monotone inclusions, SIAM J. Control Optim., 49 (2) (2011), 574–598.
  * (14) H. Bauschke, P. L. Combettes, Convex Analysis and Monotone Operator Theory in Hilbert Spaces, CSM Books in Mathematics, Springer, 2011.
  * (15) R. I. Boţ, E. R. Csetnek, S.C. László, Tikhonov regularization of a second order dynamical system with Hessian damping, Math. Program., 189 (2021), 151–186.
  * (16) C. Castera, J. Bolte, C. Févotte, E. Pauwels, An Inertial Newton Algorithm for Deep Learning, Journal of Machine Learning Research, 22 (2021), 1–31.
  * (17) A. Haraux, M. A. Jendoubi The convergence problem for dissipative autonomous systems, Springer Briefs in Mathematics, 2015.
  * (18) F. Iutzeler, J.M. Hendrickx, A generic online acceleration scheme for optimization algorithms via relaxation and inertia, Optimization Methods and Software, 34 (2) (2019), 383–405.
  * (19) T. Lin, M. I. Jordan, A control-theoretic perspective on optimal high-order optimization, Math. Program., 195 (1) (2022), 929–975.
  * (20) T. Lin, M. I. Jordan, Monotone Inclusions, Acceleration and Closed-Loop Control, accepted by Mathematics of Operations Research. arXiv:2111.08093v4 [math.OC] 26 Nov 2022.
  * (21) P.L. Maingé, F. Labarre, First-Order Frameworks for Continuous Newton-like Dynamics Governed by Maximally Monotone Operators, Set-Valued Var. Anal., 30 (2022), 425–451.
  * (22) M. Muehlebach, M. I. Jordan, A Dynamical Systems Perspective on Nesterov Acceleration, Proceedings of the International Conference on Machine Learning, 2019, https://arxiv.org/abs/1905.07436
  * (23) R. D. C. Monteiro, B. F. Svaiter An Accelerated Hybrid Proximal Extragradient Method for Convex Optimization and Its Implications to Second-order Methods, SIAM J. Optim., 23 (2) (2013), 1092–1125.
  * (24) Y. Nesterov, A method of solving a convex programming problem with convergence rate O(1/k2), Soviet Mathematics Doklady, 27 (1983), 372–376.
  * (25) Y. Nesterov, Introductory lectures on convex optimization: A basic course, volume 87 of Applied Optimization. Kluwer Academic Publishers, Boston, MA, 2004.
  * (26) J. I. Poveda, N. Li, Robust Hybrid Zero-Order Optimization Algorithms with Acceleration via Averaging in Time, arXiv:1909.00265v4 [math.OC] 15 Dec 2020.
  * (27) D. Scieur, A. D’Aspremont, F. Bach, Regularized nonlinear acceleration, Advances in Neural Information Processing Systems 29 (NIPS 2016), arXiv:1606.04133v3 [math.OC] 14 Apr 2019\.
  * (28) B. Shi, S. S. Du, M. I. Jordan, W. J. Su, Understanding the acceleration phenomenon via high-resolution differential equations, Math. Program., 195 (2022), 79–148.
  * (29) C. Song, Y. Jiang, Y. Ma, Unified Acceleration of High-Order Algorithms under General Hölder Continuity, SIAM J. Optim., 31(3) (2021), 1797–1826.
  * (30) W. J. Su, S. Boyd, E. J. Candès, A differential equation for modeling Nesterov’s accelerated gradient method: theory and insights. Neural Information Processing Systems, 27 (2014), 2510–2518.