# Fast Optimistic Gradient Descent Ascent (OGDA) method in continuous and
discrete time

Radu Ioan Boţ111Faculty of Mathematics, University of Vienna, Oskar-
Morgenstern-Platz 1, 1090 Vienna, Austria, email<EMAIL_ADDRESS>Research partially supported by FWF (Austrian Science Fund), projects W 1260
and P 34922-N. Ernö Robert Csetnek222Faculty of Mathematics, University of
Vienna, Oskar-Morgenstern-Platz 1, 1090 Vienna, Austria, email:
<EMAIL_ADDRESS>Research partially supported by FWF (Austrian
Science Fund), project P 29809-N32. Dang-Khoa Nguyen333Faculty of Mathematics,
University of Vienna, Oskar-Morgenstern-Platz 1, 1090 Vienna, Austria, email:
<EMAIL_ADDRESS>Research supported by FWF (Austrian Science
Fund), project P 34922-N.

###### Abstract

In the framework of real Hilbert spaces we study continuous in time dynamics
as well as numerical algorithms for the problem of approaching the set of
zeros of a single-valued monotone and continuous operator $V$. The starting
point of our investigations is a second order dynamical system that combines a
vanishing damping term with the time derivative of $V$ along the trajectory,
which can be seen as an analogous of the Hessian-driven damping in case the
operator is originating from a potential. Our method exhibits fast convergence
rates of order $o\left(\frac{1}{t\beta(t)}\right)$ for $\|V(z(t))\|$, where
$z(\cdot)$ denotes the generated trajectory and $\beta(\cdot)$ is a positive
nondecreasing function satisfiyng a growth condition, and also for the
restricted gap function, which is a measure of optimality for variational
inequalities. We also prove the weak convergence of the trajectory to a zero
of $V$.

Temporal discretizations of the dynamical system generate implicit and
explicit numerical algorithms, which can be both seen as accelerated versions
of the Optimistic Gradient Descent Ascent (OGDA) method for monotone
operators, for which we prove that the generated sequence of iterates
$(z_{k})_{k\geq 0}$ shares the asymptotic features of the continuous dynamics.
In particular we show for the implicit numerical algorithm convergence rates
of order $o\left(\frac{1}{k\beta_{k}}\right)$ for $\|V(z^{k})\|$ and the
restricted gap function, where $(\beta_{k})_{k\geq 0}$ is a positive
nondecreasing sequence satisfying a growth condition. For the explicit
numerical algorithm we show by additionally assuming that the operator $V$ is
Lipschitz continuous convergence rates of order $o\left(\frac{1}{k}\right)$
for $\|V(z^{k})\|$ and the restricted gap function. All convergence rate
statements are last iterate convergence results; in addition to these we prove
for both algorithms the convergence of the iterates to a zero of $V$. To our
knowledge, our study exhibits the best known convergence rate results for
monotone equations. Numerical experiments indicate the overwhelming
superiority of our explicit numerical algorithm over other methods designed to
solve monotone equations governed by monotone and Lipschitz continuous
operators.

Key Words. monotone equation, variational inequality, Optimistic Gradient
Descent Ascent (OGDA) method, extragradient method, Nesterov’s accelerated
gradient method, Lyapunov analysis, convergence rates, convergence of
trajectories, convergence of iterates

AMS subject classification. 47J20, 47H05, 65K10, 65K15, 65Y20, 90C30, 90C52

##  1 Introduction

Let $\mathcal{H}$ be a real Hilbert space and
$V\colon\mathcal{H}\to\mathcal{H}$ a monotone and continuous operator. We are
interested in developing fast converging methods aimed to find a zero of $V$,
or in other words, to solve the monotone equation

$V\left(z\right)=0,$ (1)

for which assume that it has a nonempty solution set $\mathcal{Z}$. The
monotonicity and the continuity of $V$ imply that $z_{*}$ is a solution of (1)
if and only if it is a solution of the following variational inequality

$\left\langle z-z_{*},V\left(z\right)\right\rangle\geq 0\quad\forall
z\in\mathcal{H}.$ (2)

One of the main motivations to study (1) comes from minimax problems. More
precisely, consider the problem

$\min\limits_{x\in\mathcal{X}}\max\limits_{y\in\mathcal{Y}}\Phi\left(x,y\right),$
(3)

where $\mathcal{X}$ and $\mathcal{Y}$ are real Hilbert spaces and
$\Phi\colon\mathcal{X}\times\mathcal{Y}\to\mathbb{R}$ is a continuously
differentiable and convex-concave function, i.e., $\Phi\left(\cdot,y\right)$
is convex for every $y\in\mathcal{Y}$ and $\Phi\left(x,\cdot\right)$ is convex
for every $x\in\mathcal{X}$. A solution of (3) is a saddle point
$\left(x_{*},y_{*}\right)\in\mathcal{X}\times\mathcal{Y}$ of $\Phi$, which
means that it fulfills

$\Phi\left(x_{*},y\right)\leq\Phi\left(x_{*},y_{*}\right)\leq\Phi\left(x,y_{*}\right)\quad\forall\left(x,y\right)\in\mathcal{X}\times\mathcal{Y}$

or, equivalently,

$\begin{dcases}\nabla_{x}\Phi\left(x_{*},y_{*}\right)&=0\\\
-\nabla_{y}\Phi\left(x_{*},y_{*}\right)&=0.\end{dcases}$ (4)

Taking into account that the mapping

$\left(x,y\right)\mapsto\Bigl{(}\nabla_{x}\Phi\left(x,y\right),-\nabla_{y}\Phi\left(x,y\right)\Bigr{)}$
(5)

is monotone ([43]), it means that the problem of finding a saddle point of
$\Phi$ eventually brings us back to the problem (1).

Both (1) and (3) are fundamental models in various fields such as
optimization, economics, game theory, and partial differential equations. They
have recently regained significant attention, in particular in the machine
learning and data science community, due to the fundamental role they play,
for instance, in multi agent reinforcement learning [37], robust adversarial
learning [32] and generative adversarial networks (GANs) [24, 18].

In this paper we develop fast continuous in time dynamics as well as numerical
algorithms for solving (1) and investigate their asymptotic/convergence
properties. First we formulate a second order dynamical system that combines a
vanishing damping term with the time derivative of $V$ along the trajectory,
which can be seen as an analogous of the Hessian-driven damping in case the
operator is originating from a potential. A continuously differentiable and
nondecreasing function
$\beta\colon\left[t_{0},+\infty\right)\to\left(0,+\infty\right)$, which
appears in the system, plays an important role in the analysis. If $\beta$
satisfies a specific growth condition, which is for instance satisfied by
polynomials including constant functions, then the method exhibits convergence
rates of order $o\left(\frac{1}{t\beta(t)}\right)$ for $\|V(z(t))\|$, where
$z(t)$ denotes the generated trajectory, and for the restricted gap function
associated with (2). In addition, $z(t)$ converges asymptotically weakly to a
solution of (1).

By considering a temporal discretization of the dynamical system we obtain an
implicit numerical algorithm which exhibits convergence rates of order
$o\left(\frac{1}{k\beta_{k}}\right)$ for $\|V(z^{k})\|$ and the restricted gap
function associated with (2), where $(\beta_{k})_{k\geq 0}$ is a nondecreasing
sequence and $(z_{k})_{k\geq 0}$ is the generated sequence of iterates. For
the latter we also prove that it converges weakly to a solution of (1).

By a further more involved discretization of the dynamical system we obtain an
explicit numerical algorithm, which, under the additional assumption that $V$
is Lipschitz continuous, exhibits convergence rates of order
$o\left(\frac{1}{k}\right)$ for $\|V(z^{k})\|$ and the restricted gap function
associated with (2), where $(z_{k})_{k\geq 0}$ is the generated sequence of
iterates, which is also to converge weakly to a solution of (1).

The resulting numerical schemes can be seen as accelerated versions of the
Optimistic Gradient Descent Ascent (OGDA) method ([33, 42]) formulated in
terms of a general monotone operator $V$. It should be also emphasized that
the convergence rate statements for both the implicit and the explicit
numerical algorithm are last iterate convergence results and are, to our
knowledge, the best known convergence rate results for monotone equations.

###  1.1 Related works

In the following we discuss some discrete and continuous methods from the
literature designed to solve equations governed by monotone and (Lipschitz)
continuous, and not necessarily cocoercive operators. It has been recognized
that the simplest scheme one can think of, namely the forward algorithm,
which, for a starting point $z^{0}\in{\cal H}$ and a given step size $s>0$,
reads for $k\geq 0$

$z^{k+1}:=z^{k}-sV\left(z^{k}\right),$

and mimics the classical gradient descent algorithm, does not converge. Unless
for the trivial case, the operator in (5), which arises in connection with
minimax problems, is only monotone and Lipschitz continuous but not
cocoercive. Therefore, it was early recognized that explicit numerical methods
for monotone equations require an operator corrector term.

In case $V$ is monotone and $L$-Lipschitz continuous, for $L>0$, Korpelevich
[30] and Antipin [2] proposed to solve (1) the nowadays very popular
Extragradient (EG) method, which reads for $k\geq 0$

$\displaystyle\begin{split}\widebar{z}^{k}&:=z^{k}-sV\left(z^{k}\right)\\\
z^{k+1}&:=z^{k}-sV\left(\widebar{z}^{k}\right),\end{split}$ (6)

and converges for a starting point $z^{0}\in{\cal H}$ and $0<s<\frac{1}{L}$ to
a zero of $V$. The last iterate convergence rate for the extragradient method
was only recently derived by Gorbuno-Loizou-Gidel in [25]. For
$\widebar{z}\in\mathcal{H}$ and $\delta>0$ we denote
$\mathbb{B}\left(\widebar{z};\delta\right):=\left\\{u\in\mathcal{H}\colon\left\lVert\widebar{z}-u\right\rVert\leq\delta\right\\}$.
For $z_{*}\in\mathcal{Z}\textrm{ and }\delta\left(z^{0}\right):=\left\lVert
z_{*}-z^{0}\right\rVert$, the restricted gap function associated with the
variational inequality (2) is defined as (see [36])

$\mathtt{Gap}\left(z\right):=\sup\limits_{u\in\mathbb{B}\left(z_{*};\delta\left(z^{0}\right)\right)}\left\langle
z-u,V\left(u\right)\right\rangle\geq 0.$

In [25] it was shown that

$\left\lVert
V\left(z^{k}\right)\right\rVert=\mathcal{O}\left(\dfrac{1}{\sqrt{k}}\right)\mbox{
and
}\mathtt{Gap}\left(z^{k}\right)=\mathcal{O}\left(\dfrac{1}{\sqrt{k}}\right)\quad\textrm{as}\
k\to+\infty.$

In the same setting, Popov introduced in [42] for minmax problems and the
operator in (5) the following algorithm which, when formulated for (1), reads
for $k\geq 1$

$z^{k+1}:=z^{k}-2sV\left(z^{k}\right)+sV\left(z^{k-1}\right),$ (7)

and converges for starting points $z^{0},z^{1}\in{\cal H}$ and step size
$0<s<\frac{1}{2L}$ to a zero of $V$. This algorithm is usually known as the
Optimistic Gradient Descent Ascent (OGDA) method, a name which we adopt also
for the general formulation in (7). Recently, Chavdarova-Jordan-Zampetakis
proved in [19] that for $0<s<\frac{1}{16L}$ the scheme exhibits the following
best-iterate convergence rate

$\min\limits_{1\leq i\leq k}\left\lVert
V\left(z^{i}\right)\right\rVert=\mathcal{O}\left(\dfrac{1}{\sqrt{k}}\right)\quad\textrm{
as }k\to+\infty.$

We notice also that, according to Golowich-Pattathil-Daskalakis-Ozdaglar (see
[22, 23]), the lower-bound for the restricted gap function for the algorithms
(6) and (7) is of $\mathcal{O}\left(1/\sqrt{k}\right)$ as
$k\rightarrow+\infty$.

The solving of equation (1) can be also addressed in the general framework of
continuous and discrete time methods for finding the zeros of a maximally
monotone operator. Attouch-Svaiter introduced in [14] (see also [20]) a first
order evolution equation linked to the Newton and the Levenberg-Marquardt
methods, which when applied to (1) reads

$\dot{z}\left(t\right)+\lambda(t)\dfrac{d}{dt}V(z(t))+\lambda(t)V(z(t))=0,$
(8)

where $t\mapsto\lambda(t)$ is a continuous mapping, and for which they proved
that its trajectories converge weakly to a zero of $V$.  Attouch-Peypouquet
studied in [12] the following second-order differential equation with
vanishing damping

$\ddot{z}\left(t\right)+\dfrac{\alpha}{t}\dot{z}\left(t\right)+A_{\gamma\left(t\right)}\left(z\left(t\right)\right)=0,$
(9)

where $A\colon\mathcal{H}\rightrightarrows\mathcal{H}$ is a possibly set-
valued maximally monotone operator,

$A_{\gamma}:=\dfrac{1}{\gamma}\left(\mathrm{Id}-J_{\gamma A}\right)$

stands for the Yosida approximation of $A$ of index $\gamma>0$, and $J_{\gamma
A}=(\mathrm{Id}+\gamma A)^{-1}:{\cal H}\rightarrow{\cal H}$ for the resolvent
of $\gamma A$. The dynamical system (9) gives rise via implicit discretization
to the following so-called Regularized Inertial Proximal Algorithm, which for
every $k\geq 1$ reads

$\displaystyle\begin{split}\widebar{z}^{k}&:=z^{k}+\left(1-\dfrac{\alpha}{k}\right)\left(z^{k}-z^{k-1}\right)\\\
z^{k+1}&:=\dfrac{\gamma_{k}}{\gamma_{k}+s}\widebar{z}^{k}+\dfrac{s}{\gamma_{k}+s}J_{\left(\gamma_{k}+s\right)A}\left(\widebar{z}^{k}\right),\end{split}$

$z^{0},z^{1}\in{\cal H}$ are the starting points, $\alpha>2$, $s>0$ and
$\gamma_{k}=(1+\varepsilon)\frac{s}{\alpha^{2}}k^{2}$ for every $k\geq 1$,
with $\varepsilon>0$ fixed. In [12] it was shown that the discrete velocity
$z^{k+1}-z^{k}$ vanishes with a rate of convergence of
$\mathcal{O}\left(1/k\right)$ as $k\rightarrow+\infty$ and that the sequence
of iterates converges weakly to a zero of $A$. The continuous time approach in
(9) has been extended by Attouch-László in [9] by adding a Newton-like
correction term
$\xi\frac{d}{dt}\left(A_{\gamma\left(t\right)}\left(z\left(t\right)\right)\right)$,
with $\xi\geq 0$, whereas the discrete counterpart of this scheme was proposed
and investigated in [10].

For an inertial evolution equation with asymptotically vanishing damping terms
approaching the set of primal-dual solutions of a smooth convex optimization
problem with linear equality constraints, that can also be seen as the
solution set of a monotone operator equation, and exhibiting fast convergence
rates expressed in terms of the value functions, the feasibilty measure and
the primal-dual gap we refer to the recent works [6, 17].

We also want to mention the implicit method for finding the zeros of a
maximally monotone operator proposed by Kim in [29], which relies on the
performance estimation problem approach and makes use of computer-assisted
tools.

In the case when $V$ is monotone and $L$-Lipschitz continuous, for $L>0$,
Yoon-Ryu recently proposed in [49] an accelerated algorithm for solving (1),
called Extra Anchored Gradient (EAG) algorithm, designed by using anchor
variables, a technique that can be traced back to Halpern’s algorithm (see
[28]). The iterative scheme of the EAG algorithm reads for every $k\geq 0$

$\displaystyle\begin{split}\widebar{z}^{k}&:=z^{k}+\dfrac{1}{k+2}\left(z^{0}-z^{k}\right)-s_{k}V\left(z^{k}\right)\\\
z^{k+1}&:=z^{k}+\dfrac{1}{k+2}\left(z^{0}-z^{k}\right)-s_{k}V\left(\widebar{z}^{k}\right),\end{split}$
(10)

where $z^{0}\in{\cal H}$ is the starting point and the sequence of step sizes
$(s_{k})_{k\geq 0}$ is either chosen to be equal to a constant in the interval
$\left(0,\frac{1}{8L}\right]$ or such that

$s_{k+1}:=s_{k}\left(1-\dfrac{1}{\left(k+1\right)\left(k+3\right)}\dfrac{s_{k}^{2}L^{2}}{1-s_{k}^{2}L^{2}}\right)\quad\forall
k\geq 0,$ (11)

where $s_{0}\in\left(0,\frac{3}{4}{L}\right)$. This iterative scheme exhibits
in both cases the convergence rate of

$\left\lVert
V\left(z^{k}\right)\right\rVert=\mathcal{O}\left(\dfrac{1}{k}\right)\quad\textrm{
as }k\to+\infty.$

Later, Lee-Kim proposed in [31] an algorithm formulated in the same spirit for
the problem of finding the saddle points of a smooth nonconvex-nonconcave
function.

Further variants of the anchoring based method have been proposed by Tran-Dinh
in [47] and together with Luo in [48], which all exhibit the same convergence
rate for $\|V(z^{k})\|$ as EAG. Tran-Dinh in [47] and Park-Ryu in [40] pointed
out the existence of some connections between the anchoring approach and
Nesterov’s acceleration technique used for the minimization of smooth and
convex functions ([34, 35]).

###  1.2 Our contributions

The starting point of our investigations is a second order evolution equation
associated with problem (1) that combines a vanishing damping term with the
time derivative of $V$ along the trajectory, which will then lead via temporal
discretizations to the implicit and the explicit algorithms. In [19] several
dynamical systems of EG and OGDA type were proposed, mainly in the spirit of
the heavy ball method, that is, with a constant damping term, exhibiting a
convergence rate of $\|V(z(t))\|=\mathcal{O}\left(1/\sqrt{t}\right)$ as
$t\to+\infty$ and, in case $V$ is bilinear, weak convergence of the trajectory
$z(t)$ to a zero of the operator.

One of the main discoveries of the last decade was that asymptotically
vanishing damping terms (see [46, 4, 13]) lead to the acceleration of the
convergence of the value functions along the trajectories of a inertial
gradient systems. Moreover, when enhancing the evolution equations also with
Hessian-driven damping terms, the rate of convergence of the gradient along
the trajectories can be accelerated, too ([13, 45]). It is natural to ask
whether asymptomatically vanishing damping terms have the same accelerating
impact on the values of the norm of the governing operator along the
trajectories of inertial dynamical systems associated with monotone (not
necessarily potential) operators.

The dynamical system which we associate to (1) reads
$\begin{dcases}\ddot{z}\left(t\right)+\dfrac{\alpha}{t}\dot{z}\left(t\right)+\beta\left(t\right)\dfrac{d}{dt}V\left(z\left(t\right)\right)+\dfrac{1}{2}\left(\dot{\beta}\left(t\right)+\dfrac{\alpha}{t}\beta\left(t\right)\right)V\left(z\left(t\right)\right)=0\\\
z\left(t_{0}\right)=z^{0}\textrm{ and
}\dot{z}\left(t_{0}\right)=\dot{z}^{0}\end{dcases}$ where $t_{0}>0$,
$\alpha\geq 2$,
$\left(z^{0},\dot{z}^{0}\right)\in\mathcal{H}\times\mathcal{H}$,
$\beta\colon\left[t_{0},+\infty\right)\to\left(0,+\infty\right)$ is a
continuously differentiable and nondecreasing which satisfies the following
growth condition $0\leq\sup\limits_{t\geq
t_{0}}\dfrac{t\dot{\beta}\left(t\right)}{\beta\left(t\right)}\leq\alpha-2,$
and $t\mapsto V(z(t))$ is assumed to be differentiable on $[t_{0},+\infty)$.

For $z_{*}\in\mathcal{Z}$ and the dynamics generated by this dynamical system
we will prove that

$\left\langle
z\left(t\right)-z_{*},V\left(z\left(t\right)\right)\right\rangle=\mathcal{O}\left(\dfrac{1}{t\beta\left(t\right)}\right)\
\mbox{and}\ \left\lVert
V\left(z\left(t\right)\right)\right\rVert=\mathcal{O}\left(\dfrac{1}{t\beta\left(t\right)}\right).$

Further, by assuming that

$0\leq\sup\limits_{t\geq
t_{0}}\dfrac{t\dot{\beta}\left(t\right)}{\beta\left(t\right)}<\alpha-2,$

we will prove that the trajectory $z\left(t\right)$ converges weakly to a
solution of (1) as $t\to+\infty$ and it holds

$\left\lVert\dot{z}\left(t\right)\right\rVert=o\left(\dfrac{1}{t}\right)\quad\textrm{
as }t\to+\infty,$

and

$\left\langle
z\left(t\right)-z_{*},V\left(z\left(t\right)\right)\right\rangle=o\left(\dfrac{1}{t\beta\left(t\right)}\right)\mbox{
and }\left\lVert
V\left(z\left(t\right)\right)\right\rVert=o\left(\dfrac{1}{t\beta\left(t\right)}\right)\quad\textrm{
as }t\to+\infty.$

Polynomial parameter functions $\beta(t)=\beta_{0}t^{\rho}$, for $\beta_{0}>0$
and $\rho\geq 0$, satisfy the two growth conditions for $\alpha\geq\rho+2$ and
$\alpha>\rho+2$, respectively.

To the main contributions of this work belongs not only the improvement of the
convergence rates in [19] in both continuous and discrete time, but in
particular the surprising discovery that this can be achieved by means of
asymptotically vanishing damping, respectively, as we will see below, of
Nesterov momentum. This shows that the accelerating effect of inertial methods
with asymptotically vanishing damping/Nesterov momentum goes beyond convex
optimization and opens the gate towards new unexpected research perspectives.

