# Fast Forward-Backward splitting for monotone inclusions with a convergence
rate of the tangent residual of $o(1/k)$

Radu Ioan Boţ111Faculty of Mathematics, University of Vienna, Oskar-
Morgenstern-Platz 1, 1090 Vienna, Austria, e-mail<EMAIL_ADDRESS>Research partially supported by Austrian Science Fund (FWF), project W 1260
and P 29809-N32. Dang-Khoa Nguyen222Faculty of Mathematics, University of
Vienna, Oskar-Morgenstern-Platz 1, 1090 Vienna, Austria, e-mail: dang-
<EMAIL_ADDRESS>Research partially supported by Austrian Science
Fund (FWF), project P 29809-N32. 333Faculty of Mathematics and Computer
Science, University of Science, Vietnam National University, Ho Chi Minh City
700000, Vietnam. Chunxiang Zong444School of Mathematics and Statistics,
Lanzhou University, Lanzhou 730000, People’s Republic of China, e-mail:
<EMAIL_ADDRESS>Research partially supported by the China Scholarship
Council (202206180023) and conducted during a research visit at the University
of Vienna in 2023.

###### Abstract

We address the problem of finding the zeros of the sum of a maximally monotone
operator and a cocoercive operator. Our approach introduces a modification to
the forward-backward method by integrating an inertial/momentum term alongside
a correction term. We demonstrate that the sequence of iterations thus
generated converges weakly towards a solution for the monotone inclusion
problem. Furthermore, our analysis reveals an outstanding attribute of our
algorithm: it displays rates of convergence of the order $o(1/k)$ for the
discrete velocity and the tangent residual approaching zero. These rates for
tangent residuals can be extended to fixed-point residuals frequently
discussed in the existing literature. Specifically, when applied to minimize a
nonsmooth convex function subject to linear constraints, our method evolves
into a primal-dual full splitting algorithm. Notably, alongside the
convergence of iterates, this algorithm possesses a remarkable characteristic
of nonergodic/last iterate $o(1/k)$ convergence rates for both the function
value and the feasibility measure. Our algorithm showcases the most advanced
convergence and convergence rate outcomes among primal-dual full splitting
algorithms when minimizing nonsmooth convex functions with linear constraints.

Key Words. monotone inclusion, forward-backward algorithm, Nesterov’s
momentum, Lyapunov analysis, convergence rates, convergence of the iterates,
convex optimization subject to linear constraints, primal-dual algorithm

AMS subject classification. 49M29, 65K05, 68Q25, 90C25, 65B99

##  1 Introduction and related works

###  1.1 Forward-Backward splitting

A multitude of problems in optimization, variational inequalities, partial
differential equations, mechanics, economics, game theory, and signal and
image processing can be streamlined by solving a monotone inclusion. Monotone
inclusions seeking to determine a zero of the sum of two maximally monotone
operators are efficiently solved using the splitting paradigm. This approach
involves evaluating the two operators separately from each other [10, 40].
Depending on the nature of the operators, different splitting approaches have
been considered. These include _Douglas-Rachford splitting_ [28, 20],
_Forward-Backward splitting_ [28, 38], _Tseng’s Forward-Backward-Forward
splitting_ [45], and Forward-Reflected-Backward splitting [31].

In this paper, our focal point is the _Forward-Backward splitting_ approach,
with our aim being to notably improve its convergence rate while maintaining
its inherent convergence properties.

To introduce the problem, let $\mathcal{H}$ be a real Hilbert space,
$M\colon\mathcal{H}\to 2^{\mathcal{H}}$ a maximally monotone operator and
$C\colon\mathcal{H}\to\mathcal{H}$ a $\beta$-cocoercive operator with
parameter $\beta>0$, that is

$\left\langle
C\left(z\right)-C\left(y\right),z-y\right\rangle\geq\beta\left\lVert
C\left(z\right)-C\left(y\right)\right\rVert^{2}\quad\forall
z,y\in\mathcal{H}.$

We aim to solve the monotone inclusion problem

$0\in M\left(z\right)+C\left(z\right),$ (1.1)

and assume that it has a solution, namely,

${\cal Z}:=\textrm{zer}\left(M+C\right)=\left\\{z\in\mathcal{H}\colon
M\left(z\right)+C\left(z\right)\right\\}\neq\emptyset.$

The _Forward-Backward splitting_ (FBS) algorithm, introduced by Passty [38],
stands out as the most successful and widely used method for solving (1.1). In
its classical formulation, given an initial point $z_{0}\in\mathcal{H}$, the
algorithm generates a sequence $(z_{k})_{k\geq 0}$ using the following
iteration

$(\forall k\geq 0)\quad z_{k+1}:=J_{\gamma M}\left(z_{k}-\gamma
C\left(z_{k}\right)\right),$ (1.2)

where $\gamma\in(0,2\beta)$ represents a fixed step size. Here, we define

$J_{\gamma M}\colon\mathcal{H}\to\mathcal{H},\quad J_{\gamma
M}:=\left(\mathrm{Id}+\gamma M\right)^{-1},$

as the _resolvent_ of the operator $M$ with parameter $\gamma>0$, where
$\mathrm{Id}\colon\mathcal{H}\to\mathcal{H}$ represents the _identity
operator_.

The FBS algorithm leverages the specific characteristics of each operator and
treats them accordingly. As $C$ is single-valued, it is naturally addressed
through a _forward step_. Conversely, the maximal monotonicity of $M$ ensures
that its resolvent $J_{\gamma M}$ is a single-valued operator, universally
defined, and $1$-cocoercive and is therefore addresses through a _backward
step_. However, closed-form expressions for the resolvents of certain operator
classes arising in applications are readily available. Regarding its
convergence properties, the sequence $(z_{k})_{k\geq 0}$ weakly converges to a
solution of (1.1) as $k\rightarrow+\infty$. The FBS algorithm (1.2) and its
variations have been extensively explored in [22, 19, 21, 23].

The rate of convergence of the FBS algorithm is typically assessed using
quantities such as

$\left\lVert z_{k}-z_{k-1}\right\rVert\quad\textrm{ and }\quad
r_{\mathrm{fix},\gamma}\left(z_{k}\right):=\left\lVert z_{k}-J_{\gamma
M}\left(z_{k}-\gamma C\left(z_{k}\right)\right)\right\rVert.$

These represent the _discrete velocity_ and the _fixed-point residual_ ,
respectively. While these formulas coincide in the context of the classical
FBS algorithm (1.2), they may differ for its various variants. However, the
notable significance attributed to the fixed-point residual is motivated by
the fact that the monotone inclusion problem (1.1) can be expressed
equivalently as a fixed-point problem. Precisely, for any $\gamma>0$, the
equivalence holds

$0\in M\left(z\right)+C\left(z\right)\Leftrightarrow z-\gamma
C\left(z\right)\in z+\gamma M\left(z\right)\Leftrightarrow z=J_{\gamma
M}\left(z-\gamma C\left(z\right)\right).$ (1.3)

This demonstrates that the FBS algorithm can be viewed as an application of
the Krasnosel’skiĭ-Mann method [10, 40] to a specific fixed-point problem.
Consequently, the convergence rate of the FBS method can be derived from the
more general Krasnosel’skiĭ-Mann iteration [9, 16, 24, 32], and therefore it
can be expressed as

$r_{\mathrm{fix},\gamma}\left(z_{k}\right)=\left\lVert z_{k}-J_{\gamma
M}\left(z_{k}-\gamma
C\left(z_{k}\right)\right)\right\rVert=o\left(\dfrac{1}{\sqrt{k}}\right)\textrm{
as }k\to+\infty.$

###  1.2 Related works

Over the past two decades, there has been a considerable surge of interest in
the optimization community and related fields, focusing on accelerating the
convergence speed of first-order methods. It was early recognized that
inertial/momentum effects possess the capability to expedite convergence
without significantly increasing computational effort [34, 35, 36, 11, 18, 7,
4].

In the context of minimizing a differentiable function
$\phi\colon\mathcal{H}\to\mathbb{R}$, Polyak introduced the _Heavy Ball
Method_ in [39], given by

$(\forall k\geq 1)\quad
z_{k+1}:=z_{k}+\alpha\left(z_{k}-z_{k-1}\right)-\gamma\nabla\phi\left(z_{k}\right),$
(1.4)

which originates from the discretization of the second-order dynamical system

$\ddot{z}\left(t\right)+\mu\dot{z}\left(t\right)+\nabla\phi\left(z\left(t\right)\right)=0.$

Subsequent extensive research on this dynamical system was conducted by
Attouch, Goudou, and Redont in [6].

In [1], Alvarez examined the implicit counterpart of (1.4) to address
situations where $\phi$ might lack differentiability. Subsequently, Alvarez,
in collaboration with Attouch [3, 2], extended this approach to solve monotone
inclusions $0\in M(z)$, where $M\colon\mathcal{H}\to 2^{\mathcal{H}}$
represents a maximally monotone operator. Given the initial points
$z_{0},z_{1}\in\mathcal{H}$ and a step size $\gamma>0$, they proposed the
iterative process

$(\forall k\geq 1)\quad
z_{k+1}-z_{k}-\alpha_{k}\left(z_{k}-z_{k-1}\right)+\gamma
M\left(z_{k+1}\right)\ni 0,$

called _inertial Proximal Point Method_ which, in terms of the resolvent, can
be equivalently written as

$(\forall k\geq 1)\quad z_{k+1}:=J_{\gamma
M}\left(z_{k}+\alpha_{k}\left(z_{k}-z_{k-1}\right)\right).$ (1.5)

The authors demonstrated that, subject to suitable conditions on
$\left(\alpha_{k}\right)_{k\geq 1}\in[0,1)$, the sequence
$\left(z_{k}\right)_{k\geq 0}$ converges weakly to a zero of $M$ as
$k\to+\infty$.

Over the past decade, various approaches have emerged in the literature
focusing on integrating inertial effects into the resolution of monotone
inclusions with additive structure, as represented in (1.1). In [33], Moudafi
and Oliny introduced the following iterative scheme

$(\forall k\geq 1)\quad z_{k+1}:=J_{\gamma
M}\left(z_{k}+\alpha_{k}\left(z_{k}-z_{k-1}\right)-\gamma
C\left(z_{k}\right)\right).$

Inspired by algorithms designed for optimization problems involving inertial
effects (see [34, 35, 36, 11]), Lorenz and Pock intoduced the _inertial
Forward-Backward splitting_ algorithm in [29], expressed by