######  Remark 1.1.

(restricted gap function) The convergence rates for $t\mapsto\left\langle
z\left(t\right)-z_{*},V\left(z\left(t\right)\right)\right\rangle$ and
$t\mapsto\left\lVert V\left(z\left(t\right)\right)\right\rVert$ can be easily
transferred to the restricted gap function associated with the variational
inequality (2). Indeed, for $z_{*}\in\mathcal{Z}$, let
$\delta(z^{0}):=\left\lVert z^{0}-z_{*}\right\rVert$,
$u\in\mathbb{B}\left(z_{*};\delta(z^{0})\right)$ and $t\geq t_{0}$. It holds

$\displaystyle 0\leq\left\langle
z\left(t\right)-u,V\left(u\right)\right\rangle\leq\left\langle
z\left(t\right)-u,V\left(z\left(t\right)\right)\right\rangle$
$\displaystyle=\left\langle
z\left(t\right)-z_{*},V\left(z\left(t\right)\right)\right\rangle+\left\langle
z_{*}-u,V\left(z\left(t\right)\right)\right\rangle$
$\displaystyle\leq\left\langle
z\left(t\right)-z_{*},V\left(z\left(t\right)\right)\right\rangle+\left\lVert
u-z_{*}\right\rVert\left\lVert V\left(z\left(t\right)\right)\right\rVert,$

which implies that for every $t\geq t_{0}$

$0\leq\mathtt{Gap}\left(z\left(t\right)\right)=\sup_{u\in\mathbb{B}\left(z_{*};\delta(z^{0})\right)}\left\langle
z\left(t\right)-u,V\left(u\right)\right\rangle\leq\left\langle
z\left(t\right)-z_{*},V\left(z\left(t\right)\right)\right\rangle+\delta(z^{0})\left\lVert
V\left(z\left(t\right)\right)\right\rVert,$

which proofs our claim. The same remark can be obviously made in the discrete
case.

Further we provide two temporal discretizations of the dynamical system, one
of implicit and one of explicit type.  Implicit Fast OGDA: Let $\alpha>2$,
$z^{0},z^{1}\in\mathcal{H}$, $s>0$, and $\left(\beta_{k}\right)_{k\geq 1}$ a
positive and nondecreasing sequence which satisfies $0\leq\sup_{k\geq
1}\dfrac{k\left(\beta_{k}-\beta_{k-1}\right)}{\beta_{k}}<\alpha-2.$ For every
$k\geq 1$ we set $\displaystyle z^{k+1}:=$ $\displaystyle\
z^{k}+\left(1-\dfrac{\alpha}{k+\alpha}\right)\left(z^{k}-z^{k-1}\right)-\dfrac{s\left(\alpha\beta_{k}+k\left(\beta_{k}-\beta_{k-1}\right)\right)}{2\left(k+\alpha\right)}V\left(z^{k+1}\right)$
$\displaystyle-\dfrac{sk\beta_{k-1}}{k+\alpha}\left(V\left(z^{k+1}\right)-V\left(z^{k}\right)\right).$
We will prove that, for $z_{*}\in\mathcal{Z}$, it holds

$\left\lVert z^{k}-z^{k-1}\right\rVert=o\left(\dfrac{1}{k}\right)\textrm{ as
}k\to+\infty,$

and

$\left\langle
z^{k}-z_{*},V\left(z^{k}\right)\right\rangle=o\left(\dfrac{1}{k\beta_{k}}\right)\mbox{
and }\left\lVert
V\left(z^{k}\right)\right\rVert=o\left(\dfrac{1}{k\beta_{k}}\right)\textrm{ as
}k\to+\infty,$

and that the sequence $\left(z^{k}\right)_{k\geq 0}$ converges weakly to a
solution in $\mathcal{Z}$.

The constant sequence $\beta_{k}\equiv 1$ obviously satisfies the growth
condition required in the implicit numerical scheme and for this choice the
generated sequence $\left(z^{k}\right)_{k\geq 0}$ fulfills for every $k\geq 1$

$\displaystyle z^{k+1}$
$\displaystyle=z^{k}+\left(1-\dfrac{\alpha}{k+\alpha}\right)\left(z^{k}-z^{k-1}\right)-\dfrac{s\alpha}{2\left(k+\alpha\right)}V\left(z^{k+1}\right)-\dfrac{sk}{k+\alpha}\left(V\left(z^{k+1}\right)-V\left(z^{k}\right)\right).$

From the general statement we have that

$\left\lVert z^{k}-z^{k-1}\right\rVert=o\left(\dfrac{1}{k}\right),\
\left\langle
z^{k}-z_{*},V\left(z^{k}\right)\right\rangle=o\left(\dfrac{1}{k}\right)\
\mbox{and}\ \left\lVert
V\left(z^{k}\right)\right\rVert=o\left(\dfrac{1}{k}\right)\textrm{ as
}k\to+\infty,$

and $\left(z^{k}\right)_{k\geq 0}$ converges weakly to a solution in
$\mathcal{Z}$.

A further contribution of this work is therefore this numerical algorithm with
Nesterov momentum for solving (1), obtained by implicit temporal
discretization of the inertial evolution equation and which reproduces all its
convergence properties in discrete time.

Only for the explicit discrete scheme we will additionally assume that the
operator $V$ is $L$-Lipschitz continuous, with $L>0$.

Explicit Fast OGDA: Let $\alpha>2$,
$z^{0},z^{1},\widebar{z}^{0}\in\mathcal{H}$, and $0<s<\frac{1}{2L}$. For every
$k\geq 1$ we set $\displaystyle\widebar{z}^{k}$
$\displaystyle:=z^{k}+\left(1-\dfrac{\alpha}{k+\alpha}\right)\left(z^{k}-z^{k-1}\right)-\dfrac{\alpha
s}{2\left(k+\alpha\right)}V\left(\widebar{z}^{k-1}\right)$ $\displaystyle
z^{k+1}$
$\displaystyle:=\widebar{z}^{k}-\dfrac{s}{2}\left(1+\dfrac{k}{k+\alpha}\right)\left(V\left(\widebar{z}^{k}\right)-V\left(\widebar{z}^{k-1}\right)\right).$

When taking a closer look at its equivalent formulation, which reads for every
$k\geq 1$

$\displaystyle\widebar{z}^{k}$
$\displaystyle:=z^{k}+\left(1-\dfrac{\alpha}{k+\alpha}\right)\left(z^{k}-z^{k-1}\right)-\dfrac{\alpha
s}{2\left(k+\alpha\right)}V\left(\widebar{z}^{k-1}\right)$ $\displaystyle
z^{k+1}$
$\displaystyle:=z^{k}+\left(1-\dfrac{\alpha}{k+\alpha}\right)\left(z^{k}-z^{k-1}\right)-\dfrac{\alpha
s}{2\left(k+\alpha\right)}V\left(\widebar{z}^{k}\right)-\dfrac{sk}{k+\alpha}\left(V\left(\widebar{z}^{k}\right)-V\left(\widebar{z}^{k-1}\right)\right),$

one can notice that the iterative scheme can be seen as an accelerated version
of the OGDA method. An important feature of the explicit Fast OGDA method is
that it requires the evaluation of $V$ only at the elements of the sequence
$\left(\widebar{z}^{k}\right)_{k\geq 0}$, while the Extragradient method (6)
and the Extra Anchored Gradient method (10) require the evaluation of $V$ at
both sequences $\left(z^{k}\right)_{k\geq 0}$ and
$\left(\widebar{z}^{k}\right)_{k\geq 0}$.

We will show that, for $z_{*}\in\mathcal{Z}$, it holds

$\displaystyle\left\lVert
z^{k}-z^{k-1}\right\rVert=o\left(\dfrac{1}{k}\right),\quad\left\langle
z^{k}-z_{*},V\left(z^{k}\right)\right\rangle=o\left(\dfrac{1}{k}\right),$
$\displaystyle\left\lVert
V\left(z^{k}\right)\right\rVert=o\left(\dfrac{1}{k}\right)\ \mbox{and}\
\left\lVert
V\left(\widebar{z}^{k}\right)\right\rVert=o\left(\dfrac{1}{k}\right)\textrm{
as }k\to+\infty,$

and that also for this algorithm the generated sequence
$\left(z^{k}\right)_{k\geq 0}$ converges weakly to a solution in
$\mathcal{Z}$.

Another main contribution of this work is the explicit Fast OGDA method with
Nesterov momentum and operator correction terms, for which we show the best
convergence rate results known in the literature of explicit algorithms for
monotone inclusions and the convergence of the iterates to a zero of the
operator. We illustrate the theoretical findings with numerical experiments,
which show the overwhelming superiority of our method over other numerical
algorithms designed to solve monotone equations governed by monotone and
Lipschitz continuous operators. These include the algorithms designed by using
“anchoring” techniques, for which the tracing of the iterates back to the
starting value seems to have a slowing effect on the convergence performances.

######  Remark 1.2.

(the role of the time scaling parameter function $\beta$) The function $\beta$
which appears in the formulation of the dynamical system can be seen as a time
scaling parameter function in the spirit of recent investigations on this
topic (see, for instance, [5, 7]) in the context of the minimization of a
smooth convex function. It was shown that, when used in combination with
vanishing damping (and also with Hessian-driven damping) terms, time scaling
functions improve the convergence rates of the function values and of the
gradient. The positive effect of the time scaling on the convergence rates can
be transferred to the numerical schemes obtained via implicit discretization,
as it was recently pointed out by Attouch-Chbani-Riahi in [8], and long time
ago by Güler in [26, 27] for the proximal point algorithm, which may exhibit
convergence rates for the objective function values of
$o\left(1/k^{\rho}\right)$ rate, for arbitrary $\rho>0$. On the other hand,
this does not hold for numerical schemes obtained via explicit discretization,
as it is the gradient method for which it is known that the convergence rate
of $o\left(1/k^{2}\right)$ for the objective function values (see [11]) cannot
be improved in general ([34, 35]).

This explains why the discretization of the parameter function $\beta$ appears
only in the implicit numerical scheme and in the corresponding convergence
rates, and not in the explicit numerical scheme.

##  2 The continuous time approach

In this section we will analyze the continuous time scheme proposed for (1),
and which we recall for convenience in the following.  For $t_{0}>0$ we
consider on $[t_{0},+\infty)$ the dynamical system
$\begin{dcases}\ddot{z}\left(t\right)+\dfrac{\alpha}{t}\dot{z}\left(t\right)+\beta\left(t\right)\dfrac{d}{dt}V\left(z\left(t\right)\right)+\dfrac{1}{2}\left(\dot{\beta}\left(t\right)+\dfrac{\alpha}{t}\beta\left(t\right)\right)V\left(z\left(t\right)\right)=0\\\
z\left(t_{0}\right)=z^{0}\textrm{ and
}\dot{z}\left(t_{0}\right)=\dot{z}^{0},\end{dcases}$ (12) where $\alpha\geq
2$, $\left(z^{0},\dot{z}^{0}\right)\in\mathcal{H}\times\mathcal{H}$,
$\beta\colon\left[t_{0},+\infty\right)\to\left(0,+\infty\right)$ is a
continuously differentiable and nondecreasing function which satisfies the
following growth condition $0\leq\sup\limits_{t\geq
t_{0}}\dfrac{t\dot{\beta}\left(t\right)}{\beta\left(t\right)}\leq\alpha-2,$
(13) and $t\mapsto V(z(t))$ is assumed to be differentiable on
$[t_{0},+\infty)$.

Let $z_{*}\in\mathcal{Z}$ and $0\leq\lambda\leq\alpha-1$. We consider the
following energy function
$\mathcal{E}_{\lambda}\colon\left[t_{0},+\infty\right)\to\left[0,+\infty\right)$,

$\displaystyle\mathcal{E}_{\lambda}\left(t\right):=$ $\displaystyle\
\dfrac{1}{2}\left\lVert
2\lambda\left(z\left(t\right)-z_{*}\right)+t\Bigl{(}2\dot{z}\left(t\right)+\beta\left(t\right)V\left(z\left(t\right)\right)\Bigr{)}\right\rVert^{2}+2\lambda\left(\alpha-1-\lambda\right)\left\lVert
z\left(t\right)-z_{*}\right\rVert^{2}$ $\displaystyle+2\lambda
t\beta\left(t\right)\left\langle
z\left(t\right)-z_{*},V\left(z\left(t\right)\right)\right\rangle+\dfrac{1}{2}t^{2}\beta^{2}\left(t\right)\left\lVert
V\left(z\left(t\right)\right)\right\rVert^{2},$ (14)

which will play a fundamental role in our analysis. By taking into
consideration (2), for every $0\leq\lambda\leq\alpha-1$ we have

$\mathcal{E}_{\lambda}\left(t\right)\geq 0\quad\forall t\geq t_{0}.$

Denote

$w:\left[t_{0},+\infty\right)\to\mathbb{R},\quad
w\left(t\right):=\dfrac{1}{2}\left(\left(\alpha-2\right)\dfrac{\beta\left(t\right)}{t}-\dot{\beta}\left(t\right)\right).$
(15)

The growth condition (13) guarantees that $w(t)\geq 0$ for every $t\geq
t_{0}$.

First we will show that the energy dissipates with time.

######  Lemma 2.1.

Let $z\colon\left[t_{0},+\infty\right)\to\mathcal{H}$ be a solution of (12),
$z_{*}\in\mathcal{Z}$ and $0\leq\lambda\leq\alpha-1$. Then for every $t\geq
t_{0}$ it holds

$\displaystyle\dfrac{d}{dt}\mathcal{E}_{\lambda}\left(t\right)\leq\ $
$\displaystyle-2\lambda tw\left(t\right)\left\langle
z\left(t\right)-z_{*},V\left(z\left(t\right)\right)\right\rangle+t\beta\left(t\right)\Bigl{(}\left(\alpha-1-\lambda\right)\beta\left(t\right)-2tw\left(t\right)\Bigr{)}\left\lVert
V\left(z\left(t\right)\right)\right\rVert^{2}$
$\displaystyle-\left(\alpha-1-\lambda\right)t\left\lVert
2\dot{z}\left(t\right)-\beta\left(t\right)V\left(z\left(t\right)\right)\right\rVert^{2}.$
(16)

###### Proof.

Let $t\geq t_{0}$ be fixed. From the definition of the dynamical system (12)
we have

$2t\ddot{z}\left(t\right)+t\beta\left(t\right)\dfrac{d}{dt}V\left(z\left(t\right)\right)=-2\alpha\dot{z}\left(t\right)-t\beta\left(t\right)\dfrac{d}{dt}V\left(z\left(t\right)\right)-\left(t\dot{\beta}\left(t\right)+\alpha\beta\left(t\right)\right)V\left(z\left(t\right)\right).$

Therefore

$\displaystyle\dfrac{d}{dt}\left(\dfrac{1}{2}\left\lVert
2\lambda\left(z\left(t\right)-z_{*}\right)+t\Bigl{(}2\dot{z}\left(t\right)+\beta\left(t\right)V\left(z\left(t\right)\right)\Bigr{)}\right\rVert^{2}\right)$
$\displaystyle=\ $ $\displaystyle\left\langle
2\lambda\left(z\left(t\right)-z_{*}\right)+t\Bigl{(}2\dot{z}\left(t\right)+\beta\left(t\right)V\left(z\left(t\right)\right)\Bigr{)},\right.$
$\displaystyle\ \
\left.2\left(\lambda+1\right)\dot{z}\left(t\right)+\left(t\dot{\beta}\left(t\right)+\beta\left(t\right)\right)V\left(z\left(t\right)\right)+2t\ddot{z}\left(t\right)+t\beta\left(t\right)\dfrac{d}{dt}V\left(z\left(t\right)\right)\right\rangle$
$\displaystyle=\ $ $\displaystyle\left\langle
2\lambda\left(z\left(t\right)-z_{*}\right)+2t\dot{z}\left(t\right)+t\beta\left(t\right)V\left(z\left(t\right)\right),\right.$
$\displaystyle\ \
\left.2\left(\lambda+1-\alpha\right)\dot{z}\left(t\right)+\left(1-\alpha\right)\beta\left(t\right)V\left(z\left(t\right)\right)-t\beta\left(t\right)\dfrac{d}{dt}V\left(z\left(t\right)\right)\right\rangle$
$\displaystyle=\ $ $\displaystyle
4\lambda\left(\lambda+1-\alpha\right)\left\langle
z\left(t\right)-z_{*},\dot{z}\left(t\right)\right\rangle+2\lambda\left(1-\alpha\right)\beta\left(t\right)\left\langle
z\left(t\right)-z_{*},V\left(z\left(t\right)\right)\right\rangle$
$\displaystyle-2\lambda t\beta\left(t\right)\left\langle
z\left(t\right)-z_{*},\dfrac{d}{dt}V\left(z\left(t\right)\right)\right\rangle+4\left(\lambda+1-\alpha\right)t\left\lVert\dot{z}\left(t\right)\right\rVert^{2}$
$\displaystyle+2t\left(\lambda+2-2\alpha\right)\beta\left(t\right)\left\langle\dot{z}\left(t\right),V\left(z\left(t\right)\right)\right\rangle-2t^{2}\beta\left(t\right)\left\langle\dot{z}\left(t\right),\dfrac{d}{dt}V\left(z\left(t\right)\right)\right\rangle$
$\displaystyle+\left(1-\alpha\right)t\beta^{2}\left(t\right)\left\lVert
V\left(z\left(t\right)\right)\right\rVert^{2}-t^{2}\beta^{2}\left(t\right)\left\langle
V\left(z\left(t\right)\right),\dfrac{d}{dt}V\left(z\left(t\right)\right)\right\rangle.$
(17)

By differentiating the other terms of the energy function it yields

$\displaystyle\dfrac{d}{dt}\left(2\lambda\left(\alpha-1-\lambda\right)\left\lVert
z\left(t\right)-z_{*}\right\rVert^{2}+2\lambda
t\beta\left(t\right)\left\langle
z\left(t\right)-z_{*},V\left(z\left(t\right)\right)\right\rangle+\dfrac{1}{2}t^{2}\beta^{2}\left(t\right)\left\lVert
V\left(z\left(t\right)\right)\right\rVert^{2}\right)$ $\displaystyle=\ $
$\displaystyle 4\lambda\left(\alpha-1-\lambda\right)\left\langle
z\left(t\right)-z_{*},\dot{z}\left(t\right)\right\rangle+2\lambda\left(\beta\left(t\right)+t\dot{\beta}\left(t\right)\right)\left\langle
z\left(t\right)-z_{*},V\left(z\left(t\right)\right)\right\rangle$
$\displaystyle+2\lambda
t\beta\left(t\right)\left\langle\dot{z}\left(t\right),V\left(z\left(t\right)\right)\right\rangle+2\lambda
t\beta\left(t\right)\left\langle
z\left(t\right)-z_{*},\dfrac{d}{dt}V\left(z\left(t\right)\right)\right\rangle$
$\displaystyle+t\beta\left(t\right)\left(\beta\left(t\right)+t\dot{\beta}\left(t\right)\right)\left\lVert
V\left(z\left(t\right)\right)\right\rVert^{2}+t^{2}\beta^{2}\left(t\right)\left\langle
V\left(z\left(t\right)\right),\dfrac{d}{dt}V\left(z\left(t\right)\right)\right\rangle.$
(18)

By summing up (17) and (18), and then using the definition of $w$ in (15), we
conclude that

$\displaystyle\dfrac{d}{dt}\mathcal{E}_{\lambda}\left(t\right)$
$\displaystyle=-2\lambda tw\left(t\right)\left\langle
z\left(t\right)-z_{*},V\left(z\left(t\right)\right)\right\rangle+4\left(\lambda+1-\alpha\right)t\left\lVert\dot{z}\left(t\right)\right\rVert^{2}$
$\displaystyle\quad+4\left(\lambda+1-\alpha\right)t\beta\left(t\right)\left\langle\dot{z}\left(t\right),V\left(z\left(t\right)\right)\right\rangle-2t^{2}\beta\left(t\right)\left\langle\dot{z}\left(t\right),\dfrac{d}{dt}V\left(z\left(t\right)\right)\right\rangle$
$\displaystyle\quad-2t^{2}\beta\left(t\right)w\left(t\right)\left\lVert
V\left(z\left(t\right)\right)\right\rVert^{2}.$

Finally, we observe that

$\displaystyle
4\left(\lambda+1-\alpha\right)t\left\lVert\dot{z}\left(t\right)\right\rVert^{2}+4\left(\lambda+1-\alpha\right)t\beta\left(t\right)\left\langle\dot{z}\left(t\right),V\left(z\left(t\right)\right)\right\rangle$
$\displaystyle=\ $ $\displaystyle
t\beta\left(t\right)\Bigl{(}\left(\alpha-1-\lambda\right)\beta\left(t\right)-2tw\left(t\right)\Bigr{)}\left\lVert
V\left(z\left(t\right)\right)\right\rVert^{2}-\left(\alpha-1-\lambda\right)t\left\lVert
2\dot{z}\left(t\right)-\beta\left(t\right)V\left(z\left(t\right)\right)\right\rVert^{2}.$

This, in combination with
$\left\langle\dot{z}\left(t\right),\frac{d}{dt}V\left(z\left(t\right)\right)\right\rangle\geq
0$ for every $t\geq t_{0}$, which is a consequence of the monotonicity of $V$,
leads to (16). ∎

The following theorem provides first convergence rates which follow as a
direct consequence of the previous lemma. Since $\beta$ is positive and
nondecreasing, we have $\lim_{t\to+\infty}t\beta\left(t\right)=+\infty$.

######  Theorem 2.2.

Let $z\colon\left[t_{0},+\infty\right)\to\mathcal{H}$ be a solution of (12)
and $z_{*}\in\mathcal{Z}$. For every $t\geq t_{0}$ it holds

$\displaystyle 0\leq\left\lVert V\left(z\left(t\right)\right)\right\rVert$
$\displaystyle\leq\sqrt{2\mathcal{E}_{\alpha-1}\left(t_{0}\right)}\cdot\dfrac{1}{t\beta\left(t\right)},$
(19a) $\displaystyle 0\leq\left\langle
z\left(t\right)-z_{*},V\left(z\left(t\right)\right)\right\rangle$
$\displaystyle\leq\dfrac{\mathcal{E}_{\alpha-1}\left(t_{0}\right)}{2\left(\alpha-1\right)}\cdot\dfrac{1}{t\beta\left(t\right)},$
(19b)

and the following statements are true

$\displaystyle\int_{t_{0}}^{+\infty}tw\left(t\right)\left\langle
z\left(t\right)-z_{*},V\left(z\left(t\right)\right)\right\rangle dt$
$\displaystyle<+\infty,$ (20a)
$\displaystyle\int_{t_{0}}^{+\infty}t^{2}\beta\left(t\right)w\left(t\right)\left\lVert
V\left(z\left(t\right)\right)\right\rVert^{2}dt$ $\displaystyle<+\infty.$
(20b)

If we assume in addition that

$0\leq\sup\limits_{t\geq
t_{0}}\dfrac{t\dot{\beta}\left(t\right)}{\beta\left(t\right)}<\alpha-2,$ (21)

then the trajectory $t\mapsto z\left(t\right)$ is bounded, it holds

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

and the limit
$\lim_{t\to+\infty}\mathcal{E}_{\lambda}\left(t\right)\in\mathbb{R}$ exists
for every $\lambda$ satisfying $0\leq\lambda\leq\alpha-1$.

###### Proof.

First we choose $\lambda:=\alpha-1$. Then inequality (16) reduces to

$\dfrac{d}{dt}\mathcal{E}_{\alpha-1}\left(t\right)\leq-2\left(\alpha-1\right)tw\left(t\right)\left\langle
z\left(t\right)-z_{*},V\left(z\left(t\right)\right)\right\rangle-2t^{2}\beta\left(t\right)w\left(t\right)\left\lVert
V\left(z\left(t\right)\right)\right\rVert^{2}\leq 0\quad\forall t\geq t_{0}.$
(23)

This means that $t\mapsto\mathcal{E}_{\alpha-1}\left(t\right)$ is
nonincreasing on $[t_{0},+\infty)$ and, thus ,the inequalities (19) follow
from the definition of the energy function. In addition, after integration of
(23), we obtain the statements in (20).

Now we suppose that (21) holds. Then there exists $0\leq\varepsilon<\alpha-2$
such that

$\sup\limits_{t\geq
t_{0}}\dfrac{t\dot{\beta}\left(t\right)}{\beta\left(t\right)}=\alpha-2-\varepsilon<\alpha-2.$

This means that

$w\left(t\right)=-\dfrac{1}{2}\dot{\beta}\left(t\right)+\dfrac{1}{2}\left(\alpha-2\right)\dfrac{\beta\left(t\right)}{t}\geq\dfrac{\varepsilon}{2}\dfrac{\beta\left(t\right)}{t}>0\quad\forall
t\geq t_{0}.$ (24)

Hence

$t^{2}\beta\left(t\right)w\left(t\right)\geq\dfrac{\varepsilon}{2}t\beta^{2}\left(t\right)\quad\forall
t\geq t_{0},$ (25)

which, due to (20b), gives

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

In order to prove the last statements of the theorem, we notice that the
estimate (16) gives for every $0\leq\lambda\leq\alpha-1$ and every $t\geq
t_{0}$

$\displaystyle\dfrac{d}{dt}\mathcal{E}_{\lambda}\left(t\right)$
$\displaystyle\leq\left(\alpha-1-\lambda\right)t\beta^{2}\left(t\right)\left\lVert
V\left(z\left(t\right)\right)\right\rVert^{2}-\left(\alpha-1-\lambda\right)t\left\lVert
2\dot{z}\left(t\right)-\beta\left(t\right)V\left(z\left(t\right)\right)\right\rVert^{2}$
$\displaystyle\leq
2\left(\alpha-1-\lambda\right)t\beta^{2}\left(t\right)\left\lVert
V\left(z\left(t\right)\right)\right\rVert^{2}-2\left(\alpha-1-\lambda\right)t\left\lVert\dot{z}\left(t\right)\right\rVert^{2}$
(27a) $\displaystyle\leq
2\left(\alpha-1-\lambda\right)t\beta^{2}\left(t\right)\left\lVert
V\left(z\left(t\right)\right)\right\rVert^{2}.$ (27b)

The assertion (22) follows by integration of (27a) for $\lambda:=0$ and by
using then (26). Finally, as $t\mapsto t\beta^{2}\left(t\right)\left\lVert
V\left(z\left(t\right)\right)\right\rVert^{2}\in\mathbb{L}^{1}\left(\left[t_{0},+\infty\right)\right)$,
we can apply Lemma A.1 to (27b) in order to obtain the existence of the limit
$\lim_{t\to+\infty}\mathcal{E}_{\lambda}\left(t\right)\in\mathbb{R}$ for every
$0\leq\lambda\leq\alpha-1$. ∎

The existence and uniqueness of solutions for (12) can be guaranteed in a very
general setting, which includes the one of continuously differentiable
operators defined on finite-dimensional spaces, that are obviously Lipschitz
continuous in bounded sets. The proof of Theorem 2.3 is provided in the
Appendix and it relies on showing that the maximal solution given by the
Cauchy-Lipschitz Theorem is a global solution.

######  Theorem 2.3.

Let $\alpha>2$ and assume that $V:\mathcal{H}\to\mathcal{H}$ is continuously
differentiable, $\beta:[t_{0},+\infty)\rightarrow(0,+\infty)$ is a
continuously differentiable and nondecreasing function which satisfies
condition (21) and that $V$ and $\dot{\beta}$ are Lipschitz continuous on
bounded sets. Then for every initial condition
$z\left(t_{0}\right)=z^{0}\in\mathcal{H}\textrm{ and
}\dot{z}\left(t_{0}\right)=\dot{z}^{0}\in\mathcal{H}$ the dynamical system
(12) has a unique global twice continuously differentiable solution
$z\colon\left[t_{0},+\infty\right)\to\mathcal{H}$.

Further we prove that, under the slightly stronger growth condition (21), the
trajectories of the dynamical system (12) converge to a zero of $V$. This
phenomenon is also present at inertial gradient systems with asymptotically
vanishing damping terms, where it concerns the coefficient $\alpha$, too.

######  Theorem 2.4.

Let $\alpha>2$ and $z\colon\left[t_{0},+\infty\right)\to\mathcal{H}$ be a
solution of (12) and assume that
$\beta\colon\left[t_{0},+\infty\right)\to\left(0,+\infty\right)$ satisfies the
growth condition (21), in other words

$0\leq\sup\limits_{t\geq
t_{0}}\dfrac{t\dot{\beta}\left(t\right)}{\beta\left(t\right)}<\alpha-2.$

Then $z\left(t\right)$ converges weakly to a solution of (1) as $t\to+\infty$.

###### Proof.

Let $z_{*}\in{\cal Z}$ and $0\leq\lambda_{1}<\lambda_{2}\leq\alpha-1$ be
fixed. Then by the definition of the energy function in (14) we have for every
$t\geq t_{0}$

$\displaystyle\mathcal{E}_{\lambda_{2}}\left(t\right)-\mathcal{E}_{\lambda_{1}}\left(t\right)=\
$ $\displaystyle 2\left(\lambda_{2}-\lambda_{1}\right)t\left\langle
z\left(t\right)-z_{*},2\dot{z}\left(t\right)+\beta\left(t\right)V\left(z\left(t\right)\right)\right\rangle$
$\displaystyle+2\left(\lambda_{2}-\lambda_{1}\right)\lambda\beta\left(t\right)\left\langle
z\left(t\right)-z_{*},V\left(z\left(t\right)\right)\right\rangle+2\left(\lambda_{2}-\lambda_{1}\right)\left(\alpha-1\right)\left\lVert
z\left(t\right)-z_{*}\right\rVert^{2}$ $\displaystyle=\ $ $\displaystyle
4\left(\lambda_{2}-\lambda_{1}\right)\left(t\left\langle
z\left(t\right)-z_{*},\dot{z}\left(t\right)+\beta\left(t\right)V\left(z\left(t\right)\right)\right\rangle+\dfrac{1}{2}\left(\alpha-1\right)\left\lVert
z\left(t\right)-z_{*}\right\rVert^{2}\right).$

For every $t\geq t_{0}$ we define

$\displaystyle p\left(t\right)$ $\displaystyle:=t\left\langle
z\left(t\right)-z_{*},\dot{z}\left(t\right)+\beta\left(t\right)V\left(z\left(t\right)\right)\right\rangle+\dfrac{1}{2}\left(\alpha-1\right)\left\lVert
z\left(t\right)-z_{*}\right\rVert^{2},$ (28) $\displaystyle q\left(t\right)$
$\displaystyle:=\dfrac{1}{2}\left\lVert
z\left(t\right)-z_{*}\right\rVert^{2}+\int_{t_{0}}^{t}\beta\left(s\right)\left\langle
z\left(s\right)-z_{*},V\left(z\left(s\right)\right)\right\rangle ds.$ (29)

One can easily see that for every $t\geq t_{0}$

$\dot{q}\left(t\right)=\left\langle
z\left(t\right)-z_{*},\dot{z}\left(t\right)+\beta\left(t\right)\left\langle
z\left(t\right)-z_{*},V\left(z\left(t\right)\right)\right\rangle\right\rangle=\left\langle
z\left(t\right)-z_{*},\dot{z}\left(t\right)+\beta\left(t\right)V\left(z\left(t\right)\right)\right\rangle,$

and thus

$\displaystyle\left(\alpha-1\right)q\left(t\right)+t\dot{q}\left(t\right)=p\left(t\right)+\left(\alpha-1\right)\int_{t_{0}}^{t}\beta\left(s\right)\left\langle
z\left(s\right)-z_{*},V\left(z\left(s\right)\right)\right\rangle ds.$

Since $0\leq\lambda_{1}<\lambda_{2}\leq\alpha-1$, Theorem 2.2 guarantees that
$\lim_{t\to+\infty}\left\\{\mathcal{E}_{\lambda_{2}}\left(t\right)-\mathcal{E}_{\lambda_{1}}\left(t\right)\right\\}\in\mathbb{R}$
exists, hence, by (28),

$\lim\limits_{t\to+\infty}p\left(t\right)\in\mathbb{R}\textrm{ exists}.$ (30)

Furthermore, the quantity $\int_{t_{0}}^{t}\beta\left(s\right)\left\langle
z\left(s\right)-z_{*},V\left(z\left(s\right)\right)\right\rangle ds$ is
nondecreasing with respect to $t$, and according to (24) for every $t\geq
t_{0}$ it holds

$\dfrac{\varepsilon}{2}\int_{t_{0}}^{t}\beta\left(s\right)\left\langle
z\left(s\right)-z_{*},V\left(z\left(s\right)\right)\right\rangle
ds\leq\int_{t_{0}}^{t}sw\left(s\right)\left\langle
z\left(s\right)-z_{*},V\left(z\left(s\right)\right)\right\rangle ds.$

As a consequence, we conclude from (20a) that

$\lim\limits_{t\to+\infty}\int_{t_{0}}^{t}\beta\left(s\right)\left\langle
z\left(s\right)-z_{*},V\left(z\left(s\right)\right)\right\rangle
ds\in\mathbb{R}.$ (31)

Combining (30) and (31), it yields that the limit
$\lim_{t\to+\infty}\left\\{\left(\alpha-1\right)q\left(t\right)+t\dot{q}\left(t\right)\right\\}\in\mathbb{R}$
exists, which, according to Lemma A.4, guarantees that
$\lim_{t\to+\infty}q\left(t\right)\in\mathbb{R}$. Using the definition of $q$
in (29) and once again the statement (31), we see that
$\lim_{t\to+\infty}\left\lVert
z\left(t\right)-z_{*}\right\rVert\in\mathbb{R}$. This proves the hypothesis
$\rm{(i)}$ of Opial’s Lemma (see Lemma A.2).

Finally, let $\widebar{z}$ be a weak sequential cluster point of the
trajectory $z\left(t\right)$ as $t\to+\infty$. This means that there exists a
sequence $\left(z\left(t_{n}\right)\right)_{n\geq 0}$ such that

$z\left(t_{n}\right)\rightharpoonup\widebar{z}\textrm{ as }n\to+\infty,$

where $\rightharpoonup$ denotes weak convergence. On the other hand, Theorem
2.2 ensures that

$V\left(z\left(t_{n}\right)\right)\to 0\textrm{ as }n\to+\infty.$

Since $V$ is monotone and continuous, it is maximally monotone (see, for
instance, [16, Corollary 20.28]). Therefore, the graph of $V$ is sequentially
closed in $\mathcal{H}^{\textrm{weak}}\times\mathcal{H}^{\textrm{strong}}$,
which means that $V(\widebar{z})=0$. In other words, the hypothesis
$\rm{(ii)}$ of Opial’s Lemma also holds, and the proof is complete. ∎

Next we will see that under the growth condition (21) the convergence rates
obtained in Theorem 2.2 can be improved from $\mathcal{O}$ to $o$, which is
also a phenomenon known for inertial gradient systems with asymptotically
vanishing damping terms.

######  Theorem 2.5.

Let $\alpha>2$ and $z\colon\left[t_{0},+\infty\right)\to\mathcal{H}$ be a
solution of (12), $z_{*}\in{\cal Z}$, and assume that
$\beta:[t_{0},+\infty)\rightarrow(0,+\infty)$ satisfies the growth condition
(21), in other words

$0\leq\sup\limits_{t\geq
t_{0}}\dfrac{t\dot{\beta}\left(t\right)}{\beta\left(t\right)}<\alpha-2.$

Then it holds

$\left\lVert\dot{z}\left(t\right)\right\rVert=o\left(\dfrac{1}{t}\right)\quad\textrm{
as }t\to+\infty,$

and

$\left\langle
z\left(t\right)-z_{*},V\left(z\left(t\right)\right)\right\rangle=o\left(\dfrac{1}{t\beta\left(t\right)}\right)\textrm{
and }\left\lVert
V\left(z\left(t\right)\right)\right\rVert=o\left(\dfrac{1}{t\beta\left(t\right)}\right)\quad\textrm{
as }t\to+\infty.$

###### Proof.

For every $0\leq\lambda\leq\alpha-1$ the energy function of the system can be
written as

$\displaystyle\mathcal{E}_{\lambda}\left(t\right)=$ $\displaystyle\
\dfrac{1}{2}\left\lVert
2\lambda\left(z\left(t\right)-z_{*}\right)+t\Bigl{(}2\dot{z}\left(t\right)+\beta\left(t\right)V\left(z\left(t\right)\right)\Bigr{)}\right\rVert^{2}+2\lambda\left(\alpha-1-\lambda\right)\left\lVert
z\left(t\right)-z_{*}\right\rVert^{2}$ $\displaystyle+2\lambda
t\beta\left(t\right)\left\langle
z\left(t\right)-z_{*},V\left(z\left(t\right)\right)\right\rangle+\dfrac{1}{2}t^{2}\beta^{2}\left(t\right)\left\lVert
V\left(z\left(t\right)\right)\right\rVert^{2}$ $\displaystyle=$
$\displaystyle\ 2\lambda\left(\alpha-1\right)\left\lVert
z\left(t\right)-z_{*}\right\rVert^{2}+4\lambda t\left\langle
z\left(t\right)-z_{*},\dot{z}\left(t\right)+\beta\left(t\right)V\left(z\left(t\right)\right)\right\rangle$
$\displaystyle+\dfrac{1}{2}t^{2}\left\lVert
2\dot{z}\left(t\right)+\beta\left(t\right)V\left(z\left(t\right)\right)\right\rVert^{2}+\dfrac{1}{2}t^{2}\beta^{2}\left(t\right)\left\lVert
V\left(z\left(t\right)\right)\right\rVert^{2}$ $\displaystyle=$
$\displaystyle\ 4\lambda
p\left(t\right)+t^{2}\left\lVert\dot{z}\left(t\right)+\beta\left(t\right)V\left(z\left(t\right)\right)\right\rVert^{2}+t^{2}\left\lVert\dot{z}\left(t\right)\right\rVert^{2},$

where the last equation comes from the definition of $p\left(t\right)$ in (28)
and the formula

$\left\lVert x\right\rVert^{2}+\left\lVert
y\right\rVert^{2}=\frac{1}{2}\left(\left\lVert x+y\right\rVert^{2}+\left\lVert
x-y\right\rVert^{2}\right)\quad\forall x,y\in\mathcal{H}.$ (32)

Recalling that as both limits
$\lim_{t\to+\infty}\mathcal{E}_{\lambda}\left(t\right)\in\mathbb{R}$ and
$\lim_{t\to+\infty}p\left(t\right)\in\mathbb{R}$ exist (see Theorem 2.2 and
(30)), we conclude that for
$h:[t_{0},+\infty)\rightarrow{\mathbb{R}},h(t)=t^{2}\left\lVert\dot{z}\left(t\right)+\beta\left(t\right)V\left(z\left(t\right)\right)\right\rVert^{2}+t^{2}\left\lVert\dot{z}\left(t\right)\right\rVert^{2}$,

$\lim\limits_{t\to+\infty}h\left(t\right)\in[0,+\infty)\textrm{ exists}.$ (33)

Moreover, from (22) and (26), we see that

$\displaystyle\int_{t_{0}}^{+\infty}\dfrac{1}{t}h\left(t\right)dt\leq
3\int_{t_{0}}^{+\infty}t\left\lVert\dot{z}\left(t\right)\right\rVert^{2}dt+2\int_{t_{0}}^{+\infty}t\beta^{2}\left(t\right)\left\lVert
V\left(z\left(t\right)\right)\right\rVert^{2}dt<+\infty,$

which in combination with (33) leads to $\lim_{t\rightarrow+\infty}h(t)=0$.
Thus

$\lim\limits_{t\to+\infty}t\left\lVert\dot{z}\left(t\right)+\beta\left(t\right)V\left(z\left(t\right)\right)\right\rVert=\lim\limits_{t\to+\infty}t\left\lVert\dot{z}\left(t\right)\right\rVert=0,$

and, consequently,

$\lim\limits_{t\to+\infty}t\beta\left(t\right)\left\lVert
V\left(z\left(t\right)\right)\right\rVert=0.$

Finally, by Cauchy-Schwarz inequality and the fact that the trajectory
$t\mapsto z(t)$ is bounded, we deduce that

$0\leq t\beta\left(t\right)\left\langle
z\left(t\right)-z_{*},V\left(z\left(t\right)\right)\right\rangle\leq
t\beta\left(t\right)\left\lVert z\left(t\right)-z_{*}\right\rVert\left\lVert
V\left(z\left(t\right)\right)\right\rVert\quad\forall t\geq t_{0},$

which finishes the proof. ∎

######  Remark 2.6.

One of the anonymous referees made an excellent observation regarding the
asymptotic behaviour of the trajectories on which we will elaborate in the
following. For the first order system attached to (1)

$\dot{u}\left(t\right)+V\left(u\left(t\right)\right)=0,$ (34)

it is known that the solution trajectories converge weakly in ergodic
(averaged) sense towards a zero of $V$. In other words, there exists
$z_{*}\in\mathcal{Z}$ such that
$z\left(t\right):=\frac{1}{t}\int_{0}^{t}u\left(s\right)ds\rightharpoonup
z_{*}\in\mathcal{Z}$ as $t\to+\infty$ (see, for instance, [15, 41]).

This leads to the natural idea of considering the averaging trajectory $z$,
that fulfills

$\dot{z}\left(t\right)+\dfrac{1}{t}\left(z\left(t\right)-u\left(t\right)\right)=0,$
(35)

and to drive the equation of its dynamics from (34). For more details on this
very powerful approach we refer the reader to [3].

From (35) we deduce that
$\dot{u}\left(t\right)=t\ddot{z}\left(t\right)+2\dot{z}\left(t\right)$, hence
equation (34) becomes

$t\ddot{z}\left(t\right)+2\dot{z}\left(t\right)+V\left(z\left(t\right)+t\dot{z}\left(t\right)\right)=0.$

Taking the Taylor expansion

$V\left(z\left(t\right)+t\dot{z}\left(t\right)\right)\approx
V\left(z\left(t\right)\right)+t\nabla
V\left(z\left(t\right)\right)\dot{z}\left(t\right)=V\left(z\left(t\right)\right)+t\dfrac{d}{dt}V\left(z\left(t\right)\right),$

it leads to the second-order dynamical system with correction term
$\frac{d}{dt}V\left(z\left(t\right)\right)$

$\ddot{z}\left(t\right)+\dfrac{2}{t}\dot{z}\left(t\right)+\dfrac{d}{dt}\left(V\left(z\left(t\right)\right)\right)+\dfrac{1}{t}V\left(z\left(t\right)\right)=0,$

which is of the same type as (12). This approach suggests that one can expect
the non-ergodic convergence of the solution trajectory of (12) to a zero of
$V$.