$(\forall k\geq 1)\quad\left\\{\begin{aligned}
y_{k}&:=z_{k}+\alpha_{k}(z_{k}-z_{k-1});\\\ z_{k+1}&:=J_{\gamma
M}\left(y_{k}-\gamma C\left(y_{k}\right)\right).\end{aligned}\right.$ (1.6)

Although convergence of the iterates was demonstrated, no convergence rate
results could be provided. Moreover, the convergence of iterates was achieved
under an assumption regarding the sequence $\left(\alpha_{k}\right)_{k\geq
1}$, necessitating either an adaptive selection dependent on the previously
generated iterates or an upper bound constraint of $1/3$.

The _Relaxed Inertial Forward-Backward splitting_ algorithm, introduced by
Attouch and Cabot in [5] to address (1.1), is defined as follows:

$(\forall k\geq 1)\quad\left\\{\begin{aligned}
y_{k}&:=z_{k}+\alpha_{k}(z_{k}-z_{k-1});\\\
z_{k+1}&:=(1-\rho_{k})y_{k}+\rho_{k}J_{\mu_{k}M}\left(y_{k}-\mu_{k}C(y_{k})\right),\end{aligned}\right.$
(1.7)

where $\left(\alpha_{k}\right)_{k\geq 1},\left(\rho_{k}\right)_{k\geq 1}$, and
$\left(\mu_{k}\right)_{k\geq 1}$ are positive sequences. In [8], Attouch and
Peypouquet demonstrated that the incorporation of relaxation parameters
$\left(\rho_{k}\right)_{k\geq 1}$ in the iterative scheme allows for a more
flexible allows for a more flexible selection of the inertial parameters
$\left(\alpha_{k}\right)_{k\geq 1}$ than the previously described.

Driven by their remarkable success in optimization, methods aimed at
accelerating the convergence speed of algorithms for monotone inclusions have
awakened the interest of the scientific community in recent years. Using the
performance estimate problem technique, Kim derived in [27] an _Accelerated
Proximal Point Method_ (APPM) tailored for finding a zero of a maximally
monotone operator within a finite-dimensional setting. Given the initial
points $y_{-1}=y_{0}=z_{0}=z_{1}\in\mathcal{H}$, the algorithm is expressed as

$(\forall k\geq 1)\quad\left\\{\begin{aligned}
y_{k}&:=z_{k}+\alpha_{k}(z_{k}-z_{k-1})+\alpha_{k}\left(y_{k-2}-z_{k-1}\right);\\\
z_{k+1}&:=J_{\gamma M}\left(y_{k}\right).\end{aligned}\right.$ (1.8)

This algorithm enhances the first update rule of (1.5) with the _correction
term_ “$y_{k-2}-z_{k-1}$”. For $\alpha_{k}=1-\frac{2}{k+1}$ for every $k\geq
1$, (1.8) displays a convergence rate for the fixed-point residual

$\left\lVert y_{k}-J_{\gamma
M}\left(y_{k}\right)\right\rVert=\mathcal{O}\left(\dfrac{1}{k}\right)\textrm{
as }k\to+\infty.$

The convergence of the iterates generated by (1.5) was not addressed in this
work.

Recently, in [30], Maingé introduced the _Corrected Relaxed Inertial Forward-
Backward Algorithm_ (CRIFBA), achieved by integrating in (1.2) a constant
relaxation factor, an inertial/momentum term and a correction term. With
initial points $y_{0},z_{0},z_{1}\in\mathcal{H}$, the iterative scheme is
expressed as

$(\forall k\geq 1)\quad\left\\{\begin{aligned}
y_{k}&:=z_{k}+\alpha_{k}(z_{k}-z_{k-1})+\delta_{k}(y_{k-1}-z_{k});\\\
z_{k+1}&:=(1-\rho)y_{k}+\rho J_{\gamma M}\left(y_{k}-\gamma
C(y_{k})\right),\end{aligned}\right.$ (1.9)

where $\left(\alpha_{k}\right)_{k\geq 1}\subseteq[0,1)$,
$\left(\delta_{k}\right)_{k\geq 1}\subseteq[0,1)$, $\rho\in(0,1)$, and
$\gamma>0$. Maingé’s algorithm incorporates a correction term, denoted as
“$y_{k-1}-z_{k}$”, which carries a coefficient that may be distinct from that
of the momentum term. Under conditions where $\alpha_{k}\sim 1-\frac{1}{k}$
and $\delta_{k}\sim 1-\frac{1}{k}$, the weak convergence of the iterate
sequence to a zero of $M+C$ is demonstrated. Moreover, convergence rates of
$o(1/k)$ are established for both the discrete velocity and the fixed-point
residual. The selection of the sequence of inertial parameters
$\left(\alpha_{k}\right)_{k\geq 1}$ aligns with those used in fast numerical
methods for convex optimization (see [18, 7, 4]).

As (1.1) can be reformulated as a fixed-point problem (see (1.3)), accelerated
Forward-Backward splitting methods can be directly derived from techniques
designed for fixed-point problems. One such technique, aiming to expedite the
convergence of fixed-point problems, traces its origins to the Halpern
iteration [25] and involves incorporating an anchoring point [47, 44, 37, 17].
In [43], Tran-Dinh highlighted connections between this approach and methods
utilizing an inertial/momentum term, particularly for specific parameter
choices.

Recently, in [15], we derived an iterative scheme for solving (1.1) from the
general _Fast Krasnosel’skiĭ-Mann algorithm_ (fKM) introduced for fixed-point
problems (see also [13]). With initial points $z_{0},z_{1}\in\mathcal{H}$,
$\alpha>2$, step size $0<\gamma<2\beta$ and $0<s<2-\frac{\gamma}{2\beta}$, the
iterative scheme is defined as

$\displaystyle(\forall k\geq 1)\quad z_{k+1}:=$ $\displaystyle\
\left(1-\dfrac{s\alpha}{2\left(k+\alpha\right)}\right)z_{k}+\dfrac{(1-s)k}{k+\alpha}(z_{k}-z_{k-1})+\dfrac{s(\alpha+2k)}{2(k+\alpha)}J_{\gamma
M}\left(z_{k}-\gamma C\left(z_{k}\right)\right)$ $\displaystyle\
-\dfrac{sk}{k+\alpha}J_{\gamma M}\left(z_{k-1}-\gamma
C\left(z_{k-1}\right)\right).$ (1.10)

The resulting iterates converge weakly to a solution of (1.1). Furthermore,
the algorithm exhibits a convergence rate of $o\left(\frac{1}{k}\right)$ for
both the discrete velocity $\left\lVert z_{k}-z_{k-1}\right\rVert$ and the
fixed-point residual $r_{\mathrm{fix},\gamma}\left(z_{k}\right)$ as
$k\rightarrow+\infty$.

###  1.3 Our contributions

We propose a _Fast Forward-Backward algorithm_ to solve (1.1), incorporating
an inertial/momentum term alongside a correction term. For the sequence
$(z_{k})_{k\geq 0}$ generated by our method, we demonstrate that both the
discrete velocity $\left\lVert z_{k}-z_{k-1}\right\rVert$ and the tangent
residual $r_{\mathrm{tan}}\left(z_{k}\right)$ converge to zero with a rate of
$o\left(\frac{1}{k}\right)$ as $k\rightarrow+\infty$. The _tangent residual_
is defined as

$r_{\mathrm{tan}}\left(z\right):={\rm dist}(0,M(z)+C(z))=\inf_{\xi\in
M(z)}\left\lVert\xi+C\left(z\right)\right\rVert,$

and it holds (see Lemma A.5 in the Appendix) that

$r_{\mathrm{fix},\gamma}\left(z\right)=\left\lVert z-J_{\gamma
M}\left(z-\gamma C\left(z\right)\right)\right\rVert\leq\gamma{\rm
dist}(0,M(z)+C(z))=\gamma r_{\mathrm{tan}}\left(z\right)\quad\forall
z\in\mathcal{H}.$

For discussions concerning these convegence measures in the context of
_variational inequality_ problems, we refer to [42].

Hence, the convergence rate of $o\left(\frac{1}{k}\right)$ as
$k\rightarrow+\infty$ for the fixed-point residual immediately follows.
Moreover, we will establish the weak convergence of the sequence
$(z_{k})_{k\geq 0}$ to a solution of (1.1) as $k\rightarrow+\infty$.

As a significant application case, we derive a primal-dual full splitting
algorithm for solving optimization problems of the form

$\displaystyle\min\limits_{x\in\mathcal{X}}f\left(x\right)+h\left(x\right),$
$\displaystyle\textnormal{subject to }Ax=b.$ (1.11)

Here, $\mathcal{X}$ and $\mathcal{Y}$ represent real Hilbert spaces, where
$f\colon\mathcal{X}\to\mathbb{R}\cup\\{+\infty\\}$ is a proper, convex and
lower semicontinuous function, $h\colon\mathcal{X}\to\mathbb{R}$ is a convex
and differentiable function with a gradient that is $\beta^{-1}$-Lipschitz
continuous ($\beta>0$), and $A\colon\mathcal{X}\rightarrow\mathcal{Y}$ is a
linear continuous operator. The primal-dual algorithm is derived from the
general iterative scheme via the product space approach by Vũ [46].

Given the generated sequence of primal-dual iterates
$\left(x_{k},\lambda_{k}\right)_{k\geq 0}$, we observe convergence rates for
the velocities

$\left\lVert
x_{k}-x_{k-1}\right\rVert=o\left(\dfrac{1}{k}\right)\qquad\textrm{ and
}\qquad\left\lVert\lambda_{k}-\lambda_{k-1}\right\rVert=o\left(\dfrac{1}{k}\right)\qquad\textrm{
and }\qquad k\to+\infty.$

Moreover, we derive convergence rates for the _function values_ and the
_feasibility measure_ :

$\left\lvert\left(f+h\right)\left(x_{k}\right)-\left(f+h\right)\left(x_{*}\right)\right\rvert=o\left(\dfrac{1}{k}\right)\qquad\textrm{
and }\qquad\left\lVert
Ax_{k}-b\right\rVert=o\left(\dfrac{1}{k}\right)\qquad\textrm{ and }\qquad
k\to+\infty,$

respectively. Here, $x_{*}$ denotes an optimal solution of (1.3) and
$\left(f+h\right)\left(x_{*}\right)$ its optimal objective value. The
convergence results are derived from the rates of convergence for the tangent
residual in the monotone inclusion problem. It is important to highlight that
deriving such statements from the convergence rate results based on fixed-
point residual seems unattainable. Additionally, we establish the weak
convergence of $\left(x_{k},\lambda_{k}\right)_{k\geq 0}$ to a primal-dual
optimal solution.

Finally, we verify the theoretical findings by assessing the performance of
the proposed algorithm through numerical experiments.

##  2 The proposed algorithm

In this section, we formulate the algorithm and conduct a thorough analysis of
its convergence.

######  Algorithm 2.1.

Let $\alpha>2,\gamma>0$, $z_{0},y_{0}\in\mathcal{H}$, and $z_{1}:=J_{\gamma
M}\left(y_{0}-\gamma C\left(z_{0}\right)\right)$. We set $(\forall k\geq
1)\quad\begin{dcases}y_{k}&:=z_{k}+\left(1-\dfrac{\alpha}{k+\alpha}\right)\left(z_{k}-z_{k-1}\right)+\left(1-\dfrac{\alpha}{2\left(k+\alpha\right)}\right)\left(y_{k-1}-z_{k}\right);\\\
z_{k+1}&:=J_{\gamma M}\left(y_{k}-\gamma
C\left(z_{k}\right)\right).\end{dcases}$ (2.1)

In the following, we provide an equivalent formulation for 2.1, which will
play a central role in the convergence analysis.

######  Proposition 2.2.

Let $z_{0},y_{0}\in\mathcal{H}$, $z_{1}:=J_{\gamma M}\left(y_{0}-\gamma
C\left(z_{0}\right)\right)$, and
$\xi_{1}:=\frac{1}{\gamma}\left(y_{0}-z_{1}\right)-C\left(z_{0}\right)\in
M\left(z_{1}\right)$. Then the sequence $(z_{k})_{k\geq 0}$ generated in 2.1
can also be generated equivalently by the following iterative scheme

$(\forall k\geq 1)\quad\\!\\!\\!\begin{dcases}z_{k+1}\\!\\!&:=J_{\gamma
M}\left(z_{k}-\gamma
C\left(z_{k}\right)+\left(1-\dfrac{\alpha}{k+\alpha}\right)\left(z_{k}-z_{k-1}\right)+\frac{2k+\alpha}{2(k+\alpha)}\gamma\left(\xi_{k}+C\left(z_{k-1}\right)\right)\right);\\\
\xi_{k+1}\\!\\!&:=\frac{1}{\gamma}\left(z_{k}-z_{k+1}+\left(1-\dfrac{\alpha}{k+\alpha}\right)(z_{k}-z_{k-1})\right)+\frac{2k+\alpha}{2(k+\alpha)}\left(\xi_{k}+C\left(z_{k-1}\right)\right)-C\left(z_{k}\right).\end{dcases}$
(2.2)

In addition, it holds

$\xi_{k}\in M\left(z_{k}\right)\qquad\quad\forall k\geq 1.$ (2.3)

###### Proof.

Given $z_{0},y_{0}\in\mathcal{H}$ and $z_{1}:=J_{\gamma M}\left(y_{0}-\gamma
C\left(z_{0}\right)\right)$, it follows that

$\Leftrightarrow\xi_{1}=\frac{1}{\gamma}\left(y_{0}-z_{1}\right)-C\left(z_{0}\right)\in
M\left(z_{1}\right).$

In the same way, by invoking also the second update block of 2.1, we obtain

$\xi_{k+1}:=\frac{1}{\gamma}\left(y_{k}-z_{k+1}\right)-C\left(z_{k}\right)\in
M(z_{k+1})\quad\forall k\geq 0.$

Therefore, the iterative scheme in 2.1 can be equivalently written as

$\ (\forall k\geq 1)\quad\left\\{\begin{aligned}
y_{k}&:=z_{k}+\left(1-\dfrac{\alpha}{k+\alpha}\right)\left(z_{k}-z_{k-1}\right)+\left(1-\frac{\alpha}{2(k+\alpha)}\right)\gamma\left(\xi_{k}+C\left(z_{k-1}\right)\right);\\\
z_{k+1}&:=J_{\gamma M}\left(y_{k}-\gamma C\left(z_{k}\right)\right);\\\
\xi_{k+1}&:=\frac{1}{\gamma}\left(y_{k}-z_{k+1}\right)-C\left(z_{k}\right),\end{aligned}\right.$
(2.4)

which, after some simplifications, it transforms into (2.2).

Conversely, starting from (2.2), we can define a sequence
$\left(y_{k}\right)_{k\geq 1}$ following the first update block in (2.4).
Consequently, for every $k\geq 1$, the relation

$\gamma\left(\xi_{k+1}+C\left(z_{k}\right)\right)=y_{k}-z_{k+1},$ (2.5)

holds, leading to the transformation of (2.2) into (2.1). ∎

######  Remark 2.3.

  1. $\rm{(i)}$

Remarkably, within the first update block of (2.1), we incorporate both a
_momentum term_ denoted as “$z_{k}-z_{k-1}$” and a _correction term_ denoted
as “$y_{k-1}-z_{k}$”. Nevertheless, in the forward-backward step, our method
evaluates $C$ at $z_{k}$, thereby it can be seen as an extension of [33].
Notably, it differes significantly from other forward-backward schemes in the
existing literature.

  2. $\rm{(ii)}$

The apparent similarity between 2.1 and the CRIFBA method is misleading. While
the initial update block may appear similar, a significant conceptual
distinction arises due to our scheme evaluating $C$ at $z_{k}$, contrasting
with the CRIFBA method’s evaluation of $C$ at $y_{k}$. This disparity leads to
a substantial difference in how the correction terms are defined, even when
opting for $\rho=1$ in the CRFIBA method. Notably, this falls outside the
scope of the convergence evidence established in [30].

The reformulation (2.2) reveals some connection with other Nesterov’s
acceleration-type methods in the literature. This inspires us to consider, for
$z_{*}\in{\cal Z}$, the following discrete energy function
$\mathcal{E}_{\eta,k}$ for $0\leq\eta\leq\alpha-1$ and $k\geq 1$:

$\displaystyle\mathcal{E}_{\eta,k}:=$ $\displaystyle\ \dfrac{1}{2}\left\lVert
2\eta\left(z_{k}-z_{*}\right)+2k\left(z_{k}-z_{k-1}\right)+\frac{5\alpha-2}{4(\alpha-1)}\gamma
k\left(\xi_{k}+C\left(z_{k-1}\right)\right)\right\rVert^{2}$
$\displaystyle+2\eta\left(\alpha-1-\eta\right)\left\lVert
z_{k}-z_{*}\right\rVert^{2}+2\eta\gamma\left(\frac{3(\alpha-2)}{4(\alpha-1)}k+\alpha\right)\big{\langle}z_{k}-z_{*},\xi_{k}+C\left(z_{k-1}\right)\big{\rangle}$
$\displaystyle+\frac{1}{2}\gamma^{2}\left(\frac{3(\alpha-2)}{4(\alpha-1)}k+\alpha\right)\left(\frac{5\alpha-2}{4(\alpha-1)}k+\alpha\right)\left\lVert\xi_{k}+C\left(z_{k-1}\right)\right\rVert^{2}$
$\displaystyle=$ $\displaystyle\ 2\eta\left(\alpha-1\right)\left\lVert
z_{k}-z_{*}\right\rVert^{2}+4\eta
k\big{\langle}z_{k}-z_{*},z_{k}-z_{k-1}+\gamma(\xi_{k}+C\left(z_{k-1}\right))\big{\rangle}$
$\displaystyle+2\eta\gamma\alpha\langle
z_{k}-z_{*},\xi_{k}+C\left(z_{k-1}\right)\rangle+\dfrac{1}{2}k^{2}\left\lVert
2\left(z_{k}-z_{k-1}\right)+\frac{5\alpha-2}{4(\alpha-1)}\gamma(\xi_{k}+C\left(z_{k-1}\right))\right\rVert^{2}$
$\displaystyle+\frac{1}{2}\gamma^{2}\left(\frac{3(\alpha-2)}{4(\alpha-1)}k+\alpha\right)\left(\frac{5\alpha-2}{4(\alpha-1)}k+\alpha\right)\left\lVert\xi_{k}+C\left(z_{k-1}\right)\right\rVert^{2}.$
(2.6)

In the upcoming lemma, we introduce a property of the discrete energy sequence
$\left(\mathcal{E}_{\eta,k}\right)_{k\geq 1}$, crucial for establishing the
convergence results. Its proof can be found in Appendix A.2.

######  Lemma 2.4.

Let $z_{*}\in{\cal Z}$, $\left(z_{k}\right)_{k\geq 0}$ be the sequence
generated by Algorithm 2.1, and $\left(\xi_{k}\right)_{k\geq 1}$ the sequence
generated by the iterative scheme (2.2). For every $0\leq\eta\leq\alpha-1$ and
every $k\geq 1$ it holds

$\displaystyle\mathcal{E}_{\eta,k+1}-\mathcal{E}_{\eta,k}\leq\ $
$\displaystyle 2\eta\gamma(2-\alpha)\left\langle
z_{k+1}-z_{*},\xi_{k+1}+C\left(z_{k}\right)\right\rangle+2\gamma\left(\nu_{0}k+\nu_{1}\right)\left\langle
z_{k+1}-z_{k},\xi_{k+1}+C\left(z_{k}\right)\right\rangle$
$\displaystyle+2\nu_{2}k\left\lVert
z_{k+1}-z_{k}\right\rVert^{2}+\frac{1}{2}\gamma^{2}(\nu_{3}k+\nu_{4})\left\lVert\xi_{k+1}+C\left(z_{k}\right)\right\rVert^{2}$
$\displaystyle-2\gamma\left(\frac{3(\alpha-2)}{4(\alpha-1)}k+\alpha\right)\left(k+\alpha\right)\left\langle
z_{k+1}-z_{k},\xi_{k+1}+C\left(z_{k}\right)-(\xi_{k}+C\left(z_{k-1}\right))\right\rangle$
$\displaystyle-\gamma^{2}\left(\frac{3(\alpha-2)}{4(\alpha-1)}k+\alpha\right)(k+\alpha)\left\lVert\xi_{k+1}+C\left(z_{k}\right)-(\xi_{k}+C\left(z_{k-1}\right))\right\rVert^{2},$
(2.7)

where

$\displaystyle\nu_{0}$
$\displaystyle:=\frac{3(\alpha-2)}{4(\alpha-1)}\eta+\frac{5\alpha-2}{4(\alpha-1)}\left(\eta+1-\alpha\right)-\frac{(4\alpha-1)(\alpha-2)}{4(\alpha-1)}$
$\displaystyle\nu_{1}$
$\displaystyle:=\alpha(\eta+1-\alpha)+(\eta-1)\alpha+\frac{(5\alpha-2)}{4(\alpha-1)}$
$\displaystyle\nu_{2}$ $\displaystyle:=2\left(\eta+1-\alpha\right)\leq 0$
$\displaystyle\nu_{3}$
$\displaystyle:=\frac{5\alpha-2}{2(\alpha-1)}(2-\alpha)<0$
$\displaystyle\nu_{4}$
$\displaystyle:=\frac{4\alpha^{2}+\alpha-2}{2(\alpha-1)}-\alpha^{2}.$

Further, for $0<\varepsilon<1$ and $0\leq\eta\leq\alpha-1$ we consider the
following regularization of the discrete energy function, defined for every
$k\geq 1$ by

$\displaystyle\mathcal{F}_{\eta,k}:=$ $\displaystyle\
\mathcal{E}_{\eta,k}-2\gamma\left(\frac{3(\alpha-2)}{4(\alpha-1)}k+\alpha\right)k\left\langle
z_{k}-z_{k-1},C\left(z_{k}\right)-C\left(z_{k-1}\right)\right\rangle$
$\displaystyle+\frac{1}{2}\gamma^{2}\left(\frac{3(\alpha-2)}{4(\alpha-1)}k+\alpha\right)\left((2-\varepsilon)(2k+\alpha)+\alpha\sqrt{\frac{3(\alpha-2)}{4(\alpha-1)}k+\alpha}\right)\left\lVert
C\left(z_{k}\right)-C\left(z_{k-1}\right)\right\rVert^{2}$ $\displaystyle=$
$\displaystyle\ \dfrac{1}{2}\left\lVert
2\eta\left(z_{k}-z_{*}\right)+2k\left(z_{k}-z_{k-1}\right)+\frac{5\alpha-2}{4(\alpha-1)}\gamma
k\left(\xi_{k}+C\left(z_{k-1}\right)\right)\right\rVert^{2}$
$\displaystyle+2\eta\left(\alpha-1-\eta\right)\left\lVert
z_{k}-z_{*}\right\rVert^{2}+2\eta\gamma\left(\frac{3(\alpha-2)}{4(\alpha-1)}k+\alpha\right)\big{\langle}z_{k}-z_{*},\xi_{k}+C\left(z_{k-1}\right)\big{\rangle}$
$\displaystyle+\frac{1}{2}\gamma^{2}\left(\frac{3(\alpha-2)}{4(\alpha-1)}k+\alpha\right)\left(\frac{5\alpha-2}{4(\alpha-1)}k+\alpha\right)\left\lVert\xi_{k}+C\left(z_{k-1}\right)\right\rVert^{2}$
$\displaystyle-2\gamma\left(\frac{3(\alpha-2)}{4(\alpha-1)}k+\alpha\right)k\left\langle
z_{k}-z_{k-1},C\left(z_{k}\right)-C\left(z_{k-1}\right)\right\rangle$
$\displaystyle+\frac{1}{2}\gamma^{2}\left(\frac{3(\alpha-2)}{4(\alpha-1)}k+\alpha\right)\left((2-\varepsilon)(2k+\alpha)+\alpha\sqrt{\frac{3(\alpha-2)}{4(\alpha-1)}k+\alpha}\right)\left\lVert
C\left(z_{k}\right)-C\left(z_{k-1}\right)\right\rVert^{2}.$ (2.8)

The properties of the regularized discrete energy sequence
$\left(\mathcal{F}_{\eta,k}\right)_{k\geq 0}$ are presented in 2.5, the proof
of which is also provided in Appendix A.2.

######  Lemma 2.5.

Let $z_{*}\in{\cal Z}$, $\left(z_{k}\right)_{k\geq 0}$ be the sequence
generated by Algorithm 2.1, and $\left(\xi_{k}\right)_{k\geq 1}$ the sequence
generated by the iterative scheme (2.2). For every $0\leq\eta\leq\alpha-1$ and
every $0<\varepsilon<1$, the following statements are true:

  1. $\rm{(i)}$

for every $k\geq 1$, it holds:

$\displaystyle\mathcal{F}_{\eta,k+1}-\mathcal{F}_{\eta,k}$
$\displaystyle\,\,\leq\frac{4(\alpha-2)(\alpha-1)}{3(k+1)\sqrt{k+1}}\eta^{2}\left\lVert
z_{k+1}-z_{*}\right\rVert^{2}-2\eta\gamma(\alpha-2)\left\langle
z_{k+1}-z_{*},\xi_{k+1}+C\left(z_{k+1}\right)\right\rangle$
$\displaystyle\quad+\frac{1}{2}\gamma^{2}\left(\nu_{3}k+\alpha\sqrt{\nu_{5}k+\alpha}+\nu_{4}\right)\left\lVert\xi_{k+1}+C\left(z_{k}\right)\right\rVert^{2}+2\nu_{2}k\left\lVert
z_{k+1}-z_{k}\right\rVert^{2}$
$\displaystyle\quad-\omega_{k}\|C\left(z_{k+1}\right)-C\left(z_{k}\right)\|^{2}+2\gamma\left(\nu_{0}k+\nu_{1}\right)\left\langle
z_{k+1}-z_{k},\xi_{k+1}+C\left(z_{k}\right)\right\rangle$
$\displaystyle\quad-\gamma^{2}\left(\nu_{5}k+\alpha\right)\left(\nu_{6}k+\nu_{7}\right)\|\xi_{k+1}+C\left(z_{k}\right)-(\xi_{k}+C\left(z_{k-1}\right))\|^{2},$
(2.9)

where

$\displaystyle\nu_{5}:=\frac{3}{4(\alpha-1)}(\alpha-2)>0,\quad\nu_{6}:=\frac{1}{2-\varepsilon}(1-\varepsilon)>0,\quad\nu_{7}:=\frac{1}{2(2-\varepsilon)}(3-2\varepsilon)\alpha>0,$

and

$\displaystyle\omega_{k}$
$\displaystyle:=\left(2\beta-(2-\varepsilon)\gamma\right)\frac{3(\alpha-2)}{4(\alpha-1)}\gamma(k+1)^{2}-\frac{3(\alpha-2)}{4(\alpha-1)}\gamma^{2}(k+1)\sqrt{k+1}$
$\displaystyle\quad\,\,-\frac{1}{2}\alpha\gamma^{2}\left(\frac{3(\alpha-2)}{4(\alpha-1)}(k+1)+\alpha\right)\sqrt{\frac{3(\alpha-2)}{4(\alpha-1)}(k+1)+\alpha}-\frac{1}{2}(2-\varepsilon)\gamma^{2}\alpha^{2}$
$\displaystyle\quad\,\,+\left(2\beta-(2-\varepsilon)\frac{11\alpha-14}{8(\alpha-1)}\gamma\right)\alpha\gamma(k+1).$
(2.10)

  2. $\rm{(ii)}$

for every $k\geq 1$, one has the following lower bound for the quantity
$\mathcal{F}_{\eta,k}$

$\displaystyle\mathcal{F}_{\eta,k}\geq$ $\displaystyle\
\frac{3(\alpha-2)}{4(5\alpha-2)}\left\lVert
4\eta\left(z_{k}-z_{*}\right)+2k\left(z_{k}-z_{k-1}\right)+\frac{5\alpha-2}{2(\alpha-1)}\gamma
k\left(\xi_{k}+C\left(z_{k-1}\right)\right)\right\rVert^{2}$
$\displaystyle+2\eta(\alpha-1)\left(1-\frac{8\eta}{5\alpha-2}\right)\left\lVert
z_{k}-z_{*}\right\rVert^{2}+\frac{1}{2}\gamma^{2}\alpha(2k+\alpha)\left\lVert\xi_{k}+C\left(z_{k-1}\right)\right\rVert^{2}$
$\displaystyle+\left(3(\alpha-2)\left(\frac{1}{5\alpha-2}-\frac{1}{4(2-\varepsilon)(\alpha-1)}\right)k^{2}-\frac{2}{\beta}\alpha\gamma
k\right)\left\lVert z_{k}-z_{k-1}\right\rVert^{2}$
$\displaystyle+2\eta\alpha\gamma\big{\langle}z_{k}-z_{*},\xi_{k}+C\left(z_{k-1}\right)\big{\rangle}.$
(2.11)

The last of the three technical lemmas describe the intervals where the
parameters that appear in the formulation of the algorithm and in the
definition of the discrete energy function can be chosen in order to obtain
convergence for the iterates and to derive convergence rates. Its proof is
also provided in Appendix A.2.

######  Lemma 2.6.

Let $z_{*}\in{\cal Z}$, $\left(z_{k}\right)_{k\geq 0}$ be the sequence
generated by Algorithm 2.1, and $\left(\xi_{k}\right)_{k\geq 1}$ the sequence
generated by the iterative scheme (2.2). The following statements are true:

  1. $\rm{(i)}$

if $0<\gamma<\frac{2}{2-\varepsilon}\beta$,
$0<\varepsilon<\frac{3(\alpha-2)}{4(\alpha-1)}$ and
$0<\eta<\frac{5\alpha-2}{8}$, then there exists an integer $K_{0}(\eta)\geq 1$
such that for every $k\geq K_{0}(\eta)$

$\omega_{k}\geq\left(2\beta-(2-\varepsilon)\gamma\right)\frac{3(\alpha-2)}{8(\alpha-1)}\gamma(k+1)^{2},\quad\quad\frac{3}{2}(\alpha-2)\left(\frac{1}{5\alpha-2}-\frac{1}{4(2-\varepsilon)(\alpha-1)}\right)k^{2}-\frac{2}{\beta}\alpha\gamma
k\geq 0,$ (2.12)

and

$S_{k}:=\eta(\alpha-1)\left(1-\frac{8}{5\alpha-2}\eta\right)\left\lVert
z_{k}-z_{*}\right\rVert^{2}+2\eta\alpha\gamma\langle
z_{k}-z_{*},\xi_{k}+C\left(z_{k-1}\right)\rangle+\frac{1}{2}\alpha\gamma^{2}k\left\lVert\xi_{k}+C\left(z_{k-1}\right)\right\rVert^{2}\geq
0,$ (2.13)

which yields, according to (2.11),

$\mathcal{F}_{\eta,k}\geq\eta(\alpha-1)\left(1-\frac{8}{5\alpha-2}\eta\right)\left\lVert
z_{k}-z_{*}\right\rVert^{2}\geq 0;$ (2.14)

  2. $\rm{(ii)}$

there exist two parameters

$0\leq\underline{\eta}(\alpha)<\overline{\eta}(\alpha)\leq\frac{5\alpha-2}{8}$
(2.15)

such that for every $\eta$ satisfying
$\underline{\eta}(\alpha)<\eta<\overline{\eta}(\alpha)$ one can find an
integer $K_{1}(\eta)\geq 1$ with the property that the following inequality
holds for every $k\geq K_{1}(\eta)$

$\displaystyle R_{k}:=$ $\displaystyle\
2\sqrt{\frac{9\alpha-2}{2(5\alpha-2)}}\nu_{2}k\left\lVert
z_{k+1}-z_{k}\right\rVert^{2}+2\gamma\left(\nu_{0}k+\nu_{1}\right)\left\langle
z_{k+1}-z_{k},\xi_{k+1}+C\left(z_{k}\right)\right\rangle$ $\displaystyle\
+\frac{1}{2}\sqrt{\frac{9\alpha-2}{2(5\alpha-2)}}\gamma^{2}\left(\nu_{3}k+\alpha\sqrt{\nu_{5}k+\alpha}+\nu_{4}\right)\left\lVert\xi_{k+1}+C\left(z_{k}\right)\right\rVert^{2}\leq
0;$ (2.16)

Following the previous preparatory results, we assume that the step size
$\gamma$ satisfies  $0<\gamma<\frac{8(\alpha-1)}{5\alpha-2}\beta.$ Therefore,

$\mbox{there exists}\ 0<\varepsilon<\frac{3(\alpha-2)}{4(\alpha-1)}<1\
\mbox{such that}\ 0<\gamma<\frac{2}{2-\varepsilon}\beta.$ (2.17)

Given that $\frac{8(\alpha-1)}{5\alpha-2}\beta<2\beta$, the condition on the
step size is somewhat more restrictive than in the classical forward-backward
setting, which typically permits $0<\gamma<2\beta$. However, despite this, our
methods demonstrate a superior theoretical rate of convergence when compared
to the classical forward-backward algorithm.

######  Proposition 2.7.

Let $z_{*}\in{\cal Z}$, $\left(z_{k}\right)_{k\geq 0}$ be the sequence
generated by Algorithm 2.1, and $\left(\xi_{k}\right)_{k\geq 1}$ the sequence
generated by the iterative scheme (2.2). Then the following statements are
true:

  1. $\rm{(i)}$

it holds

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

  2. $\rm{(ii)}$

the sequence $(z_{k})_{k\geq 0}$ is bounded and

$\displaystyle\left\lVert
z_{k}-z_{k-1}\right\rVert=\mathcal{O}\left(\dfrac{1}{k}\right),\,\quad\left\lVert\xi_{k}+C\left(z_{k}\right)\right\rVert=\mathcal{O}\left(\dfrac{1}{k}\right),\,\,\quad\left\langle
z_{k}-z_{*},\xi_{k}+C\left(z_{k}\right)\right\rangle=\mathcal{O}\left(\dfrac{1}{k}\right)\quad\mbox{as}\
k\rightarrow+\infty;$

  3. $\rm{(iii)}$

for every
$\eta\in\left(\underline{\eta}(\alpha),\overline{\eta}(\alpha)\right)$, where
$\underline{\eta}(\alpha)$ and $\overline{\eta}(\alpha)$ are the parameters
provided by Lemma 2.6 (ii), the sequences $(\mathcal{E}_{\eta,k})_{k\geq 1}$
and $(\mathcal{F}_{\eta,k})_{k\geq 1}$ are convergent and have the same limit.

###### Proof.

From the step size assumption we deduce that there exists
$0<\varepsilon<\frac{3(\alpha-2)}{4(\alpha-1)}<1$ such that
$0<\gamma<\frac{2}{2-\varepsilon}\beta$. Furthermore, we consider the
parameters $\underline{\eta}(\alpha)$ and $\overline{\eta}(\alpha)$ provided
by Lemma 2.6 (ii) and choose
$\eta\in\left(\underline{\eta}(\alpha),\overline{\eta}(\alpha)\right)$. From
2.6 (i) we obtain an integer $K_{0}(\eta)\geq 1$ such that for every $k\geq
K_{0}(\eta)$ the inequalities (2.12), (2.13) and (2.14) hold; from 2.6 (ii),
we obtain an integer $K_{1}(\eta)\geq 1$ such that for every $k\geq
K_{1}(\eta)$ the inequality ($\rm{(ii)}$) holds.

Invoking (2.9), for every $k\geq
K_{2}(\eta):=\max\\{K_{0}(\eta),K_{1}(\eta)\\}$ it holds

$\displaystyle\mathcal{F}_{\eta,k+1}-\mathcal{F}_{\eta,k}\leq$ $\displaystyle\
\frac{4(\alpha-2)(\alpha-1)}{3(k+1)\sqrt{k+1}}\eta^{2}\left\lVert
z_{k+1}-z_{*}\right\rVert^{2}-2\eta\gamma(\alpha-2)\left\langle
z_{k+1}-z_{*},\xi_{k+1}+C\left(z_{k+1}\right)\right\rangle$ $\displaystyle\
+\frac{1}{2}\left(1-\sqrt{\frac{9\alpha-2}{2(5\alpha-2)}}\right)\gamma^{2}\left(\nu_{3}k+\alpha\sqrt{\nu_{5}k+\alpha}+\nu_{4}\right)\left\lVert\xi_{k+1}+C\left(z_{k}\right)\right\rVert^{2}$
$\displaystyle\
-\omega_{k}\|C\left(z_{k+1}\right)-C\left(z_{k}\right)\|^{2}+2\left(1-\sqrt{\frac{9\alpha-2}{2(5\alpha-2)}}\right)\nu_{2}k\left\lVert
z_{k+1}-z_{k}\right\rVert^{2}$ $\displaystyle\
-\gamma^{2}\left(\nu_{5}k+\alpha\right)\left(\nu_{6}k+\nu_{7}\right)\|\xi_{k+1}+C\left(z_{k}\right)-(\xi_{k}+C\left(z_{k-1}\right))\|^{2}.$
(2.19)

We set

$\displaystyle\nu_{8}:=\frac{4}{3}(\alpha-2)\eta\left(1-\frac{8}{5\alpha-2}\eta\right)^{-1}>0\quad\mbox{and}\quad\nu_{9}:=\left(2\beta-(2-\varepsilon)\gamma\right)\frac{3(\alpha-2)}{8(\alpha-1)}\gamma>0.$

In view of (2.14), we have that for every $k\geq K_{2}(\eta)$

$\displaystyle\frac{4(\alpha-2)(\alpha-1)}{3(k+1)\sqrt{k+1}}\eta^{2}\left\lVert
z_{k+1}-z_{*}\right\rVert^{2}$
$\displaystyle\leq\frac{\nu_{8}}{(k+1)\sqrt{k+1}}\mathcal{F}_{\eta,k+1},$

therefore

$\displaystyle\
\left(1-\frac{\nu_{8}}{(k+1)\sqrt{k+1}}\right)\mathcal{F}_{\eta,k+1}$
$\displaystyle\leq$ $\displaystyle\
\mathcal{F}_{\eta,k}-2\eta\gamma(\alpha-2)\left\langle
z_{k+1}-z_{*},\xi_{k+1}+C\left(z_{k+1}\right)\right\rangle$ $\displaystyle\
+\frac{1}{2}\left(1-\sqrt{\frac{9\alpha-2}{2(5\alpha-2)}}\right)\gamma^{2}\left(\nu_{3}k+\alpha\sqrt{\nu_{5}k+\alpha}+\nu_{4}\right)\left\lVert\xi_{k+1}+C\left(z_{k}\right)\right\rVert^{2}$
$\displaystyle\
-\nu_{9}\left(k+1\right)^{2}\|C\left(z_{k+1}\right)-C\left(z_{k}\right)\|^{2}+2\left(1-\sqrt{\frac{9\alpha-2}{2(5\alpha-2)}}\right)\nu_{2}k\left\lVert
z_{k+1}-z_{k}\right\rVert^{2}$ $\displaystyle\
-\gamma^{2}\left(\nu_{5}k+\alpha\right)\left(\nu_{6}k+\nu_{7}\right)\|\xi_{k+1}+C\left(z_{k}\right)-(\xi_{k}+C\left(z_{k-1}\right))\|^{2}.$
(2.20)

For $K_{3}(\eta):=\lceil\sqrt[3]{\nu_{8}^{2}}-1\rceil$ we see that for every
$k\geq K_{3}(\eta)$

$\left(1-\frac{\nu_{8}}{(k+1)\sqrt{k+1}}\right)^{-1}=\frac{(k+1)\sqrt{k+1}}{(k+1)\sqrt{k+1}-\nu_{8}}=1+\frac{\nu_{8}}{(k+1)\sqrt{k+1}-\nu_{8}}>1.$

Since $\nu_{2},\nu_{3}<0$ and $\nu_{5},\nu_{6}>0$, there exists an integer
$K_{4}\geq 1$ such that for every $k\geq K_{4}$ it holds

$\nu_{3}k+\alpha\sqrt{\nu_{5}k+\alpha}+\nu_{4}<0\quad\textnormal{and}\quad\left(\nu_{5}k+\alpha\right)\left(\nu_{6}k+\nu_{7}\right)>0.$

Hence, for every $k\geq K_{5}(\eta):=\max\\{K_{2}(\eta),K_{3}(\eta),K_{4}\\}$,
according to (2.20), we obtain

$\displaystyle 0\leq\mathcal{F}_{\eta,k+1}\leq$
$\displaystyle\left(1+\frac{\nu_{8}}{(k+1)\sqrt{k+1}-\nu_{8}}\right)\mathcal{F}_{\eta,k}-2\eta\gamma(\alpha-2)\left\langle
z_{k+1}-z_{*},\xi_{k+1}+C\left(z_{k+1}\right)\right\rangle$
$\displaystyle+\frac{1}{2}\left(1-\sqrt{\frac{9\alpha-2}{2(5\alpha-2)}}\right)\gamma^{2}\left(\nu_{3}k+\alpha\sqrt{\nu_{5}k+\alpha}+\nu_{4}\right)\left\lVert\xi_{k+1}+C\left(z_{k}\right)\right\rVert^{2}$
$\displaystyle-\nu_{9}\left(k+1\right)^{2}\|C\left(z_{k+1}\right)-C\left(z_{k}\right)\|^{2}+2\left(1-\sqrt{\frac{9\alpha-2}{2(5\alpha-2)}}\right)\nu_{2}k\left\lVert
z_{k+1}-z_{k}\right\rVert^{2}$
$\displaystyle-\gamma^{2}\left(\nu_{5}k+\alpha\right)\left(\nu_{6}k+\nu_{7}\right)\|\xi_{k+1}+C\left(z_{k}\right)-(\xi_{k}+C\left(z_{k-1}\right))\|^{2},$

we utilized the fact that all summands on the right-hand side of the
inequality are nonpositive, except for the first one. The fact that
$\left\langle z_{k+1}-z_{*},\xi_{k+1}+C\left(z_{k+1}\right)\right\rangle\geq
0$ for every $k\geq 1$ follows from the monotonicity of the operator $M+C$ and
relation (2.3). This means that for

$\displaystyle a_{k}:=$ $\displaystyle\,\mathcal{F}_{\eta,k}\geq 0,$
$\displaystyle b_{k}:=$ $\displaystyle\,2\eta\gamma(\alpha-2)\left\langle
z_{k+1}-z_{*},\xi_{k+1}+C\left(z_{k+1}\right)\right\rangle-2\left(1-\sqrt{\frac{9\alpha-2}{2(5\alpha-2)}}\right)\nu_{2}k\left\lVert
z_{k+1}-z_{k}\right\rVert^{2}$
$\displaystyle+\nu_{9}\left(k+1\right)^{2}\|C\left(z_{k+1}\right)-C\left(z_{k}\right)\|^{2}+\gamma^{2}\left(\nu_{5}k+\alpha\right)\left(\nu_{6}k+\nu_{7}\right)\|\xi_{k+1}+C\left(z_{k}\right)-(\xi_{k}+C\left(z_{k-1}\right))\|^{2}$
$\displaystyle\,-\frac{1}{2}\left(1-\sqrt{\frac{9\alpha-2}{2(5\alpha-2)}}\right)\gamma^{2}\left(\nu_{3}k+\alpha\sqrt{\nu_{5}k+\alpha}+\nu_{4}\right)\left\lVert\xi_{k+1}+C\left(z_{k}\right)\right\rVert^{2}\geq
0$ $\displaystyle d_{k}:=$
$\displaystyle\,\frac{\nu_{8}}{(k+1)\sqrt{k+1}-\nu_{8}}>0,$

it holds

$a_{k+1}\leq(1+d_{k})a_{k}-b_{k}\quad\forall k\geq K_{5}(\eta),$ (2.21)

which, according A.2, ensures that the relations (2.18) hold as well as that
the sequence $(\mathcal{F}_{\eta,k})_{k\geq 1}$ is convergent.

As $(\mathcal{F}_{\eta,k})_{k\geq 1}$ is also bounded from above, (2.11),
(2.12) and (2.13) yield that for every $k\geq K_{5}(\eta)$

$\displaystyle\frac{3(\alpha-2)}{4(5\alpha-2)}\left\lVert
4\eta\left(z_{k}-z_{*}\right)+2k\left(z_{k}-z_{k-1}\right)+\frac{5\alpha-2}{2(\alpha-1)}\gamma
k\left(\xi_{k}+C\left(z_{k-1}\right)\right)\right\rVert^{2}$
$\displaystyle+\frac{3}{2}(\alpha-2)\left(\frac{1}{5\alpha-2}-\frac{1}{4(2-\varepsilon)(\alpha-1)}\right)k^{2}\left\lVert
z_{k}-z_{k-1}\right\rVert^{2}$
$\displaystyle+\eta(\alpha-1)\left(1-\frac{8\eta}{5\alpha-2}\right)\left\lVert
z_{k}-z_{*}\right\rVert^{2}$ $\displaystyle\leq\ $
$\displaystyle\mathcal{F}_{\eta,k}\leq\sup_{k\geq
1}\mathcal{F}_{\eta,k}<+\infty.$

In particular, for every $k\geq K_{5}(\eta)$ it holds

$\displaystyle\left\lVert
4\eta\left(z_{k}-z_{*}\right)+2k\left(z_{k}-z_{k-1}\right)+\frac{5\alpha-2}{2(\alpha-1)}\gamma
k\left(\xi_{k}+C\left(z_{k-1}\right)\right)\right\rVert\leq\nu_{10}:=2\sqrt{\frac{5\alpha-2}{3(\alpha-2)}\sup_{k\geq
1}\mathcal{F}_{\eta,k}}<+\infty,$ $\displaystyle k\left\lVert
z_{k}-z_{k-1}\right\rVert\leq\nu_{11}:=\sqrt{\frac{8(\alpha-1)(5\alpha-2)(2-\varepsilon)}{3(\alpha-2)\left(4(\alpha-1)(2-\varepsilon)-5\alpha+2\right)}\sup_{k\geq
1}\mathcal{F}_{\eta,k}}<+\infty,$ $\displaystyle\left\lVert
z_{k}-z_{*}\right\rVert\leq\nu_{12}:=\sqrt{\frac{5\alpha-2}{\eta(\alpha-1)(5\alpha-2-8\eta)}\sup_{k\geq
1}\mathcal{F}_{\eta,k}}<+\infty.$

Using the triangle inequality, we deduce from here that for every $k\geq
K_{5}(\eta)$

$\displaystyle\left\lVert\xi_{k}+C\left(z_{k-1}\right)\right\rVert\leq$
$\displaystyle\ \frac{2(\alpha-1)}{(5\alpha-2)\gamma k}\left\lVert
4\eta\left(z_{k}-z_{*}\right)+2k\left(z_{k}-z_{k-1}\right)+\frac{5\alpha-2}{2(\alpha-1)}\gamma
k\left(\xi_{k}+C\left(z_{k-1}\right)\right)\right\rVert$ $\displaystyle\
+\frac{4(\alpha-1)}{(5\alpha-2)\gamma}\left\lVert
z_{k}-z_{k-1}\right\rVert+\frac{8\eta(\alpha-1)}{(5\alpha-2)\gamma
k}\left\lVert z_{k}-z_{*}\right\rVert\leq\frac{\nu_{13}}{k},$

where

$\nu_{13}:=\frac{2(\alpha-1)}{(5\alpha-2)\gamma}(\nu_{10}+2\nu_{11}+4\overline{\eta}(\alpha)\nu_{12})>0.$

Further, it follows from

$\displaystyle\sum\limits_{k\geq 1}k^{2}\left\lVert
C\left(z_{k}\right)-C\left(z_{k-1}\right)\right\rVert^{2}<+\infty$

that

$\lim_{k\rightarrow+\infty}k\left\lVert
C\left(z_{k}\right)-C\left(z_{k-1}\right)\right\rVert=0\quad\Rightarrow\quad\nu_{14}:=\sup_{k\geq
1}\left\\{k\left\lVert
C\left(z_{k}\right)-C\left(z_{k-1}\right)\right\rVert\right\\}<+\infty.$

This implies that for every $k\geq K_{5}(\eta)$

$\displaystyle\|\xi_{k+1}+C\left(z_{k+1}\right)\|$
$\displaystyle\leq\|C\left(z_{k+1}\right)-C\left(z_{k}\right)\|+\|\xi_{k+1}+C\left(z_{k}\right)\|\leq\frac{\nu_{15}}{k},$

where $\nu_{15}:=\nu_{13}+\nu_{14}>0$. Since $(z_{k})_{k\geq 0}$ is bounded,
we deduce from here that for every $k\geq K_{5}(\eta)$

$0\leq\langle
z_{k+1}-z_{*},\xi_{k+1}+C\left(z_{k+1}\right)\rangle\leq\left\lVert
z_{k+1}-z_{*}\right\rVert\|\xi_{k+1}+C\left(z_{k+1}\right)\|\leq\frac{\nu_{12}\nu_{15}}{k}.$

In conclusion,

$\displaystyle\left\lVert
z_{k}-z_{k-1}\right\rVert=\mathcal{O}\left(\dfrac{1}{k}\right),\,\quad\left\lVert\xi_{k}+C\left(z_{k-1}\right)\right\rVert=\mathcal{O}\left(\dfrac{1}{k}\right)$
$\displaystyle\left\lVert\xi_{k}+C\left(z_{k}\right)\right\rVert=\mathcal{O}\left(\dfrac{1}{k}\right),\,\quad\left\langle
z_{k}-z_{*},\xi_{k}+C\left(z_{k}\right)\right\rangle=\mathcal{O}\left(\dfrac{1}{k}\right)$

as $k\rightarrow+\infty$.

In the remainder of the proof we will show that the sequence
$(\mathcal{E}_{\eta,k})_{k\geq 1}$ is convergent and that it has the same
limit as $(\mathcal{F}_{\eta,k})_{k\geq 1}$. On the one hand, the Cauchy-
Schwarz inequality yields

$\displaystyle 0$
$\displaystyle\leq\lim_{k\rightarrow+\infty}k^{2}\big{|}\langle
z_{k}-z_{k-1},C\left(z_{k}\right)-C\left(z_{k-1}\right)\rangle\big{|}\leq\nu_{11}\lim_{k\rightarrow+\infty}k\big{\|}C\left(z_{k}\right)-C\left(z_{k-1}\right)\big{\|}=0,$

therefore

$\displaystyle 0$ $\displaystyle\leq\lim_{k\rightarrow+\infty}k^{2}\langle
z_{k}-z_{k-1},C\left(z_{k}\right)-C\left(z_{k-1}\right)\rangle=0.$

On the other hand,

$\displaystyle 0\leq\lim_{k\rightarrow+\infty}\sqrt{k}\left\lVert
C\left(z_{k}\right)-C\left(z_{k-1}\right)\right\rVert^{2}$
$\displaystyle\leq\lim_{k\rightarrow+\infty}k\sqrt{k}\left\lVert
C\left(z_{k}\right)-C\left(z_{k-1}\right)\right\rVert^{2}$
$\displaystyle\leq\lim_{k\rightarrow+\infty}k^{2}\left\lVert
C\left(z_{k}\right)-C\left(z_{k-1}\right)\right\rVert^{2}=0,$

which, by using the definitions of the two discrete energy functions, allow us
to conclude that

$\lim_{k\rightarrow+\infty}\mathcal{E}_{\eta,k}=\lim_{k\rightarrow+\infty}\mathcal{F}_{\eta,k}\in\mathbb{R}.$

∎

######  Remark 2.8.

The discrete energy function employed in the convergence analysis of the _Fast
Krasnosel’skiĭ-Mann algorithm_ (fKM), as introduced in [15] (also referenced
in [13]), and forming the basis of the iterative scheme (1.2), exhibits a
nonnegative and nonincreasing nature. In the current context, the introduction
of additional structural elements inherent in the sum of two operators results
in a discrete energy function that demonstrates a perturbed decreasing
property, as observed in (2.21). However, this perturbation does not impede
the convergence of the sequence $\left(\mathcal{F}_{\eta,k}\right)_{k\geq 1}$.

Next we prove the weak convergence of the generated sequence of the iterates
and derive improved convergence rates.

######  Theorem 2.9.

Let $z_{*}\in{\cal Z}$, $\left(z_{k}\right)_{k\geq 0}$ be the sequence
generated by Algorithm 2.1, and $\left(\xi_{k}\right)_{k\geq 1}$ the sequence
generated by the iterative scheme (2.2). Then the following statements are
true:

  1. $\rm{(i)}$

the sequence $\left(z_{k}\right)_{k\geq 0}$ converges weakly to a solution of
(1.1);

  2. $\rm{(ii)}$

it holds

$\displaystyle\left\lVert
z_{k}-z_{k-1}\right\rVert=o\left(\dfrac{1}{k}\right),\,\quad\left\langle
z_{k}-z_{*},\xi_{k}+C\left(z_{k}\right)\right\rangle=o\left(\dfrac{1}{k}\right),\,\quad\left\lVert\xi_{k}+C\left(z_{k}\right)\right\rVert=o\left(\dfrac{1}{k}\right)\quad\mbox{as}\
k\rightarrow+\infty.$

Since, as seen in 2.2, $\xi_{k}\in M(z_{k})$ for every $k\geq 1$, it yields

${\rm
dist}(0,M(z_{k})+C(z_{k}))=o\left(\dfrac{1}{k}\right)\quad\mbox{and}\quad\left\lVert
z_{k}-J_{\gamma M}\big{(}z_{k}-\gamma
C\left(z_{k}\right)\big{)}\right\rVert=o\left(\dfrac{1}{k}\right)\quad\mbox{as}\
k\rightarrow+\infty.$

###### Proof.

We fix $0<\varepsilon<\frac{3(\alpha-2)}{4(\alpha-1)}<1$ such that
$0<\gamma<\frac{2}{2-\varepsilon}\beta$, consider the parameters
$\underline{\eta}(\alpha)$ and $\overline{\eta}(\alpha)$ provided by Lemma 2.6
(ii) and choose
$\eta\in\left(\underline{\eta}(\alpha),\overline{\eta}(\alpha)\right)$.

(i) 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}+\gamma(\xi_{k}+C\left(z_{k-1}\right))\right\rangle,$
(2.22) $\displaystyle q_{k}$ $\displaystyle:=\dfrac{1}{2}\left\lVert
z_{k}-z_{*}\right\rVert^{2}+\gamma\displaystyle\sum\limits_{i=1}^{k}\left\langle
z_{i}-z_{*},\xi_{i}+C(z_{i-1})\right\rangle,$ (2.23)

and notice that

$\displaystyle q_{k}-q_{k-1}$ $\displaystyle=\left\langle
z_{k}-z_{*},z_{k}-z_{k-1}\right\rangle-\dfrac{1}{2}\left\lVert
z_{k}-z_{k-1}\right\rVert^{2}+\gamma\left\langle
z_{k}-z_{*},\xi_{k}+C\left(z_{k-1}\right)\right\rangle,$

and thus

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

Invoking (2.6), we can rewrite the discrete energy function for every $k\geq
1$ as

$\displaystyle\mathcal{E}_{\eta,k}=$ $\displaystyle\ 4\eta
p_{k}+2\eta\gamma\alpha\langle
z_{k}-z_{*},\xi_{k}+C\left(z_{k-1}\right)\rangle+\dfrac{1}{2}k^{2}\left\lVert
2\left(z_{k}-z_{k-1}\right)+\frac{5\alpha-2}{4(\alpha-1)}\gamma(\xi_{k}+C\left(z_{k-1}\right))\right\rVert^{2}$
$\displaystyle+\frac{1}{2}\gamma^{2}\left(\frac{3(\alpha-2)}{4(\alpha-1)}k+\alpha\right)\left(\frac{5\alpha-2}{4(\alpha-1)}k+\alpha\right)\left\lVert\xi_{k}+C\left(z_{k-1}\right)\right\rVert^{2}.$
(2.24)

From here, we easily see that for every
$0\leq\underline{\eta}(\alpha)<\eta_{1}<\eta_{2}<\overline{\eta}(\alpha)$ and
every $k\geq 1$ it holds

$\displaystyle\mathcal{E}_{\eta_{2},k}-\mathcal{E}_{\eta_{1},k}=$
$\displaystyle
4\left(\eta_{2}-\eta_{1}\right)\left(p_{k}+\frac{1}{2}\alpha\gamma\langle
z_{k}-z_{*},\xi_{k}+C\left(z_{k-1}\right)\rangle\right).$ (2.25)

Since the limit
$\lim_{k\to+\infty}\left(\mathcal{E}_{\eta_{2},k}-\mathcal{E}_{\eta_{1},k}\right)\in\mathbb{R}$
exists and

$\displaystyle\lim_{k\rightarrow+\infty}\langle
z_{k}-z_{*},\xi_{k}+C\left(z_{k-1}\right)\rangle=\lim_{k\rightarrow+\infty}\left\lVert\xi_{k}+C\left(z_{k-1}\right)\right\rVert=0,$
(2.26)

according to (2.25)

$\lim\limits_{k\to+\infty}p_{k}\in\mathbb{R}\textrm{ exists}.$ (2.27)

Moreover, since for every $k\geq 1$

$\displaystyle\displaystyle\sum\limits_{i=1}^{k}\big{|}\langle
z_{i}-z_{*},C(z_{i-1})-C(z_{i})\rangle\big{|}$
$\displaystyle\leq\displaystyle\sum\limits_{i=1}^{k}\left\lVert
z_{i}-z_{*}\right\rVert\left\lVert C(z_{i-1})-C(z_{i})\right\rVert$
$\displaystyle\leq\frac{1}{2}\displaystyle\sum\limits_{i=1}^{k}\frac{1}{i^{2}}\left\lVert
z_{i}-z_{*}\right\rVert^{2}+\frac{1}{2}\displaystyle\sum\limits_{i=1}^{k}i^{2}\left\lVert
C(z_{i})-C(z_{i-1})\right\rVert^{2}$
$\displaystyle\leq\frac{1}{2}\nu_{12}^{2}\displaystyle\sum\limits_{i=1}^{k}\frac{1}{i^{2}}+\frac{1}{2}\displaystyle\sum\limits_{i=1}^{k}i^{2}\left\lVert
C(z_{i})-C(z_{i-1})\right\rVert^{2}$
$\displaystyle\leq\frac{1}{2}\nu_{12}^{2}\displaystyle\sum\limits_{i=1}^{+\infty}\frac{1}{i^{2}}+\frac{1}{2}\displaystyle\sum\limits_{i=1}^{+\infty}i^{2}\left\lVert
C(z_{i})-C(z_{i-1})\right\rVert^{2}<+\infty,$

the series $\sum_{k\geq 2}\langle
z_{k}-z_{*},C\left(z_{k-1}\right)-C\left(z_{k}\right)\rangle$ is absolutely
convergent, thus convergent. It follows from here that the limit

$\displaystyle\lim_{k\rightarrow+\infty}\displaystyle\sum\limits_{i=1}^{k}\langle
z_{i}-z_{*},\xi_{i}+C(z_{i-1})\rangle=\\!\\!\lim_{k\rightarrow+\infty}\displaystyle\sum\limits_{i=1}^{k}\langle
z_{i}-z_{*},\xi_{i}+C(z_{i})\rangle+\\!\\!\lim_{k\rightarrow+\infty}\\!\\!\displaystyle\sum\limits_{i=1}^{k}\langle
z_{i}-z_{*},C(z_{i-1})-C(z_{i})\rangle\in\mathbb{R}$

exists. Since, in addition,

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

we obtain

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

We also have that $\left(q_{k}\right)_{k\geq 1}$ is bounded due to the
boundedness of $\left(z_{k}\right)_{k\geq 0}$ and the fact that

$\lim_{k\rightarrow+\infty}\sum_{i=1}^{k}\left\langle
z_{i}-z_{*},\xi_{i}+C(z_{i-1})\right\rangle\in\mathbb{R},$

which, according to A.3, allows us to conclude 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}\left\langle
z_{i}-z_{*},\xi_{i}+C(z_{i-1})\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, since
$z_{*}\in{\cal Z}$ was arbitrarily chosen, the hypothesis $\rm{(i)}$ in
Opial’s Lemma (see A.4) 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 2.7 we have

$\xi_{k_{n}}+C(z_{k_{n}})\to 0\textrm{ as }n\to+\infty,\textrm{where
}\xi_{k_{n}}\in M\left(z_{k_{n}}\right)\quad\forall n\geq 0.$

Since the sum $M+C$ is maximally monotone, it is sequentially closed in
$\mathcal{H}^{\textrm{weak}}\times\mathcal{H}^{\textrm{strong}}$. This gives
that $0\in M(\overline{z})+C(\overline{z})$, thus $\widebar{z}\in\cal Z$, and
shows that hypothesis $\rm{(ii)}$ of Opial’s Lemma is also fulfilled. This
completes the proof of the weak convergence of the sequence $(z_{k})_{k\geq
0}$ to a zero of the operator $M+C$.

(ii) According to 2.7 we have that

$\lim\limits_{k\to+\infty}k\left\lVert\xi_{k}+C\left(z_{k-1}\right)\right\rVert^{2}=0\quad\textnormal{and}\quad\lim\limits_{k\to+\infty}\left\lVert\xi_{k}+C\left(z_{k-1}\right)\right\rVert^{2}=0,$

and the sequence $(\mathcal{E}_{\eta,k})_{k\geq 1}$ is convergent. Taking into
account (2), by using (2.26) and the fact that the limit
$\lim_{k\to+\infty}p_{k}\in\mathbb{R}$ exists, it follows that for the
sequence

$g_{k}:=\dfrac{k^{2}}{2}\left(\left\lVert
2\left(z_{k}-z_{k-1}\right)+\frac{5\alpha-2}{4(\alpha-1)}\gamma(\xi_{k}+C\left(z_{k-1}\right))\right\rVert^{2}+\frac{3(\alpha-2)(5\alpha-2)}{16(\alpha-1)^{2}}\gamma^{2}\left\lVert\xi_{k}+C\left(z_{k-1}\right)\right\rVert^{2}\right),$

the limit

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

Furthermore, 2.7 guarantees that

$\displaystyle\displaystyle\sum\limits_{k\geq 1}\dfrac{1}{k}g_{k}$
$\displaystyle\leq 4\displaystyle\sum\limits_{k\geq 1}k\left\lVert
z_{k}-z_{k-1}\right\rVert^{2}+\frac{(13\alpha-10)(5\alpha-2)}{32(\alpha-1)^{2}}\gamma^{2}\displaystyle\sum\limits_{k\geq
1}k\left\lVert\xi_{k}+C\left(z_{k-1}\right)\right\rVert^{2}<+\infty.$

From here we conclude that $\lim_{k\to+\infty}\frac{1}{k}g_{k}=0$, and so

$\lim\limits_{k\to+\infty}k\left\lVert
2\left(z_{k}-z_{k-1}\right)+\frac{5\alpha-2}{4(\alpha-1)}\gamma(\xi_{k}+C\left(z_{k-1}\right))\right\rVert=\lim\limits_{k\to+\infty}k\left\lVert\xi_{k}+C\left(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$ and, by using the Lipschitz continuity of $C$,
that
$\lim\limits_{k\to+\infty}k\left\lVert\xi_{k}+C\left(z_{k}\right)\right\rVert=0$.
Further, using the Cauchy-Schwarz inequality and the fact that $(z_{k})_{k\geq
0}$ is bounded, we obtain that

$\lim\limits_{k\to+\infty}k\left\langle
z_{k}-z_{*},\xi_{k}+C\left(z_{k}\right)\right\rangle=0.$

Finally, it follows from A.5 that

$\displaystyle 0\leq\lim\limits_{k\to+\infty}k\|z_{k}-J_{\gamma
M}\big{(}z_{k}-\gamma
C\left(z_{k}\right)\big{)}\|\leq\gamma\lim\limits_{k\to+\infty}k{\rm
dist}(0,M(z_{k})+C(z_{k}))\leq\gamma\lim\limits_{k\to+\infty}k\left\lVert\xi_{k}+C\left(z_{k}\right)\right\rVert=0,$

which completes the proof. ∎

##  3 A fast primal-dual full splitting algorithm

The aim of this section is to use the Fast Forward-Backward algorithm to
construct a primal-dual full splitting algorithm for nonsmooth convex
optimization problems with linear constraints that exhibits fast convergence
rates as well as convergence of the iterates.

The problem under consideration reads

$\displaystyle\begin{array}[]{rl}\min\limits_{x\in\mathcal{X}}&f\left(x\right)+h\left(x\right),\\\
\textrm{subject to}&Ax=b,\end{array}$ (3.3)

where $\mathcal{X}$ and $\mathcal{Y}$ are real Hilbert spaces,
$f\colon\mathcal{X}\rightarrow\mathbb{R}\cup\left\\{+\infty\right\\}$ is a
proper, lower semicontinuous, and convex function,
$h\colon\mathcal{X}\rightarrow\mathbb{R}$ convex differentiable function such
that $\nabla h$ is $\frac{1}{\beta}$-Lipschitz continuous with $\beta>0$, and
$A\colon\mathcal{X}\rightarrow\mathcal{Y}$ is a linear continuous operator.
Consider the saddle point problem associated to problem (3.3)

$\min_{x\in\mathcal{X}}\max_{\lambda\in\mathcal{Y}}\mathcal{L}\left(x,\lambda\right),$

where $\mathcal{L}\colon\mathcal{X}\times\mathcal{Y}\to\mathbb{R}$ denotes the
associated _Lagrangian function_

$\mathcal{L}\left(x,\lambda\right):=f\left(x\right)+h\left(x\right)+\left\langle\lambda,Ax-b\right\rangle.$

A pair $\left(x_{*},\lambda_{*}\right)\in\mathcal{X}\times\mathcal{Y}$ is said
to be a _saddle point_ of the Lagrangian function $\mathcal{L}$ if for every
$\left(x,\lambda\right)\in\mathcal{X}\times\mathcal{Y}$

$\mathcal{L}\left(x_{*},\lambda\right)\leq\mathcal{L}\left(x_{*},\lambda_{*}\right)\leq\mathcal{L}\left(x,\lambda_{*}\right).$

If $\left(x_{*},\lambda_{*}\right)\in\mathcal{X}\times\mathcal{Y}$ is a saddle
point of $\mathcal{L}$, then $x_{*}\in\mathcal{X}$ is an optimal solution of
(3.3) and $\lambda_{*}\in\mathcal{Y}$ is an optimal solution of its Lagrange
dual problem. If $x_{*}\in\mathcal{X}$ is an optimal solution of (3.3) and a
suitable constraint qualification is fulfilled (see, for instance, [12, 10]),
then there exists an optimal solution $\lambda_{*}\in\mathcal{Y}$ of the
Lagrange dual problem of (3.3) such that
$\left(x_{*},\lambda_{*}\right)\in\mathcal{X}\times\mathcal{Y}$ is a saddle
point of $\mathcal{L}$. The set of saddle points of $\mathcal{L}$, called the
_set of primal-dual optimal solutions_ of (3.3), will be denoted by
$\mathcal{S}$.

The system of primal-dual optimality conditions for (3.3) reads

$\left(x_{*},\lambda_{*}\right)\in\mathcal{S}\Leftrightarrow\begin{cases}0\in\partial_{x}\mathcal{L}\left(x_{*},\lambda_{*}\right)\\\
0=\nabla_{\lambda}\mathcal{L}\left(x_{*},\lambda_{*}\right)\end{cases}\Leftrightarrow\begin{cases}0\in\partial
f\left(x_{*}\right)+\nabla h\left(x_{*}\right)+A^{*}\lambda_{*}\\\
0=Ax_{*}-b\end{cases},$ (3.4)

where $A^{*}:\mathcal{Y}\rightarrow\mathcal{X}$ denotes the adjoint operator
of $A$.

For $\boldsymbol{\mathcal{H}}=\mathcal{X}\bigoplus\mathcal{Y}$, the problem of
finding a primal-dual solution of (3.3) can be equivalently written as the
monotone inclusion

$\textrm{find}\quad\boldsymbol{z}\in\boldsymbol{\mathcal{H}}\quad\textrm{such}\quad\textrm{that}\quad\boldsymbol{0}\in\boldsymbol{P}(\boldsymbol{z})+\boldsymbol{Q}(\boldsymbol{z}),$
(3.5)

where

$\ \left\\{\begin{aligned}
&\boldsymbol{P}\colon\boldsymbol{\mathcal{H}}\rightarrow
2^{\boldsymbol{\mathcal{H}}}\colon\left(x,\lambda\right)\mapsto\big{(}\partial
f(x)+A^{*}\lambda\big{)}\times\big{(}-Ax+b\big{)},\\\
&\boldsymbol{Q}\colon\boldsymbol{\mathcal{H}}\rightarrow\boldsymbol{\mathcal{H}}\colon\left(x,\lambda\right)\mapsto(\nabla
h(x),0).\end{aligned}\right.$ (3.6)

The operator $\boldsymbol{P}$ as the sum of the maximally monotone operators
$\left(x,\lambda\right)\mapsto\partial f(x)\times\left\\{b\right\\}$ and
$\left(x,\lambda\right)\mapsto(A^{*}\lambda,-Ax)$ is also a maximally monotone
operator. In view of the Baillon-Haddad theorem, $\nabla h$ is
$\beta$-cocoercive, which means that $\boldsymbol{Q}$ is also
$\beta$-cocoercive.

Inspired by [46], we define the self-adjoint operator

$\displaystyle\qquad\boldsymbol{N}\colon\boldsymbol{\mathcal{H}}\rightarrow\boldsymbol{\mathcal{H}},\quad(x,\lambda)\mapsto\left(\frac{1}{\tau}x-A^{*}\lambda,-Ax+\frac{1}{\sigma}\lambda\right),$
(3.7)

which is $\rho$-strongly positive with modulus

$\rho:=\min\left\\{\frac{1}{\tau},\frac{1}{\sigma}\right\\}\left(1-\sqrt{\tau\sigma\|A\|^{2}}\right).$

Therefore, its inverse $\boldsymbol{N}^{-1}$ exists and
$\|\boldsymbol{N}^{-1}\|\leq\frac{1}{\rho}$. This means that
$\boldsymbol{N}^{-1}\boldsymbol{P}$ is a maximally monotone operator and
$\boldsymbol{N}^{-1}\boldsymbol{Q}$ is a $\beta\rho$-cocoercive operator. The
algorithm below is the Fast Forward-Backward algorithm applied to the problem
of finding a zero of
$\boldsymbol{N}^{-1}\boldsymbol{P}+\boldsymbol{N}^{-1}\boldsymbol{Q}$.

######  Algorithm 3.1.

Let $\alpha>2$, $\tau,\sigma>0$ such that
$1<\min\left\\{\frac{1}{\tau},\frac{1}{\sigma}\right\\}\left(1-\sqrt{\tau\sigma\|A\|^{2}}\right)\frac{8(\alpha-1)}{(5\alpha-2)}\beta,$
$x_{0},v_{0}\in\mathcal{X}$, $\lambda_{0},\eta_{0}\in\mathcal{Y}$, and
$x_{1}:=\textnormal{prox}_{\tau f}\left(v_{0}-\tau A^{*}\eta_{0}-\tau\nabla
h\left(x_{0}\right)\right)$ and
$\lambda_{1}:=\eta_{0}+\sigma\left(Ax_{1}-b\right)+\sigma
A\left(x_{1}-v_{0}\right)$. We set $(\forall k\geq
1)\quad\begin{dcases}v_{k}&:=x_{k}+\left(1-\frac{\alpha}{k+\alpha}\right)\left(x_{k}-x_{k-1}\right)+\left(1-\frac{\alpha}{2(k+\alpha)}\right)\left(v_{k-1}-x_{k}\right);\\\
\eta_{k}&:=\lambda_{k}+\left(1-\frac{\alpha}{k+\alpha}\right)(\lambda_{k}-\lambda_{k-1})+\left(1-\frac{\alpha}{2(k+\alpha)}\right)\left(\eta_{k-1}-\lambda_{k}\right);\\\
x_{k+1}&:=\textnormal{prox}_{\tau f}\left(v_{k}-\tau A^{*}\eta_{k}-\tau\nabla
h\left(x_{k}\right)\right);\\\
\lambda_{k+1}&:=\eta_{k}+\sigma\left(Ax_{k+1}-b\right)+\sigma
A\left(x_{k+1}-v_{k}\right).\end{dcases}$

Based on 2.9, we obtain the following convergence and convergence rate
results.

######  Theorem 3.2.

Let $(x_{*},\lambda_{*})\in{\cal S}$, and
$\left(x_{k},\lambda_{k}\right)_{k\geq 0}$ be the sequence generated by
Algorithm 3.1. Then the following statements are true:

  1. $\rm{(i)}$

the sequence $\left(x_{k},\lambda_{k}\right)_{k\geq 0}$ converges weakly to a
primal-dual solution of (3.3);

  2. $\rm{(ii)}$

we have

$\displaystyle\left\lVert
x_{k}-x_{k-1}\right\rVert=o\left(\dfrac{1}{k}\right)$
$\displaystyle\qquad\textrm{ and
}\qquad\left\lVert\lambda_{k}-\lambda_{k-1}\right\rVert=o\left(\dfrac{1}{k}\right)$
$\displaystyle\left\lVert w_{k}+\nabla
h\left(x_{k}\right)\right\rVert=o\left(\dfrac{1}{k}\right)$
$\displaystyle\qquad\textrm{ and }\qquad\left\lVert
Ax_{k}-b\right\rVert=o\left(\dfrac{1}{k}\right)$
$\displaystyle\mathcal{L}\left(x_{k},\lambda_{*}\right)-\mathcal{L}\left(x_{*},\lambda_{k}\right)=o\left(\dfrac{1}{k}\right)$
$\displaystyle\qquad\textrm{ and
}\qquad\left\lvert\left(f+h\right)\left(x_{k}\right)-\left(f+h\right)\left(x_{*}\right)\right\rvert=o\left(\dfrac{1}{k}\right)$

as $k\to+\infty$, where, for every $k\geq 1$

$w_{k+1}:=\frac{1}{\tau}\left(v_{k}-x_{k+1}\right)+A^{*}\left(\lambda_{k+1}-\eta_{k}\right)-\nabla
h\left(x_{k}\right)\in\partial f(x_{k+1})+A^{*}\lambda_{k+1}.$

###### Proof.

We apply 2.1 with step size $\gamma=1$ to the problem

$\textrm{find}\quad\boldsymbol{z}\in\boldsymbol{\mathcal{H}}\quad\textrm{such}\quad\textrm{that}\quad\boldsymbol{0}\in\boldsymbol{N}^{-1}\boldsymbol{P}(\boldsymbol{z})+\boldsymbol{N}^{-1}\boldsymbol{Q}(\boldsymbol{z}).$
(3.8)

For the initial points
$\boldsymbol{z}_{0},\boldsymbol{y}_{0}\in\boldsymbol{\mathcal{H}}$ and
$\boldsymbol{z}_{1}:=J_{\boldsymbol{N}^{-1}\boldsymbol{P}}\Big{(}\boldsymbol{y}_{0}-\boldsymbol{N}^{-1}\boldsymbol{Q}(\boldsymbol{z}_{0})\Big{)}$,
this gives rise to the following iterative scheme

$(\forall k\geq 1)\quad\left\\{\begin{aligned}
\boldsymbol{y}_{k}:=&\boldsymbol{z}_{k}+\left(1-\dfrac{\alpha}{k+\alpha}\right)\left(\boldsymbol{z}_{k}-\boldsymbol{z}_{k-1}\right)+\left(1-\frac{\alpha}{2(k+\alpha)}\right)\left(\boldsymbol{y}_{k-1}-\boldsymbol{z}_{k}\right);\\\
\boldsymbol{z}_{k+1}:=&J_{\boldsymbol{N}^{-1}\boldsymbol{P}}\Big{(}\boldsymbol{y}_{k}-\boldsymbol{N}^{-1}\boldsymbol{Q}(\boldsymbol{z}_{k})\Big{)}.\\\
\end{aligned}\right.$ (3.9)

The second equation (3.9) can be equivalently written for every $k\geq 1$ as

$\boldsymbol{z}_{k+1}+\boldsymbol{N}^{-1}\boldsymbol{P}(\boldsymbol{z}_{k+1})\ni\boldsymbol{y}_{k}-\boldsymbol{N}^{-1}\boldsymbol{Q}(\boldsymbol{z}_{k})$

and further as

$\boldsymbol{N}\boldsymbol{z}_{k+1}+\boldsymbol{P}(\boldsymbol{z}_{k+1})\ni\boldsymbol{N}\boldsymbol{y}_{k}-\boldsymbol{Q}(\boldsymbol{z}_{k}).$
(3.10)

By denoting $\boldsymbol{z}_{k}:=(x_{k},\lambda_{k})$ and
$\boldsymbol{y}_{k}:=(v_{k},\eta_{k})$ for every $k\geq 0$, one can see that
the first equation in (3.9) corresponds to the first two equations in the
iterative scheme of Algorithm 3.1. On the other hand, by making use of the
definitions of $\boldsymbol{N}$, $\boldsymbol{P}$ and $\boldsymbol{Q}$, (3.10)
is nothing else than

$\ \left\\{\begin{aligned} &\frac{1}{\tau}x_{k+1}+\partial
f(x_{k+1})\ni\frac{1}{\tau}v_{k}-A^{*}\eta_{k}-\nabla h\left(x_{k}\right),\\\
&\frac{1}{\sigma}\lambda_{k+1}+b-2Ax_{k+1}=-Av_{k}+\frac{1}{\sigma}\eta_{k}\end{aligned}\right.$

or, equivalently,

$\left\\{\begin{aligned} &x_{k+1}=\textnormal{prox}_{\tau f}\left(v_{k}-\tau
A^{*}\eta_{k}-\tau\nabla h\left(x_{k}\right)\right),\\\
&\lambda_{k+1}=\eta_{k}+\sigma\left(Ax_{k+1}-b\right)+\sigma
A\left(x_{k+1}-v_{k}\right),\end{aligned}\right.$

which corresponds to the last equations in the iterative scheme of Algorithm
3.1. The initial condition
$\boldsymbol{\xi}_{1}\in\boldsymbol{N}^{-1}\boldsymbol{P}(\boldsymbol{z}_{1})$
is also equivalent the initialization made for $x_{1}$ and $\lambda_{1}$. This
proves that Algorithm 3.1 is nothing else than Algorithm 2.1 applied to a
particular monotone inclusion problem, which means that it inherits its
convergence properties.

For the formulation of the convergence rates, the sequence
$(\boldsymbol{\xi}_{k})_{k\geq 1}$ introduced in Propostion 2.2 plays a
crucial role. In the context of the iterative scheme (3.9), this is defined
for every $k\geq 1$ as

$\boldsymbol{\xi}_{k}:=\boldsymbol{y}_{k-1}-\boldsymbol{N}^{-1}\boldsymbol{Q}(\boldsymbol{z}_{k-1})-\boldsymbol{z}_{k}$

or, equivalently,

$\displaystyle\boldsymbol{N}\boldsymbol{\xi}_{k}=\boldsymbol{N}\boldsymbol{y}_{k-1}-\boldsymbol{Q}(\boldsymbol{z}_{k-1})-\boldsymbol{N}\boldsymbol{z}_{k}.$
(3.11)

By denoting $\boldsymbol{N}\boldsymbol{\xi}_{k}:=(w_{k},\zeta_{k})$, the
formula (3.11) can be equivalently written as

$\ \left\\{\begin{aligned} w_{k}&=\frac{1}{\tau}v_{k-1}-A^{*}\eta_{k-1}-\nabla
h\left(x_{k-1}\right)-\frac{1}{\tau}x_{k}+A^{*}\lambda_{k},\\\
\zeta_{k}&=-Av_{k-1}+\frac{1}{\sigma}\eta_{k-1}+Ax_{k}-\frac{1}{\sigma}\lambda_{k}.\end{aligned}\right.$
(3.12)

Furthermore, according to (2.3), for every $k\geq 1$ it holds
$\boldsymbol{N}\boldsymbol{\xi}_{k}\in\boldsymbol{P}\boldsymbol{z}_{k}$ or,
equivalently,

$\ \left\\{\begin{aligned} w_{k}&\in\partial f(x_{k})+A^{*}\lambda_{k},\\\
\zeta_{k}&=-Ax_{k}+b.\end{aligned}\right.$ (3.13)

(i) 2.9 (i) guarantees that the sequence
$\left(\boldsymbol{z}_{k}\right)_{k\geq 0}$ generated by the iterative scheme
(3.9) converges weakly to an element of
$\textnormal{zer}\left(\boldsymbol{N}^{-1}\boldsymbol{P}+\boldsymbol{N}^{-1}\boldsymbol{Q}\right)=\textnormal{zer}\left(\boldsymbol{P}+\boldsymbol{Q}\right)$.
In other words, the sequence $\left(x_{k},\lambda_{k}\right)_{k\geq 0}$
generated by Algorithm 3.1 converges weakly to a primal-dual optimal solution
of (3.3).

(ii) 2.9 (ii) yields

$\displaystyle\left\lVert\boldsymbol{z}_{k}-\boldsymbol{z}_{k-1}\right\rVert=o\left(\dfrac{1}{k}\right),\,\quad\left\langle\boldsymbol{z}_{k}-\boldsymbol{z}_{*},\boldsymbol{\xi}_{k}+\boldsymbol{N}^{-1}\boldsymbol{Q}(\boldsymbol{z}_{k})\right\rangle=o\left(\dfrac{1}{k}\right),\,\quad\left\lVert\boldsymbol{\xi}_{k}+\boldsymbol{N}^{-1}\boldsymbol{Q}(\boldsymbol{z}_{k})\right\rVert=o\left(\dfrac{1}{k}\right)$

as $k\rightarrow+\infty$. Since

$\left\lVert
x_{k}-x_{k-1}\right\rVert+\left\lVert\lambda_{k}-\lambda_{k-1}\right\rVert\leq\sqrt{2}\sqrt{\left\lVert
x_{k}-x_{k-1}\right\rVert^{2}+\left\lVert\lambda_{k}-\lambda_{k-1}\right\rVert^{2}}=\sqrt{2}\left\lVert\boldsymbol{z}_{k}-\boldsymbol{z}_{k-1}\right\rVert\
\forall k\geq 1,$

we obtain

$\displaystyle\left\lVert
x_{k}-x_{k-1}\right\rVert=o\left(\dfrac{1}{k}\right)\quad\mbox{and}\quad\left\lVert\lambda_{k}-\lambda_{k-1}\right\rVert=o\left(\dfrac{1}{k}\right)\
\mbox{as}\ k\rightarrow+\infty.$

Since

$\displaystyle 0$
$\displaystyle\leq\lim_{k\rightarrow+\infty}k\left\lVert\boldsymbol{N}\boldsymbol{\xi}_{k}+\boldsymbol{Q}(\boldsymbol{z}_{k})\right\rVert\leq\|\boldsymbol{N}\|\lim_{k\rightarrow+\infty}k\left\lVert\boldsymbol{\xi}_{k}+\boldsymbol{N}^{-1}\boldsymbol{Q}(\boldsymbol{z}_{k})\right\rVert=0,$

it yields

$\displaystyle\left\lVert\boldsymbol{N}\boldsymbol{\xi}_{k}+\boldsymbol{Q}(\boldsymbol{z}_{k})\right\rVert=o\left(\dfrac{1}{k}\right)\
\mbox{as}\ k\rightarrow+\infty,$

and further, by the boundedness of $\left(\boldsymbol{z}_{k}\right)_{k\geq
0}$,

$\displaystyle\left\langle\boldsymbol{z}_{k}-\boldsymbol{z}_{*},\boldsymbol{N}\boldsymbol{\xi}_{k}+\boldsymbol{Q}(\boldsymbol{z}_{k})\right\rangle=o\left(\dfrac{1}{k}\right)\
\mbox{as}\ k\rightarrow+\infty.$

For $\boldsymbol{z}_{k}=(x_{k},\lambda_{k})$ and
$\boldsymbol{N}\boldsymbol{\xi}_{k}=(w_{k},b-Ax_{k})$, where
$w_{k}=\frac{1}{\tau}v_{k-1}-A^{*}\eta_{k-1}-\nabla
h\left(x_{k-1}\right)-\frac{1}{\tau}x_{k}+A^{*}\lambda_{k}$, this yields

$\displaystyle\left\lVert\boldsymbol{N}\boldsymbol{\xi}_{k}+\boldsymbol{Q}(\boldsymbol{z}_{k})\right\rVert=\left\lVert\begin{pmatrix}w_{k}+\nabla
h\left(x_{k}\right),b-Ax_{k}\end{pmatrix}\right\rVert=o\left(\dfrac{1}{k}\right)\
\mbox{as}\ k\rightarrow+\infty$ (3.14)

and

$\displaystyle\left\langle\begin{pmatrix}x_{k}-x_{*},\lambda_{k}-\lambda_{*}\end{pmatrix},\begin{pmatrix}w_{k}+\nabla
h\left(x_{k}\right),b-Ax_{k}\end{pmatrix}\right\rangle=o\left(\dfrac{1}{k}\right)\
\mbox{as}\ k\rightarrow+\infty,$ (3.15)

respectively. By arguing as above, we obtain

$\left\lVert w_{k}+\nabla
h\left(x_{k}\right)\right\rVert=o\left(\dfrac{1}{k}\right)\quad\mbox{and}\quad\left\lVert
Ax_{k}-b\right\rVert=o\left(\dfrac{1}{k}\right)\ \mbox{as}\
k\rightarrow+\infty.$ (3.16)

Recall that from (3.13) we have $w_{k}\in\partial
f\left(x_{k}\right)+A^{*}\lambda_{k}$. Using the convexity of $f$ and $h$, for
every $k\geq 1$ it yields

$\displaystyle\langle w_{k}-A^{*}\lambda_{k},x_{k}-x_{*}\rangle\geq
f\left(x_{k}\right)-f(x_{*}),$ $\displaystyle\langle\nabla
h\left(x_{k}\right),x_{k}-x_{*}\rangle\geq h\left(x_{k}\right)-h(x_{*}),$

and, by adding the two inequalities,

$\displaystyle\left\langle\boldsymbol{z}_{k}-\boldsymbol{z}_{*},\boldsymbol{N}\boldsymbol{\xi}_{k}+\boldsymbol{Q}(\boldsymbol{z}_{k})\right\rangle$
$\displaystyle=\ $ $\displaystyle\langle w_{k}+\nabla
h\left(x_{k}\right),x_{k}-x_{*}\rangle+\langle
b-Ax_{k},\lambda_{k}-\lambda_{*}\rangle$ $\displaystyle=\ $
$\displaystyle\langle w_{k}-A^{*}\lambda_{k},x_{k}-x_{*}\rangle+\langle\nabla
h\left(x_{k}\right),x_{k}-x_{*}\rangle+\langle
b-Ax_{k},\lambda_{k}-\lambda_{*}\rangle+\langle
A^{*}\lambda_{k},x_{k}-x_{*}\rangle$ $\displaystyle\geq\ $ $\displaystyle
f\left(x_{k}\right)-f(x_{*})+h\left(x_{k}\right)-h(x_{*})+\langle\lambda_{*},Ax_{k}-b\rangle$
$\displaystyle=\ $
$\displaystyle\mathcal{L}\left(x_{k},\lambda_{*}\right)-\mathcal{L}\left(x_{*},\lambda_{k}\right)\geq
0.$ (3.17)

Combining this esitmate with (3.15) yields

$\displaystyle\mathcal{L}\left(x_{k},\lambda_{*}\right)-\mathcal{L}\left(x_{*},\lambda_{k}\right)=o\left(\dfrac{1}{k}\right)\
\mbox{as}\ k\rightarrow+\infty.$

Furthermore, from (3) and the Cauchy-Schwarz inequality, we have for every
$k\geq 1$

$\displaystyle\left\langle\boldsymbol{z}_{k}-\boldsymbol{z}_{*},\boldsymbol{N}\boldsymbol{\xi}_{k}+\boldsymbol{Q}(\boldsymbol{z}_{k})\right\rangle\geq\
$ $\displaystyle
f\left(x_{k}\right)-f(x_{*})+h\left(x_{k}\right)-h(x_{*})+\langle\lambda_{*},Ax_{k}-b\rangle$
$\displaystyle\geq\ $
$\displaystyle(f+h)\left(x_{k}\right)-(f+h)(x_{*})-\left\lVert\lambda_{*}\right\rVert\left\lVert
Ax_{k}-b\right\rVert,$

while on the other hand, since
$-A^{*}\lambda_{*}\in\partial(f+h)\left(x_{*}\right)$ and $Ax_{*}=b$, we
deduce

$\displaystyle(f+h)\left(x_{k}\right)$
$\displaystyle\geq(f+h)\left(x_{*}\right)-\langle
A^{*}\lambda_{*},x_{k}-x_{*}\rangle=(f+h)(x_{*})-\langle\lambda_{*},Ax_{k}-b\rangle$
$\displaystyle\geq(f+h)(x_{*})-\left\lVert\lambda_{*}\right\rVert\left\lVert
Ax_{k}-b\right\rVert.$

Combining these relations, we obtain for every $k\geq 1$

$-\left\lVert\lambda_{*}\right\rVert\left\lVert
Ax_{k}-b\right\rVert\leq(f+h)\left(x_{k}\right)-(f+h)(x_{*})\leq\left\lVert\lambda_{*}\right\rVert\left\lVert
Ax_{k}-b\right\rVert+\left\langle\boldsymbol{z}_{k}-\boldsymbol{z}_{*},\boldsymbol{N}\boldsymbol{\xi}_{k}+\boldsymbol{Q}(\boldsymbol{z}_{k})\right\rangle.$

Multiplying the above relation by $k$, letting $k$ converge to $+\infty$, and
using (3.16), the convergence rate for the objective function value follows. ∎

######  Remark 3.3.

An equivalent formulation for 3.1 can be provided by using instead of (2.1)
the iterative scheme (2.2) when solving (3.8). For initial points
$\boldsymbol{z}_{0},\boldsymbol{z}_{1}\in\boldsymbol{\mathcal{H}}$ and
$\boldsymbol{\xi}_{1}\in M(\boldsymbol{z}_{1})$ and step size $\gamma=1$,
(2.2) reads for every $k\geq 1$

$\ \left\\{\begin{aligned}
&\boldsymbol{z}_{k+1}:=J_{\boldsymbol{N}^{-1}\boldsymbol{P}}\Biggl{(}\boldsymbol{z}_{k}-\boldsymbol{N}^{-1}\boldsymbol{Q}(\boldsymbol{z}_{k})+\left(1-\dfrac{\alpha}{k+\alpha}\right)\left(\boldsymbol{z}_{k}-\boldsymbol{z}_{k-1}\right)+\frac{2k+\alpha}{2(k+\alpha)}\left(\boldsymbol{\xi}_{k}+\boldsymbol{N}^{-1}\boldsymbol{Q}(\boldsymbol{z}_{k-1})\right)\Biggr{)};\\\
&\boldsymbol{\xi}_{k+1}:=\boldsymbol{z}_{k}-\boldsymbol{N}^{-1}\boldsymbol{Q}(\boldsymbol{z}_{k})+\left(1-\dfrac{\alpha}{k+\alpha}\right)(\boldsymbol{z}_{k}-\boldsymbol{z}_{k-1})+\frac{2k+\alpha}{2(k+\alpha)}\left(\boldsymbol{\xi}_{k}+\boldsymbol{N}^{-1}\boldsymbol{Q}(\boldsymbol{z}_{k-1})\right)-\boldsymbol{z}_{k+1},\end{aligned}\right.$

which is equivalent to

$\ \left\\{\begin{aligned}
&\boldsymbol{z}_{k+1}+\boldsymbol{N}^{-1}\boldsymbol{P}(\boldsymbol{z}_{k+1})\ni\boldsymbol{z}_{k}-\boldsymbol{N}^{-1}\boldsymbol{Q}(\boldsymbol{z}_{k})+\left(1-\dfrac{\alpha}{k+\alpha}\right)\left(\boldsymbol{z}_{k}-\boldsymbol{z}_{k-1}\right)\\\
&\qquad\qquad\qquad\qquad\qquad+\frac{2k+\alpha}{2(k+\alpha)}\left(\boldsymbol{\xi}_{k}+\boldsymbol{N}^{-1}\boldsymbol{Q}(\boldsymbol{z}_{k-1})\right);\\\
&\boldsymbol{\xi}_{k+1}=\boldsymbol{z}_{k}-\boldsymbol{N}^{-1}\boldsymbol{Q}(\boldsymbol{z}_{k})+\left(1-\dfrac{\alpha}{k+\alpha}\right)(\boldsymbol{z}_{k}-\boldsymbol{z}_{k-1})+\frac{2k+\alpha}{2(k+\alpha)}\left(\boldsymbol{\xi}_{k}+\boldsymbol{N}^{-1}\boldsymbol{Q}(\boldsymbol{z}_{k-1})\right)-\boldsymbol{z}_{k+1},\\\
\end{aligned}\right.$

and further to

$\ \left\\{\begin{aligned}
&\boldsymbol{N}\boldsymbol{z}_{k+1}+\boldsymbol{P}(\boldsymbol{z}_{k+1})\ni\boldsymbol{N}\left(\boldsymbol{z}_{k}+\big{(}1-\frac{\alpha}{k+\alpha}\big{)}(\boldsymbol{z}_{k}-\boldsymbol{z}_{k-1})+\frac{2k+\alpha}{2(k+\alpha)}\boldsymbol{\xi}_{k}\right)+\frac{2k+\alpha}{2(k+\alpha)}\boldsymbol{Q}(\boldsymbol{z}_{k-1})-\boldsymbol{Q}(\boldsymbol{z}_{k});\\\
&\boldsymbol{N}\boldsymbol{\xi}_{k+1}=\boldsymbol{N}\left(\boldsymbol{z}_{k}-\boldsymbol{z}_{k+1}+\Big{(}1-\frac{\alpha}{k+\alpha}\Big{)}(\boldsymbol{z}_{k}-\boldsymbol{z}_{k-1})+\frac{2k+\alpha}{2(k+\alpha)}\boldsymbol{\xi}_{k}\right)+\frac{2k+\alpha}{2(k+\alpha)}\boldsymbol{Q}(\boldsymbol{z}_{k-1})-\boldsymbol{Q}(\boldsymbol{z}_{k}).\end{aligned}\right.$
(3.18)

According to the definitions of $\boldsymbol{N}$, $\boldsymbol{P}$ and
$\boldsymbol{Q}$ in (LABEL:lef15) and (3.7), and using
$\boldsymbol{z}_{k}=(x_{k},\lambda_{k})$ and
$\boldsymbol{N}\boldsymbol{\xi}_{k}=(w_{k},\zeta_{k})$ in (3.10), we obtain an
equivalent iterative scheme that reads for every $k\geq 1$

$\ \left\\{\begin{aligned} \frac{1}{\tau}x_{k+1}+\partial
f(x_{k+1})&\ni\frac{1}{\tau}\left(x_{k}+\left(1-\frac{\alpha}{k+\alpha}\right)\left(x_{k}-x_{k-1}\right)\right)-A^{*}\left(\lambda_{k}+\left(1-\frac{\alpha}{k+\alpha}\right)\left(\lambda_{k}-\lambda_{k-1}\right)\right)\\\
&\quad+\frac{2k+\alpha}{2(k+\alpha)}w_{k}+\frac{2k+\alpha}{2(k+\alpha)}\nabla
h\left(x_{k-1}\right)-\nabla h\left(x_{k}\right);\\\
\frac{1}{\sigma}\lambda_{k+1}+b-2Ax_{k+1}&=-A\left(x_{k}+\left(1-\frac{\alpha}{k+\alpha}\right)\left(x_{k}-x_{k-1}\right)\right)\\\
&\quad+\frac{1}{\sigma}\left(\lambda_{k}+\left(1-\frac{\alpha}{k+\alpha}\right)\left(\lambda_{k}-\lambda_{k-1}\right)\right)+\frac{2k+\alpha}{2(k+\alpha)}\zeta_{k};\\\
w_{k+1}&=\frac{1}{\tau}\left(x_{k}-x_{k+1}+\left(1-\frac{\alpha}{k+\alpha}\right)\left(x_{k}-x_{k-1}\right)\right)\\\
&\quad-A^{*}\left(\lambda_{k}-\lambda_{k+1}+\left(1-\frac{\alpha}{k+\alpha}\right)\left(\lambda_{k}-\lambda_{k-1}\right)\right)\\\
&\quad+\frac{2k+\alpha}{2(k+\alpha)}w_{k}+\frac{2k+\alpha}{2(k+\alpha)}\nabla
h\left(x_{k-1}\right)-\nabla h\left(x_{k}\right);\\\
\zeta_{k+1}&=-A\left(x_{k}-x_{k+1}+\left(1-\frac{\alpha}{k+\alpha}\right)\left(x_{k}-x_{k-1}\right)\right)\\\
&\quad+\frac{1}{\sigma}\left(\lambda_{k}-\lambda_{k+1}+\left(1-\frac{\alpha}{k+\alpha}\right)\left(\lambda_{k}-\lambda_{k-1}\right)\right)+\frac{2k+\alpha}{2(k+\alpha)}\zeta_{k}.\end{aligned}\right.$
(3.19)

According to (3.13),

$\zeta_{k}=-Ax_{k}+b\quad\forall k\geq 1,$

which means that we can formulate (3.19) by making use of only the first three
sequences. Noticing that the first equation in (3.19) is equivalent to

$\displaystyle x_{k+1}=\textnormal{prox}_{\tau
f}\Bigg{(}x_{k}-\tau\left(\nabla
h\left(x_{k}\right)+A^{*}\lambda_{k}\right)+\left(1-\frac{\alpha}{k+\alpha}\right)\left(x_{k}-x_{k-1}\right)-\tau
A^{*}\left(1-\frac{\alpha}{k+\alpha}\right)\left(\lambda_{k}-\lambda_{k-1}\right)$
$\displaystyle\qquad\qquad\qquad\qquad+\frac{2k+\alpha}{2(k+\alpha)}\tau\left(w_{k}+\nabla
h\left(x_{k-1}\right)\right)\Bigg{)},$

and the second equation in (3.19) is equivalent to

$\displaystyle\lambda_{k+1}=2\sigma Ax_{k+1}-\sigma b-\sigma
A\left(x_{k}+\left(1-\frac{\alpha}{k+\alpha}\right)\left(x_{k}-x_{k-1}\right)\right)-\frac{2k+\alpha}{2(k+\alpha)}\sigma\left(Ax_{k}-b\right)$
$\displaystyle\qquad\quad+\lambda_{k}+\left(1-\frac{\alpha}{k+\alpha}\right)\left(\lambda_{k}-\lambda_{k-1}\right),$

we obtain a further alternative formulation for 3.1 that reads for every
$k\geq 1$

$\ \left\\{\begin{aligned} x_{k+1}:=&\ \textnormal{prox}_{\tau
f}\Bigg{(}x_{k}-\tau\left(\nabla
h\left(x_{k}\right)+A^{*}\lambda_{k}\right)+\left(1-\frac{\alpha}{k+\alpha}\right)\left(x_{k}-x_{k-1}\right)\\\
&\qquad\qquad-\tau
A^{*}\left(1-\frac{\alpha}{k+\alpha}\right)\left(\lambda_{k}-\lambda_{k-1}\right)+\left(1-\frac{\alpha}{2(k+\alpha)}\right)\tau\left(w_{k}+\nabla
h\left(x_{k-1}\right)\right)\Bigg{)};\\\ \lambda_{k+1}:=&\
\lambda_{k}+\sigma\left(Ax_{k+1}-b\right)+\left(1-\frac{\alpha}{k+\alpha}\right)\left(\lambda_{k}-\lambda_{k-1}\right)\\\
&+\sigma
A\left(x_{k+1}-x_{k}-\left(1-\frac{\alpha}{k+\alpha}\right)\left(x_{k}-x_{k-1}\right)\right)-\left(1-\frac{\alpha}{2(k+\alpha)}\right)\sigma\left(Ax_{k}-b\right);\\\
w_{k+1}:=&\frac{1}{\tau}\left(x_{k}-x_{k+1}+\left(1-\frac{\alpha}{k+\alpha}\right)\left(x_{k}-x_{k-1}\right)\right)-A^{*}\left(\lambda_{k}-\lambda_{k+1}+\left(1-\frac{\alpha}{k+\alpha}\right)\left(\lambda_{k}-\lambda_{k-1}\right)\right)\\\
&+\left(1-\frac{\alpha}{2(k+\alpha)}\right)\left(w_{k}+\nabla
h\left(x_{k-1}\right)\right)-\nabla h\left(x_{k}\right).\end{aligned}\right.$

######  Remark 3.4.

Sabach and Teboulle proposed in [41] in finite-dimensional spaces a class of
_faster Lagrangian-based methods_ (FLAG), which, when applied to the convex
optimization problem (3.3), for initial points $x_{1}$ and $\widebar{x}_{1}$
and constants $\tau,r>0$ and $\theta\in(0,1]$, reads

$\ (\forall k\geq 1)\quad\left\\{\begin{aligned}
&\widebar{x}_{k+1}:=\textnormal{prox}_{\tau
f}\left(\widebar{x}_{k}-\tau\left(\nabla
h(\widebar{x}_{k})+A^{*}\lambda_{k}+rA^{*}(A\widebar{x}_{k}-b)\right)-\tau
rkA^{*}(Ax_{k}-b)\right);\\\ &\lambda_{k+1}:=\lambda_{k}+\theta
r\left(A\widebar{x}_{k+1}-b\right);\\\
&x_{k+1}:=\left(1-\frac{1}{k+1}\right)x_{k}+\frac{1}{k+1}\widebar{x}_{k+1}.\end{aligned}\right.$

The authors derived nonergodic/last iterate convergence rates for the function
values and the feasibility violation measure, expressed as

$(f+h)\left(x_{k}\right)-(f+h)(x_{*})=\mathcal{O}\left(\frac{1}{k}\right)\quad\textrm{
and }\quad\left\lVert
A\left(x_{k}\right)-b\right\rVert=\mathcal{O}\left(\frac{1}{k}\right)\
\mbox{as}\ k\rightarrow+\infty.$

Recently, He, Huang, and Fang introduced in [26] a primal-dual full splitting
algorithm in finite-dimensional spaces, formulated in a manner akin to FLAG.
When applied to the convex optimization problem (3.3), their algorithm
demonstrates nonergodic/last iterate convergence rates of
$\mathcal{O}\left(\frac{1}{k}\right)$ for the restricted primal-dual gap, as
well as for the primal and dual discrete velocities. Moreover, they establish
that every limit point of the primal-dual iterates sequence is a primal-dual
optimal solution.

In contrast, our convergence rate results are of a _little-o_ type instead of
the _Big-O_ type. Specifically, this applies to the primal and dual discrete
velocities, the primal-dual gap, the feasibility violation measure, and
function values. For the latter, we also present a convergence rate from
below. Furthermore, we have successfully proven the convergence of the entire
primal-dual sequence of iterates to a primal-dual optimal solution.

Our algorithm demonstrates the most advanced convergence and convergence rate
results among primal-dual full splitting algorithms in the context of
minimizing a nonsmooth convex function under linear constraints. Moreover, the
iterative scheme and its convergence results can be readily extended to
minimize separable nonsmooth convex optimization functions with linearly
coupled block variables (see [14]).

##  4 Numerical experiments

In this section, we validate the derived convergence rates for our proposed
algorithm concerning optimization problems with linear constraints (3.3). We
conduct numerical experiments to compare its performance with the FLAG method
[41]. All experiments are executed using Matlab on a standard Lenovo laptop
equipped with an Intel(R) Core(TM) i5-8265U CPU and 8GB RAM.

(a) The discrete velocities of the primal sequence

(b) The discrete velocities of the dual sequence

Figure 4.1: Comparing the convergence behaviour of the discrete velocities across various dimension settings Quantity Measure | FLAG | $\alpha=5$ | $\alpha=10$
---|---|---|---
$\left\lVert x_{k}-x_{k-1}\right\rVert$ | $1.5124\times 10^{-9}$ | $1.2723\times 10^{-10}$ | $3.6571\times 10^{-13}$
$\left\lVert\lambda_{k}-\lambda_{k-1}\right\rVert$ | $2.4809\times 10^{-9}$ | $6.2010\times 10^{-11}$ | $1.7187\times 10^{-13}$
$\left\lVert Ax_{k}-b\right\rVert$ | $3.6996\times 10^{-7}$ | $3.4758\times 10^{-4}$ | $3.3808\times 10^{-7}$
$\left(f+h\right)\left(x_{k}\right)$ | $25.6340$ | $25.6330$ | $25.6332$
Table 4.1: Comparing the average convergence behavior of the discrete
velocities, feasibility violation measure, and function values for
$\left(m,p,n\right)=\left(100,500,1000\right)$.

Particulaly, we considered the following convex optimization problem

$\displaystyle\min_{x\in\mathbb{R}^{n}}\,\,$ $\displaystyle\left\lVert
x\right\rVert_{1}+\frac{1}{2}\left\lVert Bx-c\right\rVert^{2}$ s.t.
$\displaystyle Ax=b,$

where $A\in\mathbb{R}^{m\times n}$, $B\in\mathbb{R}^{p\times n}$,
$b\in\mathbb{R}^{m}$ and $c\in\mathbb{R}^{p}$. We carried out the numerical
experiments for different choices of the triple of dimensions $(m,p,n)$ for
randomly generated matrices and vectors. For each dimensional setting, we
conducted the experiments $10$ times with $10^{6}$ iterations per run. This
was achieved by generating $A\in\mathbb{R}^{m\times n}$,
$B\in\mathbb{R}^{p\times n}$, $b\in\mathbb{R}^{m}$ and $c\in\mathbb{R}^{p}$,
all following a standard normal distribution. In the Tables 4.1 and 4.2 and
the Figures 4.1 and 4.2 we showcase the average convergence behavior of the
discrete velocities, feasibility violation measure, and function values over
$10$ runs for $(m,p,n)=(100,500,1000)$ and $(m,p,n)=(100,100,10000)$,
respectively. These two instances serve as typical examples for the
convergence behavior of the two considered numerical methods.

When solving the optimization problems with FLAG and 3.1, we selected optimal
algorithm parameters based on theoretical considerations. According to [41],
we chose

$r=1\quad\textrm{ and }\quad\tau=\dfrac{\beta}{\beta\left\lVert
A\right\rVert^{2}+1}.$

Specifically for 3.1, we explored different choices for $\alpha$ and chose
accordingly

$\tau=\sigma:=\dfrac{0.99\beta}{\beta\left\lVert
A\right\rVert+\left(1-\frac{0.99\cdot
3\left(\alpha-2\right)}{8\left(\alpha-1\right)}\right)}<\dfrac{\beta}{\beta\left\lVert
A\right\rVert+\left(1-\frac{3\left(\alpha-2\right)}{8\left(\alpha-1\right)}\right)}=\dfrac{1}{\left\lVert
A\right\rVert+\frac{5\alpha-2}{8\left(\alpha-1\right)\beta}}.$

FLAG demonstrates superior convergence concerning the feasibility violation
measure, while 3.1 outperforms FLAG in terms of the convergence of function
values and discrete velocities.

(a) The feasibility violation measures

(b) The function values

Figure 4.2: Comparing the convergence behavior of the feasibility violation measure and function values across various dimension settings Quantity Measure | FLAG | $\alpha=5$ | $\alpha=10$
---|---|---|---
$\left\lVert x_{k}-x_{k-1}\right\rVert$ | $1.2429\times 10^{-9}$ | $3.0553\times 10^{-10}$ | $1.5930\times 10^{-13}$
$\left\lVert\lambda_{k}-\lambda_{k-1}\right\rVert$ | $5.6672\times 10^{-10}$ | $1.6168\times 10^{-9}$ | $4.1257\times 10^{-10}$
$\left\lVert Ax_{k}-b\right\rVert$ | $1.5354\times 10^{-7}$ | $7.0237\times 10^{-4}$ | $2.4590\times 10^{-5}$
$\left(f+h\right)\left(x_{k}\right)$ | $5.2996$ | $5.2967$ | $5.2969$
Table 4.2: Comparing the average convergence behavior of the discrete
velocities, feasibility violation measure, and function values for
$\left(m,p,n\right)=\left(100,100,10000\right)$.

##  Appendix A Appendix

Within the appendix, we have assembled supplementary results and furnished
proofs for the two technical lemmas essential in analyzing the convergence of
the proposed forward-backward algorithm.

###  A.1 Preliminaries

######  Lemma A.1.

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

$a\|x\|^{2}+2b\langle x,y\rangle+c\|y\|^{2}\geq 0\qquad\forall
x,y\in\mathcal{H};$

  2. $\rm{(ii)}$

if $a<0$, then

$a\|x\|^{2}+2b\langle x,y\rangle+c\|y\|^{2}\geq 0\qquad\forall
x,y\in\mathcal{H}.$

The following result follows from [10, Lemma 5.31].

######  Lemma A.2.

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

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

then the following statements are true:

  1. $\rm{(i)}$

the sequence $(b_{k})_{k\geq 1}$ is summable, i.e., $\sum_{k\geq
1}b_{k}<+\infty$;

  2. $\rm{(ii)}$

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

The following result is stated and proven in [13, Lemma A.5].

######  Lemma A.3.

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$.

For the convergence proof of the iterates we use the discrete version of
Opial’s Lemma.

######  Lemma A.4.

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 lemma illustrates the relationship between the two convergence
measures utilized in this paper (see [Fact 1, [17]]).

######  Lemma A.5.

For every $z\in\mathcal{H}$ and every $\gamma>0$, it holds

$r_{\mathrm{fix},\gamma}(z)=\|z-J_{\gamma M}\big{(}z-\gamma
C(z)\big{)}\|\leq\gamma\inf_{\xi\in M(z)}\|\xi+C(z)\|=\gamma{\rm
dist}(0,M(z)+C(z))=\gamma r_{\mathrm{tan}}(z).$

###### Proof.

Let $z\in\mathcal{H}$. For arbitrary $\xi\in M(z)$, it follows from the
nonexpansivity of $J_{\gamma M}$ that

$\displaystyle r_{\mathrm{fix}}(z)$ $\displaystyle=\|z-J_{\gamma
M}\big{(}z-\gamma C(z)\big{)}\|=\|J_{\gamma M}(z+\gamma\xi)-J_{\gamma
M}\big{(}z-\gamma C(z)\big{)}\|\leq\gamma\|\xi+C(z)\|.$

This proves the statement. ∎

###  A.2 Proofs of the technical lemmas

In this subsection we provide the proofs of the Lemmas 2.4, 2.5, and 2.6. By
invoking the second update block in Algorithm 2.1, we have that for every
$k\geq 1$

$\displaystyle\ 2\left(k+\alpha\right)\left(z_{k+1}-z_{k}\right)$
$\displaystyle=$ $\displaystyle\
2k\left(z_{k}-z_{k-1}\right)-(2k+\alpha)\gamma\Big{(}\xi_{k+1}+C\left(z_{k}\right)-\left(\xi_{k}+C\left(z_{k-1}\right)\right)\Big{)}-\gamma\alpha\left(\xi_{k+1}+C\left(z_{k}\right)\right),$
(A.2)

######  Proof of Lemma 2.4 .

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

$u_{\eta,k+1}:=2\eta\left(z_{k+1}-z_{*}\right)+2\left(k+1\right)\left(z_{k+1}-z_{k}\right)+\frac{5\alpha-2}{4(\alpha-1)}\gamma\left(k+1\right)(\xi_{k+1}+C\left(z_{k}\right)).$
(A.3)

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

$u_{\eta,k}=2\eta\left(z_{k}-z_{*}\right)+2k\left(z_{k}-z_{k-1}\right)+\frac{5\alpha-2}{4(\alpha-1)}\gamma
k(\xi_{k}+C\left(z_{k-1}\right)).$

Therefore, taking the difference and using (A.2), we deduce that for every
$k\geq 1$

$\displaystyle u_{\eta,k+1}-u_{\eta,k}=$ $\displaystyle\
2\left(\eta+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+\frac{5\alpha-2}{4(\alpha-1)}\gamma\left(k+1\right)(\xi_{k+1}+C\left(z_{k}\right))-\frac{5\alpha-2}{4(\alpha-1)}\gamma
k(\xi_{k}+C\left(z_{k-1}\right))$ $\displaystyle=$ $\displaystyle\
2\left(\eta+1-\alpha\right)\left(z_{k+1}-z_{k}\right)-\frac{(4\alpha-1)(\alpha-2)}{4(\alpha-1)}\gamma\left(\xi_{k+1}+C\left(z_{k}\right)\right)$
$\displaystyle-\left(\frac{3(\alpha-2)}{4(\alpha-1)}k+\alpha\right)\gamma\Big{(}\xi_{k+1}+C\left(z_{k}\right)-(\xi_{k}+C\left(z_{k-1}\right))\Big{)}.$
(A.4)

Let $k\geq 1$. In the following we want to use the identity

$\dfrac{1}{2}\left(\left\lVert u_{\eta,k+1}\right\rVert^{2}-\left\lVert
u_{\eta,k}\right\rVert^{2}\right)=\left\langle
u_{\eta,k+1},u_{\eta,k+1}-u_{\eta,k}\right\rangle-\dfrac{1}{2}\left\lVert
u_{\eta,k+1}-u_{\eta,k}\right\rVert^{2}.$ (A.5)

Using (A.3) and (A.4), we obtain that

$\displaystyle\left\langle u_{\eta,k+1},u_{\eta,k+1}-u_{\eta,k}\right\rangle$
$\displaystyle=$ $\displaystyle\ 4\eta\left(\eta+1-\alpha\right)\left\langle
z_{k+1}-z_{*},z_{k+1}-z_{k}\right\rangle-\frac{(4\alpha-1)(\alpha-2)}{2(\alpha-1)}\eta\gamma\left\langle
z_{k+1}-z_{*},\xi_{k+1}+C\left(z_{k}\right)\right\rangle$
$\displaystyle-2\left(\frac{3(\alpha-2)}{4(\alpha-1)}k+\alpha\right)\eta\gamma\left\langle
z_{k+1}-z_{*},\xi_{k+1}+C\left(z_{k}\right)-(\xi_{k}+C\left(z_{k-1}\right))\right\rangle$
$\displaystyle+\left(\frac{5\alpha-2}{2(\alpha-1)}(\eta+1-\alpha)-\frac{(4\alpha-1)(\alpha-2)}{2(\alpha-1)}\right)\gamma\left(k+1\right)\left\langle
z_{k+1}-z_{k},\xi_{k+1}+C\left(z_{k}\right)\right\rangle$
$\displaystyle-2\left(\frac{3(\alpha-2)}{4(\alpha-1)}k+\alpha\right)\gamma\left(k+1\right)\left\langle
z_{k+1}-z_{k},\xi_{k+1}+C\left(z_{k}\right)-(\xi_{k}+C\left(z_{k-1}\right))\right\rangle$
$\displaystyle-\frac{(4\alpha-1)(\alpha-2)(5\alpha-2)}{16(\alpha-1)^{2}}\gamma^{2}\left(k+1\right)\left\lVert\xi_{k+1}+C\left(z_{k}\right)\right\rVert^{2}+4\left(\eta+1-\alpha\right)\left(k+1\right)\left\lVert
z_{k+1}-z_{k}\right\rVert^{2}$
$\displaystyle-\frac{5\alpha-2}{4(\alpha-1)}\left(\frac{3(\alpha-2)}{4(\alpha-1)}k+\alpha\right)\gamma^{2}\left(k+1\right)\left\langle\xi_{k+1}+C\left(z_{k}\right),\xi_{k+1}+C\left(z_{k}\right)-(\xi_{k}+C\left(z_{k-1}\right))\right\rangle,$
(A.6)

and

$\displaystyle-\dfrac{1}{2}\left\lVert
u_{\eta,k+1}-u_{\eta,k}\right\rVert^{2}$ $\displaystyle=$
$\displaystyle-2\left(\eta+1-\alpha\right)^{2}\|z_{k+1}-z_{k}\|^{2}-\frac{(4\alpha-1)^{2}(\alpha-2)^{2}}{32(\alpha-1)^{2}}\gamma^{2}\left\lVert\xi_{k+1}+C\left(z_{k}\right)\right\rVert^{2}$
$\displaystyle\quad-\frac{1}{2}\left(\frac{3(\alpha-2)}{4(\alpha-1)}k+\alpha\right)^{2}\gamma^{2}\left\lVert\xi_{k+1}+C\left(z_{k}\right)-(\xi_{k}+C\left(z_{k-1}\right))\right\rVert^{2}$
$\displaystyle\quad+\frac{(4\alpha-1)(\alpha-2)}{2(\alpha-1)}\left(\eta+1-\alpha\right)\gamma\left\langle
z_{k+1}-z_{k},\xi_{k+1}+C\left(z_{k}\right)\right\rangle$
$\displaystyle\quad+2\left(\eta+1-\alpha\right)\left(\frac{3(\alpha-2)}{4(\alpha-1)}k+\alpha\right)\gamma\left\langle
z_{k+1}-z_{k},\xi_{k+1}+C\left(z_{k}\right)-(\xi_{k}+C\left(z_{k-1}\right))\right\rangle$
$\displaystyle\quad-\frac{(4\alpha-1)(\alpha-2)}{4(\alpha-1)}\left(\frac{3(\alpha-2)}{4(\alpha-1)}k+\alpha\right)\gamma^{2}\left\langle\xi_{k+1}+C\left(z_{k}\right),\xi_{k+1}+C\left(z_{k}\right)-(\xi_{k}+C\left(z_{k-1}\right))\right\rangle.$
(A.7)

By plugging (A.6) and (A.7) into (A.5), we get

$\displaystyle\dfrac{1}{2}\left(\left\lVert
u_{\eta,k+1}\right\rVert^{2}-\left\lVert u_{\eta,k}\right\rVert^{2}\right)$
$\displaystyle=$ $\displaystyle\ 4\eta\left(\eta+1-\alpha\right)\left\langle
z_{k+1}-z_{*},z_{k+1}-z_{k}\right\rangle-\frac{(4\alpha-1)(\alpha-2)}{2(\alpha-1)}\eta\gamma\left\langle
z_{k+1}-z_{*},\xi_{k+1}+C\left(z_{k}\right)\right\rangle$
$\displaystyle-2\left(\frac{3(\alpha-2)}{4(\alpha-1)}k+\alpha\right)\eta\gamma\left\langle
z_{k+1}-z_{*},\xi_{k+1}+C\left(z_{k}\right)-(\xi_{k}+C\left(z_{k-1}\right))\right\rangle$
$\displaystyle+2\left(\eta+1-\alpha\right)\left(2k+\alpha+1-\eta\right)\left\lVert
z_{k+1}-z_{k}\right\rVert^{2}$
$\displaystyle+2\left(\frac{5\alpha-2}{4(\alpha-1)}\left(\eta+1-\alpha\right)-\frac{(4\alpha-1)(\alpha-2)}{4(\alpha-1)}\right)k\gamma\left\langle
z_{k+1}-z_{k},\xi_{k+1}+C\left(z_{k}\right)\right\rangle$
$\displaystyle-2\left(\frac{(4\alpha-1)(\alpha-2)}{4(\alpha-1)}-\alpha(\eta+1-\alpha)\right)\gamma\left\langle
z_{k+1}-z_{k},\xi_{k+1}+C\left(z_{k}\right)\right\rangle$
$\displaystyle-2\left(\frac{3(\alpha-2)}{4(\alpha-1)}k+\alpha\right)\left(k+\alpha-\eta\right)\gamma\left\langle
z_{k+1}-z_{k},\xi_{k+1}+C\left(z_{k}\right)-(\xi_{k}+C\left(z_{k-1}\right))\right\rangle$
$\displaystyle-\frac{(4\alpha-1)(\alpha-2)}{8(\alpha-1)}\left(\frac{5\alpha-2}{2(\alpha-1)}k+\frac{4\alpha^{2}+\alpha-2}{4(\alpha-1)}\right)\gamma^{2}\left\lVert\xi_{k+1}+C\left(z_{k}\right)\right\rVert^{2}$
$\displaystyle-\left(\frac{3(\alpha-2)}{4(\alpha-1)}k+\alpha\right)\left(\frac{5\alpha-2}{4(\alpha-1)}k+\alpha\right)\gamma^{2}\left\langle\xi_{k+1}+C\left(z_{k}\right),\xi_{k+1}+C\left(z_{k}\right)-(\xi_{k}+C\left(z_{k-1}\right))\right\rangle$
$\displaystyle-\frac{1}{2}\left(\frac{3(\alpha-2)}{4(\alpha-1)}k+\alpha\right)^{2}\gamma^{2}\left\lVert\xi_{k+1}+C\left(z_{k}\right)-(\xi_{k}+C\left(z_{k-1}\right))\right\rVert^{2}.$
(A.8)

Above we obtained an estimate for the difference of the first terms in the
definition of $\mathcal{E}_{\eta,k+1}$ and $\mathcal{E}_{\eta,k}$,
respectively. Next we evaluate the differences of the remaining terms in the
two discrete energy functions, respectively. First, we observe that

$\displaystyle\ 2\eta\left(\alpha-1-\eta\right)\left(\left\lVert
z_{k+1}-z_{*}\right\rVert^{2}-\left\lVert z_{k}-z_{*}\right\rVert^{2}\right)$
$\displaystyle=$ $\displaystyle\
2\eta\left(\alpha-1-\eta\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).$ (A.9)

Further, we have

$\displaystyle\
2\eta\gamma\left(\frac{3(\alpha-2)}{4(\alpha-1)}\left(k+1\right)+\alpha\right)\left\langle
z_{k+1}-z_{*},\xi_{k+1}+C\left(z_{k}\right)\right\rangle$
$\displaystyle-2\eta\gamma\left(\frac{3(\alpha-2)}{4(\alpha-1)}k+\alpha\right)\left\langle
z_{k}-z_{*},\xi_{k}+C\left(z_{k-1}\right)\right\rangle$ $\displaystyle=$
$\displaystyle\ \frac{3(\alpha-2)}{2(\alpha-1)}\eta\gamma\left\langle
z_{k+1}-z_{*},\xi_{k+1}+C\left(z_{k}\right)\right\rangle+2\eta\gamma\left(\frac{3(\alpha-2)}{4(\alpha-1)}k+\alpha\right)\big{(}\left\langle
z_{k+1}-z_{*},\xi_{k+1}+C\left(z_{k}\right)\right\rangle$
$\displaystyle-\left\langle
z_{k}-z_{*},\xi_{k}+C\left(z_{k-1}\right)\right\rangle\big{)}$
$\displaystyle=$ $\displaystyle\
\frac{3(\alpha-2)}{2(\alpha-1)}\eta\gamma\left\langle
z_{k+1}-z_{*},\xi_{k+1}+C\left(z_{k}\right)\right\rangle+2\eta\gamma\left(\frac{3(\alpha-2)}{4(\alpha-1)}k+\alpha\right)\left\langle
z_{k+1}-z_{k},\xi_{k+1}+C\left(z_{k}\right)\right\rangle$
$\displaystyle+2\eta\gamma\left(\frac{3(\alpha-2)}{4(\alpha-1)}k+\alpha\right)\left\langle
z_{k+1}-z_{*},\xi_{k+1}+C\left(z_{k}\right)-(\xi_{k}+C\left(z_{k-1}\right))\right\rangle$
$\displaystyle-2\eta\gamma\left(\frac{3(\alpha-2)}{4(\alpha-1)}k+\alpha\right)\left\langle
z_{k+1}-z_{k},\xi_{k+1}+C\left(z_{k}\right)-(\xi_{k}+C\left(z_{k-1}\right))\right\rangle,$
(A.10)

and

$\displaystyle\
\dfrac{1}{2}\gamma^{2}\left(\frac{3(\alpha-2)}{4(\alpha-1)}(k+1)+\alpha\right)\left(\frac{5\alpha-2}{4(\alpha-1)}(k+1)+\alpha\right)\left\lVert\xi_{k+1}+C\left(z_{k}\right)\right\rVert^{2}$
$\displaystyle-\dfrac{1}{2}\gamma^{2}\left(\frac{3(\alpha-2)}{4(\alpha-1)}k+\alpha\right)\left(\frac{5\alpha-2}{4(\alpha-1)}k+\alpha\right)\left\lVert\xi_{k}+C\left(z_{k-1}\right)\right\rVert^{2}$
$\displaystyle=$ $\displaystyle\
\dfrac{1}{2}\gamma^{2}\left(\frac{3(5\alpha-2)(\alpha-2)}{8(\alpha-1)^{2}}k+\frac{(5\alpha-2)\alpha}{4(\alpha-1)}+\frac{3(\alpha-2)(4\alpha^{2}+\alpha-2)}{16(\alpha-1)^{2}}\right)\left\lVert\xi_{k+1}+C\left(z_{k}\right)\right\rVert^{2}$
$\displaystyle-\dfrac{1}{2}\gamma^{2}\left(\frac{3(\alpha-2)}{4(\alpha-1)}k+\alpha\right)\left(\frac{5\alpha-2}{4(\alpha-1)}k+\alpha\right)\left\lVert\xi_{k+1}+C\left(z_{k}\right)-(\xi_{k}+C\left(z_{k-1}\right))\right\rVert^{2}$
$\displaystyle+\gamma^{2}\left(\frac{3(\alpha-2)}{4(\alpha-1)}k+\alpha\right)\left(\frac{5\alpha-2}{4(\alpha-1)}k+\alpha\right)\left\langle\xi_{k+1}+C\left(z_{k}\right),\xi_{k+1}+C\left(z_{k}\right)-(\xi_{k}+C\left(z_{k-1}\right))\right\rangle.$
(A.11)

Summing the indentities in (A.8), (A.9), (A.10) and (A.11) and taking into
account that $\eta+1-\alpha\leq 0$, we obtain the statement in 2.4.
$\blacksquare$

######  Proof of Lemma 2.5 .

Let $k\geq 1$ be fixed.

(i) By 2.4, we have that

$\displaystyle\mathcal{E}_{\eta,k+1}-\mathcal{E}_{\eta,k}\leq\ $
$\displaystyle 2\eta\gamma(2-\alpha)\left\langle
z_{k+1}-z_{*},\xi_{k+1}+C\left(z_{k}\right)\right\rangle+2\gamma\left(\nu_{0}k+\nu_{1}\right)\left\langle
z_{k+1}-z_{k},\xi_{k+1}+C\left(z_{k}\right)\right\rangle$
$\displaystyle+2\nu_{2}k\left\lVert
z_{k+1}-z_{k}\right\rVert^{2}+\frac{1}{2}\gamma^{2}(\nu_{3}k+\nu_{4})\left\lVert\xi_{k+1}+C\left(z_{k}\right)\right\rVert^{2}$
$\displaystyle-2\gamma\left(\frac{3(\alpha-2)}{4(\alpha-1)}k+\alpha\right)\left(k+\alpha\right)\left\langle
z_{k+1}-z_{k},\xi_{k+1}+C\left(z_{k}\right)-(\xi_{k}+C\left(z_{k-1}\right))\right\rangle$
$\displaystyle-\gamma^{2}\left(\frac{3(\alpha-2)}{4(\alpha-1)}k+\alpha\right)(k+\alpha)\left\lVert\xi_{k+1}+C\left(z_{k}\right)-(\xi_{k}+C\left(z_{k-1}\right))\right\rVert^{2}.$
(A.12)

Using the Cauchy-Schwarz inequality, we obtain

$\displaystyle-2\eta\gamma(\alpha-2)\left\langle
z_{k+1}-z_{*},\xi_{k+1}+C\left(z_{k}\right)\right\rangle$ $\displaystyle=\,\,$
$\displaystyle-2\eta\gamma(\alpha-2)\left\langle
z_{k+1}-z_{*},\xi_{k+1}+C\left(z_{k+1}\right)\right\rangle+2\eta\gamma(\alpha-2)\left\langle
z_{k+1}-z_{*},C\left(z_{k+1}\right)-C\left(z_{k}\right)\right\rangle$
$\displaystyle\leq\,\,$ $\displaystyle-2\eta\gamma(\alpha-2)\left\langle
z_{k+1}-z_{*},\xi_{k+1}+C\left(z_{k+1}\right)\right\rangle+\frac{4\eta^{2}(\alpha-2)(\alpha-1)}{3(k+1)\sqrt{k+1}}\left\lVert
z_{k+1}-z_{*}\right\rVert^{2}$
$\displaystyle\qquad+\frac{3(\alpha-2)}{4(\alpha-1)}\gamma^{2}(k+1)\sqrt{k+1}\|C\left(z_{k+1}\right)-C\left(z_{k}\right)\|^{2}.$
(A.13)

Using the monotonicity of $M$ in combination with (2.3), the coercivity of
$C$, and (A.2), it yields

$\displaystyle\quad-2\gamma\left(\frac{3(\alpha-2)}{4(\alpha-1)}k+\alpha\right)\left(k+\alpha\right)\left\langle
z_{k+1}-z_{k},\xi_{k+1}+C\left(z_{k}\right)-(\xi_{k}+C\left(z_{k-1}\right))\right\rangle$
$\displaystyle\,\,=-2\gamma\left(\frac{3(\alpha-2)}{4(\alpha-1)}k+\alpha\right)\left(k+\alpha\right)\Big{(}\left\langle
z_{k+1}-z_{k},\xi_{k+1}-\xi_{k}\right\rangle+\left\langle
z_{k+1}-z_{k},C\left(z_{k}\right)-C\left(z_{k-1}\right)\right\rangle\Big{)}$
$\displaystyle\,\,\leq-2\gamma\left(\frac{3(\alpha-2)}{4(\alpha-1)}k+\alpha\right)\left(k+\alpha\right)\left\langle
z_{k+1}-z_{k},C\left(z_{k}\right)-C\left(z_{k-1}\right)\right\rangle$
$\displaystyle\,\,=-2\gamma\left(\frac{3(\alpha-2)}{4(\alpha-1)}k+\alpha\right)k\left\langle
z_{k}-z_{k-1},C\left(z_{k}\right)-C\left(z_{k-1}\right)\right\rangle$
$\displaystyle\qquad+\alpha\gamma^{2}\left(\frac{3(\alpha-2)}{4(\alpha-1)}k+\alpha\right)\left\langle\xi_{k+1}+C\left(z_{k}\right),C\left(z_{k}\right)-C\left(z_{k-1}\right)\right\rangle$
$\displaystyle\qquad+\gamma^{2}\left(\frac{3(\alpha-2)}{4(\alpha-1)}k+\alpha\right)(2k+\alpha)\left\langle\xi_{k+1}+C\left(z_{k}\right)-(\xi_{k}+C\left(z_{k-1}\right)),C\left(z_{k}\right)-C\left(z_{k-1}\right)\right\rangle$
$\displaystyle\,\,\leq\Bigg{(}2\gamma\left(\frac{3(\alpha-2)}{4(\alpha-1)}(k+1)+\alpha\right)(k+1)\left\langle
z_{k+1}-z_{k},C\left(z_{k+1}\right)-C\left(z_{k}\right)\right\rangle$
$\displaystyle\qquad-2\gamma\left(\frac{3(\alpha-2)}{4(\alpha-1)}k+\alpha\right)k\left\langle
z_{k}-z_{k-1},C\left(z_{k}\right)-C\left(z_{k-1}\right)\right\rangle\Bigg{)}$
$\displaystyle\qquad-2\gamma\beta\left(\frac{3(\alpha-2)}{4(\alpha-1)}(k+1)+\alpha\right)(k+1)\|C\left(z_{k+1}\right)-C\left(z_{k}\right)\|^{2}$
$\displaystyle\qquad+\alpha\gamma^{2}\left(\frac{3(\alpha-2)}{4(\alpha-1)}k+\alpha\right)\left\langle\xi_{k+1}+C\left(z_{k}\right),C\left(z_{k}\right)-C\left(z_{k-1}\right)\right\rangle$
$\displaystyle\qquad+\gamma^{2}\left(\frac{3(\alpha-2)}{4(\alpha-1)}k+\alpha\right)(2k+\alpha)\left\langle\xi_{k+1}+C\left(z_{k}\right)-(\xi_{k}+C\left(z_{k-1}\right)),C\left(z_{k}\right)-C\left(z_{k-1}\right)\right\rangle.$
(A.14)

Using Young’s inequality, we obtain

$\displaystyle\alpha\gamma^{2}\left(\frac{3(\alpha-2)}{4(\alpha-1)}k+\alpha\right)\left\langle\xi_{k+1}+C\left(z_{k}\right),C\left(z_{k}\right)-C\left(z_{k-1}\right)\right\rangle$
$\displaystyle\leq\,\,$
$\displaystyle\frac{1}{2}\alpha\gamma^{2}\left(\frac{3(\alpha-2)}{4(\alpha-1)}k+\alpha\right)\sqrt{\frac{3(\alpha-2)}{4(\alpha-1)}k+\alpha}\left\lVert
C\left(z_{k}\right)-C\left(z_{k-1}\right)\right\rVert^{2}$
$\displaystyle\quad+\frac{1}{2}\alpha\gamma^{2}\sqrt{\frac{3(\alpha-2)}{4(\alpha-1)}k+\alpha}\left\lVert\xi_{k+1}+C\left(z_{k}\right)\right\rVert^{2}$
$\displaystyle=\,\,$
$\displaystyle-\frac{1}{2}\alpha\gamma^{2}\Bigg{(}\left(\frac{3(\alpha-2)}{4(\alpha-1)}(k+1)+\alpha\right)\sqrt{\frac{3(\alpha-2)}{4(\alpha-1)}(k+1)+\alpha}\|C\left(z_{k+1}\right)-C\left(z_{k}\right)\|^{2}$
$\displaystyle\qquad\qquad\quad-\left(\frac{3(\alpha-2)}{4(\alpha-1)}k+\alpha\right)\sqrt{\frac{3(\alpha-2)}{4(\alpha-1)}k+\alpha}\left\lVert
C\left(z_{k}\right)-C\left(z_{k-1}\right)\right\rVert^{2}\Bigg{)}$
$\displaystyle\quad+\frac{1}{2}\alpha\gamma^{2}\left(\frac{3(\alpha-2)}{4(\alpha-1)}(k+1)+\alpha\right)\sqrt{\frac{3(\alpha-2)}{4(\alpha-1)}(k+1)+\alpha}\|C\left(z_{k+1}\right)-C\left(z_{k}\right)\|^{2}$
$\displaystyle\quad+\frac{1}{2}\alpha\gamma^{2}\sqrt{\frac{3(\alpha-2)}{4(\alpha-1)}k+\alpha}\left\lVert\xi_{k+1}+C\left(z_{k}\right)\right\rVert^{2},$
(A.15)

and

$\displaystyle\gamma^{2}\left(\frac{3(\alpha-2)}{4(\alpha-1)}k+\alpha\right)(2k+\alpha)\left\langle\xi_{k+1}+C\left(z_{k}\right)-(\xi_{k}+C\left(z_{k-1}\right)),C\left(z_{k}\right)-C\left(z_{k-1}\right)\right\rangle$
$\displaystyle\leq$ $\displaystyle\
\frac{1}{2(2-\varepsilon)}\gamma^{2}\left(\frac{3(\alpha-2)}{4(\alpha-1)}k+\alpha\right)(2k+\alpha)\|\xi_{k+1}+C\left(z_{k}\right)-(\xi_{k}+C\left(z_{k-1}\right))\|^{2}$
$\displaystyle\
+\frac{1}{2}(2-\varepsilon)\gamma^{2}\left(\frac{3(\alpha-2)}{4(\alpha-1)}(k+1)+\alpha\right)(2(k+1)+\alpha)\|C\left(z_{k+1}\right)-C\left(z_{k}\right)\|^{2}$
$\displaystyle\
-\frac{1}{2}(2-\varepsilon)\gamma^{2}\Bigg{(}\left(\frac{3(\alpha-2)}{4(\alpha-1)}(k+1)+\alpha\right)(2(k+1)+\alpha)\|C\left(z_{k+1}\right)-C\left(z_{k}\right)\|^{2}$
$\displaystyle\qquad\qquad\qquad\qquad-\left(\frac{3(\alpha-2)}{4(\alpha-1)}k+\alpha\right)(2k+\alpha)\|C\left(z_{k}\right)-C\left(z_{k-1}\right)\|^{2}\Bigg{)}.$
(A.16)

Plugging (A.15) and (A.16) into (A.14), and adding the resulting inequality to
(A.13), yields

$\displaystyle-2\eta\gamma(\alpha-2)\left\langle
z_{k+1}-z_{*},\xi_{k+1}+C\left(z_{k}\right)\right\rangle$
$\displaystyle-2\gamma\left(\frac{3(\alpha-2)}{4(\alpha-1)}k+\alpha\right)\left(k+\alpha\right)\left\langle
z_{k+1}-z_{k},\xi_{k+1}+C\left(z_{k}\right)-(\xi_{k}+C\left(z_{k-1}\right))\right\rangle$
$\displaystyle\leq$ $\displaystyle\
2\gamma\Bigg{(}\left(\frac{3(\alpha-2)}{4(\alpha-1)}(k+1)+\alpha\right)(k+1)\left\langle
z_{k+1}-z_{k},C\left(z_{k+1}\right)-C\left(z_{k}\right)\right\rangle$
$\displaystyle\qquad\
-\left(\frac{3(\alpha-2)}{4(\alpha-1)}k+\alpha\right)k\left\langle
z_{k}-z_{k-1},C\left(z_{k}\right)-C\left(z_{k-1}\right)\right\rangle\Bigg{)}$
$\displaystyle\
-\frac{1}{2}\alpha\gamma^{2}\Bigg{(}\left(\frac{3(\alpha-2)}{4(\alpha-1)}(k+1)+\alpha\right)\sqrt{\frac{3(\alpha-2)}{4(\alpha-1)}(k+1)+\alpha}\|C\left(z_{k+1}\right)-C\left(z_{k}\right)\|^{2}$
$\displaystyle\qquad\qquad\quad-\left(\frac{3(\alpha-2)}{4(\alpha-1)}k+\alpha\right)\sqrt{\frac{3(\alpha-2)}{4(\alpha-1)}k+\alpha}\left\lVert
C\left(z_{k}\right)-C\left(z_{k-1}\right)\right\rVert^{2}\Bigg{)}$
$\displaystyle\
-\frac{1}{2}(2-\varepsilon)\gamma^{2}\Bigg{(}\left(\frac{3(\alpha-2)}{4(\alpha-1)}(k+1)+\alpha\right)(2(k+1)+\alpha)\|C\left(z_{k+1}\right)-C\left(z_{k}\right)\|^{2}$
$\displaystyle\qquad\qquad\qquad\quad-\left(\frac{3(\alpha-2)}{4(\alpha-1)}k+\alpha\right)(2k+\alpha)\|C\left(z_{k}\right)-C\left(z_{k-1}\right)\|^{2}\Bigg{)}$
$\displaystyle\ -2\eta\gamma(\alpha-2)\left\langle
z_{k+1}-z_{*},\xi_{k+1}+C\left(z_{k+1}\right)\right\rangle+\frac{4\eta^{2}(\alpha-2)(\alpha-1)}{3(k+1)\sqrt{k+1}}\left\lVert
z_{k+1}-z_{*}\right\rVert^{2}$ $\displaystyle\
+\frac{1}{2}\alpha\gamma^{2}\sqrt{\frac{3(\alpha-2)}{4(\alpha-1)}k+\alpha}\left\lVert\xi_{k+1}+C\left(z_{k}\right)\right\rVert^{2}-\omega_{k}\|C\left(z_{k+1}\right)-C\left(z_{k}\right)\|^{2}$
$\displaystyle\
+\frac{1}{2(2-\varepsilon)}\gamma^{2}\left(\frac{3(\alpha-2)}{4(\alpha-1)}k+\alpha\right)(2k+\alpha)\|\xi_{k+1}+C\left(z_{k}\right)-(\xi_{k}+C\left(z_{k-1}\right))\|^{2},$
(A.17)

where $\omega_{k}$ is defined in (2.10).

Finally, after summing (A.17) and (A.12), we obtain

$\displaystyle\ \mathcal{E}_{\eta,k+1}-\mathcal{E}_{\eta,k}$
$\displaystyle\leq$ $\displaystyle\
2\gamma\Bigg{(}\left(\frac{3(\alpha-2)}{4(\alpha-1)}(k+1)+\alpha\right)(k+1)\left\langle
z_{k+1}-z_{k},C\left(z_{k+1}\right)-C\left(z_{k}\right)\right\rangle$
$\displaystyle\qquad\
-\left(\frac{3(\alpha-2)}{4(\alpha-1)}k+\alpha\right)k\left\langle
z_{k}-z_{k-1},C\left(z_{k}\right)-C\left(z_{k-1}\right)\right\rangle\Bigg{)}$
$\displaystyle\
-\frac{1}{2}\alpha\gamma^{2}\Bigg{(}\left(\frac{3(\alpha-2)}{4(\alpha-1)}(k+1)+\alpha\right)\sqrt{\frac{3(\alpha-2)}{4(\alpha-1)}(k+1)+\alpha}\|C\left(z_{k+1}\right)-C\left(z_{k}\right)\|^{2}$
$\displaystyle\qquad\qquad\quad-\left(\frac{3(\alpha-2)}{4(\alpha-1)}k+\alpha\right)\sqrt{\frac{3(\alpha-2)}{4(\alpha-1)}k+\alpha}\left\lVert
C\left(z_{k}\right)-C\left(z_{k-1}\right)\right\rVert^{2}\Bigg{)}$
$\displaystyle\
-\frac{1}{2}(2-\varepsilon)\gamma^{2}\Bigg{(}\left(\frac{3(\alpha-2)}{4(\alpha-1)}(k+1)+\alpha\right)(2(k+1)+\alpha)\|C\left(z_{k+1}\right)-C\left(z_{k}\right)\|^{2}$
$\displaystyle\qquad\qquad\qquad\quad-\left(\frac{3(\alpha-2)}{4(\alpha-1)}k+\alpha\right)(2k+\alpha)\|C\left(z_{k}\right)-C\left(z_{k-1}\right)\|^{2}\Bigg{)}$
$\displaystyle\ -2\eta\gamma(\alpha-2)\left\langle
z_{k+1}-z_{*},\xi_{k+1}+C\left(z_{k+1}\right)\right\rangle+\frac{4\eta^{2}(\alpha-2)(\alpha-1)}{3(k+1)\sqrt{k+1}}\left\lVert
z_{k+1}-z_{*}\right\rVert^{2}$ $\displaystyle\
+2\gamma\left(\nu_{0}k+\nu_{1}\right)\left\langle
z_{k+1}-z_{k},\xi_{k+1}+C\left(z_{k}\right)\right\rangle+2\nu_{2}k\left\lVert
z_{k+1}-z_{k}\right\rVert^{2}$ $\displaystyle\
+\frac{1}{2}\gamma^{2}(\nu_{3}k+\alpha\sqrt{\frac{3(\alpha-2)}{4(\alpha-1)}k+\alpha}+\nu_{4})\left\lVert\xi_{k+1}+C\left(z_{k}\right)\right\rVert^{2}-\omega_{k}\|C\left(z_{k+1}\right)-C\left(z_{k}\right)\|^{2}$
$\displaystyle\
-\gamma^{2}\left(\frac{3(\alpha-2)}{4(\alpha-1)}k+\alpha\right)\left(\frac{1-\varepsilon}{2-\varepsilon}k+\frac{3-2\varepsilon}{2(2-\varepsilon)}\alpha\right)\left\lVert\xi_{k+1}+C\left(z_{k}\right)-(\xi_{k}+C\left(z_{k-1}\right))\right\rVert^{2}.$
(A.18)

Taking into account the definition of $\mathcal{F}_{\eta,k}$ in (2.8), we
notice that (A.18) is nothing else than (2.9).

(ii) Observe that

$\displaystyle\ \frac{3(\alpha-2)}{2(\alpha-1)}\eta\gamma
k\big{\langle}z_{k}-z_{*},\xi_{k}+C\left(z_{k-1}\right)\big{\rangle}+\frac{3(\alpha-2)(5\alpha-2)}{32(\alpha-1)^{2}}\gamma^{2}k^{2}\left\lVert\xi_{k}+C\left(z_{k-1}\right)\right\rVert^{2}$
$\displaystyle=$ $\displaystyle\
\frac{3(\alpha-2)}{2(5\alpha-2)}\left(\frac{5\alpha-2}{\alpha-1}\eta\gamma
k\langle
z_{k}-z_{*},\xi_{k}+C\left(z_{k-1}\right)\rangle+\frac{(5\alpha-2)^{2}}{16(\alpha-1)^{2}}\gamma^{2}k^{2}\left\lVert\xi_{k}+C\left(z_{k-1}\right)\right\rVert^{2}\right)$
$\displaystyle=$ $\displaystyle\ \frac{3(\alpha-2)}{2(5\alpha-2)}\left\lVert
2\eta(z_{k}-z_{*})+\frac{5\alpha-2}{4(\alpha-1)}\gamma
k\left(\xi_{k}+C\left(z_{k-1}\right)\right)\right\rVert^{2}-\frac{6(\alpha-2)}{5\alpha-2}\eta^{2}\left\lVert
z_{k}-z_{*}\right\rVert^{2}.$ (A.19)

By plugging (A.19) into the definition of $\mathcal{F}_{\eta,k}$, it yields

$\displaystyle\mathcal{F}_{\eta,k}=$ $\displaystyle\ \dfrac{1}{2}\left\lVert
2\eta\left(z_{k}-z_{*}\right)+2k\left(z_{k}-z_{k-1}\right)+\frac{5\alpha-2}{4(\alpha-1)}\gamma
k\left(\xi_{k}+C\left(z_{k-1}\right)\right)\right\rVert^{2}$
$\displaystyle+2\eta\left(\alpha-1-\eta\right)\left\lVert
z_{k}-z_{*}\right\rVert^{2}+2\eta\gamma\left(\frac{3(\alpha-2)}{4(\alpha-1)}k+\alpha\right)\big{\langle}z_{k}-z_{*},\xi_{k}+C\left(z_{k-1}\right)\big{\rangle}$
$\displaystyle+\frac{1}{2}\gamma^{2}\left(\frac{3(\alpha-2)}{4(\alpha-1)}k+\alpha\right)\left(\frac{5\alpha-2}{4(\alpha-1)}k+\alpha\right)\left\lVert\xi_{k}+C\left(z_{k-1}\right)\right\rVert^{2}$
$\displaystyle-2\gamma\left(\frac{3(\alpha-2)}{4(\alpha-1)}k+\alpha\right)k\left\langle
z_{k}-z_{k-1},C\left(z_{k}\right)-C\left(z_{k-1}\right)\right\rangle$
$\displaystyle+\frac{1}{2}\gamma^{2}\left(\frac{3(\alpha-2)}{4(\alpha-1)}k+\alpha\right)\left((2-\varepsilon)(2k+\alpha)+\alpha\sqrt{\frac{3(\alpha-2)}{4(\alpha-1)}k+\alpha}\right)\left\lVert
C\left(z_{k}\right)-C\left(z_{k-1}\right)\right\rVert^{2}$ $\displaystyle=$
$\displaystyle\ \dfrac{1}{2}\left\lVert
2\eta\left(z_{k}-z_{*}\right)+2k\left(z_{k}-z_{k-1}\right)+\frac{5\alpha-2}{4(\alpha-1)}\gamma
k\left(\xi_{k}+C\left(z_{k-1}\right)\right)\right\rVert^{2}$
$\displaystyle+\frac{3(\alpha-2)}{2(5\alpha-2)}\left\lVert
2\eta\left(z_{k}-z_{*}\right)+\frac{5\alpha-2}{4(\alpha-1)}\gamma
k\left(\xi_{k}+C\left(z_{k-1}\right)\right)\right\rVert^{2}$
$\displaystyle+2\eta(\alpha-1)\left(1-\frac{8\eta}{5\alpha-2}\right)\left\lVert
z_{k}-z_{*}\right\rVert^{2}+\frac{1}{2}\gamma^{2}\alpha(2k+\alpha)\left\lVert\xi_{k}+C\left(z_{k-1}\right)\right\rVert^{2}$
$\displaystyle-2\gamma\left(\frac{3(\alpha-2)}{4(\alpha-1)}k+\alpha\right)k\left\langle
z_{k}-z_{k-1},C\left(z_{k}\right)-C\left(z_{k-1}\right)\right\rangle+2\eta\alpha\gamma\big{\langle}z_{k}-z_{*},\xi_{k}+C\left(z_{k-1}\right)\big{\rangle}$
$\displaystyle+\frac{1}{2}\gamma^{2}\left(\frac{3(\alpha-2)}{4(\alpha-1)}k+\alpha\right)\left((2-\varepsilon)(2k+\alpha)+\alpha\sqrt{\frac{3(\alpha-2)}{4(\alpha-1)}k+\alpha}\right)\left\lVert
C\left(z_{k}\right)-C\left(z_{k-1}\right)\right\rVert^{2}$ $\displaystyle=$
$\displaystyle\ \frac{\alpha+2}{5\alpha-2}\left\lVert
2\eta\left(z_{k}-z_{*}\right)+2k\left(z_{k}-z_{k-1}\right)+\frac{5\alpha-2}{4(\alpha-1)}\gamma
k\left(\xi_{k}+C\left(z_{k-1}\right)\right)\right\rVert^{2}$
$\displaystyle+\frac{3(\alpha-2)}{4(5\alpha-2)}\left\lVert
4\eta\left(z_{k}-z_{*}\right)+2k\left(z_{k}-z_{k-1}\right)+\frac{5\alpha-2}{2(\alpha-1)}\gamma
k\left(\xi_{k}+C\left(z_{k-1}\right)\right)\right\rVert^{2}$
$\displaystyle+2\eta(\alpha-1)\left(1-\frac{8\eta}{5\alpha-2}\right)\left\lVert
z_{k}-z_{*}\right\rVert^{2}+\frac{1}{2}\gamma^{2}\alpha(2k+\alpha)\left\lVert\xi_{k}+C\left(z_{k-1}\right)\right\rVert^{2}$
$\displaystyle+\frac{3(\alpha-2)}{5\alpha-2}k^{2}\left\lVert
z_{k}-z_{k-1}\right\rVert^{2}-2\gamma\left(\frac{3(\alpha-2)}{4(\alpha-1)}k+\alpha\right)k\left\langle
z_{k}-z_{k-1},C\left(z_{k}\right)-C\left(z_{k-1}\right)\right\rangle$
$\displaystyle+\frac{1}{2}\gamma^{2}\left(\frac{3(\alpha-2)}{4(\alpha-1)}k+\alpha\right)\left((2-\varepsilon)(2k+\alpha)+\alpha\sqrt{\frac{3(\alpha-2)}{4(\alpha-1)}k+\alpha}\right)\left\lVert
C\left(z_{k}\right)-C\left(z_{k-1}\right)\right\rVert^{2}$
$\displaystyle+2\eta\alpha\gamma\big{\langle}z_{k}-z_{*},\xi_{k}+C\left(z_{k-1}\right)\big{\rangle},$
(A.20)

where for obtaining the last statement we used the identity

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

Finally, by employing in (A.20)

$\displaystyle-\frac{3(\alpha-2)}{2(\alpha-1)}\gamma k^{2}\left\langle
z_{k}-z_{k-1},C\left(z_{k}\right)-C\left(z_{k-1}\right)\right\rangle+\frac{3(\alpha-2)}{4(\alpha-1)}(2-\varepsilon)\gamma^{2}k^{2}\left\lVert
C\left(z_{k}\right)-C\left(z_{k-1}\right)\right\rVert^{2}$ $\displaystyle=$
$\displaystyle\ \frac{3(\alpha-2)}{4(\alpha-1)}\gamma
k^{2}\left\lVert\frac{1}{\sqrt{(2-\varepsilon)\gamma}}(z_{k}-z_{k-1})-\sqrt{(2-\varepsilon)\gamma}(C\left(z_{k}\right)-C\left(z_{k-1}\right))\right\rVert^{2}$
$\displaystyle-\frac{3(\alpha-2)}{4(\alpha-1)(2-\varepsilon)}k^{2}\left\lVert
z_{k}-z_{k-1}\right\rVert^{2},$

and then the Lipschitz continuity of $C$ , it yields

$\displaystyle\mathcal{F}_{\eta,k}=$ $\displaystyle\
\frac{\alpha+2}{5\alpha-2}\left\lVert
2\eta\left(z_{k}-z_{*}\right)+2k\left(z_{k}-z_{k-1}\right)+\frac{5\alpha-2}{4(\alpha-1)}\gamma
k\left(\xi_{k}+C\left(z_{k-1}\right)\right)\right\rVert^{2}$
$\displaystyle+\frac{3(\alpha-2)}{4(5\alpha-2)}\left\lVert
4\eta\left(z_{k}-z_{*}\right)+2k\left(z_{k}-z_{k-1}\right)+\frac{5\alpha-2}{2(\alpha-1)}\gamma
k\left(\xi_{k}+C\left(z_{k-1}\right)\right)\right\rVert^{2}$
$\displaystyle+2\eta(\alpha-1)\left(1-\frac{8\eta}{5\alpha-2}\right)\left\lVert
z_{k}-z_{*}\right\rVert^{2}+\frac{1}{2}\gamma^{2}\alpha(2k+\alpha)\left\lVert\xi_{k}+C\left(z_{k-1}\right)\right\rVert^{2}$
$\displaystyle+3(\alpha-2)\left(\frac{1}{5\alpha-2}-\frac{1}{4(2-\varepsilon)(\alpha-1)}\right)k^{2}\left\lVert
z_{k}-z_{k-1}\right\rVert^{2}$
$\displaystyle+\frac{3(\alpha-2)}{4(\alpha-1)}\gamma
k^{2}\left\lVert\frac{1}{\sqrt{(2-\varepsilon)\gamma}}(z_{k}-z_{k-1})-\sqrt{(2-\varepsilon)\gamma}(C\left(z_{k}\right)-C\left(z_{k-1}\right))\right\rVert^{2}$
$\displaystyle-2\alpha\gamma k\left\langle
z_{k}-z_{k-1},C\left(z_{k}\right)-C\left(z_{k-1}\right)\right\rangle+\rho_{k}\left\lVert
C\left(z_{k}\right)-C\left(z_{k-1}\right)\right\rVert^{2}$
$\displaystyle+2\eta\alpha\gamma\big{\langle}z_{k}-z_{*},\xi_{k}+C\left(z_{k-1}\right)\big{\rangle}$
$\displaystyle\geq$ $\displaystyle\ \frac{\alpha+2}{5\alpha-2}\left\lVert
2\eta\left(z_{k}-z_{*}\right)+2k\left(z_{k}-z_{k-1}\right)+\frac{5\alpha-2}{4(\alpha-1)}\gamma
k\left(\xi_{k}+C\left(z_{k-1}\right)\right)\right\rVert^{2}$
$\displaystyle+\frac{3(\alpha-2)}{4(5\alpha-2)}\left\lVert
4\eta\left(z_{k}-z_{*}\right)+2k\left(z_{k}-z_{k-1}\right)+\frac{5\alpha-2}{2(\alpha-1)}\gamma
k\left(\xi_{k}+C\left(z_{k-1}\right)\right)\right\rVert^{2}$
$\displaystyle+2\eta(\alpha-1)\left(1-\frac{8\eta}{5\alpha-2}\right)\left\lVert
z_{k}-z_{*}\right\rVert^{2}+\frac{1}{2}\gamma^{2}\alpha(2k+\alpha)\left\lVert\xi_{k}+C\left(z_{k-1}\right)\right\rVert^{2}$
$\displaystyle+\left(3(\alpha-2)\left(\frac{1}{5\alpha-2}-\frac{1}{4(2-\varepsilon)(\alpha-1)}\right)k^{2}-\frac{2}{\beta}\alpha\gamma
k\right)\left\lVert z_{k}-z_{k-1}\right\rVert^{2}$
$\displaystyle+\frac{3(\alpha-2)}{4(\alpha-1)}\gamma
k^{2}\left\lVert\frac{1}{\sqrt{(2-\varepsilon)\gamma}}(z_{k}-z_{k-1})-\sqrt{(2-\varepsilon)\gamma}(C\left(z_{k}\right)-C\left(z_{k-1}\right))\right\rVert^{2}$
$\displaystyle+2\eta\alpha\gamma\big{\langle}z_{k}-z_{*},\xi_{k}+C\left(z_{k-1}\right)\big{\rangle}+\rho_{k}\left\lVert
C\left(z_{k}\right)-C\left(z_{k-1}\right)\right\rVert^{2},$

where

$\rho_{k}:=\frac{1}{2}\gamma^{2}\left(\left(\frac{3(\alpha-2)}{4(\alpha-1)}k+\alpha\right)\alpha\sqrt{\frac{3(\alpha-2)}{4(\alpha-1)}k+\alpha}+\frac{11\alpha-14}{4(\alpha-1)}(2-\varepsilon)\alpha
k+(2-\varepsilon)\alpha^{2}\right)>0.$

The desired inequality follows by taking into account that the last term is
nonnegative. $\blacksquare$

######  Proof of Lemma 2.6 .

(i) Since $0<\gamma<\left(1+\frac{\varepsilon}{2-\varepsilon}\right)\beta$ and
$0<\varepsilon<\frac{3(\alpha-2)}{4(\alpha-1)}$, it holds

$2\beta-(2-\varepsilon)\gamma>0\quad\textnormal{and}\quad\frac{1}{5\alpha-2}-\frac{1}{4(\alpha-1)(2-\varepsilon)}>0.$

Therefore, for $k$ large enough

$\omega_{k}>0\quad\textnormal{and}\quad\frac{3}{2}(\alpha-2)\left(\frac{1}{5\alpha-2}-\frac{1}{4(2-\varepsilon)(\alpha-1)}\right)k^{2}-\frac{2}{\beta}\alpha\gamma
k>0.$ (A.21)

For every $k\geq 1$, the discriminant of the quadratic expression in $S_{k}$
reads

$\displaystyle\Delta_{k}$
$\displaystyle=(2\eta\alpha\gamma)^{2}-2\eta(\alpha-1)\left(1-\frac{8}{5\alpha-2}\eta\right)\alpha\gamma^{2}k$
$\displaystyle=-2\eta\alpha\gamma^{2}(\alpha-1)\left(1-\frac{8}{5\alpha-2}\eta\right)k+4\eta^{2}\alpha^{2}\gamma^{2}.$

Since $0<\eta<\frac{5\alpha-2}{8}$, the coefficient of $k$ is negative,
therefore, for $k$ large enough, $\Delta_{k}\leq 0$, which, invoking A.1 (i),
implies $S_{k}\geq 0$. Consequently, there exists $K_{0}(\eta)\geq 1$ such
that for every $k\geq K_{0}(\eta)$ the inequalities in (A.21) hold and
$S_{k}\geq 0$. By taking into consideration the lower bound of
$\mathcal{F}_{\eta,k}$ in (2.11), we see that (2.14) holds for every $k\geq
K_{0}(\eta)$.

(ii) Let $k\geq 1$ be fixed. For the discriminant of the quadratic expression
in $R_{k}$, it holds

$\displaystyle\frac{\Delta_{k}}{4\gamma^{2}}$
$\displaystyle=(\nu_{0}k+\nu_{1})^{2}-\frac{9\alpha-2}{2(5\alpha-2)}\nu_{2}\left(\nu_{3}k+\alpha\sqrt{\nu_{5}k+\alpha}+\nu_{4}\right)k$
$\displaystyle=\left(\nu_{0}^{2}-\frac{9\alpha-2}{2(5\alpha-2)}\nu_{2}\nu_{3}\right)k^{2}-\frac{9\alpha-2}{2(5\alpha-2)}\nu_{2}\alpha
k\sqrt{\nu_{5}k+\alpha}+\left(2\nu_{0}\nu_{1}-\frac{9\alpha-2}{2(5\alpha-2)}\nu_{2}\nu_{4}\right)k+\nu_{1}^{2}.$

Since
$\left(\nu_{0}^{2}-\frac{9\alpha-2}{2(5\alpha-2)}\nu_{2}\nu_{3}\right)k^{2}$
is the dominant term in the above polynomial, it suffices to show that for
every $\eta$ in an open interval it holds

$\nu_{0}^{2}-\frac{9\alpha-2}{2(5\alpha-2)}\nu_{2}\nu_{3}<0,$ (A.22)

where

$\displaystyle\nu_{0}$
$\displaystyle=2(\eta+1-\alpha)-\frac{1}{4(\alpha-1)}(\alpha+2)(\alpha-2),$
$\displaystyle\nu_{2}\nu_{3}$
$\displaystyle=-\frac{1}{\alpha-1}(5\alpha-2)(\alpha-2)(\eta+1-\alpha).$

This will ensure the existence of some integer $K_{1}(\eta)\geq 1$ such that
$\Delta_{k}\leq 0$ for every $k\geq K_{1}(\eta)$, and further, due to A.1
(ii), that $R_{k}\leq 0$ for every $k\geq K_{1}(\eta)$.

We set $\zeta:=\eta+1-\alpha\leq 0$ and get

$\displaystyle\nu_{0}$
$\displaystyle=2\zeta-\frac{1}{4(\alpha-1)}(\alpha+2)(\alpha-2),$
$\displaystyle\nu_{2}\nu_{3}$
$\displaystyle=-\frac{1}{\alpha-1}(5\alpha-2)(\alpha-2)\zeta,$

and

$\displaystyle\nu_{0}^{2}-\frac{9\alpha-2}{2(5\alpha-2)}\nu_{2}\nu_{3}=$
$\displaystyle\
\left(2\zeta-\frac{(\alpha+2)(\alpha-2)}{4(\alpha-1)}\right)^{2}+\frac{9\alpha-2}{2(5\alpha-2)}\frac{(5\alpha-2)(\alpha-2)}{\alpha-1}\zeta$
$\displaystyle=$ $\displaystyle\
4\zeta^{2}+\frac{(\alpha-2)(7\alpha-6)}{2(\alpha-1)}\zeta+\frac{(\alpha+2)^{2}(\alpha-2)^{2}}{16(\alpha-1)^{2}}.$
(A.23)

The discriminant of this expression is

$\displaystyle\Delta_{\zeta}=\frac{(\alpha-2)^{2}(7\alpha-6)^{2}}{4(\alpha-1)^{2}}-\frac{(\alpha+2)^{2}(\alpha-2)^{2}}{(\alpha-1)^{2}}=\frac{1}{4(\alpha-1)^{2}}(\alpha-2)^{2}(9\alpha-2)(5\alpha-10)>0.$

Hence, in order to guarantee (A.22), we have to choose $\zeta$ between the two
roots of the quadratic function arising in (Proof of Lemma 2.6), in other
words,

$\displaystyle\zeta_{1}(\alpha)$
$\displaystyle:=\frac{1}{8}\left(-\frac{1}{2(\alpha-1)}(\alpha-2)(7\alpha-6)-\sqrt{\Delta_{\zeta}}\right)$
$\displaystyle=-\frac{1}{16(\alpha-1)}(\alpha-2)\left(7\alpha-6+\sqrt{(9\alpha-2)(5\alpha-10)}\right)$
$\displaystyle<\zeta$ $\displaystyle=\eta+1-\alpha<$
$\displaystyle\zeta_{2}(\alpha)$
$\displaystyle:=\frac{1}{8}\left(-\frac{1}{2(\alpha-1)}(\alpha-2)(7\alpha-6)+\sqrt{\Delta_{\zeta}}\right)$
$\displaystyle=-\frac{1}{16(\alpha-1)}(\alpha-2)\left(7\alpha-6-\sqrt{(9\alpha-2)(5\alpha-10)}\right).$

Obviously $\zeta_{1}(\alpha)<0$ and from Vieta formula
$\zeta_{1}(\alpha)\cdot\zeta_{2}(\alpha)=\frac{(\alpha+2)^{2}(\alpha-2)^{2}}{64(\alpha-1)^{2}}>0$,
it follows that $\zeta_{2}(\alpha)<0$. Therefore, in order to be sure that
$\nu_{0}^{2}-\frac{9\alpha-2}{2(5\alpha-2)}\nu_{2}\nu_{3}<0$, $\eta$ must be
chosen such that

$\alpha-1+\zeta_{1}(\alpha)<\eta<\alpha-1+\zeta_{2}(\alpha).$

Next we will show that

$0<\alpha-1-\frac{1}{16(\alpha-1)}(\alpha-2)(7\alpha-6)<\frac{5\alpha}{8}-\frac{1}{4}.$
(A.24)

Indeed, the first inequality follows immediately, since

$\displaystyle\alpha-1-\frac{1}{16(\alpha-1)}(\alpha-2)(7\alpha-6)$
$\displaystyle=\frac{1}{16(\alpha-1)}\left(16(\alpha-1)^{2}-(\alpha-2)(7\alpha-6)\right)$
$\displaystyle=\frac{1}{16(\alpha-1)}\left(\alpha^{2}+4(\alpha-1)(2\alpha-1)\right)>0.$

Using this relation, the second inequality in (A.24) can be equivalently
written as

$\alpha^{2}+4(\alpha-1)(2\alpha-1)<2(\alpha-1)(5\alpha-2)\ \Leftrightarrow\
0<\alpha(\alpha-2),$

which is true as $\alpha>2$.

From (A.24) we immediately deduce that

$0<\alpha-1+\zeta_{2}(\alpha)\qquad\textrm{ and
}\qquad\alpha-1+\zeta_{1}(\alpha)<\frac{5\alpha}{8}-\frac{1}{4}.$

This allows us to define

$\displaystyle\underline{\eta}(\alpha)$
$\displaystyle:=\max\left\\{0,\alpha-1+\zeta_{1}(\alpha)\right\\}$
$\displaystyle=\max\left\\{0,\frac{1}{16(\alpha-1)}\alpha^{2}+\frac{1}{4}(2\alpha-1)-\frac{1}{16(\alpha-1)}(\alpha-2)\sqrt{(9\alpha-2)(5\alpha-10)}\right\\};$
$\displaystyle\overline{\eta}(\alpha)$
$\displaystyle:=\min\left\\{\frac{5}{8}\alpha-\frac{1}{4},\alpha-1+\zeta_{2}(\alpha)\right\\}$
$\displaystyle=\min\left\\{\frac{5}{8}\alpha-\frac{1}{4},\frac{1}{16(\alpha-1)}\alpha^{2}+\frac{1}{4}(2\alpha-1)+\frac{1}{16(\alpha-1)}(\alpha-2)\sqrt{(9\alpha-2)(5\alpha-10)}\right\\},$

and to notice that $\underline{\eta}(\alpha)<\overline{\eta}(\alpha)$. In
conclusion, choosing $\eta$ such that
$\underline{\eta}(\alpha)<\eta<\overline{\eta}(\alpha)$, we have

$\nu_{0}^{2}-\frac{9\alpha-2}{2(5\alpha-2)}\nu_{2}\nu_{3}<0,$

and therefore there exists $K_{1}(\eta)\geq 1$ such that $R_{k}\leq 0$ for
every $k\geq K_{1}(\eta)$. $\blacksquare$

## References

  * [1] F. Alvarez.  On the minimizing property of a second order dissipative system in Hilbert spaces.  SIAM Journal on Control and Optimization, 38(4):1102–1119, 2000\.
  * [2] F. Alvarez.  Weak convergence of a relaxed and inertial hybrid projection-proximal point algorithm for maximal monotone operators in Hilbert space.  SIAM Journal on Optimization, 14(3):773–782, 2003.
  * [3] F. Alvarez and H. Attouch.  An inertial proximal method for maximal monotone operators via discretization of a nonlinear oscillator with damping.  Set-Valued Analysis, 9:3–11, 2001.
  * [4] H. Attouch and A. Cabot.  Convergence rates of inertial forward-backward algorithms.  SIAM Journal on Optimization, 28(1):849–874, 2018.
  * [5] H. Attouch and A. Cabot.  Convergence of a relaxed inertial forward–backward algorithm for structured monotone inclusions.  Applied Mathematics and Optimization, 80(1):547–598, 2019.
  * [6] H. Attouch, X. Goudou, and P. Redont.  The heavy ball with friction method: I. the continuous dynamical system.  Communications in Contemporary Mathematics, 2(1):1–34, 2000.
  * [7] H. Attouch and J. Peypouquet.  The rate of convergence of Nesterov’s accelerated forward-backward method is actually faster than $1/k^{2}$.  SIAM Journal on Optimization, 26(3):1824–1834, 2016.
  * [8] H. Attouch and J. Peypouquet.  Convergence of inertial dynamics and proximal algorithms governed by maximally monotone operators.  Mathematical Programming, 174:391–432, 2019.
  * [9] J. B. Baillon and R. E. Bruck.  The rate of asymptotic regularity is $o(1/\sqrt{n})$.  In Theory and Applications of Nonlinear Operators of Accretive and Monotone Types, volume 178, pages 51–81. Dekker, 1996.
  * [10] H. H. Bauschke and P. L. Combettes.  Convex Analysis and Monotone Operator Theory in Hilbert Spaces.  Springer, London, 2017.
  * [11] A. Beck and M. Teboulle.  A fast iterative shrinkage-thresholding algorithm for linear inverse problems.  SIAM Journal on Imaging Sciences, 2(1):183–202, 2009.
  * [12] R. I. Boţ.  Conjugate Duality in Convex Optimization.  Springer, Berlin, 2010.
  * [13] R. I. Boţ, E. R. Csetnek, and D. K. Nguyen.  Fast Optimistic Gradient Descent Ascent (OGDA) method in continuous and discrete time.  Foundations of Computational Mathematics, 2023.
  * [14] R. I. Boţ and D. K. Nguyen.  Improved convergence rates and trajectory convergence for primal-dual dynamical systems with vanishing damping.  Journal of Differential Equations, 303:369–406, 2021.
  * [15] R. I. Boţ and D. K. Nguyen.  Fast Krasnosel’skiĭ-Mann algorithm with a convergence rate of the fixed point iteration of $o(\frac{1}{k})$.  SIAM Journal on Numerical Analysis, 61(6):2813–2843, 2023.
  * [16] M. Bravo and R. Cominetti.  Sharp convergence rates for averaged nonexpansive maps.  Israel Journal of Mathematics, 227:163–188, 2018.
  * [17] Y. Cai and W. Q. Zheng.  Accelerated single-call methods for constrained min-max optimization.  The 11th International Conference on Learning Representations (ICLR), 2023.
  * [18] A. Chambolle and C. Dossal.  On the convergence of the iterates of the “fast iterative shrinkage/thresholding algorithm”.  Journal of Optimization Theory and Applications, 166(3):968–982, 2015.
  * [19] G. H.-G. Chen and R. T. Rockafellar.  Convergence rates in forward-backward splitting.  SIAM Journal on Optimization, 7(2):421–444, 1997.
  * [20] P. L. Combettes and J. C. Pesquet.  A Douglas-Rachford splitting approach to nonsmooth convex variational signal recovery.  IEEE Journal of Selected Topics in Signal Processing, 1(4):564–574, 2007.
  * [21] P. L. Combettes and B. C. Vũ.  Variable metric forward-backward splitting with applications to monotone inclusions in duality.  Optimization, 63(9):1289–1318, 2014.
  * [22] P. L. Combettes and V. R. Wajs.  Signal recovery by proximal forward-backward splitting.  Multiscale Modeling and Simulation, 4(4):1168–1200, 2005.
  * [23] P. L. Combettes and I. Yamada.  Compositions and convex combinations of averaged nonexpansive operators.  Journal of Mathematical Analysis and Applications, 425(1):55–70, 2015.
  * [24] D. Davis and W. Yin.  Convergence rate analysis of several splitting schemes.  In R Glowinski, S. J. Osher, and W. Yin, editors, Splitting Methods in Communication, Imaging, Science, and Engineering, pages 115–163. Springer International Publishing, 2016.
  * [25] B. Halpern.  Fixed points of nonexpanding maps.  Bulletin of the American Mathematical Society, 73(6):957–961, 1967\.