The function $\beta$ can be “inserted” into the system through time scaling
approaches aimed to speed up its convergence behaviour (see also [3, 5, 7, 8]
for related ideas).

##  3 An implicit numerical algorithm

In this section we formulate and investigate an implicit type numerical
algorithm which follows from a temporal discretization of the dynamical system
(12). We recall that the latter can be equivalently written as (see the proof
of Theorem 2.3)

$\begin{dcases}\dot{u}\left(t\right)&=\Bigl{(}t\dot{\beta}\left(t\right)+\left(2-\alpha\right)\beta\left(t\right)\Bigr{)}V\left(z\left(t\right)\right)\\\
u\left(t\right)&=2\left(\alpha-1\right)z\left(t\right)+2t\dot{z}\left(t\right)+2t\beta\left(t\right)V\left(z\left(t\right)\right)\end{dcases},$
(36)

with the initializations $z\left(t_{0}\right)=z^{0}\textrm{ and
}\dot{z}\left(t_{0}\right)=\dot{z}^{0}$.

We fix a time step $s>0$, set $\tau_{k}:=s\left(k+1\right)$ and
$\sigma_{k}:=sk$ for every $k\geq 1$, and approximate
$z\left(\tau_{k}\right)\approx z^{k+1}$, $u\left(\tau_{k}\right)\approx
u^{k+1}$, and $\beta\left(\sigma_{k}\right)\approx\beta_{k}$. The implicit
finite-difference scheme for (36) at time $t:=\tau_{k}$ for $\left(z,u\right)$
and at time $t:=\sigma_{k}$ for $\beta$ gives for every $k\geq 1$

$\begin{dcases}\dfrac{u^{k+1}-u^{k}}{s}&=\Bigl{(}k\left(\beta_{k}-\beta_{k-1}\right)+\left(2-\alpha\right)\beta_{k}\Bigr{)}V\left(z^{k+1}\right)\\\
u^{k+1}&=2\left(\alpha-1\right)z^{k+1}+2\left(k+1\right)\left(z^{k+1}-z^{k}\right)+2s\left(k+1\right)\beta_{k}V\left(z^{k+1}\right)\end{dcases},$
(37)

with the initialization $u^{1}:=z^{0}$ and $u^{0}:=z^{0}-s\dot{z}^{0}$.
Therefore we have for every $k\geq 1$

$u^{k}=2\left(\alpha-1\right)z^{k}+2k\left(z^{k}-z^{k-1}\right)+2sk\beta_{k-1}V\left(z^{k}\right),$

and after substraction we get

$\displaystyle u^{k+1}-u^{k}=$ $\displaystyle\
2\left(k+\alpha\right)\left(z^{k+1}-z^{k}\right)-2k\left(z^{k}-z^{k-1}\right)+2s\Bigl{(}\left(k+1\right)\beta_{k}-k\beta_{k-1}\Bigr{)}V\left(z^{k+1}\right)$
$\displaystyle+2sk\beta_{k-1}\left(V\left(z^{k+1}\right)-V\left(z^{k}\right)\right)$
$\displaystyle=$ $\displaystyle\
s\Bigl{(}k\left(\beta_{k}-\beta_{k-1}\right)+\left(2-\alpha\right)\beta_{k}\Bigr{)}V\left(z^{k+1}\right),$
(38)

where the last relation comes from the first equation in (37). From here, we
deduce that for every $k\geq 1$

$\displaystyle z^{k+1}=$ $\displaystyle\
z^{k}+\left(1-\dfrac{\alpha}{k+\alpha}\right)\left(z^{k}-z^{k-1}\right)-\dfrac{s\left(\alpha\beta_{k}+k\left(\beta_{k}-\beta_{k-1}\right)\right)}{2\left(k+\alpha\right)}V\left(z^{k+1}\right)$
$\displaystyle-\dfrac{sk\beta_{k-1}}{k+\alpha}\left(V\left(z^{k+1}\right)-V\left(z^{k}\right)\right).$

For

$s_{k}:=\dfrac{s\left(\alpha\beta_{k}+k\left(\beta_{k}-\beta_{k-1}\right)\right)}{2\left(k+\alpha\right)}\quad\mbox{and}\quad
t_{k}:=\dfrac{sk\beta_{k-1}}{k+\alpha},$

the algorithm can be further equivalently written as

$\displaystyle
z^{k+1}:=(\mathrm{Id}+(s_{k}+t_{k})V)^{-1}\left(z^{k}+\left(1-\dfrac{\alpha}{k+\alpha}\right)\left(z^{k}-z^{k-1}\right)+t_{k}V\left(z^{k}\right)\right)\quad\forall
k\geq 1,$

and is therefore well-defined due to the maximal monotonicity of $V$.

We also want to point out that the discrete version of the growth condition
(21) reads

$0\leq\sup_{k\geq
1}\dfrac{k\left(\beta_{k}-\beta_{k-1}\right)}{\beta_{k}}<\alpha-2,$

where $\left(\beta_{k}\right)_{k\geq 0}$ is a positive and nondecreasing
sequence. This means that there exists some $0\leq\varepsilon<\alpha-2$ such
that

$\dfrac{k\left(\beta_{k}-\beta_{k-1}\right)}{\beta_{k}}\leq\alpha-2-\varepsilon\
\mbox{or, equivalently,}\
k\left(\beta_{k}-\beta_{k-1}\right)\leq\left(\alpha-2-\varepsilon\right)\beta_{k}\quad\forall
k\geq 1.$ (39)

In addition, for every $k\geq\left\lceil\alpha\right\rceil$ it holds

$\beta_{k}\leq\dfrac{k}{k+2+\varepsilon-\alpha}\beta_{k-1}\leq\dfrac{\alpha}{2+\varepsilon}\beta_{k-1}.$
(40)

To sum up, the implicit algorithm we propose for solving (1) is formulated
below.

######  Algorithm 1.

(Implicit Fast OGDA) Let $\alpha>2,z^{0},z^{1}\in\mathcal{H}$, $s>0$, and
$\left(\beta_{k}\right)_{k\geq 0}$ a positive and nondecreasing sequence which
satisfies $0\leq\sup_{k\geq
1}\dfrac{k\left(\beta_{k}-\beta_{k-1}\right)}{\beta_{k}}<\alpha-2.$ (41) For
every $k\geq 1$ we set $\displaystyle z^{k+1}=$ $\displaystyle\
z^{k}+\left(1-\dfrac{\alpha}{k+\alpha}\right)\left(z^{k}-z^{k-1}\right)-\dfrac{s\left(\alpha\beta_{k}+k\left(\beta_{k}-\beta_{k-1}\right)\right)}{2\left(k+\alpha\right)}V\left(z^{k+1}\right)$
$\displaystyle-\dfrac{sk\beta_{k-1}}{k+\alpha}\left(V\left(z^{k+1}\right)-V\left(z^{k}\right)\right).$
Inspired by the continuous setting, we consider for $0\leq\lambda\leq\alpha-1$
the following sequence defined for every $k\geq 1$

$\displaystyle\mathcal{E}_{\lambda}^{k}:=$ $\displaystyle\
\dfrac{1}{2}\left\lVert
2\lambda\left(z^{k}-z_{*}\right)+2k\left(z^{k}-z^{k-1}\right)+sk\beta_{k-1}V\left(z^{k}\right)\right\rVert^{2}+2\lambda\left(\alpha-1-\lambda\right)\left\lVert
z^{k}-z_{*}\right\rVert^{2}$ $\displaystyle+2\lambda sk\beta_{k-1}\left\langle
z^{k}-z_{*},V\left(z^{k}\right)\right\rangle+\dfrac{1}{2}s^{2}\left(k+\alpha\right)k\beta_{k}\beta_{k-1}\left\lVert
V\left(z^{k}\right)\right\rVert^{2}\geq 0,$

which is the discrete version of the energy function considered in the
previous section. We have for every $k\geq 1$

$\displaystyle\mathcal{E}_{\lambda}^{k}=$ $\displaystyle\
2\lambda\left(\alpha-1\right)\left\lVert z^{k}-z_{*}\right\rVert^{2}+4\lambda
k\left\langle
z^{k}-z_{*},z^{k}-z^{k-1}+s\beta_{k-1}V\left(z^{k}\right)\right\rangle$
$\displaystyle+\dfrac{1}{2}k^{2}\left\lVert
2\left(z^{k}-z^{k-1}\right)+s\beta_{k-1}V\left(z^{k}\right)\right\rVert^{2}+\dfrac{1}{2}s^{2}\left(k+\alpha\right)k\beta_{k}\beta_{k-1}\left\lVert
V\left(z^{k}\right)\right\rVert^{2}.$ (42)

The following lemma shows that the discrete energy dissipates with every
iteration of the algorithm. Its proof can be found in the Appendix. Lemma 3.1
is the essential ingredient for the derivation of the convergence rates in
Theorem 3.2.

######  Lemma 3.1.

Let $z_{*}\in{\cal Z}$ and $\left(z^{k}\right)_{k\geq 0}$ the sequence
generated by Algorithm 1 for $\left(\beta_{k}\right)_{k\geq 0}$ a positive and
nondecreasing sequence which satisfies (41). Then for every
$0\leq\lambda\leq\alpha-1$ and every $k\geq\left\lceil\alpha\right\rceil$ it
holds

$\displaystyle\mathcal{E}_{\lambda}^{k+1}-\mathcal{E}_{\lambda}^{k}$
$\displaystyle\leq 2\lambda
s\Bigl{(}\left(k+2-\alpha\right)\beta_{k}-k\beta_{k-1}\Bigr{)}\left\langle
z^{k+1}-z_{*},V\left(z^{k+1}\right)\right\rangle$
$\displaystyle\quad+2\left(\lambda+1-\alpha\right)\left(2k+\alpha+1\right)\left\lVert
z^{k+1}-z^{k}\right\rVert^{2}$
$\displaystyle\quad+2s\biggl{(}\Bigl{(}\left(\lambda+1-\alpha\right)\left(2k+\alpha+1\right)-\lambda\Bigr{)}\beta_{k}-\lambda
k\left(\beta_{k}-\beta_{k-1}\right)\biggr{)}\left\langle
z^{k+1}-z^{k},V\left(z^{k+1}\right)\right\rangle$
$\displaystyle\quad-2sk\left(k+\alpha\right)\beta_{k-1}\left\langle
z^{k+1}-z^{k},V\left(z^{k+1}\right)-V\left(z^{k}\right)\right\rangle$
$\displaystyle\quad+\dfrac{1}{2}\Bigl{(}C-\varepsilon\left(2k+\alpha+1\right)\Bigr{)}s^{2}\beta_{k}^{2}\left\lVert
V\left(z^{k+1}\right)\right\rVert^{2}$
$\displaystyle\quad-\dfrac{1}{2}s^{2}k\Bigl{(}\left(k+\alpha\right)\beta_{k}+k\beta_{k-1}\Bigr{)}\beta_{k-1}\left\lVert
V\left(z^{k+1}\right)-V\left(z^{k}\right)\right\rVert^{2},$ (43)

where

$C:=\dfrac{\alpha}{2+\varepsilon}\left(\alpha-2-\varepsilon\right)\left(2\alpha-2-\varepsilon\right)>0$
(44)

and $\varepsilon$ is chosen to fulfill (39).

######  Theorem 3.2.

Let $z_{*}\in{\cal Z}$ and $\left(z^{k}\right)_{k\geq 0}$ the sequence
generated by Algorithm 1 for $\left(\beta_{k}\right)_{k\geq 0}$ a positive and
nondecreasing sequence which satisfies (41), and $0\leq\varepsilon<\alpha-2$
be such that (39) is satisfied. Then it holds

$\left\langle
z^{k}-z_{*},V\left(z^{k}\right)\right\rangle=\mathcal{O}\left(\dfrac{1}{k\beta_{k}}\right)\textrm{
and }\left\lVert
V\left(z^{k}\right)\right\rVert=\mathcal{O}\left(\dfrac{1}{k\beta_{k}}\right)\textrm{
as }k\to+\infty.$

In addition, for every $\alpha-1-\frac{\varepsilon}{4}<\lambda<\alpha-1$, the
sequence $\left(\mathcal{E}_{\lambda}^{k}\right)_{k\geq 1}$ converges,
$\left(z^{k}\right)_{k\geq 0}$ is bounded and

$\displaystyle\displaystyle\sum\limits_{k\geq 1}\beta_{k}\left\langle
z^{k+1}-z_{*},V\left(z^{k+1}\right)\right\rangle<+\infty,$ (45a)
$\displaystyle\displaystyle\sum\limits_{k\geq 1}k\left\lVert
z^{k+1}-z^{k}\right\rVert^{2}<+\infty,$ (45b)
$\displaystyle\displaystyle\sum\limits_{k\geq 1}k\beta_{k}^{2}\left\lVert
V\left(z^{k+1}\right)\right\rVert^{2}<+\infty.$ (45c)

###### Proof.

Let $0<\alpha-1-\frac{\varepsilon}{4}<\lambda<\alpha-1$. First we show that
for sufficiently large $k$ it holds

$\displaystyle R_{k}:=$
$\displaystyle\left(\lambda+1-\alpha\right)\left(2k+\alpha+1\right)\left\lVert
z^{k+1}-z^{k}\right\rVert^{2}$
$\displaystyle+2s\biggl{(}\Bigl{(}\left(\lambda+1-\alpha\right)\left(2k+\alpha+1\right)-\lambda\Bigr{)}\beta_{k}-\lambda
k\left(\beta_{k}-\beta_{k-1}\right)\biggr{)}\left\langle
z^{k+1}-z^{k},V\left(z^{k+1}\right)\right\rangle$
$\displaystyle+\dfrac{1}{4}\Bigl{(}C-\varepsilon\left(2k+\alpha+1\right)\Bigr{)}s^{2}\beta_{k}^{2}\left\lVert
V\left(z^{k+1}\right)\right\rVert^{2}\leq 0,$ (46)

where $C>0$ is given by (44). By setting $K_{\alpha}:=2k+\alpha+1\geq 1$, for
every $k\geq 0$ we have

$\displaystyle R_{k}=$
$\displaystyle\left(\lambda+1-\alpha\right)K_{\alpha}\left\lVert
z^{k+1}-z^{k}\right\rVert^{2}+\dfrac{1}{4}s^{2}\left(C-\varepsilon
K_{\alpha}\right)\beta_{k}^{2}\left\lVert
V\left(z^{k+1}\right)\right\rVert^{2}$
$\displaystyle+2s\biggl{(}\Bigl{(}\left(\lambda+1-\alpha\right)K_{\alpha}-\lambda\Bigr{)}\beta_{k}-\lambda
k\left(\beta_{k}-\beta_{k-1}\right)\biggr{)}\left\langle
z^{k+1}-z^{k},V\left(z^{k+1}\right)\right\rangle.$

To guarantee that $R_{k}\leq 0$ for sufficiently large $k$, we show that

$\dfrac{\Delta_{k}}{s^{2}}:=4\biggl{(}\Bigl{(}\left(\lambda+1-\alpha\right)K_{\alpha}-\lambda\Bigr{)}\beta_{k}-\lambda
k\left(\beta_{k}-\beta_{k-1}\right)\biggr{)}^{2}-\left(\lambda+1-\alpha\right)\left(C-\varepsilon
K_{\alpha}\right)K_{\alpha}\beta_{k}^{2}\leq 0$

sufficiently large $k$. Since $\left(\beta_{k}\right)_{k\geq 0}$ is
nondecreasing and $\lambda<\alpha-1$, it follows from (39) that for every
$k\geq 1$

$\displaystyle 0\geq$
$\displaystyle\Bigl{(}\left(\lambda+1-\alpha\right)K_{\alpha}-\lambda\Bigr{)}\beta_{k}-\lambda
k\left(\beta_{k}-\beta_{k-1}\right)\geq\Bigl{(}\left(\lambda+1-\alpha\right)K_{\alpha}-\lambda\Bigr{)}\beta_{k}-\lambda\left(\alpha-2-\varepsilon\right)\beta_{k}$
$\displaystyle=$
$\displaystyle\Bigl{(}\left(\lambda+1-\alpha\right)K_{\alpha}-\lambda\left(\alpha-1-\varepsilon\right)\Bigr{)}\beta_{k},$

and thus

$\displaystyle\dfrac{\Delta_{k}}{s^{2}\beta_{k}^{2}}:=$
$\displaystyle\dfrac{4}{\beta_{k}^{2}}\Bigl{(}\Bigl{(}\left(\lambda+1-\alpha\right)K_{\alpha}-\lambda\Bigr{)}\beta_{k}-\lambda
k\left(\beta_{k}-\beta_{k-1}\right)\Bigr{)}^{2}-\left(\lambda+1-\alpha\right)\left(C-\varepsilon
K_{\alpha}\right)K_{\alpha}$ $\displaystyle\leq$ $\displaystyle\
4\Bigl{(}\left(\lambda+1-\alpha\right)K_{\alpha}-\lambda\left(\alpha-1-\varepsilon\right)\Bigr{)}^{2}-\left(\lambda+1-\alpha\right)\left(C-\varepsilon
K_{\alpha}\right)K_{\alpha}$ $\displaystyle=$ $\displaystyle\
4\left(\lambda+1-\alpha\right)^{2}K_{\alpha}^{2}-8\lambda\left(\lambda+1-\alpha\right)\left(\alpha-1-\varepsilon\right)K_{\alpha}+4\lambda^{2}\left(\alpha-1-\varepsilon\right)^{2}$
$\displaystyle-\left(\lambda+1-\alpha\right)CK_{\alpha}+\varepsilon\left(\lambda+1-\alpha\right)K_{\alpha}^{2}$
$\displaystyle=$
$\displaystyle\left(\lambda+1-\alpha\right)\\!\Bigl{(}4\left(\lambda+1-\alpha\right)+\varepsilon\Bigr{)}K_{\alpha}^{2}-\\!\left(\lambda+1-\alpha\right)\Bigl{(}8\lambda\left(\alpha-1-\varepsilon\right)+C\Bigr{)}K_{\alpha}+4\lambda^{2}\left(\alpha-1-\varepsilon\right)^{2}.$

Since $\alpha-1-\frac{\varepsilon}{4}<\lambda<\alpha-1$, we have
$\left(\lambda+1-\alpha\right)\Bigl{(}4\left(\lambda+1-\alpha\right)+\varepsilon\Bigr{)}<0$,
hence for sufficiently large $k\geq 0$ it holds $\Delta_{k}\leq 0$ and,
consequently, $R_{k}\geq 0$.

From (39) we deduce that
$\left(k+2-\alpha\right)\beta_{k}-k\beta_{k-1}\leq-\varepsilon\beta_{k}$ for
every $k\geq 1$. Hence, for every
$\alpha-1-\frac{\varepsilon}{4}<\lambda<\alpha-1$, from Lemma 3.1 and (46) we
have that for sufficiently large $k$ it holds

$\displaystyle\mathcal{E}_{\lambda}^{k+1}-\mathcal{E}_{\lambda}^{k}\leq$
$\displaystyle-\varepsilon 2\lambda s\beta_{k}\left\langle
z^{k+1}-z_{*},V\left(z^{k+1}\right)\right\rangle+\left(\lambda+1-\alpha\right)\left(2k+\alpha+1\right)\left\lVert
z^{k+1}-z^{k}\right\rVert^{2}$
$\displaystyle-2sk\left(k+\alpha\right)\beta_{k-1}\left\langle
z^{k+1}-z^{k},V\left(z^{k+1}\right)-V\left(z^{k}\right)\right\rangle$
$\displaystyle+\dfrac{1}{4}\Bigl{(}C-\varepsilon\left(2k+\alpha+1\right)\Bigr{)}s^{2}\beta_{k}^{2}\left\lVert
V\left(z^{k+1}\right)\right\rVert^{2}$
$\displaystyle-\dfrac{1}{2}s^{2}k\Bigl{(}\left(k+\alpha\right)\beta_{k}+k\beta_{k-1}\Bigr{)}\beta_{k-1}\left\lVert
V\left(z^{k+1}\right)-V\left(z^{k}\right)\right\rVert^{2},$

which means the sequence $\left\\{\mathcal{E}_{\lambda}^{k}\right\\}_{k\geq
1}$ is nonincreasing for sufficiently large $k$, thus it is convergent and the
boundedness of $\left(z^{k}\right)_{k\geq 0}$ and the convergence rates follow
from the definition of $\mathcal{E}_{\lambda}^{k}$ and (40). The remaining
assertions follow from Lemma A.6. ∎

Next we prove the weak convergence of the generated sequence of iterates.

######  Theorem 3.3.

Let $z_{*}\in{\cal Z}$ and $\left(z^{k}\right)_{k\geq 0}$ the sequence
generated by Algorithm 1 for $\left(\beta_{k}\right)_{k\geq 0}$ a positive and
nondecreasing sequence which satisfies (41). Then the sequence
$\left(z^{k}\right)_{k\geq 0}$ converges weakly to a solution of (1).

###### Proof.

Let $0\leq\varepsilon<\alpha-2$ such that (39) is satisfied and
$0<\alpha-1-\frac{\varepsilon}{4}<\lambda_{1}<\lambda_{2}<\alpha-1$. For every
$k\geq 1$ we set

$\displaystyle p_{k}$
$\displaystyle:=\dfrac{1}{2}\left(\alpha-1\right)\left\lVert
z^{k}-z_{*}\right\rVert^{2}+k\left\langle
z^{k}-z_{*},z^{k}-z^{k-1}+s\beta_{k-1}V\left(z^{k}\right)\right\rangle,$ (47)
$\displaystyle q_{k}$ $\displaystyle:=\dfrac{1}{2}\left\lVert
z^{k}-z_{*}\right\rVert^{2}+s\displaystyle\sum\limits_{i=1}^{k}\beta_{i-1}\left\langle
z^{i}-z_{*},V\left(z^{i}\right)\right\rangle,$ (48)

and notice that

$\left(\alpha-1\right)q_{k}+k\left(q_{k}-q_{k-1}\right)=p_{k}+\left(\alpha-1\right)s\displaystyle\sum\limits_{i=1}^{k+1}\beta_{i-1}\left\langle
z^{i}-z_{*},V\left(z^{i}\right)\right\rangle-\dfrac{k}{2}\left\lVert
z^{k}-z^{k-1}\right\rVert^{2}.$

We have that

$\lim\limits_{k\to+\infty}p_{k}=\lim_{k\to+\infty}\frac{1}{4(\lambda_{2}-\lambda_{1})}\left(\mathcal{E}_{\lambda_{2}}^{k}-\mathcal{E}_{\lambda_{1}}^{k}\right)\in\mathbb{R}\textrm{
exists}$ (49)

and, thanks to (45), that the limit
$\lim_{k\to+\infty}\sum_{i=1}^{k+1}\beta_{i-1}\left\langle
z^{i}-z_{*},V\left(z^{i}\right)\right\rangle\in\mathbb{R}$ exists and

$\lim\limits_{k\to+\infty}k\left\lVert z^{k+1}-z^{k}\right\rVert^{2}=0.$

Consequently,

$\lim\limits_{k\to+\infty}\left(\left(\alpha-1\right)q_{k}+k\left(q_{k}-q_{k-1}\right)\right)\in\mathbb{R}\textrm{
exists}.$

From Theorem 3.2 we deduce that $\left(q_{k}\right)_{k\geq 1}$ is bounded.
This allows us to apply Lemma A.5 and to conclude from here that
$\lim_{k\to+\infty}q_{k}\in\mathbb{R}$ also exists. Once again, by the
definition of $q_{k}$ and the fact that the sequence
$\left(\sum_{i=1}^{k}\beta_{i-1}\left\langle
z^{i}-z_{*},V\left(z^{i}\right)\right\rangle\right)_{k\geq 1}$ converges, it
follows that $\lim_{k\to+\infty}\left\lVert
z_{k}-z_{*}\right\rVert\in\mathbb{R}$ exists. In other words, the hypothesis
$\rm{(i)}$ in Opial’s Lemma (see Lemma A.3) is fulfilled.

Now let $\widebar{z}$ be a weak sequential cluster point of
$\left(z^{k}\right)_{k\geq 0}$, meaning that there exists a subsequence
$\left(z^{k_{n}}\right)_{n\geq 0}$ such that

$z^{k_{n}}\rightharpoonup\widebar{z}\textrm{ as }n\to+\infty.$

From Theorem 3.2 we have

$V\left(z^{k_{n}}\right)\to 0\textrm{ as }n\to+\infty.$

Since $V$ monotone and continuous, it s maximally monotone [16, Corollary
20.28]. Therefore, the graph of $V$ is sequentially closed in
$\mathcal{H}^{\textrm{weak}}\times\mathcal{H}^{\textrm{strong}}$, which gives
that $V(\widebar{z})=0$, thus $\widebar{z}\in\mathcal{Z}$. This shows that
hypothesis $\rm{(ii)}$ of Opial’s Lemma is also fulfilled, and completes the
proof. ∎

We close the section with a result which improves the convergence rates
derived in Theorem 3.2 for the implicit algorithm.

######  Theorem 3.4.

Let $z_{*}\in{\cal Z}$ and $\left(z^{k}\right)_{k\geq 0}$ the sequence
generated by Algorithm 1 for $\left(\beta_{k}\right)_{k\geq 0}$ a positive and
nondecreasing sequence which satisfies (41). Then it holds

$\left\lVert z^{k}-z^{k-1}\right\rVert=o\left(\dfrac{1}{k}\right)\textrm{ as
}k\to+\infty$

and

$\left\langle
z^{k}-z_{*},V\left(z^{k}\right)\right\rangle=o\left(\dfrac{1}{k\beta_{k}}\right)\
\mbox{and}\ \left\lVert
V\left(z^{k}\right)\right\rVert=o\left(\dfrac{1}{k\beta_{k}}\right)\textrm{ as
}k\to+\infty.$

###### Proof.

Let $0\leq\varepsilon<\alpha-2$ such that (39) is satisfied and
$0<\alpha-1-\frac{\varepsilon}{4}<\lambda<\alpha-1$. In the view of (47), the
discrete energy sequence can be written as

$\mathcal{E}_{\lambda}^{k}=4\lambda p_{k}+\dfrac{1}{2}k^{2}\left\lVert
2\left(z^{k}-z^{k-1}\right)+s\beta_{k-1}V\left(z^{k}\right)\right\rVert^{2}+\dfrac{1}{2}s^{2}\left(k+\alpha\right)k\beta_{k}\beta_{k-1}\left\lVert
V\left(z^{k}\right)\right\rVert^{2}\quad\forall k\geq 1.$

According to Theorem 3.2, we have

$\lim\limits_{k\to+\infty}k\beta_{k}\beta_{k-1}\left\lVert
V\left(z^{k}\right)\right\rVert^{2}=0.$

This statement together with the fact that the limits
$\lim_{k\to+\infty}\mathcal{E}_{\lambda}^{k}\in\mathbb{R}$ and
$\lim_{k\to+\infty}p_{k}\in\mathbb{R}$ (according to (49)) exist, allows us to
deduce that for the sequence

$h_{k}:=\dfrac{k^{2}}{2}\left(\left\lVert
2\left(z^{k}-z^{k-1}\right)+s\beta_{k-1}V\left(z^{k}\right)\right\rVert^{2}+s^{2}\beta_{k}\beta_{k-1}\left\lVert
V\left(z^{k}\right)\right\rVert^{2}\right)\quad\forall k\geq 1,$

the limit

$\lim\limits_{k\to+\infty}h_{k}\in[0,+\infty)\textrm{ exists}.$

Furthermore, by taking into consideration the relation (40), Theorem 3.2 also
guarantees that

$\displaystyle\displaystyle\sum\limits_{k\geq\left\lceil\alpha\right\rceil}\dfrac{1}{k}h_{k}$
$\displaystyle\leq
2\displaystyle\sum\limits_{k\geq\left\lceil\alpha\right\rceil}k\left\lVert
z^{k}-z^{k-1}\right\rVert^{2}+s^{2}\displaystyle\sum\limits_{k\geq\left\lceil\alpha\right\rceil}k\left(\beta_{k-1}+\dfrac{\beta_{k}}{2}\right)\beta_{k-1}\left\lVert
V\left(z^{k}\right)\right\rVert^{2}$ $\displaystyle\leq
2\displaystyle\sum\limits_{k\geq\left\lceil\alpha\right\rceil}k\left\lVert
z^{k}-z^{k-1}\right\rVert^{2}+s^{2}\left(1+\dfrac{\alpha}{2\left(2+\varepsilon\right)}\right)\displaystyle\sum\limits_{k\geq
1}k\beta_{k-1}^{2}\left\lVert V\left(z^{k}\right)\right\rVert^{2}<+\infty.$

From here we conclude that $\lim_{k\to+\infty}h_{k}=0$, and since $h_{k}$ is a
sum of two nonnegative terms and, since $\left(\beta_{k}\right)_{k\geq 0}$ is
nondecreasing, we further deduce

$\lim\limits_{k\to+\infty}k\left\lVert
2\left(z^{k}-z^{k-1}\right)+s\beta_{k-1}V\left(z^{k}\right)\right\rVert=\lim\limits_{k\to+\infty}k\sqrt{\beta_{k}\beta_{k-1}}\left\lVert
V\left(z^{k}\right)\right\rVert=\lim\limits_{k\to+\infty}k\beta_{k-1}\left\lVert
V\left(z^{k}\right)\right\rVert=0.$

Using once again (40), we obtain

$\lim\limits_{k\to+\infty}k\beta_{k}\left\lVert
V\left(z^{k}\right)\right\rVert=0.$

Since $\left(z_{k}\right)_{k\geq 0}$ is bounded, we use the Cauchy-Schwarz
inequality to derive

$0\leq\lim\limits_{k\to+\infty}k\beta_{k}\left\langle
z^{k}-z_{*},V\left(z^{k}\right)\right\rangle\leq\lim\limits_{k\to+\infty}k\beta_{k}\left\lVert
z^{k}-z_{*}\right\rVert\left\lVert V\left(z^{k}\right)\right\rVert=0,$

and the proof is complete. ∎

##  4 An explicit algorithm

In this section, additional to its monotonicity, we will assume that the
operator $V$ is $L$-Lipschitz continuous, with $L>0$. We propose and
investigate an explicit numerical algorithm for solving (1), which follows
from a temporal discretization of the dynamical system (12).

The starting point is again its reformulation (36). We fix a time step $s>0$,
set $\tau_{k}:=s\left(k+1\right)$ for every $k\geq 1$, and approximate
$z\left(\tau_{k}\right)\approx z^{k+1}$ and $u\left(\tau_{k}\right)\approx
u^{k+1}$. In addition, we choose $\beta\left(\tau_{k}\right)=1$ for every
$k\geq 1$ and refer to Remark 1.2 for the explanation of why the time scaling
parameter function $\beta$ is discretized via a constant sequence. The finite-
difference scheme for (36) at time $t:=\tau_{k}$ gives for every $k\geq 0$

$\begin{dcases}\dfrac{u^{k+1}-u^{k}}{s}&=\left(2-\alpha\right)V\left(\widebar{z}^{k}\right)\\\
u^{k+1}&=2\left(\alpha-1\right)z^{k+1}+2\left(k+1\right)\left(z^{k+1}-z^{k}\right)+2s\left(k+1\right)V\left(\widebar{z}^{k}\right)\end{dcases}.$
(50)

Therefore we have for every $k\geq 1$

$u^{k}=2\left(\alpha-1\right)z^{k}+2k\left(z^{k}-z^{k-1}\right)+2skV\left(\widebar{z}^{k-1}\right),$
(51)

and after substraction we get

$\displaystyle u^{k+1}-u^{k}$
$\displaystyle=2\left(k+\alpha\right)\left(z^{k+1}-z^{k}\right)-2k\left(z^{k}-z^{k-1}\right)+2sV\left(\widebar{z}^{k}\right)+2sk\left(V\left(\widebar{z}^{k}\right)-V\left(\widebar{z}^{k-1}\right)\right)$
$\displaystyle=\left(2-\alpha\right)sV\left(\widebar{z}^{k}\right),$ (52)

where the last relation comes from the first equation in (50).

On the other hand, the second equation in (50) can be rewritten for every
$k\geq 0$ as

$z^{k+1}=\dfrac{1}{2\left(k+\alpha\right)}u^{k+1}+\dfrac{k+1}{k+\alpha}\left(z^{k}-sV\left(\widebar{z}^{k}\right)\right).$
(53)

To get an explicit choice for $\widebar{z}^{k}$, we opt for

$\widebar{z}^{k}:=\dfrac{1}{2\left(k+\alpha\right)}u^{k}+\dfrac{k+1}{k+\alpha}\left(z^{k}-\dfrac{sk}{k+1}V\left(\widebar{z}^{k-1}\right)\right)-\dfrac{\alpha
s}{2\left(k+\alpha\right)}V\left(\widebar{z}^{k-1}\right)\quad\forall k\geq
1.$ (54)

From here, (51) gives for all $k\geq 1$

$\displaystyle\widebar{z}^{k}$
$\displaystyle=z^{k}+\dfrac{k}{k+\alpha}\left(z^{k}-z^{k-1}\right)-\dfrac{\alpha
s}{2\left(k+\alpha\right)}V\left(\widebar{z}^{k-1}\right)$
$\displaystyle=z^{k}+\left(1-\dfrac{\alpha}{k+\alpha}\right)\left(z^{k}-z^{k-1}\right)-\dfrac{\alpha
s}{2\left(k+\alpha\right)}V\left(\widebar{z}^{k-1}\right),$

thus, by subtracting (54) from (53), we obtain

$\displaystyle z^{k+1}-\widebar{z}^{k}$
$\displaystyle=\dfrac{1}{2\left(k+\alpha\right)}\left(u^{k+1}-u^{k}\right)-\dfrac{s\left(k+1\right)}{k+\alpha}V\left(\widebar{z}^{k}\right)+\dfrac{sk}{k+\alpha}V\left(\widebar{z}^{k-1}\right)-\dfrac{\alpha
s}{2\left(k+\alpha\right)}V\left(\widebar{z}^{k-1}\right)$
$\displaystyle=-\dfrac{\alpha
s}{2\left(k+\alpha\right)}V\left(\widebar{z}^{k}\right)-\dfrac{sk}{k+\alpha}\left(V\left(\widebar{z}^{k}\right)-V\left(\widebar{z}^{k-1}\right)\right)+\dfrac{\alpha
s}{2\left(k+\alpha\right)}V\left(\widebar{z}^{k-1}\right)$
$\displaystyle=-\dfrac{s}{2}\left(1+\dfrac{k}{k+\alpha}\right)\left(V\left(\widebar{z}^{k}\right)-V\left(\widebar{z}^{k-1}\right)\right).$
(55)

This gives the following important estimate, which holds for every $s>0$ such
that $sL\leq 1$ and every $k\geq 1$

$\left\lVert
V\left(z^{k+1}\right)-V\left(\widebar{z}^{k}\right)\right\rVert\leq
L\left\lVert z^{k+1}-\widebar{z}^{k}\right\rVert\leq sL\left\lVert
V\left(\widebar{z}^{k}\right)-V\left(\widebar{z}^{k-1}\right)\right\rVert\leq\left\lVert
V\left(\widebar{z}^{k}\right)-V\left(\widebar{z}^{k-1}\right)\right\rVert.$
(56)

Now we can formally state our explicit numerical algorithm.

######  Algorithm 2.

(Explicit Fast OGDA) Let $\alpha>2,z^{0},z^{1},\widebar{z}^{0}\in\mathcal{H}$,
and $0<s<\frac{1}{2L}$. For every $k\geq 1$ we set
$\displaystyle\widebar{z}^{k}$
$\displaystyle:=z^{k}+\left(1-\dfrac{\alpha}{k+\alpha}\right)\left(z^{k}-z^{k-1}\right)-\dfrac{\alpha
s}{2\left(k+\alpha\right)}V\left(\widebar{z}^{k-1}\right)$ $\displaystyle
z^{k+1}$
$\displaystyle:=\widebar{z}^{k}-\dfrac{s}{2}\left(1+\dfrac{k}{k+\alpha}\right)\left(V\left(\widebar{z}^{k}\right)-V\left(\widebar{z}^{k-1}\right)\right).$

For $z_{*}\in{\cal Z}$, $0\leq\lambda\leq\alpha-1$ and $z_{*}\in{\cal Z}$
$0<\gamma<2$ we define first in analogy to the implicit case the discrete
energy function for every $k\geq 1$ by

$\displaystyle\mathcal{E}_{\lambda}^{k}:=$ $\displaystyle\
\dfrac{1}{2}\left\lVert
u^{k}_{\lambda}\right\rVert^{2}+2\lambda\left(\alpha-1-\lambda\right)\left\lVert
z^{k}-z_{*}\right\rVert^{2}+2\left(2-\gamma\right)\lambda sk\left\langle
z^{k}-z_{*},V\left(\widebar{z}^{k-1}\right)\right\rangle$
$\displaystyle+\dfrac{1}{2}\left(2-\gamma\right)s^{2}k\left(\gamma
k+\alpha\right)\left\lVert V\left(\widebar{z}^{k-1}\right)\right\rVert^{2},$
(57)

where

$u^{k}_{\lambda}:=2\lambda\left(z^{k}-z_{*}\right)+2k\left(z^{k}-z^{k-1}\right)+\gamma
skV\left(\widebar{z}^{k-1}\right).$ (58)

In strong contrast to the implicit case, the discrete energy sequence
$(\mathcal{E}_{\lambda}^{k})_{k\geq 1}$ might not dissipate with every
iteration of the algorithm and be even negative. This is the reason why we
consider instead the following regularized seuquence of the energy function,
defined for every $k\geq 2$ as

$\displaystyle\mathcal{F}_{\lambda}^{k}:=$ $\displaystyle\
\mathcal{E}_{\lambda}^{k}-2\left(2-\gamma\right)sk^{2}\left\langle
z^{k}-z^{k-1},V\left(z^{k}\right)-V\left(\widebar{z}^{k-1}\right)\right\rangle$
$\displaystyle+\dfrac{1}{2}\left(2-\gamma\right)s^{2}k\sqrt{k}\left(2sL\sqrt{k}+\alpha\right)\left\lVert
V\left(\widebar{z}^{k-1}\right)-V\left(\widebar{z}^{k-2}\right)\right\rVert^{2}$
$\displaystyle-\dfrac{1}{2}\lambda\left(\alpha-2\right)s^{2}\left(2-\frac{\alpha}{k+\alpha}\right)\left\lVert
V\left(\widebar{z}^{k-1}\right)\right\rVert^{2}.$ (59)

Its properties are collected in the following lemma, the proof of which is
deferred to the Appendix.

######  Lemma 4.1.

Let $z_{*}\in{\cal Z}$ and $\left(z^{k}\right)_{k\geq 0}$ be the sequence
generated by Algorithm 2 for $0<\gamma<2$ and $0\leq\lambda\leq\alpha-1$. Then
the following statements are true:

  1. $\rm{(i)}$

for every $k\geq
k_{0}:=\max\left\\{2,\left\lceil\frac{1}{\alpha-2}\right\rceil\right\\}$ it
holds

$\displaystyle\mathcal{F}_{\lambda}^{k+1}-\mathcal{F}_{\lambda}^{k}\leq$
$\displaystyle\
2\lambda\left(2-\alpha\right)s\left\langle\widebar{z}^{k}-z_{*},V\left(\widebar{z}^{k}\right)\right\rangle-\dfrac{1}{2}s^{2}\mu_{k}\left\lVert
V\left(\widebar{z}^{k}\right)-V\left(\widebar{z}^{k-1}\right)\right\rVert^{2}$
$\displaystyle+2\Bigl{(}\omega_{2}k+\omega_{3}\sqrt{k}\Bigr{)}\left\lVert
z^{k+1}-z^{k}\right\rVert^{2}+2s\Bigl{(}\omega_{0}k+\omega_{1}\Bigr{)}\left\langle
z^{k+1}-z^{k},V\left(\widebar{z}^{k}\right)\right\rangle$
$\displaystyle+\dfrac{1}{2}s^{2}\Bigl{(}\omega_{4}k+\omega_{5}\sqrt{k}\Bigr{)}\left\lVert
V\left(\widebar{z}^{k}\right)\right\rVert^{2},$

where

$\displaystyle\mu_{k}$
$\displaystyle:=\left(2-\gamma\right)\left(2\left(1-2sL\right)\left(k+1\right)+\alpha^{2}\sqrt{k+1}+\alpha-4\right)\left(k+1\right)-\left(2-\gamma\right)\left(\alpha-2\right)-2\lambda\left(\alpha-2\right),$
(60a) $\displaystyle\omega_{0}$
$\displaystyle:=\left(2-\gamma\right)\lambda+\gamma-\alpha+\gamma\left(\lambda+1-\alpha\right),$
(60b) $\displaystyle\omega_{1}$
$\displaystyle:=\gamma-\alpha+\alpha\left(\lambda+1-\alpha\right)<0,$ (60c)
$\displaystyle\omega_{2}$ $\displaystyle:=2\left(\lambda+1-\alpha\right)\leq
0,$ (60d) $\displaystyle\omega_{3}$
$\displaystyle:=\left(2-\gamma\right)\sqrt{\alpha-2}>0,$ (60e)
$\displaystyle\omega_{4}$ $\displaystyle:=2\gamma\left(2-\alpha\right)<0,$
(60f) $\displaystyle\omega_{5}$
$\displaystyle:=\left(2-\gamma\right)\alpha>0.$ (60g)

  2. $\rm{(ii)}$

if $1<\gamma<2$, then for every $k\geq
k_{1}:=\left\lceil\frac{2\lambda\left(\alpha-2\right)}{\left(2-\gamma\right)\alpha}\right\rceil$
it holds

$\displaystyle\mathcal{F}_{\lambda}^{k}\geq$ $\displaystyle\
\dfrac{2-\gamma}{\gamma}\left\lVert
2\lambda\left(z^{k}-z_{*}\right)+k\left(z^{k}-z^{k-1}\right)+\gamma
skV\left(\widebar{z}^{k-1}\right)\right\rVert^{2}$
$\displaystyle+\dfrac{\left(2-\gamma\right)^{2}}{2\gamma}k^{2}\left\lVert
z^{k}-z^{k-1}\right\rVert^{2}+2\lambda\left(\alpha-1-\dfrac{2\lambda}{\gamma}\right)\left\lVert
z^{k}-z_{*}\right\rVert^{2}.$ (61)

In Lemma 4.1 we have two degree of freedoms in the choice of the parameters
$\gamma$ and $\lambda$. The next result proves that there are choices for
these parameters for which the discrete energy starts to dissipate with every
iteration after a finite number of iterations and in the same time it is
bounded from below by a nonnegative term. These two statements are fundamental
in the derivation of the convergence rates and finally in the proof of the
convergence of the iterates. The proof of Lemma 4.2 can be found in the
Appendix.

######  Lemma 4.2.

The following statements are true:

  1. $\rm{(i)}$

if $\gamma$ and $\delta$ are such that

$1+\dfrac{1}{\alpha-1}<\gamma<2,$ (62)

and

$\max\left\\{\sqrt{2\left(1-\dfrac{1}{\gamma}\right)},\sqrt{\dfrac{\left(2-\gamma\right)\left(\alpha-1\right)+\left(\gamma-1\right)\left(\alpha-2\right)}{\gamma\left(\alpha-2\right)}}\right\\}<\delta<1,$
(63)

then there exist two parameters

$0\leq\underline{\lambda}\left(\alpha,\gamma\right)<\overline{\lambda}\left(\alpha,\gamma\right)\leq\dfrac{\gamma}{2}\left(\alpha-1\right),$
(64)

such that for every $\lambda$ satisfying
$\underline{\lambda}\left(\alpha,\gamma\right)<\lambda<\overline{\lambda}\left(\alpha,\gamma\right)$
one can find an integer $k_{2}\left(\lambda\right)\geq 1$ with the property
that the following inequality holds for every $k\geq
k_{2}\left(\lambda\right)$

$\displaystyle
R_{k}:=2\delta\Bigl{(}\omega_{2}k+\omega_{3}\sqrt{k}\Bigr{)}\left\lVert
z^{k+1}-z^{k}\right\rVert^{2}+2s\Bigl{(}\omega_{0}k+\omega_{1}\Bigr{)}\left\langle
z^{k+1}-z^{k},V\left(\widebar{z}^{k}\right)\right\rangle$
$\displaystyle\quad+\dfrac{\delta}{2}s^{2}\Bigl{(}\omega_{4}k+\omega_{5}\sqrt{k}\Bigr{)}\left\lVert
V\left(\widebar{z}^{k}\right)\right\rVert^{2}$ $\displaystyle\leq 0;$ (65)

  2. $\rm{(ii)}$

there exists a positive integer $k_{3}$ such that for every $k\geq k_{3}$ it
holds

$\mu_{k}\geq\left(2-\gamma\right)\left(1-2sL\right)\left(k+1\right)^{2}.$ (66)

Now we are in position to provide first convergence rates statements for
Algorithm 2.

######  Theorem 4.3.

Let $z_{*}\in{\cal Z}$ and $\left(z^{k}\right)_{k\geq 0}$ be the sequence
generated by Algorithm 2. Then the following statements are true:

  1. $\rm{(i)}$

it holds

$\displaystyle\displaystyle\sum\limits_{k\geq
1}\left\langle\widebar{z}^{k}-z_{*},V\left(\widebar{z}^{k}\right)\right\rangle$
$\displaystyle<+\infty,$ (67a) $\displaystyle\displaystyle\sum\limits_{k\geq
1}k^{2}\left\lVert
V\left(\widebar{z}^{k}\right)-V\left(\widebar{z}^{k-1}\right)\right\rVert^{2}$
$\displaystyle<+\infty,$ (67b) $\displaystyle\displaystyle\sum\limits_{k\geq
1}k\left\lVert z^{k+1}-z^{k}\right\rVert^{2}$ $\displaystyle<+\infty,$ (67c)
$\displaystyle\displaystyle\sum\limits_{k\geq 1}k\left\lVert
V\left(\widebar{z}^{k}\right)\right\rVert^{2}$ $\displaystyle<+\infty;$ (67d)

  2. $\rm{(ii)}$

the sequence $\left(z^{k}\right)_{k\geq 0}$ is bounded and it holds

$\displaystyle\left\lVert
z^{k}-z^{k-1}\right\rVert=\mathcal{O}\left(\dfrac{1}{k}\right),\quad\left\langle
z^{k}-z_{*},V\left(z^{k}\right)\right\rangle=\mathcal{O}\left(\dfrac{1}{k}\right),$
$\displaystyle\left\lVert
V\left(z^{k}\right)\right\rVert=\mathcal{O}\left(\dfrac{1}{k}\right),\quad\left\lVert
V\left(\widebar{z}^{k}\right)\right\rVert=\mathcal{O}\left(\dfrac{1}{k}\right)\textrm{
as }k\to+\infty;$

  3. $\rm{(iii)}$

if $1+\dfrac{1}{\alpha-1}<\gamma<2$, then there exist
$0\leq\underline{\lambda}\left(\alpha,\gamma\right)<\overline{\lambda}\left(\alpha,\gamma\right)\leq\frac{\gamma}{2}\left(\alpha-1\right)$
such that for every
$\underline{\lambda}\left(\alpha,\gamma\right)<\lambda<\overline{\lambda}\left(\alpha,\gamma\right)$
both sequences $\left(\mathcal{E}_{\lambda}^{k}\right)_{k\geq 1}$ and
$\left(\mathcal{F}_{\lambda}^{k}\right)_{k\geq 2}$ converge.

###### Proof.

Let $1+\dfrac{1}{\alpha-1}<\gamma<2$ and $0<\delta<1$ such that (63) holds.
According to Lemma 4.2 there exist
$\underline{\lambda}\left(\alpha,\gamma\right)<\overline{\lambda}\left(\alpha,\gamma\right)$
such that (64) holds. We choose
$\underline{\lambda}\left(\alpha,\gamma\right)<\lambda<\overline{\lambda}\left(\alpha,\gamma\right)$
and get, according to the same result, an integer $k_{2}(\lambda)\geq 1$ such
that for every $k\geq k_{2}(\lambda)$ the inequality (65) holds. In addition,
according to Lemma 4.2(ii), we get a positive integer $k_{3}$ such that (66)
holds for every $k\geq k_{3}$.

This means that for every $k\geq
k_{4}\left(\lambda\right):=\max\left\\{k_{0},k_{2}\left(\lambda\right),k_{3}\right\\}$,
where $k_{0}$ is the positive integer provided by Lemma (4.1)(i), we have

$\displaystyle\mathcal{F}_{\lambda}^{k+1}-\mathcal{F}_{\lambda}^{k}\leq$
$\displaystyle\
2\lambda\left(2-\alpha\right)s\left\langle\widebar{z}^{k}-z_{*},V\left(\widebar{z}^{k}\right)\right\rangle-\dfrac{1}{2}\left(2-\gamma\right)\left(1-2sL\right)s^{2}\left(k+1\right)^{2}\left\lVert
V\left(\widebar{z}^{k}\right)-V\left(\widebar{z}^{k-1}\right)\right\rVert^{2}$
$\displaystyle+2\left(1-\delta\right)\Bigl{(}\omega_{2}k+\omega_{3}\sqrt{k}\Bigr{)}\left\lVert
z^{k+1}-z^{k}\right\rVert^{2}+\dfrac{1}{2}\left(1-\delta\right)s^{2}\Bigl{(}\omega_{4}k+\omega_{5}\sqrt{k}\Bigr{)}\left\lVert
V\left(\widebar{z}^{k}\right)\right\rVert^{2}.$

Since $\omega_{2}<0,\omega_{4}<0$ and $\omega_{3},\omega_{5}\geq 0$, we can
choose
$k_{5}:=\left\lceil\max\left\\{-\frac{2\omega_{3}}{\omega_{2}},-\frac{2\omega_{5}}{\omega_{4}}\right\\}\right\rceil>0$,
which then means that for every $k\geq
k_{6}:=\max\left\\{k_{4}\left(\lambda\right),k_{5}\right\\}$

$\displaystyle\mathcal{F}_{\lambda}^{k+1}-\mathcal{F}_{\lambda}^{k}$
$\displaystyle\leq
2\lambda\left(2-\alpha\right)s\left\langle\widebar{z}^{k}-z_{*},V\left(\widebar{z}^{k}\right)\right\rangle-\dfrac{1}{2}\left(2-\gamma\right)s^{2}\left(1-2sL\right)\left(k+1\right)^{2}\left\lVert
V\left(\widebar{z}^{k}\right)-V\left(\widebar{z}^{k-1}\right)\right\rVert^{2}$
$\displaystyle\quad+\left(1-\delta\right)\omega_{2}k\left\lVert
z^{k+1}-z^{k}\right\rVert^{2}+\dfrac{1}{4}\left(1-\delta\right)s^{2}\omega_{4}k\left\lVert
V\left(\widebar{z}^{k}\right)\right\rVert^{2}.$ (68)

In view of (61) and by taking into account that
$\lambda<\frac{\gamma}{2}\left(\alpha-1\right)$, we get that
$\mathcal{F}_{\lambda}^{k}\geq 0$ starting from the index $k_{1}$, thus the
sequence $\left(\mathcal{F}_{\lambda}^{k}\right)_{k\geq 2}$ is bounded from
below. Under these premises, we can apply Lemma A.6 to (68), and obtain
$\rm{(i)}$ as well as that the sequence
$\left(\mathcal{F}_{\lambda}^{k}\right)_{k\geq 1}$ converges.

According to (68), we also have that
$\left(\mathcal{F}_{\lambda}^{k}\right)_{k\geq k_{6}}$ is nonincreasing,
which, according to (61), implies that following estimate holds for every
$k\geq k_{6}$

$\displaystyle\dfrac{2-\gamma}{\gamma}\left\lVert
2\lambda\left(z^{k}-z_{*}\right)+k\left(z^{k}-z^{k-1}\right)+\gamma
skV\left(\widebar{z}^{k-1}\right)\right\rVert^{2}$
$\displaystyle+\dfrac{\left(2-\gamma\right)^{2}}{2\gamma}k^{2}\left\lVert
z^{k}-z^{k-1}\right\rVert^{2}+2\lambda\left(\alpha-1-\dfrac{2\lambda}{\gamma}\right)\left\lVert
z^{k}-z_{*}\right\rVert^{2}$
$\displaystyle\leq\mathcal{F}_{\lambda}^{k}\leq\mathcal{F}_{\lambda}^{k_{6}}<+\infty.$

This yields that the sequences
$\left(2\lambda\left(z^{k}-z_{*}\right)+k\left(z^{k}-z^{k-1}\right)+\gamma
skV\left(\widebar{z}^{k-1}\right)\right)_{k\geq 1}$,
$\left(k\left(z^{k}-z^{k-1}\right)\right)_{k\geq 1}$, and
$\left(z^{k}\right)_{k\geq 0}$ are bounded. In particular, for every $k\geq
k_{6}$ we have

$\displaystyle\left\lVert
2\lambda\left(z^{k}-z_{*}\right)+k\left(z^{k}-z^{k-1}\right)+\gamma
skV\left(\widebar{z}^{k-1}\right)\right\rVert$ $\displaystyle\leq
C_{0}:=\sqrt{\dfrac{\gamma\mathcal{F}_{\lambda}^{k_{6}}}{2-\gamma}}<+\infty,$
$\displaystyle k\left\lVert z^{k}-z^{k-1}\right\rVert$ $\displaystyle\leq
C_{1}:=\dfrac{\sqrt{2\gamma\mathcal{F}_{\lambda}^{k_{6}}}}{2-\gamma}<+\infty,$
$\displaystyle\left\lVert z^{k}-z_{*}\right\rVert$ $\displaystyle\leq
C_{2}:=\sqrt{\dfrac{\gamma\mathcal{F}_{\lambda}^{k_{6}}}{2\lambda\left(\gamma\left(\alpha-1\right)-2\lambda\right)}}<+\infty.$

Using the triangle inequality, we deduce from here that for every $k\geq
k_{6}$

$\displaystyle\left\lVert V\left(\widebar{z}^{k-1}\right)\right\rVert$
$\displaystyle\leq\dfrac{1}{\gamma sk}\left(\left\lVert
2\lambda\left(z^{k}-z_{*}\right)+k\left(z^{k}-z^{k-1}\right)+\gamma
skV\left(\widebar{z}^{k-1}\right)\right\rVert+2\lambda\left\lVert
z^{k}-z_{*}\right\rVert\right)$ $\displaystyle\quad+\dfrac{1}{\gamma
s}\left\lVert z^{k}-z^{k-1}\right\rVert\leq\dfrac{C_{3}}{k},$ (69)

where

$C_{3}:=\dfrac{1}{\gamma
s}\left(C_{0}+C_{1}+2\lambda\left(\alpha,\gamma\right)C_{2}\right)>0.$

The statement (67b) yields

$\lim\limits_{k\to+\infty}k\left\lVert
V\left(\widebar{z}^{k}\right)-V\left(\widebar{z}^{k-1}\right)\right\rVert=0\quad\Rightarrow\quad
C_{4}:=\sup_{k\geq 1}\left\\{k\left\lVert
V\left(\widebar{z}^{k}\right)-V\left(\widebar{z}^{k-1}\right)\right\rVert\right\\}<+\infty,$
(70)

which, together with (56) implies that for every $k\geq k_{6}$

$\displaystyle\left\lVert V\left(z^{k+1}\right)\right\rVert\leq\left\lVert
V\left(z^{k+1}\right)-V\left(\widebar{z}^{k}\right)\right\rVert+\left\lVert
V\left(\widebar{z}^{k}\right)\right\rVert$ $\displaystyle\leq\left\lVert
V\left(\widebar{z}^{k}\right)-V\left(\widebar{z}^{k-1}\right)\right\rVert+\left\lVert
V\left(\widebar{z}^{k}\right)\right\rVert\leq\dfrac{C_{5}}{k},$ (71)

where

$C_{5}:=C_{3}+C_{4}>0.$

The last assertion in $\rm{(ii)}$ follows from the Cauchy-Schwarz inequality
and the boundedness of $\left(z^{k}\right)_{k\geq 0}$, namely, for for every
$k\geq k_{6}$ it holds

$0\leq\left\langle z^{k}-z_{*},V\left(z^{k}\right)\right\rangle\leq\left\lVert
z^{k}-z_{*}\right\rVert\left\lVert
V\left(z^{k}\right)\right\rVert\leq\dfrac{C_{2}C_{5}}{k-1}.$

To complete the proof of $\rm{(iii)}$, we are going to show that in fact

$\lim\limits_{k\to+\infty}\mathcal{E}_{\lambda}^{k}=\lim\limits_{k\to+\infty}\mathcal{F}_{\lambda}^{k}\in\mathbb{R}.$

Indeed, we already have seen that

$\lim\limits_{k\to+\infty}\left(k+1\right)\left\lVert
V\left(\widebar{z}^{k}\right)-V\left(\widebar{z}^{k-1}\right)\right\rVert=\lim\limits_{k\to+\infty}\left\lVert
V\left(\widebar{z}^{k}\right)\right\rVert=0,$

which, by the Cauchy-Schwarz inequality and (56) yields

$\displaystyle 0\leq\lim\limits_{k\to+\infty}k^{2}\left\lvert\left\langle
z^{k}-z^{k-1},V\left(z^{k}\right)-V\left(\widebar{z}^{k-1}\right)\right\rangle\right\rvert$
$\displaystyle\leq C_{1}\lim\limits_{k\to+\infty}k\left\lVert
V\left(z^{k}\right)-V\left(\widebar{z}^{k-1}\right)\right\rVert$
$\displaystyle\leq C_{1}\lim\limits_{k\to+\infty}k\left\lVert
V\left(\widebar{z}^{k-1}\right)-V\left(\widebar{z}^{k-2}\right)\right\rVert=0.$

From here we obtain the desired statement. ∎

The following theorem addresses the convergence of the sequence of iterates to
an element in ${\cal Z}$.

######  Theorem 4.4.

Let $z_{*}\in{\cal Z}$ and $\left(z^{k}\right)_{k\geq 0}$ be the sequence
generated by Algorithm 2. Then the sequence $\left(z^{k}\right)_{k\geq 0}$
converges weakly to a solution of (1).

###### Proof.

Let $1+\dfrac{1}{\alpha-1}<\gamma<2$ and
$\underline{\lambda}\left(\alpha,\gamma\right)<\overline{\lambda}\left(\alpha,\gamma\right)$
be the parameters provided by Lemma 4.2 such that (64) holds and with the
property that for every
$\underline{\lambda}\left(\alpha,\gamma\right)<\lambda<\overline{\lambda}\left(\alpha,\gamma\right)$
there exists an integer $k_{2}(\lambda)\geq 1$ such that for every $k\geq
k_{2}(\lambda)$ the inequality (65) holds. The proof relies on Opial’s Lemma
and follows the line of the proof of Theorem 3.3, by defining this time for
every $k\geq 1$

$\displaystyle p_{k}$
$\displaystyle:=\dfrac{1}{2}\left(\alpha-1\right)\left\lVert
z^{k}-z_{*}\right\rVert^{2}+k\left\langle
z^{k}-z_{*},z^{k}-z^{k-1}+sV\left(\widebar{z}^{k-1}\right)\right\rangle,$ (72)
$\displaystyle q_{k}$ $\displaystyle:=\dfrac{1}{2}\left\lVert
z^{k}-z_{*}\right\rVert^{2}+s\displaystyle\sum\limits_{i=1}^{k}\left\langle
z^{i}-z_{*},V\left(\widebar{z}^{i-1}\right)\right\rangle.$ (73)

One can notice that the limit

$\lim_{k\to+\infty}\sum_{i=1}^{k}\left\langle
z^{i}-z_{*},V\left(\widebar{z}^{i-1}\right)\right\rangle=\lim_{k\to+\infty}\sum_{i=1}^{k}\left\langle
z^{i}-\widebar{z}^{i-1},V\left(\widebar{z}^{i-1}\right)\right\rangle+\lim_{k\to+\infty}\sum_{i=1}^{k}\left\langle\widebar{z}^{i-1}-z_{*},V\left(\widebar{z}^{i-1}\right)\right\rangle\in\mathbb{R}$

exists due to (67a) and the fact that the series $\sum_{k\geq 2}\left\langle
z^{k}-\widebar{z}^{k-1},V\left(\widebar{z}^{k-1}\right)\right\rangle$ is
absolutely convergent, which follows from

$\displaystyle\displaystyle\sum\limits_{i=2}^{k}\left\lvert\left\langle
z^{i}-\widebar{z}^{i-1},V\left(\widebar{z}^{i-1}\right)\right\rangle\right\rvert\leq\displaystyle\sum\limits_{i=2}^{k}\left\lVert
V\left(\widebar{z}^{i-1}\right)\right\rVert\left\lVert
z^{i}-\widebar{z}^{i-1}\right\rVert\leq
sC_{3}C_{4}\displaystyle\sum\limits_{i=2}^{\infty}\dfrac{1}{i\left(i-1\right)}<+\infty\quad\forall
k\geq 2,$

where we make use of (56), (70), and (4), and of the constants $C_{3},C_{4}$
defined in the proof of Theorem 4.3. ∎

As for the implicit algorithm, we can improve also for the explicit algorithm
the convergence rates.

######  Theorem 4.5.

Let $z_{*}\in{\cal Z}$ and $\left(z^{k}\right)_{k\geq 0}$ be the sequence
generated by Algorithm 2. Then it holds

$\displaystyle\left\lVert
z^{k}-z^{k-1}\right\rVert=o\left(\dfrac{1}{k}\right),\quad\left\langle
z^{k}-z_{*},V\left(z^{k}\right)\right\rangle=o\left(\dfrac{1}{k}\right),$
$\displaystyle\left\lVert
V\left(z^{k}\right)\right\rVert=o\left(\dfrac{1}{k}\right),\quad\left\lVert
V\left(\widebar{z}^{k}\right)\right\rVert=o\left(\dfrac{1}{k}\right)\textrm{
as }k\to+\infty.$

###### Proof.

Let $1+\dfrac{1}{\alpha-1}<\gamma<2$ and
$\underline{\lambda}\left(\alpha,\gamma\right)<\overline{\lambda}\left(\alpha,\gamma\right)$
be the parameters provided by Lemma 4.2 such that (64) holds and with the
property that for every
$\underline{\lambda}\left(\alpha,\gamma\right)<\lambda<\overline{\lambda}\left(\alpha,\gamma\right)$
there exists an integer $k_{2}(\lambda)\geq 1$ such that for every $k\geq
k_{2}(\lambda)$ the inequality (65) holds.

We fix
$\underline{\lambda}\left(\alpha,\gamma\right)<\lambda<\overline{\lambda}\left(\alpha,\gamma\right)$
and recall that according to Theorem 4.3(iii) the sequence
$(\mathcal{E}_{\lambda}^{k})_{k\geq 1}$ converges.

From (58) and (57) we have that for every $k\geq 1$

$\displaystyle\mathcal{E}_{\lambda}^{k}=$ $\displaystyle\
\dfrac{1}{2}\left\lVert
2\lambda\left(z^{k}-z_{*}\right)+2k\left(z^{k}-z^{k-1}\right)+\gamma
skV\left(\widebar{z}^{k-1}\right)\right\rVert^{2}+2\lambda\left(\alpha-1-\lambda\right)\left\lVert
z^{k}-z_{*}\right\rVert^{2}$ $\displaystyle+2\left(2-\gamma\right)\lambda
sk\left\langle
z^{k}-z_{*},V\left(\widebar{z}^{k-1}\right)\right\rangle+\dfrac{1}{2}\left(2-\gamma\right)s^{2}k\left(\gamma
k+\alpha\right)\left\lVert V\left(\widebar{z}^{k-1}\right)\right\rVert^{2}$
$\displaystyle=$ $\displaystyle\ 2\lambda\left(\alpha-1\right)\left\lVert
z^{k}-z_{*}\right\rVert^{2}+4\lambda k\left\langle
z^{k}-z_{*},z^{k}-z^{k-1}+sV\left(\widebar{z}^{k-1}\right)\right\rangle+\dfrac{1}{2}\left(2-\gamma\right)\alpha
s^{2}k\left\lVert V\left(\widebar{z}^{k-1}\right)\right\rVert^{2}$
$\displaystyle+\dfrac{k^{2}}{2}\left(\left\lVert
2\left(z^{k}-z^{k-1}\right)+\gamma
sV\left(\widebar{z}^{k-1}\right)\right\rVert^{2}+\left(2-\gamma\right)\gamma
s^{2}\left\lVert V\left(\widebar{z}^{k-1}\right)\right\rVert^{2}\right).$

We set for every $k\geq 1$

$h_{k}:=\dfrac{k^{2}}{2}\left(\left\lVert 2\left(z^{k}-z^{k-1}\right)+\gamma
sV\left(\widebar{z}^{k-1}\right)\right\rVert^{2}+\left(2-\gamma\right)\gamma
s^{2}\left\lVert V\left(\widebar{z}^{k-1}\right)\right\rVert^{2}\right),$

and notice that, in view of (72), we have

$\mathcal{E}_{\lambda}^{k}=4\lambda
p_{k}+\dfrac{1}{2}\left(2-\gamma\right)\alpha s^{2}k\left\lVert
V\left(\widebar{z}^{k-1}\right)\right\rVert^{2}+h_{k}.$

Theorem 4.3 asserts that

$\lim\limits_{k\to\infty}k\left\lVert
V\left(\widebar{z}^{k-1}\right)\right\rVert^{2}=0,$

which, together with
$\lim_{k\to+\infty}\mathcal{E}_{\lambda}^{k}\in\mathbb{R}$ and
$\lim_{k\to+\infty}p_{k}\in\mathbb{R}$, yields

$\lim\limits_{k\to+\infty}h_{k}\in\mathbb{R}\textrm{ exists}.$

In addition, (67c) and (67d) in Theorem 4.3 guarantee that

$\displaystyle\displaystyle\sum\limits_{k\geq 1}\dfrac{1}{k}h_{k}\leq
4\displaystyle\sum\limits_{k\geq 1}k\left\lVert
z^{k}-z^{k-1}\right\rVert^{2}+\dfrac{1}{2}\left(2+\gamma\right)\gamma
s^{2}\displaystyle\sum\limits_{k\geq 1}k\left\lVert
V\left(\widebar{z}^{k-1}\right)\right\rVert^{2}<+\infty.$

Consequently, $\lim_{k\to+\infty}h_{k}=0$, which yields

$\lim\limits_{k\to\infty}k\left\lVert 2\left(z^{k}-z^{k-1}\right)+\gamma
sV\left(\widebar{z}^{k-1}\right)\right\rVert=\lim\limits_{k\to\infty}k\left\lVert
V\left(\widebar{z}^{k-1}\right)\right\rVert=0.$

This immediately implies $\lim_{k\to+\infty}k\left\lVert
z^{k}-z^{k-1}\right\rVert=0$. The fact that $\lim_{k\to+\infty}k\left\lVert
V\left(z^{k}\right)\right\rVert=0$ follows from (70) and (71), since

$0\leq\lim\limits_{k\to+\infty}k\left\lVert
V\left(z^{k}\right)\right\rVert\leq\lim\limits_{k\to+\infty}k\left\lVert
V\left(\widebar{z}^{k}\right)-V\left(\widebar{z}^{k-1}\right)\right\rVert+\lim\limits_{k\to+\infty}k\left\lVert
V\left(\widebar{z}^{k}\right)\right\rVert=0.$

Finally, using the Cauchy-Schwarz inequality and the fact that
$\left(z^{k}\right)_{k\geq 0}$ is bounded, we obtain that
$\lim_{k\to+\infty}k\left\langle
z^{k}-z_{*},V\left(z^{k}\right)\right\rangle=0$. ∎

##  5 Numerical experiments

In this section we perform numerical experiments to illustrate the convergence
rates derived for the explicit Fast OGDA method and to compare our algorithm
with other numerical schemes from the literature designed to solve equations
governed by a monotone and Lipschitz continuous operator. To this end we
consider a minmax problem studied in [39], which has then been used in [49] to
illustrate the performances of anchoring based numerical methods. This reads

$\min\limits_{x\in\mathbb{R}^{n}}\max\limits_{y\in\mathbb{R}^{n}}\mathcal{L}\left(x,y\right):=\dfrac{1}{2}\left\langle
x,Hx\right\rangle-\left\langle x,h\right\rangle-\left\langle
y,Ax-b\right\rangle,$ (74)

where

$\displaystyle A:=\dfrac{1}{4}\begin{pmatrix}&&&-1&1\\\ &&\iddots&\iddots\\\
&-1&1\\\ -1&1\\\ 1\end{pmatrix}\in\mathbb{R}^{n\times n},\quad
H:=2A^{T}A,\quad b:=\dfrac{1}{4}\begin{pmatrix}1\\\ 1\\\ \vdots\\\ 1\\\
1\end{pmatrix}\in\mathbb{R}^{n}\ \mbox{and}\
h:=\dfrac{1}{4}\begin{pmatrix}0\\\ 0\\\ \vdots\\\ 0\\\
1\end{pmatrix}\in\mathbb{R}^{n}.$

We notice that $\mathcal{L}$ is nothing else than the Lagrangian of a linearly
constrained quadratic minimization problem. It has been shown in [39] that
$\left\lVert A\right\rVert\leq\frac{1}{2}$, thus $\left\lVert
H\right\rVert\leq\frac{1}{2}$, and, consequently, for the monotone mapping
$\left(x,y\right)\mapsto\Bigl{(}\nabla_{x}\mathcal{L}\left(x,y\right),-\nabla_{y}\mathcal{L}\left(x,y\right)\Bigr{)}$
we can take $L=1$ as Lipschitz constant.

In the following we summarize all the algorithms we use in the numerical
experiments and the corresponding step sizes:

  1. $\rm{(i)}$

OGDA: Optimistic Gradient Descent Ascent method (7) (see [42]) with
$s:=\frac{0.48}{L}$ ;

  2. $\rm{(ii)}$

EG: Extragradient method (6) (see [30, 2]) with $s:=\frac{0.96}{L}$;

  3. $\rm{(iii)}$

EAG-V: Extra Anchored Gradient method (10) (see [49]) with variable step sizes
$\left(s_{k}\right)_{k\geq 0}$ satisfying (11);

  4. $\rm{(iv)}$

Nesterov-EAG: Nesterov’s accelerated variant of the Extra Anchored Gradient
method, which has been proposed in [47] and can be obtained from (10) be
taking in the first update line the sequence
$\left(\frac{k+1}{L\left(k+2\right)}\right)_{k\geq 0}$ as step sizes, and in
the second one the constant step size $\frac{1}{L}$ (see [47, Theorem 5.1,
Lemma 5.1, Theorem 5.2]);

  5. $\rm{(v)}$

Halpern-OGDA: OGDA mixed with the Halpern anchoring scheme, which has been
proposed in [48] and can be obtained from the variant of (10) with variable
step sizes by replacing in the first update line $V\left(z^{k}\right)$ by
$V\left(\widebar{z}^{k-1}\right)$;

  6. $\rm{(vi)}$

Fast OGDA: our explicit algorithm with $s:=\frac{0.48}{L}$ and various choices
of $\alpha$.

Figure 1: Explicit Fast OGDA outperforms all other explicit methods

For the first numerical experiments we consider the same setting as in [49],
namely, we take $n=200$, which means that the underlying space is
${\mathbb{R}}^{400}$, and allow a maximum number of iterations of $5\times
10^{5}$. Figure 1 presents the convergence behaviour of the different methods
when solving (74) in logarithmic scale. One can see that the anchoring based
methods perform better than the classical algorithms EG and OGDA, and that
Nesterov-EAG performs better than Halpern-OGDA, which reconfirms a finding of
[47] and is not surprising when one takes into account that the first allows
for larger step sizes than EAG-V (and Halpnern-OGDA). On the other hand, Fast
OGDA outperforms all the other methods in spite of the fact that the step size
is restricted to $\left(0,\frac{1}{2L}\right)$.

Figure 2: The parameter $\alpha$ influences the convergence behaviour of
explicit Fast OGDA

Figure 2 shows that the parameter $\alpha>2$ influences significantly the
convergence behaviour of the explicit Fast OGDA method. For this numerical
experiment we take $n=1000$, which means that the underlying space is
${\mathbb{R}}^{2000}$, and allow a maximum number of iterations of $5\times
10^{5}$. The speed of convergence increases with increasing $\alpha$ and seem
to be much better than $o\left(1/k\right)$. Let us mention that the minimax
problem (74) was constructed to show lower complexity bounds of first order
methods for convex-concave saddle point problems.

For Nesterov’s dynamical systems with $\frac{\alpha}{t}$ as damping
coefficient and the corresponding numerical algorithms approaching the
minimization of a smooth and convex function, it is known that $\alpha$
influences in the same way the convergence rates of the objective function
values. Another intriguing similarity with Nesterov’s continuous and discrete
schemes is the evident oscillatory behaviour of the trajectories, however,
there for the objective function values, while for explicit Fast OGDA for the
norm of the operator along the trajectory/sequence of generated iterates. This
suggests that Nesterov’s acceleration approach can improve the convergence
behaviour of continuous and discrete time approaches beyond the optimization
setting.

In the following we complement the comparative study of the above numerical
methods by following the performance profile developed by Dolan and Moré
([21]). We denote by $\mathsf{S}$ the set of the algorithms/solvers (i)-(vi)
from above, where for the Fast OGDA method we take $\alpha:=3$. We solve
minmax problems of the form (74) with ${\cal
L}:\mathbb{R}^{n}\times\mathbb{R}^{m}\rightarrow\mathbb{R}$, for 10 different
pairs $\left(n,m\right)$ such that $20\leq m\leq n\leq 200$ and, for each such
pair, for $100$ randomly generated sparse matrices $A\in\mathbb{R}^{m\times
n}$ and vectors $b\in\mathbb{R}^{m}$ and $h\in\mathbb{R}^{n}$, and
$H:=2A^{T}A$. For each pair $\left(n,m\right)$ we also take $10$ initial
points with normal distribution, which leads to a set of problems $\mathsf{P}$
with $\mathsf{N_{p}}=10\times 100\times 10=10000$ instances.

For each problem $\mathsf{p}\in\mathsf{P}$ and each solver
$\mathsf{s}\in\mathsf{S}$, we denote by $\mathsf{t_{p,s}}$ the number of
iterations needed by solver $\mathsf{s}$ to solve the problem $\mathsf{p}$
successfully, i.e. by satsifying the following stopping criteria before
$\mathtt{k_{\max}}:=10^{5}$ iterations

$\dfrac{\left\lVert V\left(x_{k},y_{k}\right)\right\rVert}{\left\lVert
V\left(x_{0},y_{0}\right)\right\rVert}\leq\mathtt{Tol_{op}}=10^{-6}\quad\textrm{
and
}\quad\dfrac{\left\lVert\left(x_{k},y_{k}\right)-\left(x_{k-1},y_{k-1}\right)\right\rVert}{\left\lVert\left(x_{k},y_{k}\right)\right\rVert+1}\leq\mathtt{Tol_{vec}}=10^{-5}.$

The two stopping criteria quantify the relative errors measured for the
operator norm and the discrete velocity. We define the _performance ratio_ as

$\mathsf{r_{p,s}}:=\begin{cases}\dfrac{\mathsf{t_{p,s}}}{\min\left\\{\mathsf{t_{p,s}}\colon\mathsf{s}\in\mathsf{S}\right\\}}&\textrm{
if }\mathsf{t_{p,s}}<\mathtt{k_{\max}},\\\ 0&\textrm{ otherwise, }\end{cases}$

and the _performance_ of the solver $\mathsf{s}$ as

$\mathsf{\rho_{s}}\left(\tau\right):=\dfrac{1}{\mathsf{N_{p}}}\mathrm{size}\left\\{\mathsf{p}\in\mathsf{P}\colon
0<\mathsf{r_{p,s}}\leq\tau\right\\},$

where $\tau$ is a real factor. The performance
$\mathsf{\rho_{s}}\left(\tau\right)$ for solver $\mathsf{s}$ gives the
probability that the performance ratio $\mathsf{r_{p,s}}$ is within a factor
$\tau\in\mathbb{R}$ of the best possible ratio. Therefore, the value of
$\mathsf{\rho_{s}}\left(1\right)$ gives the probability that the solver
$\mathsf{s}$ gives the best numerical performance when compared to the others,
while $\mathsf{\rho_{s}}\left(\tau\right)$ for large values of $\tau$ measures
its robustness.

Figure 3 represents the performance profiles of the six solvers. We observe
that the Fast OGDA method is the most efficient, followed by EAG-V and
Halpern-OGDA. We note that for $\tau\geq 3$ these three solvers are robust and
solve $90\%$ of the problems, while Nesterov-EGA and EG solve for $\tau\geq 4$
$80\%$ of the problems.

Figure 3: The performance profiles of the six solvers

##  Appendix A Appendix

In the first subsection of the appendix we collect some fundamental auxiliary
results for the analysis carried out in the paper. Further, we present the
proof of the existence and uniqueness theorem for (12) and also the proofs of
technical lemmas used in the convergence analysis of the numerical algorithms.

###  A.1 Auxiliary results

The following result can be found in [1, Lemma 5.1].

######  Lemma A.1.

Let $\delta>0$. Suppose that $f\colon\left[\delta,+\infty\right)\to\mathbb{R}$
is locally absolutely continuous, bounded from below, and there exists
$g\in\mathbb{L}^{1}\left(\left[\delta,+\infty\right)\right)$ such that for
almost every $t\geq\delta$

$\dfrac{d}{dt}f\left(t\right)\leq g\left(t\right).$

Then the limit $\lim\limits_{t\to+\infty}f\left(t\right)\in\mathbb{R}$ exists.

Opial’s Lemma ([38]) in continuous form is used in the proof of the weak
convergence of the trajectory of the dynamical system (12).

######  Lemma A.2.

Let $\mathcal{S}$ be a nonempty subset of $\mathcal{H}$ and
$z\colon\left[t_{0},+\infty\right)\to\mathcal{H}$. Assume that

  1. $\rm{(i)}$

for every $z_{*}\in\mathcal{S}$, $\lim\limits_{t\to+\infty}\left\lVert
z\left(t\right)-z_{*}\right\rVert$ exists;

  2. $\rm{(ii)}$

every weak sequential cluster point of the trajectory $z\left(t\right)$ as
$t\to+\infty$ belongs to $\mathcal{S}$.

Then $z(t)$ converges weakly to a point in $\mathcal{S}$ as $t\to+\infty$.

For the convergence proof of the iterates generated by the two numerical
algorithms we use the discrete counterpart of Opial’s Lemma.

######  Lemma A.3.

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

  1. $\rm{(i)}$

for every $z_{*}\in\mathcal{S}$, $\lim\limits_{k\to+\infty}\left\lVert
z_{k}-z_{*}\right\rVert$ exists;

  2. $\rm{(ii)}$

every weak sequential cluster point of the sequence $\left(z_{k}\right)_{k\geq
1}$ as $k\to+\infty$ belongs to $\mathcal{S}$.

Then $\left(z_{k}\right)_{k\geq 1}$ converges weakly to a point in
$\mathcal{S}$ as $k\to+\infty$.

The following result can be found in [13, Lemma A.2].

######  Lemma A.4.

Let $a>0$ and $q\colon\left[t_{0},+\infty\right)\rightarrow\mathcal{H}$ be a
continuously differentiable function such that

$\lim\limits_{t\to+\infty}\left(q\left(t\right)+\dfrac{t}{a}\dot{q}\left(t\right)\right)=l\in\mathcal{H}.$

Then it holds $\lim\limits_{t\to+\infty}q\left(t\right)=l$.

The discrete counterpart of this result is stated below. We provide a proof
for it, as we could not find any reference for this result in the literature.

######  Lemma A.5.

Let $a\geq 1$ and $\left(q_{k}\right)_{k\geq 0}$ be a bounded sequence in
$\mathcal{H}$ such that

$\lim\limits_{k\to+\infty}\left(q_{k+1}+\dfrac{k}{a}\left(q_{k+1}-q_{k}\right)\right)=l\in\mathcal{H}.$

Then it holds $\lim\limits_{k\to+\infty}q_{k}=l$.

###### Proof.

For every $k\geq 0$ we set $r_{k}:=q_{k}-l$. We fix $\varepsilon>0$. Then
there exists $k_{0}\geq 1$ such that for every $k\geq k_{0}$

$\left\lVert
r_{k+1}+\dfrac{k}{a}\left(r_{k+1}-r_{k}\right)\right\rVert\leq\varepsilon.$

Multiplying both side by $ak^{a-1}$, we obtain for every $k\geq k_{0}$

$\left\lVert\left(ak^{a-1}+k^{a}\right)r_{k+1}-k^{a}r_{k}\right\rVert\leq\varepsilon
ak^{a-1}.$

Then by applying the triangle inequality and using the fact that
$\overline{r}:=\sup_{k\geq 0}\left\lVert r_{k}\right\rVert<+\infty$, we deduce
that for every $k\geq k_{0}$

$\left\lVert\left(k+1\right)^{a}r_{k+1}-k^{a}r_{k}\right\rVert\leq\varepsilon
ak^{a-1}+\left\lvert\left(k+1\right)^{a}-k^{a}-ak^{a-1}\right\rvert\overline{r}.$
(75)

The Lagrange error bound of a Taylor series says that for every $k\geq k_{0}$
there exists $m_{k}\in\left(k,k+1\right)$ such that

$\left\lvert\left(k+1\right)^{a}-k^{a}-ak^{a-1}\right\rvert\leq\dfrac{1}{2}a\left\lvert
a-1\right\rvert m_{k}^{a-2}.$

From here we consider two cases.

Then for every $k\geq k_{0}$ and every $m\in\left(k,k+1\right)$ we have
$m^{a-2}\leq 1$ and thus (75) leads to

$\left\lVert\left(k+1\right)^{a}r_{k+1}-k^{a}r_{k}\right\rVert\leq\varepsilon
ak^{a-1}+\dfrac{1}{2}a\left\lvert a-1\right\rvert\overline{r}.$

We choose $K\geq k_{0}$ and use a telescoping sum argument to get

$\displaystyle\left\lVert\left(K+1\right)^{a}r_{K+1}-k_{0}^{a}r_{k_{0}}\right\rVert$
$\displaystyle=\left\lVert\displaystyle\sum\limits_{k=k_{0}}^{K}\Bigl{(}\left(k+1\right)^{a}r_{k+1}-k^{a}r_{k}\Bigr{)}\right\rVert\leq\displaystyle\sum\limits_{k=k_{0}}^{K}\left\lVert\left(k+1\right)^{a}r_{k+1}-k^{a}r_{k}\right\rVert$
$\displaystyle\leq\varepsilon
a\displaystyle\sum\limits_{k=k_{0}}^{K}k^{a-1}+\dfrac{1}{2}a\left\lvert
a-1\right\rvert\overline{r}\displaystyle\sum\limits_{k=k_{0}}^{K}1\leq\varepsilon
a\left(K+1\right)^{a}+\dfrac{1}{2}a\left\lvert
a-1\right\rvert\overline{r}\left(K+1\right).$

Once again, using the triangle inequality, we conclude that

$\displaystyle\left\lVert r_{K+1}\right\rVert$
$\displaystyle\leq\dfrac{1}{\left(K+1\right)^{a}}\left\lVert\left(K+1\right)^{a}r_{K+1}-k_{0}^{a}r_{k_{0}}\right\rVert+\dfrac{k_{0}^{a}}{\left(K+1\right)^{a}}\left\lVert
r_{k_{0}}\right\rVert\leq\varepsilon a+\dfrac{a\left\lvert
a-1\right\rvert\overline{r}}{2\left(K+1\right)^{a-1}}+\dfrac{k_{0}^{a}\overline{r}}{\left(K+1\right)^{a}}.$

For for every $k\geq k_{0}$ and every $m\in\left(k,k+1\right)$ we have
$m^{a-2}\leq\left(k+1\right)^{a-2}$, hence (75) leads to

$\left\lVert\left(k+1\right)^{a}r_{k+1}-k^{a}r_{k}\right\rVert\leq\varepsilon
ak^{a-1}+\dfrac{1}{2}a\left(a-1\right)\overline{r}\left(k+1\right)^{a-2}.$

We choose also in this case $K\geq k_{0}$ and by a similar argument as above
we have that

$\displaystyle\left\lVert\left(K+1\right)^{a}r_{K+1}-k_{0}^{a}r_{k_{0}}\right\rVert$
$\displaystyle=\left\lVert\displaystyle\sum\limits_{k=k_{0}}^{K}\Bigl{(}\left(k+1\right)^{a}r_{k+1}-k^{a}r_{k}\Bigr{)}\right\rVert\leq\displaystyle\sum\limits_{k=k_{0}}^{K}\left\lVert\left(k+1\right)^{a}r_{k+1}-k^{a}r_{k}\right\rVert$
$\displaystyle\leq\varepsilon
a\displaystyle\sum\limits_{k=k_{0}}^{K}k^{a-1}+\dfrac{1}{2}a\left(a-1\right)\overline{r}\displaystyle\sum\limits_{k=k_{0}}^{K}\left(k+1\right)^{a-2}$
$\displaystyle\leq\varepsilon
a\left(K+1\right)^{a-1}\displaystyle\sum\limits_{k=0}^{K}1+\dfrac{1}{2}a\left(a-1\right)\overline{r}\left(K+1\right)^{a-2}\displaystyle\sum\limits_{k=0}^{K}1$
$\displaystyle\leq\varepsilon
a\left(K+1\right)^{a}+\dfrac{1}{2}a\left(a-1\right)\overline{r}\left(K+1\right)^{a-1}.$

This leads to

$\displaystyle\left\lVert r_{K+1}\right\rVert\leq\varepsilon
a+\dfrac{a\left(a-1\right)\overline{r}}{2\left(K+1\right)}+\dfrac{k_{0}^{a}\overline{r}}{\left(K+1\right)^{a}}.$

Therefore, in both scenarios we obtain

$\limsup_{k\to+\infty}\left\lVert r_{k}\right\rVert\leq\varepsilon a,$

which leads to the desired conclusion, as $\varepsilon>0$ was arbitrarily
chosen. ∎

The following result is a particular instance of [16, Lemma 5.31].

######  Lemma A.6.

Let $\left(a_{k}\right)_{k\geq 1}$, $\left(b_{k}\right)_{k\geq 1}$ and
$\left(d_{k}\right)_{k\geq 1}$ be sequences of real numbers. Assume that
$\left(a_{k}\right)_{k\geq 1}$ is bounded from below, and
$\left(b_{k}\right)_{k\geq 1}$ and $\left(d_{k}\right)_{k\geq 1}$ are
nonnegative sequences such that $\sum_{k\geq 1}d_{k}<+\infty$. If

$a_{k+1}\leq a_{k}-b_{k}+d_{k}\quad\forall k\geq 1,$

then the following statements are true:

  1. $\rm{(i)}$

the sequence $\left(b_{k}\right)_{k\geq 1}$ is summable, namely $\sum_{k\geq
1}b_{k}<+\infty$;

  2. $\rm{(ii)}$

the sequence $\left(a_{k}\right)_{k\geq 1}$ is convergent.

The following elementary result is used several times in the paper.

######  Lemma A.7.

Let $a,b,c\in\mathbb{R}$ be such that $a\neq 0$ and $b^{2}-ac\leq 0$. The
following statements are true:

  1. $\rm{(i)}$

if $a>0$, then it holds

$a\left\lVert x\right\rVert^{2}+2b\left\langle x,y\right\rangle+c\left\lVert
y\right\rVert^{2}\geq 0\quad\forall x,y\in\mathcal{H};$

  2. $\rm{(ii)}$

if $a<0$, then it holds

$a\left\lVert x\right\rVert^{2}+2b\left\langle x,y\right\rangle+c\left\lVert
y\right\rVert^{2}\leq 0\quad\forall x,y\in\mathcal{H}.$

###  A.2 Proof of the existence and uniqueness theorem for the evolution
equation

In this subsection we provide the proof of the existence and uniqueness of the
trajectories of (12).

######  Proof of Theorem 2.3 .

The system (12) can be rewritten as a first-order ordinary differential
equation

$\begin{dcases}\dot{z}\left(t\right)&=\dfrac{1}{2t}u\left(t\right)-\dfrac{1}{t}\left(\alpha-1\right)z\left(t\right)-\beta\left(t\right)V\left(z\left(t\right)\right)\\\
\dot{u}\left(t\right)&=\Bigl{(}t\dot{\beta}\left(t\right)+\left(2-\alpha\right)\beta\left(t\right)\Bigr{)}V\left(z\left(t\right)\right)\\\
\Bigl{(}z\left(t_{0}\right),u\left(t_{0}\right)\Bigr{)}&=\Bigl{(}z^{0},2\left(\alpha-1\right)z^{0}+2t_{0}\dot{z}^{0}+2t_{0}\beta\left(t_{0}\right)V\left(z^{0}\right)\Bigr{)}\end{dcases},$
(76)

where for every $t\geq t_{0}$ we define

$u\left(t\right):=2\left(\alpha-1\right)z\left(t\right)+2t\dot{z}\left(t\right)+2t\beta\left(t\right)V\left(z\left(t\right)\right).$

We define
$G\colon\left[t_{0},+\infty\right)\times\mathcal{H}\times\mathcal{H}\to\mathcal{H}\times\mathcal{H}$
by

$G\left(t,\zeta,\mu\right):=\biggl{(}\Bigl{(}t\dot{\beta}\left(t\right)+\left(2-\alpha\right)\beta\left(t\right)\Bigr{)}V\left(\zeta\right),\dfrac{1}{2t}\mu-\dfrac{1}{t}\left(\alpha-1\right)\zeta-\beta\left(t\right)V\left(\zeta\right)\biggr{)},$

so that (76) becomes

$\begin{dcases}\Bigl{(}\dot{u}\left(t\right),\dot{z}\left(t\right)\Bigr{)}&=G\left(t,z\left(t\right),u\left(t\right)\right)\\\
\Bigl{(}z\left(t_{0}\right),u\left(t_{0}\right)\Bigr{)}&=\Bigl{(}z^{0},2\left(\alpha-1\right)z^{0}+2t_{0}\dot{z}^{0}+2t_{0}\beta\left(t_{0}\right)V\left(z^{0}\right)\Bigr{)}\end{dcases}.$

Since $G$ is Lipschitz continuous on bounded sets, the local existence and
uniqueness theorem (see, for instance, [44, Theorems 46.2 and 46.3]) allows to
conclude that there exists a unique continuous differentiable solution
$\left(z,u\right)\in\mathcal{H}\times\mathcal{H}$ of (76) defined on a
maximally interval $\left[t_{0},T_{\max}\right)$ where
$0<t_{0}<T_{\max}\leq+\infty$. Furthermore, either

$T_{\max}=+\infty\qquad\textrm{ or }\qquad\lim\limits_{t\to
T_{\max}}\left\lVert\left(z\left(t\right),u\left(t\right)\right)\right\rVert=+\infty.$

In the following we will show that indeed $T_{\max}=+\infty$.

According to (23), for $z_{*}\in\mathcal{Z}$ fixed, for every $t_{0}\leq
t<T_{\max}$ it holds

$\mathcal{E}_{\alpha-1}\left(t\right)+2\int_{t_{0}}^{t}\tau^{2}\beta\left(\tau\right)w\left(\tau\right)\left\lVert
V\left(z\left(\tau\right)\right)\right\rVert^{2}d\tau\leq\mathcal{E}_{\alpha-1}\left(t_{0}\right)<+\infty,$

which implies that

$t\mapsto u(t)\mbox{ is bounded on }[t_{0},T_{\max}).$ (77)

On the other hand, inequality (25) implies that

$\int_{t_{0}}^{T_{\max}}\tau\beta^{2}\left(\tau\right)\left\lVert
V\left(z\left(\tau\right)\right)\right\rVert^{2}d\tau\leq\dfrac{\mathcal{E}_{\alpha-1}\left(t_{0}\right)}{\varepsilon}<+\infty,$

for some $\varepsilon>0$. Now for $0<\lambda<\alpha-1$, we have according to
(27b) that for every $t_{0}\leq t<T_{\max}$

$\displaystyle 2\lambda\left(\alpha-1-\lambda\right)\left\lVert
z\left(t\right)-z_{*}\right\rVert^{2}\leq\mathcal{E}_{\lambda}\left(t\right)$
$\displaystyle\leq\mathcal{E}_{\lambda}\left(t_{0}\right)+\dfrac{2}{\varepsilon}\left(\alpha-1-\lambda\right)\mathcal{E}_{\alpha-1}\left(t_{0}\right)<+\infty.$
(78)

From (77) and (78) we have that $\lim_{t\to
T_{\max}}\left\lVert\left(z\left(t\right),u\left(t\right)\right)\right\rVert<+\infty$,
therefore $T_{\max}=+\infty$. $\blacksquare$

###  A.3 Proof of the technical lemma used in the analysis of the implicit
algorithm

In this subsection we provide the proof of Lemma 3.1 which shows that the
discrete energy (42) dissipates with every iteration of the implicit Fast OGDA
method.

######  Proof of Lemma 3.1 .

Let $0\leq\lambda\leq\alpha-1$. For brevity we denote for every $k\geq 0$

$u^{k+1}_{\lambda}:=2\lambda\left(z^{k+1}-z_{*}\right)+2\left(k+1\right)\left(z^{k+1}-z^{k}\right)+s\left(k+1\right)\beta_{k}V\left(z^{k+1}\right).$
(79)

This means that for every $k\geq 1$ it holds

$u^{k}_{\lambda}=2\lambda\left(z^{k}-z_{*}\right)+2k\left(z^{k}-z^{k-1}\right)+sk\beta_{k-1}V\left(z^{k}\right),$

therefore taking the difference and using (38) we deduce that

$\displaystyle u^{k+1}_{\lambda}-u^{k}_{\lambda}=$ $\displaystyle\
2\left(\lambda+1-\alpha\right)\left(z^{k+1}-z^{k}\right)+2\left(k+\alpha\right)\left(z^{k+1}-z^{k}\right)-2k\left(z^{k}-z^{k-1}\right)$
$\displaystyle+s\Bigl{(}\left(k+1\right)\beta_{k}-k\beta_{k-1}\Bigr{)}V\left(z^{k+1}\right)+sk\beta_{k-1}\left(V\left(z^{k+1}\right)-V\left(z^{k}\right)\right)$
$\displaystyle=$ $\displaystyle\
2\left(\lambda+1-\alpha\right)\left(z^{k+1}-z^{k}\right)+\left(1-\alpha\right)s\beta_{k}V\left(z^{k+1}\right)-sk\beta_{k-1}\left(V\left(z^{k+1}\right)-V\left(z^{k}\right)\right).$
(80)

In the following we want to use the following identity

$\dfrac{1}{2}\left(\left\lVert u^{k+1}_{\lambda}\right\rVert^{2}-\left\lVert
u^{k}_{\lambda}\right\rVert^{2}\right)=\left\langle
u^{k+1}_{\lambda},u^{k+1}_{\lambda}-u^{k}_{\lambda}\right\rangle-\dfrac{1}{2}\left\lVert
u^{k+1}_{\lambda}-u^{k}_{\lambda}\right\rVert^{2}\quad\forall k\geq 1.$ (81)

Using the relations (79) and (80), for every $k\geq 1$ we derive that

$\displaystyle\left\langle
u^{k+1}_{\lambda},u^{k+1}_{\lambda}-u^{k}_{\lambda}\right\rangle$
$\displaystyle=$ $\displaystyle\
4\lambda\left(\lambda+1-\alpha\right)\left\langle
z^{k+1}-z_{*},z^{k+1}-z^{k}\right\rangle+2\lambda\left(1-\alpha\right)s\beta_{k}\left\langle
z^{k+1}-z_{*},V\left(z^{k+1}\right)\right\rangle$ $\displaystyle-2\lambda
sk\beta_{k-1}\left\langle
z^{k+1}-z_{*},V\left(z^{k+1}\right)-V\left(z^{k}\right)\right\rangle+4\left(\lambda+1-\alpha\right)\left(k+1\right)\left\lVert
z^{k+1}-z^{k}\right\rVert^{2}$
$\displaystyle+2s\left(\lambda+2-2\alpha\right)\left(k+1\right)\beta_{k}\left\langle
z^{k+1}-z^{k},V\left(z^{k+1}\right)\right\rangle$
$\displaystyle-2s\left(k+1\right)k\beta_{k-1}\left\langle
z^{k+1}-z^{k},V\left(z^{k+1}\right)-V\left(z^{k}\right)\right\rangle+\left(1-\alpha\right)s^{2}\left(k+1\right)\beta_{k}^{2}\left\lVert
V\left(z^{k+1}\right)\right\rVert^{2}$
$\displaystyle-s^{2}\left(k+1\right)k\beta_{k}\beta_{k-1}\left\langle
V\left(z^{k+1}\right),V\left(z^{k+1}\right)-V\left(z^{k}\right)\right\rangle,$
(82)

and

$\displaystyle-\dfrac{1}{2}\left\lVert
u^{k+1}_{\lambda}-u^{k}_{\lambda}\right\rVert^{2}$
$\displaystyle=-2\left(\lambda+1-\alpha\right)^{2}\left\lVert
z^{k+1}-z^{k}\right\rVert^{2}-\dfrac{1}{2}\left(1-\alpha\right)^{2}s^{2}\beta_{k}^{2}\left\lVert
V\left(z^{k+1}\right)\right\rVert^{2}$
$\displaystyle\quad-\dfrac{1}{2}s^{2}k^{2}\beta_{k-1}^{2}\left\lVert
V\left(z^{k+1}\right)-V\left(z^{k}\right)\right\rVert^{2}$
$\displaystyle\quad-2\left(\lambda+1-\alpha\right)\left(1-\alpha\right)s\beta_{k}\left\langle
z^{k+1}-z^{k},V\left(z^{k+1}\right)\right\rangle$
$\displaystyle\quad+2\left(\lambda+1-\alpha\right)sk\beta_{k-1}\left\langle
z^{k+1}-z^{k},V\left(z^{k+1}\right)-V\left(z^{k}\right)\right\rangle$
$\displaystyle\quad+\left(1-\alpha\right)s^{2}k\beta_{k}\beta_{k-1}\left\langle
V\left(z^{k+1}\right),V\left(z^{k+1}\right)-V\left(z^{k}\right)\right\rangle.$
(83)

A direct computation shows that

$\displaystyle\Bigl{(}\left(\lambda+2-2\alpha\right)\left(k+1\right)-\left(\lambda+1-\alpha\right)\left(1-\alpha\right)\Bigr{)}\beta_{k}$
$\displaystyle=\ $
$\displaystyle\Bigl{(}\left(\lambda+1-\alpha\right)\left(2k+\alpha+1\right)-\lambda\left(k+1\right)\Bigr{)}\beta_{k}$
$\displaystyle=\ $
$\displaystyle\Bigl{(}\left(\lambda+1-\alpha\right)\left(2k+\alpha+1\right)-\lambda\Bigr{)}\beta_{k}-\lambda
k\left(\beta_{k}-\beta_{k-1}\right)+\lambda k\beta_{k-1}.$ (84)

By plugging (82) and (83) into (81), we get for every $k\geq 1$

$\displaystyle\dfrac{1}{2}\left(\left\lVert
u^{k+1}_{\lambda}\right\rVert^{2}-\left\lVert
u^{k}_{\lambda}\right\rVert^{2}\right)$ $\displaystyle=$ $\displaystyle\
4\lambda\left(\lambda+1-\alpha\right)\left\langle
z^{k+1}-z_{*},z^{k+1}-z^{k}\right\rangle+2\lambda\left(1-\alpha\right)s\beta_{k}\left\langle
z^{k+1}-z_{*},V\left(z^{k+1}\right)\right\rangle$ $\displaystyle-2\lambda
sk\beta_{k-1}\left\langle
z^{k+1}-z_{*},V\left(z^{k+1}\right)-V\left(z^{k}\right)\right\rangle+2\left(\lambda+1-\alpha\right)\left(2k+\alpha+1-\lambda\right)\left\lVert
z^{k+1}-z^{k}\right\rVert^{2}$
$\displaystyle+2s\Bigl{(}\left(\lambda+1-\alpha\right)\left(2k+\alpha+1\right)-\lambda\left(k+1\right)\Bigr{)}\beta_{k}\left\langle
z^{k+1}-z^{k},V\left(z^{k+1}\right)\right\rangle$
$\displaystyle-2sk\left(k+\alpha-\lambda\right)\beta_{k-1}\\!\left\langle
z^{k+1}-z^{k},V\left(z^{k+1}\right)-V\left(z^{k}\right)\right\rangle+\\!\dfrac{1}{2}\left(1-\alpha\right)s^{2}\beta_{k}^{2}\left(2k+\alpha+1\right)\left\lVert
V\left(z^{k+1}\right)\right\rVert^{2}$
$\displaystyle-s^{2}\left(k+\alpha\right)k\beta_{k}\beta_{k-1}\left\langle
V\left(z^{k+1}\right),V\left(z^{k+1}\right)-V\left(z^{k}\right)\right\rangle-\dfrac{1}{2}s^{2}k^{2}\beta_{k-1}^{2}\left\lVert
V\left(z^{k+1}\right)-V\left(z^{k}\right)\right\rVert^{2}.$ (85)

Next we are going to consider the remaining terms in the difference of the
discrete energy functions. First we observe that for every $k\geq 0$

$\displaystyle 2\lambda\left(\alpha-1-\lambda\right)\left(\left\lVert
z^{k+1}-z_{*}\right\rVert^{2}-\left\lVert z^{k}-z_{*}\right\rVert^{2}\right)$
$\displaystyle=\ $ $\displaystyle
2\lambda\left(\alpha-1-\lambda\right)\left(2\left\langle
z^{k+1}-z_{*},z^{k+1}-z^{k}\right\rangle-\left\lVert
z^{k+1}-z^{k}\right\rVert^{2}\right).$ (86)

Some algebra shows that for every $k\geq 1$

$\displaystyle 2\lambda s\left(k+1\right)\beta_{k}\left\langle
z^{k+1}-z_{*},V\left(z^{k+1}\right)\right\rangle-2\lambda
sk\beta_{k-1}\left\langle z^{k}-z_{*},V\left(z^{k}\right)\right\rangle$
$\displaystyle=\ $ $\displaystyle 2\lambda
s\Bigl{(}\left(k+1\right)\beta_{k}-k\beta_{k-1}\Bigr{)}\left\langle
z^{k+1}-z_{*},V\left(z^{k+1}\right)\right\rangle$ $\displaystyle\quad+2\lambda
sk\beta_{k-1}\left(\left\langle
z^{k+1}-z_{*},V\left(z^{k+1}\right)\right\rangle-\left\langle
z^{k}-z_{*},V\left(z^{k}\right)\right\rangle\right)$ $\displaystyle=\ $
$\displaystyle 2\lambda
s\Bigl{(}\left(k+1\right)\beta_{k}-k\beta_{k-1}\Bigr{)}\left\langle
z^{k+1}-z_{*},V\left(z^{k+1}\right)\right\rangle$ $\displaystyle\quad+2\lambda
sk\beta_{k-1}\left\langle
z^{k+1}-z_{*},V\left(z^{k+1}\right)-V\left(z^{k}\right)\right\rangle+2\lambda
sk\beta_{k-1}\left\langle z^{k+1}-z^{k},V\left(z^{k}\right)\right\rangle$
$\displaystyle=\ $ $\displaystyle 2\lambda
s\Bigl{(}\left(k+1\right)\beta_{k}-k\beta_{k-1}\Bigr{)}\left\langle
z^{k+1}-z_{*},V\left(z^{k+1}\right)\right\rangle-2\lambda
sk\beta_{k-1}\left\langle
z^{k+1}-z^{k},V\left(z^{k+1}\right)-V\left(z^{k}\right)\right\rangle$
$\displaystyle\quad+2\lambda sk\beta_{k-1}\left\langle
z^{k+1}-z_{*},V\left(z^{k+1}\right)-V\left(z^{k}\right)\right\rangle+2\lambda
sk\beta_{k-1}\left\langle z^{k+1}-z^{k},V\left(z^{k+1}\right)\right\rangle.$
(87)

Finally, according to (39) and (40), we have for every
$k\geq\left\lceil\alpha\right\rceil$

$\displaystyle\left(k+\alpha+1\right)\left(k+1\right)\beta_{k+1}-\left(k+\alpha\right)k\beta_{k-1}$
$\displaystyle=\ $
$\displaystyle\left(k+\alpha+1\right)\left(k+1\right)\bigl{(}\beta_{k+1}-\beta_{k}\bigr{)}+\left(k+\alpha\right)k\bigl{(}\beta_{k}-\beta_{k-1}\bigr{)}+\left(2k+\alpha+1\right)\beta_{k}$
$\displaystyle\leq\ $
$\displaystyle\left(\alpha-2-\varepsilon\right)\Bigl{(}\left(k+\alpha+1\right)\beta_{k+1}+\left(k+\alpha\right)\beta_{k}\Bigr{)}+\left(2k+\alpha+1\right)\beta_{k}$
$\displaystyle=\ $
$\displaystyle\left(\alpha-2-\varepsilon\right)\Bigl{(}\left(k+1\right)\left(\beta_{k+1}-\beta_{k}\right)+\alpha\beta_{k+1}+\left(2k+\alpha+1\right)\beta_{k}\Bigr{)}+\left(2k+\alpha+1\right)\beta_{k}$
$\displaystyle\leq\ $
$\displaystyle\left(\alpha-2-\varepsilon\right)\left(2\alpha-2-\varepsilon\right)\beta_{k+1}+\left(\alpha-1-\varepsilon\right)\left(2k+\alpha+1\right)\beta_{k}$
$\displaystyle\leq\ $
$\displaystyle\dfrac{\alpha}{2+\varepsilon}\left(\alpha-2-\varepsilon\right)\left(2\alpha-2-\varepsilon\right)\beta_{k}+\left(\alpha-1-\varepsilon\right)\left(2k+\alpha+1\right)\beta_{k}$

and thus it holds

$\displaystyle\
\dfrac{1}{2}s^{2}\left(k+\alpha+1\right)\left(k+1\right)\beta_{k+1}\beta_{k}\left\lVert
V\left(z^{k+1}\right)\right\rVert^{2}-\dfrac{1}{2}s^{2}\left(k+\alpha\right)k\beta_{k}\beta_{k-1}\left\lVert
V\left(z^{k}\right)\right\rVert^{2}$ $\displaystyle=$ $\displaystyle\
\dfrac{1}{2}s^{2}\Bigl{(}\left(k+\alpha+1\right)\left(k+1\right)\beta_{k+1}-\left(k+\alpha\right)k\beta_{k-1}\Bigr{)}\beta_{k}\left\lVert
V\left(z^{k+1}\right)\right\rVert^{2}$