# Symplectic Extra-gradient Type Method for Solving General Non-monotone
Inclusion Problem ††thanks: This work was partially supported by grant
12288201 from NSF of China.

Ya-xiang Yuan  Institute of Computational Mathematics and
Scientific/Engineering Computing, Academy of Mathematics and Systems Science,
Chinese Academy of Sciences, Beijing 100190, China  Yi Zhang Corresponding
author<EMAIL_ADDRESS>University of Chinese Academy of Sciences,
Beijing 100049, China

###### Abstract

In recent years, accelerated extra-gradient methods have attracted much
attention by researchers, for solving monotone inclusion problems. A
limitation of most current accelerated extra-gradient methods lies in their
direct utilization of the initial point, which can potentially decelerate
numerical convergence rate. In this work, we present a new accelerated extra-
gradient method, by utilizing the symplectic acceleration technique. We
establish the inverse of quadratic convergence rate by employing the Lyapunov
function technique. Also, we demonstrate a faster inverse of quadratic
convergence rate alongside its weak convergence property under stronger
assumptions. To improve practical efficiency, we introduce a line search
technique for our symplectic extra-gradient method. Theoretically, we prove
the convergence of the symplectic extra-gradient method with line search.
Numerical tests show that this adaptation exhibits faster convergence rates in
practice compared to several existing extra-gradient type methods.

_K_ eywords Extra-gradient method $\cdot$ Symplectic acceleration $\cdot$
Lyapunov function $\cdot$ Comonotone operator

##  1 Introduction

Min-max problem and min-max duality theory lie at the foundations of game
theory, designing algorithms [34, 39] and duality theory of mathematical
programming [12], and have found far-reaching applications across a range of
disciplines, including decision theory [21], economics [36], structural design
[29], control theory [35] and robust optimization [3]. Recently, as burgeoning
of Generative Adversarial Networks [7, 8] and adversarial attacks [17],
solving min-max problem under nonconvex-nonconcave assumption has gained
researchers’ attention. However, due to the nonconvex-nonconcave assumption,
solving min-max problem exactly is nearly impossible. Similar to nonlinear
programming, solving first-order stationary point of nonconvex-nonconcave min-
max problem is relatively easier. The first-order stationary condition of most
min-max problems can be described by the following inclusion problem

$0\in T(z):=F(z)+G(z),\quad z\in\mathcal{H},$ (1)

where $\mathcal{H}$ is a real Hilbert space equipped with inner product
$\left\langle\cdot,\cdot\right\rangle$ and norm
$\left\|\cdot\right\|=\sqrt{\left\langle\cdot,\cdot\right\rangle}$. Let
$\mathrm{zero}(T)$ be the set of all solutions of (1). Throughout this paper,
we assume $F:\mathcal{H}\to\mathcal{H}$ is a single-value $L-$Lipschitz
continuous operator, $G:\mathcal{H}\to 2^{\mathcal{H}}$ is a set-valued
maximally monotone operator and $\mathrm{zero}(T)$ is non-empty.

When $G=0$, $F$ is monotone and $L-$Lipschitz continuous, the extra-gradient
(EG) method proposed in [15] and [26] is an efficient method for solving (1).
Theoretically, the EG method has $O(1/k)$ ergodic convergence rate without
additional requirement on $F$. Practically, the EG method can be described as
applying gradient descent step twice per iteration. Owning to its fascinating
theoretical properties and simple recursive rule, extensions of the EG method
have been studied, such as the mirror-prox method in [13] and [23] when $G$ is
the normal cone of convex set $C$, the Tseng’s splitting method or forward-
backward splitting method in [28] and [33] when $G\neq 0$ and the EG+ method
[5] to solve (1) under non-monotone assumption. The adaptive EG+ method
proposed in [6] and [25] further generalizes the EG+ method by considering an
adaptive step-size. Here, we refer to the survey [31] of the EG method for
more existing theory about the EG method. As stochastic optimization continues
to gain significant attention, research on stochastic extra-gradient method
has seen a rise, such as [9], [11], [14] and [19].

Nesterov’s accelerated gradient method [24] has stimulated research on
acceleration technique. The first acceleration form of EG method for solving
monotone inclusion problem, called extra anchored gradient (EAG) algorithm,
was presented by [37]. From the observation that the EG method is closed to
proximal point algorithm [20], [37] uses the Halpern’s iteration [5, 10, 27],
which is a widely studied acceleration technique for the proximal point
algorithm, to derive the EAG algorithm. Also, the complexity lower bound of EG
type method was proven to be $O(1/k^{2})$ in [37]. Nowadays, studies of
acceleration form of the EG method have increased. [16] combined the EAG
algorithm and the EG+ method and obtained the fast EG method, which can solve
(1) under non-monotone assumption. [4] obtained an accelerated forward-
backward splitting method by further generalizing the fast EG method.

However, the EAG type method is prone to oscillatory phenomena, which
eventually slows down numerical performance. That is because the Halpern’s
iteration can be characterized as calculating convex combination of the
initial starting point and the current feasible point. The use of the initial
starting point may cause the current feasible point far away from the solution
set, leading to oscillation phenomena.

###  1.1 Our Contributions

In Section 3, we exploit a recently proposed acceleration method, called
_symplectic acceleration_ [38], to devise a novel accelerated variant of the
extra-gradient method, named _Symplectic Extra-Gradient (SEG) Method_.
Capitalizing on the Lyapunov function framework proposed in [38], we establish
that both the SEG and its extended versions exhibit a convergence rate of
$O(1/k^{2})$. Moreover, in Section 4, we demonstrate that by imposing stricter
conditions, we can prove the SEG type methods admits a faster $o(1/k^{2})$
convergence rate and weak convergence property. To the best of our knowledge,
the SEG type method is the first EG type method with proved $o(1/k^{2})$
convergence rate. A concise summary of these theoretical results is presented
in Table 1.

Methods | Convergence Rate | Weak Convergence Property
---|---|---
EG+ [5] | $O(1/k)$ | -
FEG [16] | $O(1/k^{2})$ | -
SEG+ (This paper) | $o(1/k^{2})$ | ✓
Table 1: Illustration of theoretical results in this paper.

In Section 5, we address the challenge posed by the difficulty in precisely
estimating the Lipschitz constant and the comonotone index, as well as
handling situations involving rapid variations in both the local Lipschitz
constant and the local comonotone index. To this end, we integrate the line
search framework into the SEG framework. Under specified assumptions, we prove
the convergence of the SEG method equipped with line search. Our numerical
experiments demonstrate that our method performs better than several existing
EG type methods.

##  2 Preliminaries

###  2.1 Basic Concepts

Let $\mathcal{H}$ be a real Hilbert space, and let $T:\mathcal{H}\to
2^{\mathcal{H}}$ is a set-valued operator. The operator $T$ is said to be
_$\rho-$ comonotone_ if

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

When $\rho=0$, the concept of $0-$comonotone coincide with the concept of
monotone. If $\rho>0$, $\rho-$comonotone is the same as $\rho-$coercive. A
monotone operator $G$ is _maximally_ if the graph of $G$ is not a proper
subset of the graph of another monotone operator. The Minty surjectivity
theorem [18] shows that a monotone operator $G$ is maximal if and only if the
domain of resolvent $J_{G}=(I+G)^{-1}$ of $G$ is $\mathcal{H}$. Also, a
continuous and monotone single-value operator is a maximally monotone
operator. For further theories on comonotone operator, we refer to [2].

###  2.2 Extra-gradient Method and Extra-gradient+ Method

The extra-gradient method for solving zero-point of $L-$Lipschitz continuous
and monotone operator $F$, i. e. solving

$0=F(z),$

is given as follows:

$\begin{split}z_{k+\frac{1}{2}}&=z_{k}-sF(z_{k}),\\\
z_{k+1}&=z_{k}-sF(z_{k+\frac{1}{2}}).\end{split}$ (2)

In [15] and [32], the proof of convergence results of EG method is based on
the following inequality:

$\left\|z_{k+1}-z^{*}\right\|^{2}\leqslant\left\|z_{k}-z^{*}\right\|^{2}-(1-s^{2}L^{2})\left\|F(z_{k})\right\|^{2},\quad\forall
0=F(z^{*}).$

By summing the above inequality respect to $k$, one can easily show that the
ergodic convergence rate of the EG method on $\left\|F(z_{k})\right\|^{2}$ is
$O(1/k)$ when $0<s<\dfrac{1}{L}$. The result that the sequence $\\{z_{k}\\}$
converges weakly to a zero-point of $F$ relies on the following propositions.

######  Proposition 1 (Lemma 2.47 in [1]).

Let $\\{z_{k}\\}$ be a sequence in $\mathcal{H}$ and let $C$ be a nonempty
subset of $\mathcal{H}$. Suppose that, for every $z\in C$,
$\left\|z_{k}-z\right\|$ converges and that every weak sequential cluster
point of $\\{z_{k}\\}$ belongs to $C$. Then $\\{z_{k}\\}$ converges weakly to
a point in $C$.

######  Proposition 2 (Proposition 20.38 (ii) in [1]).

Let $T:\mathcal{H}\to 2^{\mathcal{H}}$ be a maximally monotone operator,
$\\{z_{k}\\}$ and $\\{v_{k}\\}$ be the sequences in $\mathcal{H}$ such that
$v_{k}\in T(z_{k})$. If $z_{k}\rightharpoonup z$ and $v_{k}\to v$. Then $v\in
T(z)$.

The details of the proof of weak convergence property of the EG method can be
found in [22]. The EG+ method proposed in [5] for solving zero-point of
$L-$Lipschitz continuous and $\rho-$comonotone operator $F$ is given as
follows:

$\begin{split}z_{k+\frac{1}{2}}&=z_{k}-\frac{s}{\beta}F(z_{k}),\\\
z_{k+1}&=z_{k}-sF(z_{k+\frac{1}{2}}).\end{split}$ (3)

Similar to the EG method, [5] shows that if
$\beta=\dfrac{1}{2},s=\dfrac{1}{2L}$, $\rho>-\dfrac{1}{8L}$, then we have

$\left\|z_{k+1}-z^{*}\right\|^{2}\leqslant\left\|z_{k}-z^{*}\right\|-\frac{1}{4L}\left(\frac{1}{4L}+2\rho\right)\left\|F(z_{k+\frac{1}{2}})\right\|^{2},\quad\forall
0=F(z^{*}).$

By using the above inequality respect to $k$, one can prove the ergodic
convergence rate of the EG+ method.

###  2.3 Anchor Acceleration

Since [20] suggested that the sequence generated by the EG method is closed to
the sequence generated by the proximal point algorithm, recent study of
acceleration form of the EG method is based on existing acceleration technique
for proximal point algorithm. Among most acceleration form of proximal point
algorithm, the Halpern’s iteration [10] is one of the most wildly studied
acceleration technique. The Halpern’s iteration for solving zero-point of
maximally monotone operator $F$ is

$z_{k+1}=\alpha_{k}z_{0}+(1-\alpha_{k})J_{F}(z_{k}).$ (4)

Replacing the proximal point term by the EG step, we obtain the extra anchored
gradient algorithm [37]:

$\begin{split}z_{k+\frac{1}{2}}&=\alpha_{k}z_{0}+(1-\alpha_{k})z_{k}-\beta_{k}F(z_{k}),\\\
z_{k+1}&=\alpha_{k}z_{0}+(1-\alpha_{k})z_{k}-\beta_{k}F(z_{k+\frac{1}{2}}).\end{split}$
(5)

In [37], (5) was proven to be $O(1/k^{2})$ convergence rate if $F$ is an
$L-$Lipschitz continuous and monotone operator and the parameters in (5)
satisfy several assumptions. Combining the EG+ method and (5), [16] gave the
fast EG (FEG) method as follows:

$\begin{split}z_{k+\frac{1}{2}}&=\alpha_{k}z_{0}+(1-\alpha_{k})z_{k}-(1-\alpha_{k})\left(\frac{1}{L}+2\rho\right)F(z_{k}),\\\
z_{k+1}&=\alpha_{k}z_{0}+(1-\alpha_{k})z_{k}-\frac{1}{L}F(z_{k+\frac{1}{2}})-(1-\alpha_{k})2\rho
F(z_{k}).\end{split}$ (6)

If $\alpha_{k}=\dfrac{1}{k+1}$, (6) admits $O(1/k^{2})$ convergence rate. The
convergence results of accelerated forward-backward splitting method in [4] is
similar to the convergence results (6).

###  2.4 Symplectic Acceleration

The symplectic acceleration technique proposed in [38] is a new way to
accelerate proximal point algorithm. The symplectic proximal point algorithm
for solving zero-point of maximally monotone operator $F$ is given as follows:

$\begin{split}\tilde{z}_{k+1}&=\frac{k}{k+r}z_{k}+\frac{r}{k+r}u_{k},\\\
z_{k+1}&=J_{F}(z_{k}),\\\
u_{k+1}&=u_{k}+\frac{D}{r}(z_{k+1}-\tilde{z}_{k+1}).\end{split}$ (7)

The reason why (7) is called symplectic proximal point algorithm is that (7)
is obtained by applying first-order implicit symplectic method to a first-
order ODEs system. If $r>1$, $0<D<r-1$, then (7) admits $O(1/k^{2})$
convergence rate. Moreover, $o(1/k^{2})$ convergence rate and weak convergence
property of (7) can be established by considering two auxiliary functions.

##  3 Symplectic Extra-gradient Type Method

In this section, we introduce the symplectic extra-gradient+ framework for
solving general inclusion problem

$0\in T(z):=F(z)+G(z).$

At first, we explain how to propose symplectic extra-gradient framework by
considering the zero-point problem $0=F(z)$. In Section 2.4, we introduce the
symplectic proximal point algorithm (7). (7) can be generalized as follows:

$\begin{split}\tilde{z}_{k+1}&=(1-\alpha_{k})z_{k}+\alpha_{k}u_{k},\\\
z_{k+1}&=J_{F}(\tilde{z}_{k+1}),\\\
u_{k+1}&=u_{k}+C_{k}(z_{k+1}-\tilde{z}_{k+1}).\end{split}$ (8)

To formulate the desired algorithm, we need a two-step modification to
equation (8). Due to the fact that $\tilde{z}_{k+1}-z_{k+1}=F(z_{k+1})$, the
update rule for $u_{k+1}$ is transformed to

$u_{k+1}=u_{k}-C_{k}F(z_{k+1}).$

Moreover, similar to (5), we replace the proximal point step by the EG step
and obtain the _symplectic extra-gradient (SEG) method_ described as follows:

$\displaystyle\tilde{z}_{k+1}$
$\displaystyle=(1-\alpha_{k})z_{k}+\alpha_{k}u_{k},$ (9a) $\displaystyle
z_{k+\frac{1}{2}}$ $\displaystyle=\tilde{z}_{k+1}-\beta_{k}F(z_{k}),$ (9b)
$\displaystyle z_{k+1}$
$\displaystyle=\tilde{z}_{k+1}-\beta_{k}F(z_{k+\frac{1}{2}}),$ (9c)
$\displaystyle u_{k+1}$ $\displaystyle=u_{k}-C_{k}F(z_{k+1}).$ (9d)

The coefficients $\\{\alpha_{k}\\},\\{\beta_{k}\\}$ in (9) are positive for
all $k\geqslant 1$. First, we notice that if we does not impose any constrains
on $\\{\alpha_{k}\\}$ and $\\{C_{k}\\}$, the EG method and EAG algorithm can
be included in (9). Specifically, let $\alpha_{k}\equiv
1,\beta_{k}\equiv\dfrac{1}{L}$, (9) can be simplified as (2), and let
$C_{k}\equiv 0$, (9) is the same as (5). However, it is noteworthy that
despite the apparent requirement of three gradient evaluations per iteration
in (9), a strategic reordering of the iterative process can economize
computations to merely two gradient evaluations per loop. This is achieved
through the adoption of the following alternative iteration rule:

$\displaystyle u_{k+1}$ $\displaystyle=u_{k}-C_{k}F(z_{k}),$
$\displaystyle\tilde{z}_{k+1}$
$\displaystyle=(1-\alpha_{k})z_{k}+\alpha_{k}u_{k+1},$ $\displaystyle
z_{k+\frac{1}{2}}$ $\displaystyle=\tilde{z}_{k+1}-\beta_{k}F(z_{k}),$
$\displaystyle z_{k+1}$
$\displaystyle=\tilde{z}_{k+1}-\beta_{k}F(z_{k+\frac{1}{2}}).$

The employment of such a reordering methodology can decrease the quantity of
necessary gradient evaluations within subsequent algorithms. Consequently,
further expounding on this technique will be omitted in the remaining text.

It should be noted that the SEG method is only suitable for solving zero-point
of $F$ under monotone assumption, coupled with complicate convergence results
discussed in Section A. As such, we focus on the symplectic extra-gradient+
framework in the remaining text. Inspired by the FEG method (6) proposed in
[16], the corresponding _symplectic extra-gradient+ (SEG+) method_ for solving
zero-point of $L-$Lipschitz continuous and $\rho-$comonotone operator $F$ is
given as follows:

$\displaystyle\tilde{z}_{k+1}$
$\displaystyle=(1-\alpha_{k})z_{k}+\alpha_{k}u_{k},$ (10a) $\displaystyle
z_{k+\frac{1}{2}}$
$\displaystyle=\tilde{z}_{k+1}-(1-\alpha_{k})\left(\frac{1}{L}+2\rho\right)F(z_{k}),$
(10b) $\displaystyle z_{k+1}$
$\displaystyle=\tilde{z}_{k+1}-\dfrac{1}{L}F(z_{k+\frac{1}{2}})-(1-\alpha_{k})2\rho
F(z_{k}),$ (10c) $\displaystyle u_{k+1}$
$\displaystyle=u_{k}-C_{k}F(z_{k+1}).$ (10d)

Motivated by Tseng’s splitting algorithm [33] and the accelerated forward-
backward splitting method [4], we can further generalize the SEG+ method and
propose the _symplectic forward-backward splitting (SFBS) method_ with
$\alpha_{k}=\dfrac{r}{k+r}$ and $C_{k}=\dfrac{D}{r}$, which is described in
Algorithm 1.

Input:  Operators $F$ and $G$,
$L\in(0,+\infty),\rho\in\left(-\dfrac{1}{2L},+\infty\right)$;

Initialization: $z_{0}$, $u_{0}=z_{0}$, $\tilde{G}_{0}=0$;

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

$\tilde{z}_{k+1}=\dfrac{k}{k+r}z_{k}+\dfrac{r}{k+r}u_{k}$;

$z_{k+\frac{1}{2}}=\tilde{z}_{k+1}-\dfrac{k}{k+r}\left(\dfrac{1}{L}+2\rho\right)(F(z_{k})+\tilde{G}_{k})$;

$z_{k+1}=J_{L^{-1}G}\left(\tilde{z}_{k+1}-\dfrac{1}{L}F(z_{k+\frac{1}{2}})-\dfrac{2\rho
k}{k+r}(F(z_{k})+\tilde{G}_{k})\right)$;

$\tilde{G}_{k+1}=L\left[\tilde{z}_{k+1}-z_{k+1}-\dfrac{1}{L}F(z_{k+\frac{1}{2}})-\dfrac{2\rho
k}{k+r}(F(z_{k})+\tilde{G}_{k})\right]$;

$u_{k+1}=u_{k}-\dfrac{D}{r}(F(z_{k+1})+\tilde{G}_{k+1})$.

Algorithm 1 Symplectic Forward-Backward Splitting Method, SFBS

Next, we apply the Lyapunov function technique to demonstrate the convergence
rates of (10). Here, inspired by the Lyapunov function in [16] for proving the
convergence rates of the FEG method and the Lyapunov function in [38] for
proving the convergence rates of the symplectic proximal point algorithm, the
Lyapunov function for Algorithm 1 is

$\begin{split}\mathcal{E}(k):=&\ \left[\frac{Dk^{2}}{2L}+\rho
Dk(k-r)\right]\left\|F(z_{k})+\tilde{G}_{k}\right\|^{2}\\\ &\ +Drk\left\langle
F(z_{k})+\tilde{G}_{k},z_{k}-u_{k}\right\rangle+\frac{r^{3}-r^{2}}{2}\left\|u_{k}-z^{*}\right\|^{2},\end{split}$
(11)

where $z^{*}\in\mathrm{zero}(T)$. Given the fundamental role that the
difference of the Lyapunov function, i. e. $\mathcal{E}(k+1)-\mathcal{E}(k)$,
plays in establishing convergence rates for (10), it becomes imperative to
estimate the upper bound of the difference. By estimating the upper bound of
$\mathcal{E}(k+1)-\mathcal{E}(k)$, we can give the convergence results of
Algorithm 1 in Theorem 1.

######  Theorem 1.

Let $\\{z_{k}\\}$ and $\\{u_{k}\\}$ be the sequences generated by Algorithm 1.
If $r>1$ and $0<D\leqslant(r-1)\left(\dfrac{1}{L}+2\rho\right)$, then we have

$\left(\frac{1}{2L}+\rho-\frac{D}{2(r-1)}\right)k^{2}\mathrm{dist}(0,T(z_{k}))^{2}\leqslant\frac{r^{3}-r^{2}}{2D}\cdot\mathrm{dist}(z_{0},\mathrm{zero}(T))^{2},\quad\forall
k\geqslant 1.$

Thus if $D<(r-1)\left(\dfrac{1}{L}+2\rho\right)$, the last-iterate convergence
rate of Algorithm 1 is

$\mathrm{dist}(0,T(z_{k}))^{2}\leqslant\frac{(r-1)^{2}r^{2}}{\left[(r-1)\left(\dfrac{1}{L}+2\rho\right)D-D^{2}\right]k^{2}}\cdot\mathrm{dist}(z_{0},\mathrm{zero}(T))^{2},\quad\forall
k\geqslant 1.$

In addition, we have

$\displaystyle\
\sum_{k=0}^{\infty}\frac{1}{2}\left[(r-1)\left(\frac{1}{L}+2\rho\right)-D\right](2k+r+1)\left\|F(z_{k+1})+\tilde{G}_{k+1}\right\|^{2}$
$\displaystyle\leqslant$ $\displaystyle\
\frac{r^{3}-r^{2}}{2D}\cdot\mathrm{dist}(z_{0},\mathrm{zero}(T))^{2}.$

###### Proof.

Let $\tilde{T}(z_{k})=F(z_{k})+\tilde{G}_{k}$. By the definition of
$\tilde{G}_{k}$, we have

$\displaystyle z_{k+1}$
$\displaystyle=\tilde{z}_{k+1}-\frac{1}{L}[F(z_{k+\frac{1}{2}})+\tilde{G}_{k+1}]-\frac{2\rho
k}{k+r}\tilde{T}(z_{k}).$

With above equation, we obtain the following useful equations

$\displaystyle k(z_{k+1}-z_{k})$
$\displaystyle=r(u_{k}-z_{k+1})-\frac{k+r}{L}[F(z_{k+\frac{1}{2}})+\tilde{G}_{k+1}]-2\rho
k\tilde{T}(z_{k}),$ (12) $\displaystyle r(z_{k}-u_{k})$
$\displaystyle=-(k+r)(z_{k+1}-z_{k})-\frac{k+r}{L}[F(z_{k+\frac{1}{2}})+\tilde{G}_{k+1}]-2\rho
k\tilde{T}(z_{k}).$ (13)

Also, by $L-$Lipschitz continuity of $F$, we have

$\left\|F(z_{k+1})-F(z_{k+\frac{1}{2}})\right\|^{2}\leqslant
L^{2}\left\|z_{k+1}-z_{k+\frac{1}{2}}\right\|^{2}.$

Since

$z_{k+1}-z_{k+\frac{1}{2}}=\frac{1}{L}\left[\frac{k}{k+r}\tilde{T}(z_{k})-F(z_{k+\frac{1}{2}})-\tilde{G}_{k+1}\right],$

we have

$\left\|F(z_{k+1})-F(z_{k+\frac{1}{2}})\right\|^{2}\leqslant\left\|\frac{k}{k+r}\tilde{T}(z_{k})-F(z_{k+\frac{1}{2}})-\tilde{G}_{k+1}\right\|^{2}.$
(14)

Recall the Lyapunov function

$\mathcal{E}(k)=\left[\frac{Dk^{2}}{2L}+\rho
Dk(k-r)\right]\left\|\tilde{T}(z_{k})\right\|^{2}+Drk\left\langle\tilde{T}(z_{k}),z_{k}-u_{k}\right\rangle+\frac{r^{3}-r^{2}}{2}\left\|u_{k}-z^{*}\right\|^{2}.$

First, we divide the difference $\mathcal{E}(k+1)-\mathcal{E}(k)$ into three
parts.

$\displaystyle\ \mathcal{E}(k+1)-\mathcal{E}(k)$ $\displaystyle=$
$\displaystyle\ \underbrace{\left[\frac{D(k+1)^{2}}{2L}+\rho
D(k+1)(k+1-r)\right]\left\|\tilde{T}(z_{k+1})\right\|^{2}-\left[\frac{Dk^{2}}{2L}+\rho
Dk(k-r)\right]\left\|\tilde{T}(z_{k})\right\|^{2}}_{\text{I}}$ $\displaystyle\
+\underbrace{Dr(k+1)\left\langle\tilde{T}(z_{k+1}),z_{k+1}-u_{k+1}\right\rangle-
Drk\left\langle\tilde{T}(z_{k}),z_{k}-u_{k}\right\rangle}_{\text{II}}$
$\displaystyle\
+\underbrace{\frac{r^{3}-r^{2}}{2}\left[\left\|u_{k+1}-z^{*}\right\|^{2}-\left\|u_{k}-z^{*}\right\|^{2}\right]}_{\text{III}}.$

Secondly, we reckon the upper bound of II and III. First we consider II.

$\displaystyle\text{II}=$ $\displaystyle\
Dr\left\langle\tilde{T}(z_{k+1}),z_{k+1}-u_{k+1}\right\rangle+Drk\left\langle\tilde{T}(z_{k+1}),z_{k+1}-z_{k}-u_{k+1}+u_{k}\right\rangle$
$\displaystyle\
+Drk\left\langle\tilde{T}(z_{k+1})-\tilde{T}(z_{k}),z_{k}-u_{k}\right\rangle.$

Due to (12) and the equality
$u_{k+1}-u_{k}=-\dfrac{D}{r}[F(z_{k+1})+\tilde{G}_{k+1}]$, we have

$\begin{split}&\
Drk\left\langle\tilde{T}(z_{k+1}),z_{k+1}-z_{k}-u_{k+1}+u_{k}\right\rangle\\\
=&\
Dr\left\langle\tilde{T}(z_{k+1}),r(u_{k}-z_{k+1})-\frac{k+r}{L}[F(z_{k+\frac{1}{2}})+\tilde{G}_{k+1}]-2\rho
k\tilde{T}(z_{k})\right\rangle\\\ &\
+D^{2}k\left\|\tilde{T}(z_{k+1})\right\|^{2}.\end{split}$ (15)

In addition, because of (13), we have

$\begin{split}&\
Drk\left\langle\tilde{T}(z_{k+1})-\tilde{T}(z_{k}),z_{k}-u_{k}\right\rangle\\\
=&\
Dk\left\langle\tilde{T}(z_{k+1})-\tilde{T}(z_{k}),-(k+r)(z_{k+1}-z_{k})-\frac{k+r}{L}[F(z_{k+\frac{1}{2}})+\tilde{G}_{k+1}]-2\rho
k\tilde{T}(z_{k})\right\rangle.\end{split}$ (16)

Also,

$Dr\left\langle\tilde{T}(z_{k+1}),z_{k+1}-u_{k+1}\right\rangle=D^{2}\left\|\tilde{T}(z_{k+1})\right\|^{2}+Dr\left\langle\tilde{T}(z_{k+1}),z_{k+1}-u_{k}\right\rangle.$
(17)

By summing (45), (46) and (47), we have

II $\displaystyle=$ $\displaystyle\ -\frac{D(k+r)^{2}}{L}\left\langle
F(z_{k+1}),F(z_{k+\frac{1}{2}})\right\rangle+\frac{D}{L}\left\langle
F(z_{k+\frac{1}{2}}),k(k+r)\tilde{T}(z_{k})-(k+r)^{2}\tilde{G}_{k+1}\right\rangle$
$\displaystyle\
+\frac{D}{L}\left\langle\tilde{G}_{k+1},k(k+r)\tilde{T}(z_{k})-(k+r)^{2}\tilde{T}(z_{k+1})\right\rangle$
$\displaystyle\
+D^{2}(k+1)\left\|\tilde{T}(z_{k+1})\right\|^{2}-Dk(k+r)\left\langle\tilde{T}(z_{k+1})-\tilde{T}(z_{k}),z_{k+1}-z_{k}\right\rangle$
$\displaystyle\ -2D\rho
k(k+r)\left\langle\tilde{T}(z_{k+1}),\tilde{T}(z_{k})\right\rangle+2D\rho
k^{2}\left\|\tilde{T}(z_{k})\right\|^{2}$ $\displaystyle\
+D(r-r^{2})\left\langle\tilde{T}(z_{k+1}),z_{k+1}-u_{k}\right\rangle.$

Combining $\rho-$comonotonicity of $F$, (14) and the following equality

$-\left\langle
F(z_{k+1}),F(z_{k+\frac{1}{2}})\right\rangle=\frac{1}{2}\left[\left\|F(z_{k+1})-F(z_{k+\frac{1}{2}})\right\|^{2}-\left\|F(z_{k+1})\right\|^{2}-\left\|F(z_{k+\frac{1}{2}})\right\|^{2}\right],$

we obtain the following estimation

$\displaystyle\text{II}\leqslant$
$\displaystyle-\frac{D(k+r)^{2}}{2L}\left\|\tilde{T}(z_{k+1})\right\|^{2}-\rho
Dk(k+r)\left(\left\|\tilde{T}(z_{k+1})\right\|^{2}+\left\|\tilde{T}(z_{k})\right\|^{2}\right)$
$\displaystyle+\underbrace{D(r-r^{2})\left\langle\tilde{T}(z_{k+1}),z_{k+1}-u_{k}\right\rangle}_{\text{II}_{1}}+D^{2}(k+1)\left\|\tilde{T}(z_{k+1})\right\|^{2}+\frac{Dk^{2}}{2L}\left\|\tilde{T}(z_{k})\right\|^{2}.$

Now estimate III. Owing to the equation

$\frac{1}{2}\left\|a\right\|^{2}-\frac{1}{2}\left\|b\right\|^{2}=\left\langle
a-b,b\right\rangle+\frac{1}{2}\left\|a-b\right\|^{2},$ (18)

we have

III $\displaystyle=(r^{3}-r^{2})\left\langle
u_{k+1}-u_{k},u_{k}-z^{*}\right\rangle+\frac{r^{3}-r^{2}}{2}\left\|u_{k+1}-u_{k}\right\|^{2}$
$\displaystyle=-\underbrace{D(r^{2}-r)\left\langle\tilde{T}(z_{k+1}),u_{k}-z^{*}\right\rangle}_{\text{III}_{1}}+\frac{D^{2}(r-1)}{2}\left\|\tilde{T}(z_{k+1})\right\|^{2}.$

By summing previous estimation, we can deduce the upper bound of
$\mathcal{E}(k+1)-\mathcal{E}(k)$. Since

$\text{II}_{1}-\text{III}_{1}=-D(r^{2}-r)\left\langle\tilde{T}(z_{k+1}),z_{k+1}-z^{*}\right\rangle,$

the upper bound of $\mathcal{E}(k+1)-\mathcal{E}(k)$ can be simplified as
follows:

$\displaystyle\mathcal{E}(k+1)-\mathcal{E}(k)$ $\displaystyle\leqslant$
$\displaystyle\left[-(r-1)\left(\frac{1}{L}+2\rho\right)Dk+D^{2}k-\frac{Dr^{2}-D}{2L}+\rho
D(1-r)+\frac{D^{2}(r+1)}{2}\right]\left\|\tilde{T}(z_{k+1})\right\|^{2}$
$\displaystyle-D(r^{2}-r)\left\langle
F(z_{k+1})+\tilde{G}_{k+1},z_{k+1}-z^{*}\right\rangle$
$\displaystyle\leqslant$
$\displaystyle-\frac{D}{2}\left[(r-1)\left(\frac{1}{L}+2\rho\right)-D\right](2k+r+1)\left\|\tilde{T}(z_{k+1})\right\|^{2}.$

Since $r>1$, $D\leqslant(r-1)\left(\dfrac{1}{L}+2\rho\right)$, we have

$\mathcal{E}(k+1)-\mathcal{E}(k)\leqslant 0.$

Finally, we can obtain the convergence rates of Algorithm 1. First, we
translate $\mathcal{E}(k)$ into the following form.

$\displaystyle\mathcal{E}(k)=$ $\displaystyle\left[\frac{Dk^{2}}{2L}+\rho
Dk(k-r)-\frac{D^{2}k^{2}}{2(r-1)}\right]\left\|\tilde{T}(z_{k})\right\|^{2}+Drk\left\langle\tilde{T}(z_{k}),z_{k}-z^{*}\right\rangle$
$\displaystyle+\frac{1}{2}\left\|\frac{Dk}{\sqrt{r-1}}\tilde{T}(z_{k})-\sqrt{r^{3}-r^{2}}(u_{k}-z^{*})\right\|^{2}.$

By $\rho-$comonotonicity of $T$, we have

$\displaystyle\mathcal{E}(k)\geqslant$ $\displaystyle\
\left[\left(\frac{1}{2L}+\rho\right)Dk^{2}-\frac{D^{2}k^{2}}{2(r-1)}\right]\left\|\tilde{T}(z_{k})\right\|^{2}$
$\displaystyle\
+\frac{1}{2}\left\|\frac{Dk}{\sqrt{r-1}}\tilde{T}(z_{k})-\sqrt{r^{3}-r^{2}}(u_{k}-z^{*})\right\|^{2}.$

Since $D\leqslant(r-1)\left(\dfrac{1}{L}+2\rho\right)$,
$\left(\dfrac{1}{2L}+\rho\right)Dk^{2}-\dfrac{D^{2}k^{2}}{2(r-1)}\geqslant 0$.
Thus $\mathcal{E}(k)\geqslant 0$ and

$\left[\left(\frac{1}{2L}+\rho\right)Dk^{2}-\frac{D^{2}k^{2}}{2(r-1)}\right]\left\|\tilde{T}(z_{k})\right\|^{2}\leqslant\mathcal{E}(k)\leqslant\mathcal{E}(0)=\frac{r^{3}-r^{2}}{2}\left\|z_{0}-z^{*}\right\|^{2}.$

By taking infimum respect to all $z^{*}\in\mathrm{zero}(T)$, we obtain the
desire result. Moreover, by summing $\mathcal{E}(k+1)-\mathcal{E}(k)$ from $0$
to $\infty$ and taking infimum respect to all $z^{*}\in\mathrm{zero}(T)$, we
have

$\displaystyle\
\sum_{k=0}^{\infty}\frac{1}{2}\left[(r-1)\left(\frac{1}{L}+2\rho\right)-D\right](2k+r+1)\left\|\tilde{T}(z_{k+1})\right\|^{2}$
$\displaystyle\leqslant$ $\displaystyle\
\frac{r^{3}-r^{2}}{2D}\mathrm{dist}(z_{0},\mathrm{zero}(T))^{2}.$

∎

Next, we consider a special monotone inclusion problem:

$0\in T(z)=F(z)+N_{C}(z).$ (19)

Here $N_{C}(z)=\\{z^{*}\in\mathcal{H}|\left\langle
z^{*},z^{\prime}-z\right\rangle\leqslant 0,\forall z^{\prime}\in C\\}$ is the
normal cone of convex subset $C$ at $z$ and $F$ is $L-$Lipschitz continuous
and monotone. The inclusion problem is equivalent to the Stampacchia
Variational Inequality problem

$\left\langle F(z),z^{\prime}-z\right\rangle\geqslant 0,\quad\forall
z^{\prime}\in C.$ (20)

######  Example 1.

Consider the matrix game problem

$\min_{x\in\Delta_{m}}\max_{y\in\Delta_{n}}x^{\mathrm{T}}Ay,$

where $\Delta_{m}$ is the $m-1$-dimensional unit simplex. Let
$C=\Delta_{m}\times\Delta_{n}$, the first-order characterization of matrix
game is

$0\in\binom{Ay}{-A^{\mathrm{T}}x}+N_{C}(x,y).$

Based on the projected EG method in [15] and the accelerated projected EG
method in [4], we propose the _symplectc projected extra-gradient+ (SPEG+)
method_ , described in Algorithm 2.

Input: Operator $F$, Convex set $C$,
$L\in(0,+\infty),\rho\in\left(-\dfrac{1}{2L},+\infty\right)$;

Initialization: $z_{0},u_{0}=z_{0}$;

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

$\tilde{z}_{k+1}=\dfrac{k}{k+r}z_{k}+\dfrac{r}{k+r}u_{k}$;

$z_{k+\frac{1}{2}}=P_{C}\left(\tilde{z}_{k+1}-\dfrac{k}{(k+r)L}F(z_{k})\right)$;

$z_{k+1}=P_{C}\left(\tilde{z}_{k+1}-\dfrac{1}{L}F(z_{k+\frac{1}{2}})\right)$;

$\tilde{C}_{k+1}=L(\tilde{z}_{k+1}-z_{k+1})-F(z_{k+\frac{1}{2}})$;

$u_{k+1}=u_{k}-\dfrac{D}{r}[F(z_{k+1})+\tilde{C}_{k+1}]$.

Algorithm 2 Symplectic Projected Extra-gradient+ Method, SPEG+

The corresponding convergence results in given as follows.

######  Theorem 2.

Let $\\{z_{k}\\}$ and $\\{u_{k}\\}$ be the sequences generated by Algorithm 2.
If $F$ is $L-$Lipschitz and monotone, $C$ is closed and convex, $r>1$ and
$0<D\leqslant\dfrac{r-1}{L}$, then we have

$\displaystyle\left(\frac{1}{2L}-\frac{D}{2(r-1)}\right)k^{2}\mathrm{dist}(0,T(z_{k}))^{2}$
$\displaystyle\leqslant\frac{r^{3}-r^{2}}{2D}\cdot\mathrm{dist}(z_{0},\mathrm{zero}(T))^{2},\quad\forall
k\geqslant 1,$ $\displaystyle Drk\left\langle
F(z_{k})+\tilde{C}_{k},z_{k}-z^{*}\right\rangle$
$\displaystyle\leqslant\frac{r^{3}-r^{2}}{2}\left\|z_{0}-z^{*}\right\|^{2},\quad\forall
z^{*}\in\mathrm{zero}(T).$

Thus, if $D<\dfrac{r-1}{L}$, the last-iterate convergence rates of Algorithm 2
are

$\displaystyle\mathrm{dist}(0,T(z_{k}))^{2}$
$\displaystyle\leqslant\cfrac{r^{2}(r-1)^{2}}{\left[\cfrac{r-1}{L}D-D^{2}\right]k^{2}}\cdot\mathrm{dist}(z_{0},\mathrm{zero}(T))^{2},\quad\forall
k\geqslant 1,$ $\displaystyle\left\langle
F(z_{k})+\tilde{C}_{k},z_{k}-z^{*}\right\rangle$
$\displaystyle\leqslant\frac{r^{2}-r}{2Dk}\left\|z_{0}-z^{*}\right\|^{2},\quad\forall
z^{*}\in\mathrm{zero}(T).$

In addition, we have

$\displaystyle\sum_{k=0}^{\infty}\frac{1}{2}\left(\frac{r-1}{L}-D\right)(2k+r+1)\left\|F(z_{k+1})+\tilde{C}_{k+1}\right\|^{2}\leqslant\
\frac{r^{3}-r^{2}}{2}\mathrm{dist}(z_{0},\mathrm{zero}(T))^{2},$
$\displaystyle\sum_{k=0}^{\infty}\frac{(k+r)^{2}}{2L}\left\|\tilde{C}_{k+\frac{1}{2}}-\frac{k}{k+r}\tilde{C}_{k}\right\|^{2}\leqslant\frac{r^{3}-r^{2}}{2D}\mathrm{dist}(z_{0},\mathrm{zero}(T))^{2}.$

###### Proof.

Similar to the proof for Theorem 1 , we need to obtain some useful equalities
and inequalities similar to (12)-(14). Here we let
$\tilde{C}_{k+\frac{1}{2}}=L\left(\tilde{z}_{k+1}-z_{k+\frac{1}{2}}-\dfrac{k}{(k+r)L}F(z_{k})\right)$.
By equivalent characterization of projection operator, we have

$\tilde{C}_{k+1}\in N_{C}(z_{k+1}),\quad\tilde{C}_{k+\frac{1}{2}}\in
N_{C}(z_{k+\frac{1}{2}}).$

Also by the definition of $\tilde{C}_{k+1}$ and $\tilde{C}_{k+\frac{1}{2}}$,
we have

$\displaystyle z_{k+1}$
$\displaystyle=\tilde{z}_{k+1}-\frac{1}{L}[F(z_{k+\frac{1}{2}})+\tilde{C}_{k+1}],$
(21) $\displaystyle z_{k+\frac{1}{2}}$
$\displaystyle=\tilde{z}_{k+1}-\frac{k}{(k+r)L}F(z_{k})-\frac{1}{L}\tilde{C}_{k+\frac{1}{2}}.$
(22)

Using (21) and (22), we obtain the following useful equations

$\displaystyle k(z_{k+1}-z_{k})$
$\displaystyle=r(u_{k}-z_{k+1})-\frac{k+r}{L}[F(z_{k+\frac{1}{2}})+\tilde{C}_{k+1}],$
(23) $\displaystyle r(z_{k}-u_{k})$
$\displaystyle=-(k+r)(z_{k+1}-z_{k})-\frac{k+r}{L}[F(z_{k+\frac{1}{2}})+\tilde{C}_{k+1}].$
(24)

Also. by $L-$Lipschitz continuity of $F$, we have

$\left\|F(z_{k+1})-F(z_{k+\frac{1}{2}})\right\|^{2}\leqslant
L^{2}\left\|z_{k+1}-z_{k+\frac{1}{2}}\right\|^{2}.$

Since $\tilde{C}_{k+\frac{1}{2}}\in N_{C}(z_{k+\frac{1}{2}}),z_{k+1}\in C$, we
have

$\left\langle\tilde{C}_{k+\frac{1}{2}},z_{k+\frac{1}{2}}-z_{k+1}\right\rangle\geqslant
0.$

Thus

$\displaystyle\left\|z_{k+1}-z_{k+\frac{1}{2}}\right\|^{2}\leqslant$
$\displaystyle\left\|z_{k+1}-z_{k+\frac{1}{2}}\right\|^{2}+\frac{2}{L}\left\langle\tilde{C}_{k+\frac{1}{2}},z_{k+\frac{1}{2}}-z_{k+1}\right\rangle$
$\displaystyle=$
$\displaystyle\left\|z_{k+1}-z_{k+\frac{1}{2}}-\frac{1}{L}\tilde{C}_{k+\frac{1}{2}}\right\|^{2}-\frac{1}{L^{2}}\left\|\tilde{C}_{k+\frac{1}{2}}\right\|^{2}.$

By subtracting (21) by (22), we obtain

$\left\|F(z_{k+1})-F(z_{k+\frac{1}{2}})\right\|^{2}\leqslant\left\|\frac{k}{k+r}F(z_{k})-F(z_{k+\frac{1}{2}})-\tilde{C}_{k+1}\right\|^{2}-\left\|\tilde{C}_{k+\frac{1}{2}}\right\|.$
(25)

Next, we consider the following Lyapunov function

$\mathcal{E}(k)=\frac{Dk^{2}}{2L}\left\|F(z_{k})+\tilde{C}_{k}\right\|^{2}+Drk\left\langle
F(z_{k})+\tilde{C}_{k},z_{k}-u_{k}\right\rangle+\frac{r^{3}-r^{2}}{2}\left\|u_{k}-z^{*}\right\|^{2},$
(26)

where $z^{*}\in\mathrm{zero}(T)$. First, we divide the difference
$\mathcal{E}(k+1)-\mathcal{E}(k)$ into three parts.

$\displaystyle\ \mathcal{E}(k+1)-\mathcal{E}(k)$ $\displaystyle=$
$\displaystyle\
\underbrace{\frac{D(k+1)^{2}}{2L}\left\|F(z_{k+1})+\tilde{C}_{k+1}\right\|^{2}-\frac{Dk^{2}}{2L}\left\|F(z_{k})+\tilde{C}_{k}\right\|^{2}}_{\text{I}}$
$\displaystyle\ +\underbrace{Dr(k+1)\left\langle
F(z_{k+1})+\tilde{C}_{k+1},z_{k+1}-u_{k+1}\right\rangle-Drk\left\langle
F(z_{k})+\tilde{C}_{k},z_{k}-u_{k}\right\rangle}_{\text{II}}$ $\displaystyle\
+\underbrace{\frac{r^{3}-r^{2}}{2}\left[\left\|u_{k+1}-z^{*}\right\|^{2}-\left\|u_{k}-z^{*}\right\|^{2}\right]}_{\text{III}}.$

Secondly, we reckon the upper bound of II and III. First we consider II. II
can be split into the following three terms.

$\displaystyle\text{II}=$ $\displaystyle\ Dr\left\langle
F(z_{k+1})+\tilde{C}_{k+1},z_{k+1}-u_{k+1}\right\rangle$ $\displaystyle\
+Drk\left\langle
F(z_{k+1})+\tilde{C}_{k+1},z_{k+1}-z_{k}-u_{k+1}+u_{k}\right\rangle$
$\displaystyle\ +Drk\left\langle
F(z_{k+1})+\tilde{C}_{k+1}-F(z_{k})-\tilde{C}_{k},z_{k}-u_{k}\right\rangle.$

Due to (23) and the equality
$u_{k+1}-u_{k}=-\dfrac{D}{r}[F(z_{k+1})+\tilde{C}_{k+1}]$, we have

$\begin{split}&\ Drk\left\langle
F(z_{k+1}),z_{k+1}-z_{k}-u_{k+1}+u_{k}\right\rangle\\\ =&\ Dr\left\langle
F(z_{k+1})+\tilde{C}_{k+1},r(u_{k}-z_{k+1})-\frac{k+r}{L}[F(z_{k+\frac{1}{2}})+\tilde{C}_{k+1}]\right\rangle\\\
&\ +D^{2}k\left\|F(z_{k+1})+\tilde{C}_{k+1}\right\|^{2}.\end{split}$ (27)

In addition, because of (24), we have

$\begin{split}&\ Drk\left\langle
F(z_{k+1})-F(z_{k})+\tilde{C}_{k+1}-\tilde{C}_{k},z_{k}-u_{k}\right\rangle\\\
=&\ Dk\left\langle
F(z_{k+1})+\tilde{C}_{k+1}-F(z_{k})-\tilde{C}_{k},-(k+r)(z_{k+1}-z_{k})-\frac{k+r}{L}[F(z_{k+\frac{1}{2}})+\tilde{C}_{k+1}]\right\rangle.\end{split}$
(28)

Also,

$\begin{split}&\ Dr\left\langle
F(z_{k+1})+\tilde{C}_{k+1},z_{k+1}-u_{k+1}\right\rangle\\\ =&\
D^{2}\left\|F(z_{k+1})+\tilde{C}_{k+1}\right\|^{2}+Dr\left\langle
F(z_{k+1})+\tilde{C}_{k+1},z_{k+1}-u_{k}\right\rangle.\end{split}$ (29)

By summing (27), (28) and (29), we have

II $\displaystyle=$ $\displaystyle\ -\frac{D(k+r)^{2}}{L}\left\langle
F(z_{k+1}),F(z_{k+\frac{1}{2}})\right\rangle+\frac{Dk(k+r)}{L}\left\langle
F(z_{k}),F(z_{k+\frac{1}{2}})\right\rangle-\frac{D(k+r)^{2}}{L}\left\|\tilde{C}_{k+1}\right\|^{2}$
$\displaystyle\
-\frac{D}{L}\left\langle\tilde{C}_{k+1},(k+r)^{2}[F(z_{k+\frac{1}{2}})+F(z_{k+1})]-k(k+r)[F(z_{k})+\tilde{C}_{k}]\right\rangle+\frac{Dk(k+r)}{L}\left\langle\tilde{C}_{k},F(z_{k+\frac{1}{2}})\right\rangle$
$\displaystyle\ -Dk(k+r)\left\langle
F(z_{k+1})+\tilde{C}_{k+1}-F(z_{k})-\tilde{C}_{k},z_{k+1}-z_{k}\right\rangle$
$\displaystyle\ +D(r-r^{2})\left\langle
F(z_{k+1})+\tilde{C}_{k+1},z_{k+1}-u_{k}\right\rangle+D^{2}(k+1)\left\|F(z_{k+1})+\tilde{C}_{k+1}\right\|^{2}.$

Combining $\rho-$comonotonicity of $F$, (25) and the following equality

$-\left\langle
F(z_{k+1}),F(z_{k+\frac{1}{2}})\right\rangle=\frac{1}{2}\left[\left\|F(z_{k+1})-F(z_{k+\frac{1}{2}})\right\|^{2}-\left\|F(z_{k+1})\right\|^{2}-\left\|F(z_{k+\frac{1}{2}})\right\|^{2}\right],$

we can obtain the upper bound of II as follows:

$\displaystyle\text{II}\leqslant$ $\displaystyle\
-\frac{D(k+r)^{2}}{2L}\left\|F(z_{k+1})+\tilde{C}_{k+1}\right\|^{2}+Dk(k+r)\left\langle\tilde{C}_{k},z_{k+1}-z_{k}+\frac{1}{L}[F(z_{k+\frac{1}{2}})+\tilde{C}_{k+1}]\right\rangle$
$\displaystyle\ -Dk(k+r)\left\langle
F(z_{k+1})+\tilde{C}_{k+1}-F(z_{k}),z_{k+1}-z_{k}\right\rangle-\frac{D(k+r)^{2}}{2L}\left\|\tilde{C}_{k+\frac{1}{2}}\right\|$
$\displaystyle\ +D(r-r^{2})\left\langle
F(z_{k+1})+\tilde{C}_{k+1},z_{k+1}-u_{k}\right\rangle+D^{2}(k+1)\left\|F(z_{k+1})+\tilde{C}_{k+1}\right\|^{2}+\frac{Dk^{2}}{2L}\left\|F(z_{k})\right\|^{2}.$

Since

$z_{k+1}+\frac{1}{L}[F(z_{k+\frac{1}{2}})+\tilde{C}_{k+1}]=z_{k+\frac{1}{2}}+\frac{k}{(k+r)L}F(z_{k})+\frac{1}{L}\tilde{C}_{k+1},$

we have

$\displaystyle\
Dk(k+r)\left\langle\tilde{C}_{k},z_{k+1}-z_{k}+\frac{1}{L}[F(z_{k+\frac{1}{2}})+\tilde{C}_{k+1}]\right\rangle$
$\displaystyle=$ $\displaystyle\
Dk(k+r)\left\langle\tilde{C}_{k},z_{k+\frac{1}{2}}-z_{k}+\frac{1}{L}\left(\frac{k}{k+r}F(z_{k})+\tilde{C}_{k+\frac{1}{2}}\right)\right\rangle.$

Thus

$\displaystyle\text{II}\leqslant$ $\displaystyle\
-\frac{D(k+r)^{2}}{2L}\left\|F(z_{k+1})+\tilde{C}_{k+1}\right\|^{2}+\frac{Dk^{2}}{2L}\left\|F(z_{k})+\tilde{C}_{k}\right\|^{2}-\frac{D}{2L}\left\|(k+r)\tilde{C}_{k+\frac{1}{2}}-k\tilde{C}_{k}\right\|^{2}$
$\displaystyle\ -Dk(k+r)\left\langle
F(z_{k+1})+\tilde{C}_{k+1}-F(z_{k}),z_{k+1}-z_{k}\right\rangle+Dk(k+r)\left\langle\tilde{C}_{k},z_{k+\frac{1}{2}}-z_{k}\right\rangle$
$\displaystyle\ +D(r-r^{2})\left\langle
F(z_{k+1})+\tilde{C}_{k+1},z_{k+1}-u_{k}\right\rangle+D^{2}(k+1)\left\|F(z_{k+1})+\tilde{C}_{k+1}\right\|^{2}.$

Now we estimate III. Owing to (18), we have

III $\displaystyle=(r^{3}-r^{2})\left\langle
u_{k+1}-u_{k},u_{k}-z^{*}\right\rangle+\frac{r^{3}-r^{2}}{2}\left\|u_{k+1}-u_{k}\right\|^{2}$
$\displaystyle=-\underbrace{D(r^{2}-r)\left\langle
F(z_{k+1})+\tilde{C}_{k+1},u_{k}-z^{*}\right\rangle}_{\text{III}_{1}}+\frac{D^{2}(r-1)}{2}\left\|F(z_{k+1})+\tilde{C}_{k+1}\right\|^{2}.$

Next, we can deduce the upper bound of $\mathcal{E}(k+1)-\mathcal{E}(k)$. Due
to

$\text{II}_{1}-\text{III}_{1}=-D(r^{2}-r)\left\langle
F(z_{k+1})+\tilde{C}_{k+1},z_{k+1}-z^{*}\right\rangle,$

the upper bound of $\mathcal{E}(k+1)-\mathcal{E}(k)$ can be simplified as
follows:

$\displaystyle\ \mathcal{E}(k+1)-\mathcal{E}(k)$ $\displaystyle\leqslant$
$\displaystyle\
-\frac{D}{2}\left(\frac{r-1}{L}-D\right)(2k+r+1)\left\|F(z_{k+1})+\tilde{C}_{k+1}\right\|^{2}$
$\displaystyle\ -D(r^{2}-r)\left\langle
F(z_{k+1})+\tilde{C}_{k+1},z_{k+1}-z^{*}\right\rangle-Dk(k+r)\left\langle
F(z_{k+1})+\tilde{C}_{k+1}-F(z_{k}),z_{k+1}-z_{k}\right\rangle$
$\displaystyle\
+Dk(k+r)\left\langle\tilde{C}_{k},z_{k+\frac{1}{2}}-z_{k}\right\rangle-\frac{D}{2L}\left\|(k+r)\tilde{C}_{k+\frac{1}{2}}-k\tilde{C}_{k}\right\|^{2}.$

Because $\tilde{C}_{k+1}\in N_{C}(z_{k+1})$, $\tilde{C}_{k}\in N_{C}(z_{k})$,
we have

$\left\langle\tilde{C}_{k+1},z_{k}-z_{k+1}\right\rangle\leqslant
0,\quad\left\langle\tilde{C}_{k},z_{k+\frac{1}{2}}-z_{k}\right\rangle\leqslant
0.$

In conclusion

$\displaystyle\ \mathcal{E}(k+1)-\mathcal{E}(k)$ $\displaystyle\leqslant$
$\displaystyle\
-\frac{D}{2}\left(\frac{r-1}{L}-D\right)(2k+r+1)\left\|F(z_{k+1})+\tilde{C}_{k+1}\right\|^{2}-\frac{D}{2L}\left\|(k+r)\tilde{C}_{k+\frac{1}{2}}-k\tilde{C}_{k}\right\|^{2}$
$\displaystyle\leqslant$ $\displaystyle\ 0.$

Finally, we can obtain the convergence results of Algorithm 2. First, we
translate $\mathcal{E}(k)$ into the following form.

$\displaystyle\mathcal{E}(k)=$ $\displaystyle\
\left(\frac{D}{2L}-\frac{D^{2}}{2(r-1)}\right)k^{2}\left\|F(z_{k})+\tilde{C}_{k}\right\|^{2}+Drk\left\langle
F(z_{k})+\tilde{C}_{k},z_{k}-z^{*}\right\rangle$ $\displaystyle\
+\frac{1}{2}\left\|\frac{Dk}{\sqrt{r-1}}[F(z_{k})+\tilde{C}_{k}]-\sqrt{r^{3}-r^{2}}(u_{k}-z^{*})\right\|^{2}.$

Since $F$ is monotone, $\mathcal{E}(k)$ can be represented by the sum of three
non-negative terms. Then we have

$\displaystyle\left(\frac{D}{2L}-\frac{D^{2}}{2(r-1)}\right)k^{2}\mathrm{dist}(0,T(z_{k}))^{2}$
$\displaystyle\leqslant\mathcal{E}(k)\leqslant\mathcal{E}(0)=\frac{r^{3}-r^{2}}{2}\left\|z_{0}-z^{*}\right\|^{2}.$
$\displaystyle Drk\left\langle
F(z_{k})+\tilde{C}_{k},z_{k}-z^{*}\right\rangle$
$\displaystyle\leqslant\mathcal{E}(k)\leqslant\mathcal{E}(0)=\frac{r^{3}-r^{2}}{2}\left\|z_{0}-z^{*}\right\|^{2}.$

Taking infimum respect to all $z^{*}\in\mathrm{zero}(T)$ on both sides of the
first above inequality and using the inequality
$\mathrm{dist}(0,T(z_{k}))\leqslant\left\|F(z_{k})+\tilde{C}_{k}\right\|$, we
obtain the desire result. Moreover, by summing
$\mathcal{E}(k+1)-\mathcal{E}(k)$ from $0$ to $\infty$, we have

$\displaystyle\sum_{k=0}^{\infty}\frac{D}{2}\left(\frac{r-1}{L}-D\right)(2k+r+1)\left\|F(z_{k+1})+\tilde{C}_{k+1}\right\|^{2}\leqslant\frac{r^{3}-r^{2}}{2}\left\|z_{0}-z^{*}\right\|^{2},$
$\displaystyle\sum_{k=0}^{\infty}\frac{(k+r)^{2}}{2L}\left\|\tilde{C}_{k+\frac{1}{2}}-\frac{k}{k+r}\tilde{C}_{k}\right\|^{2}\leqslant\frac{r^{3}-r^{2}}{2}\left\|z_{0}-z^{*}\right\|^{2}.$

Also, taking infimum respect to all $z^{*}\in\mathrm{zero}(T)$, we obtain the
desire results. ∎

##  4 Sharper Rate

In this section, we will build up the $o(1/k^{2})$ convergence rate of the SEG
type method. It is noteworthy that the symplectic proximal point algorithm
admits an $o(1/k^{2})$ convergence rate if the assumption $D<r-1$ holds.
Analogously, one may suggest that the symplectic EG type method admits
$o(1/k^{2})$ convergence rate when $D<(r-1)\left(\dfrac{1}{L}+2\rho\right)$.
However, the assumption $D<(r-1)\left(\dfrac{1}{L}+2\rho\right)$ alone is not
enough. The main reason is that the EG type method tries to use
$F(z_{k+\frac{1}{2}})$ to approximate $F(z_{k+1})$, but the error term
$\left\|F(z_{k+\frac{1}{2}})-F(z_{k+1})\right\|^{2}$ can not be estimated
directly. To overcome this problem, we need additional assumption on the step-
size in the SEG type method. Here, we make use of Algorithm 1 to illustrate
the desire result.

######  Lemma 3 (Estimation of error).

Let $\\{z_{\frac{k}{2}}\\}$, $\\{\tilde{z}_{k+1}\\}$ and $\\{u_{k}\\}$ be the
sequences generated by

$\displaystyle\tilde{z}_{k+1}$
$\displaystyle=\frac{k}{k+r}z_{k}+\frac{r}{k+r}u_{k},$ (30) $\displaystyle
z_{k+\frac{1}{2}}$
$\displaystyle=\tilde{z}_{k+1}-\frac{k}{k+r}(s+2\rho)(F(z_{k})+\tilde{G}_{k}),$
(31) $\displaystyle z_{k+1}$
$\displaystyle=J_{\frac{1}{s}G}\left[\tilde{z}_{k+1}-sF(z_{k+\frac{1}{2}})-\frac{k}{k+r}2\rho(F(z_{k})+\tilde{G}_{k})\right],$
(32) $\displaystyle\tilde{G}_{k+1}$
$\displaystyle=s^{-1}\left[\tilde{z}_{k+1}-z_{k+1}-sF(z_{k+\frac{1}{2}})-\frac{k}{k+r}2\rho(F(z_{k})+\tilde{G}_{k})\right],$
(33) $\displaystyle u_{k+1}$
$\displaystyle=u_{k}-\frac{D}{r}[F(z_{k+1})+\tilde{G}_{k+1}].$ (34)

If $F$ is $L-$Lipschitz continuous and $s<\dfrac{1}{L}$, there exists a
positive constant $C$ such that

$\left\|F(z_{k+1})-F(z_{k+\frac{1}{2}})\right\|^{2}\leqslant
C\left\|F(z_{k+1})+\tilde{G}_{k+1}-F(z_{k})-\tilde{G}_{k}\right\|^{2}.$

###### Proof.

First, we show that for all $C_{1}>1$, there exists a constant $C_{2}>1$ such
that

$\left\|x+y\right\|^{2}\leqslant
C_{2}\left\|x\right\|^{2}+C_{1}\left\|y\right\|^{2},\quad\forall
x,y\in\mathcal{H}.$ (35)

By using the Cauchy-Schwarz inequality, we have

$\displaystyle\left\|x+y\right\|^{2}$
$\displaystyle=\left\|x\right\|^{2}+\left\|y\right\|^{2}+2\left\langle
x,y\right\rangle$
$\displaystyle=\left\|x\right\|^{2}+\left\|y\right\|^{2}+2\left\langle(C_{1}-1)^{-\frac{1}{2}}x,\sqrt{C_{1}-1}y\right\rangle$
$\displaystyle\leqslant\frac{C_{1}}{C_{1}-1}\left\|x\right\|^{2}+C_{1}\left\|y\right\|^{2},\quad\forall
C_{1}>1.$

Let $C_{2}=\dfrac{C_{1}}{C_{1}-1}$, we obtain the desire result. Let
$\tilde{T}(z_{k})=F(z_{k})+\tilde{G}_{k}$. Due to $L-$Lipschitz continuity of
$F$, we have

$\displaystyle\left\|F(z_{k+1})-F(z_{k+\frac{1}{2}})\right\|^{2}\leqslant
L^{2}s^{2}\left\|F(z_{k+1})-F(z_{k+\frac{1}{2}})-\tilde{T}(z_{k+1})+\tilde{T}(z_{k})\right\|^{2}.$

Let $y=F(z_{k+1})-F(z_{k+\frac{1}{2}})$ and
$x=-\tilde{T}(z_{k+1})+\tilde{T}(z_{k})$. Since $s<\dfrac{1}{L}$, there exists
a constant $C_{1}$ such that $C_{1}>1$ and $L^{2}s^{2}C_{1}<1$. By applying
(35), we have

$\left\|F(z_{k+1})-F(z_{k+\frac{1}{2}})\right\|^{2}\leqslant
L^{2}s^{2}C_{2}\left\|\tilde{T}(z_{k+1})-\tilde{T}(z_{k})\right\|^{2}+L^{2}s^{2}C_{1}\left\|F(z_{k+1})-F(z_{k+\frac{1}{2}})\right\|^{2}.$

Let $C=\dfrac{L^{2}s^{2}C_{2}}{1-L^{2}s^{2}C_{1}}$, we have

$\left\|F(z_{k+1})-F(z_{k+\frac{1}{2}})\right\|^{2}\leqslant
C\left\|\tilde{T}(z_{k+1})-\tilde{T}(z_{k})\right\|^{2}.$

∎

With Lemma 3, we can demonstrate the $o(1/k^{2})$ convergence rate of the SFBS
method.

######  Theorem 4 (Faster convergence rate).

Let $\\{z_{\frac{k}{2}}\\}$, $\\{\tilde{z}_{k+1}\\}$ and $\\{u_{k}\\}$ be the
sequences generated by (30)-(34). If $F$ is $L-$Lipschitz continuous, $G$ is
maximally monotone, $T=F+G$ is $\rho-$comonotone, $0<s<\dfrac{1}{L}$,
$\rho>-\dfrac{s}{2}$ and $0<D<(r-1)(s+2\rho)$, we have

$\displaystyle\lim_{k\to\infty}\left\|z_{k}-u_{k}\right\|^{2}=0,\qquad$
$\displaystyle\lim_{k\to\infty}\left\|u_{k}-z^{*}\right\|^{2}\text{ exists for
all }z^{*}\in\mathrm{zero}(T),$
$\displaystyle\lim_{k\to\infty}k^{2}\mathrm{dist}(0,T(z_{k}))^{2}=0,\qquad$
$\displaystyle\lim_{k\to\infty}k^{2}\left\|z_{k+1}-z_{k}\right\|^{2}=0.$

###### Proof.

Let $\tilde{T}(z_{k})=F(z_{k})+\tilde{G}_{k}$. Owing to $s<\dfrac{1}{L}$, the
operator $F$ can be regarded as $s^{-1}-$Lipschitz continuous. By Theorem 1,
we have

$\left\|\tilde{T}(z_{k})\right\|^{2}\leqslant
O\left(\frac{1}{k^{2}}\right),\quad\sum_{k=0}^{\infty}k\left\|\tilde{T}(z_{k})\right\|^{2}<+\infty.$

Due to Lemma 3, we have

$\left\|F(z_{k+1})-F(z_{k+\frac{1}{2}})\right\|^{2}\leqslant
O\left(\frac{1}{k^{2}}\right),\quad\sum_{k=0}^{\infty}k\left\|F(z_{k+1})-F(z_{k+\frac{1}{2}})\right\|^{2}<+\infty.$

Next, we show that

$\sum_{k=1}^{\infty}\frac{\left\|z_{k+1}-u_{k+1}\right\|^{2}}{2k}<+\infty.$

To obtain such result, we need to study the following auxiliary Lyapunov
function:

$\mathcal{G}(k)=\frac{1}{2}\left\|z_{k}-u_{k}\right\|^{2}+\frac{r}{2D}\cdot\frac{(k+r)^{2}}{k^{2}}\left(s+2\rho-\frac{D}{r}\right)\left\|u_{k}-z^{*}\right\|^{2}.$

First, consider the difference
$\dfrac{1}{2}\left\|z_{k+1}-u_{k+1}\right\|^{2}-\dfrac{1}{2}\left\|z_{k}-u_{k}\right\|^{2}$.

$\displaystyle\
\frac{1}{2}\left\|z_{k+1}-u_{k+1}\right\|^{2}-\frac{1}{2}\left\|z_{k}-u_{k}\right\|^{2}$
$\displaystyle=$ $\displaystyle\ \frac{1}{2}\left\langle
z_{k+1}+z_{k}-u_{k+1}-u_{k},z_{k+1}-z_{k}-u_{k+1}+u_{k}\right\rangle$
$\displaystyle=$ $\displaystyle\
\frac{1}{2}\left\langle\left(2+\frac{r}{k}\right)z_{k+1}-u_{k+1}-\left(1+\frac{r}{k}\right)u_{k}+\frac{k+r}{k}s[F(z_{k+\frac{1}{2}})+\tilde{G}_{k+1}]+2\rho\tilde{T}(z_{k}),\right.$
$\displaystyle\qquad\
\left.-\frac{r}{k}z_{k+1}+\left(1+\frac{r}{k}\right)u_{k}-u_{k+1}-\frac{k+r}{k}s[F(z_{k+\frac{1}{2}})+\tilde{G}_{k+1}]-2\rho\tilde{T}(z_{k})\right\rangle$
$\displaystyle=$ $\displaystyle\
-\frac{(2k+r)r}{2k^{2}}\left\|z_{k+1}-u_{k+1}\right\|^{2}-\frac{(k+r)^{2}}{k^{2}}s\left\langle
F(z_{k+1})-F(z_{k+\frac{1}{2}}),z_{k+1}-u_{k+1}\right\rangle$ $\displaystyle\
-\frac{k+r}{k}2\rho s\left\langle
F(z_{k+\frac{1}{2}})-F(z_{k+1}),\tilde{T}(z_{k})-\frac{k+r}{k}\tilde{T}(z_{k+1})\right\rangle$
$\displaystyle\
-\frac{(k+r)^{2}}{k^{2}}\left(s+2\rho-\frac{D}{r}\right)\left\langle\tilde{T}(z_{k+1}),z_{k+1}-u_{k+1}\right\rangle$
$\displaystyle\ -\frac{k+r}{k}\left(s+2\rho-\frac{D}{r}\right)2\rho
s\left\langle\tilde{T}(z_{k})-\frac{k+r}{k}\tilde{T}(z_{k+1}),\tilde{T}(z_{k+1})\right\rangle$
$\displaystyle\leqslant$ $\displaystyle\
-\frac{(2k+r)(r-1)}{2k^{2}}\left\|z_{k+1}-u_{k+1}\right\|^{2}+\frac{(k+r)^{4}s^{2}}{2k^{2}(2k+r)}\left\|F(z_{k+1})-F(z_{k+\frac{1}{2}})\right\|^{2}$
$\displaystyle\
-\frac{(k+r)^{2}}{k^{2}}\left(s+2\rho-\frac{D}{r}\right)\left\langle\tilde{T}(z_{k+1}),z_{k+1}-u_{k+1}\right\rangle$
$\displaystyle\ +\frac{k+r}{k}\rho
s\left(\left\|F(z_{k+\frac{1}{2}})-F(z_{k+1})\right\|^{2}+\left\|\tilde{T}(z_{k})-\frac{k+r}{k}\tilde{T}(z_{k+1})\right\|^{2}\right)$
$\displaystyle\ +\frac{k+r}{k}\left(s+2\rho-\frac{D}{r}\right)\rho
s\left(\left\|\tilde{T}(z_{k})-\frac{k+r}{k}\tilde{T}(z_{k+1})\right\|^{2}+\left\|\tilde{T}(z_{k+1})\right\|^{2}\right).$

Also, since $\dfrac{(k+r)^{2}}{k^{2}}$ is non-increasing, we have

$\displaystyle\
\frac{r}{2D}\cdot\frac{(k+1+r)^{2}}{(k+1)^{2}}\left(s+2\rho-\frac{D}{r}\right)\left\|u_{k+1}-z^{*}\right\|^{2}-\frac{r}{2D}\cdot\frac{(k+r)^{2}}{k^{2}}\left(s+2\rho-\frac{D}{r}\right)\left\|u_{k}-z^{*}\right\|^{2}$
$\displaystyle\leqslant$ $\displaystyle\
\frac{r}{2D}\cdot\frac{(k+r)^{2}}{k^{2}}\left(s+2\rho-\frac{D}{r}\right)\left(\left\|u_{k+1}-z^{*}\right\|^{2}-\left\|u_{k}-z^{*}\right\|^{2}\right)$
$\displaystyle=$ $\displaystyle\
\frac{r}{2D}\cdot\frac{(k+r)^{2}}{k^{2}}\left(s+2\rho-\frac{D}{r}\right)\left(2\left\langle
u_{k+1}-u_{k},u_{k+1}-z^{*}\right\rangle-\left\|u_{k+1}-u_{k}\right\|^{2}\right)$
$\displaystyle=$ $\displaystyle\
\frac{r}{2D}\cdot\frac{(k+r)^{2}}{k^{2}}\left(s+2\rho-\frac{D}{r}\right)\left(-\frac{2D}{r}\left\langle\tilde{T}(z_{k+1}),u_{k+1}-z^{*}\right\rangle-\frac{D^{2}}{r^{2}}\left\|\tilde{T}(z_{k+1})\right\|^{2}\right).$

Let

$\displaystyle\varphi(k)=$ $\displaystyle\
\frac{(k+r)^{4}s^{2}}{2k^{2}(2k+r)}\left\|F(z_{k+1})-F(z_{k+\frac{1}{2}})\right\|^{2}$
$\displaystyle\
-\frac{(k+r)^{2}}{k^{2}}\left(s+2\rho-\frac{D}{r}\right)\left(\rho+\frac{D}{2r}\right)\left\|\tilde{T}(z_{k+1})\right\|^{2}$
$\displaystyle\ +\frac{k+r}{k}\rho
s\left(\left\|F(z_{k+\frac{1}{2}})-F(z_{k+1})\right\|^{2}+\left\|\tilde{T}(z_{k})-\frac{k+r}{k}\tilde{T}(z_{k+1})\right\|^{2}\right)$
$\displaystyle\ +\frac{k+r}{k}\left(s+2\rho-\frac{D}{r}\right)\rho
s\left(\left\|\tilde{T}(z_{k})-\frac{k+r}{k}\tilde{T}(z_{k+1})\right\|^{2}+\left\|\tilde{T}(z_{k+1})\right\|^{2}\right).$

By previous argument, we have

$\mathcal{G}(k+1)-\mathcal{G}(k)\leqslant-\frac{(2k+r)(r-1)}{2k^{2}}\left\|z_{k+1}-u_{k+1}\right\|^{2}+\varphi(k).$

Since $\sum\limits_{k=1}^{\infty}\varphi(k)<+\infty$, we have

$\mathcal{G}(k+1)+\sum_{i=k+1}^{\infty}\varphi(i)\leqslant\mathcal{G}(k)+\sum_{i=k}^{\infty}\varphi(k)-\frac{(2k+r)(r-1)}{2k^{2}}\left\|z_{k+1}-u_{k+1}\right\|^{2}.$

Then we have

$\lim_{k\to\infty}\mathcal{G}(k)\text{ exists,
}\quad\sum_{k=1}^{\infty}\frac{\left\|z_{k}-u_{k}\right\|^{2}}{k}\leqslant+\infty.$

The next thing we need to do is to show that for all
$z^{*}\in\mathrm{zero}(T)$,
$\lim\limits_{k\to\infty}\left\|u_{k}-z^{*}\right\|^{2}$ exists. If
$\lim\limits_{k\to\infty}\left\|u_{k}-z^{*}\right\|^{2}$ exists,
$\lim\limits_{k\to\infty}\mathcal{G}(k)$ exists and
$\sum\limits_{k=1}^{\infty}\dfrac{\left\|z_{k+1}-u_{k+1}\right\|^{2}}{2k}<+\infty$,
we can easily show that

$\lim_{k\to\infty}\left\|z_{k}-u_{k}\right\|^{2}=0.$

Calculating the difference of $\dfrac{1}{2}\left\|u_{k}-z^{*}\right\|^{2}$, we
have

$\displaystyle\
\frac{1}{2}\left\|u_{k+1}-z^{*}\right\|^{2}-\frac{1}{2}\left\|u_{k}-z^{*}\right\|^{2}$
$\displaystyle\leqslant$ $\displaystyle\
-\frac{D}{r}\left\langle\tilde{T}(z_{k+1}),u_{k+1}-z^{*}\right\rangle$
$\displaystyle\leqslant$ $\displaystyle\
\frac{D}{2r}\left(k\left\|\tilde{T}(z_{k+1})\right\|^{2}+k^{-1}\left\|u_{k+1}-z_{k+1}\right\|^{2}\right)-\frac{D\rho}{r}\left\|\tilde{T}(z_{k+1})\right\|^{2}.$

Since

$\sum_{k=1}^{\infty}\frac{D}{2r}\left(k\left\|T_{k+1}\right\|^{2}+k^{-1}\left\|u_{k+1}-z_{k+1}\right\|^{2}\right)-\frac{D\rho}{r}\left\|T_{k+1}\right\|^{2}<+\infty,$

we prove the existence of the limitation
$\lim\limits_{k\to\infty}\left\|u_{k}-z^{*}\right\|^{2}$.

Finally, we can prove the results presented in Theorem 1. Since

$\left\|\tilde{T}(z_{k})\right\|^{2}\leqslant
O\left(\frac{1}{k^{2}}\right),\quad\lim_{k\to\infty}\left\|z_{k}-u_{k}\right\|^{2}=0,$

we have

$\lim_{k\to\infty}Drk\left\langle\tilde{T}(z_{k}),z_{k}-u_{k}\right\rangle=0.$

Consider the following Lyapunov function

$\displaystyle\mathcal{E}(k)=$ $\displaystyle\ \left[\frac{Dk^{2}s}{2}+\rho
Dk(k-r)\right]\left\|\tilde{T}(z_{k})\right\|^{2}$ $\displaystyle\
+Drk\left\langle\tilde{T}(z_{k}),z_{k}-u_{k}\right\rangle+\frac{r^{3}-r^{2}}{2}\left\|u_{k}-z^{*}\right\|.$

By Theorem 4, we have $\\{\mathcal{E}(k)\\}$ is non-increasing and non-
negetive. Thus, $\lim\limits_{k\to\infty}\mathcal{E}(k)$ exists. Also, by the
existence of $\lim\limits_{k\to\infty}\left\|u_{k}-z^{*}\right\|^{2}$, we have

$\lim_{k\to\infty}\left[\frac{Dk^{2}s}{2}+\rho
Dk(k-r)\right]\left\|\tilde{T}(z_{k})\right\|^{2}\text{ exists}.$

Since
$\sum\limits_{k=0}^{\infty}k\left\|\tilde{T}(z_{k})\right\|^{2}<+\infty$, we
have

$\lim_{k\to\infty}k^{2}\left\|\tilde{T}(z_{k})\right\|^{2}=0.$

By the inequality
$0\leqslant\mathrm{dist}(0,T(z_{k}))^{2}\leqslant\left\|\tilde{T}(z_{k})\right\|^{2}$,
we can obtain

$\lim_{k\to\infty}k^{2}\mathrm{dist}(0,T(z_{k}))^{2}=0.$

Also, by the inequality

$k(z_{k+1}-z_{k})=r(u_{k+1}-z_{k+1})-[(k+r)s-D]\tilde{T}(z_{k+1})-(k+r)s[F(z_{k+\frac{1}{2}})-F(z_{k+1})]-2\rho
k\tilde{T}(z_{k}),$

we have

$\lim_{k\to\infty}k^{2}\left\|z_{k+1}-z_{k}\right\|^{2}=0.$

∎

Although Theorem 4 requires that the step-size
$s\in\left(-2\rho,\dfrac{1}{L}\right)$, the existence of desired step-size $s$
can be easily ensure if $\rho>-\dfrac{1}{2L}$.

######  Theorem 5 (Weak convergence property).

Let $\\{z_{\frac{k}{2}}\\}$, $\\{\tilde{z}_{k+1}\\}$ and $\\{u_{k}\\}$ be the
sequences generated by (30)-(34) with $\rho=0$. If $F$ is $L-$Lipschitz
continuous and monotone, $G$ is maximally monotone, $0<s<\dfrac{1}{L}$, and
$0<D<(r-1)s$, then both of the sequences $\\{z_{k}\\}$ and $\\{u_{k}\\}$
converge weakly to a point in $\mathrm{zero}(T)$.

###### Proof.

By Theorem 4, $\lim\limits_{k\to\infty}\left\|u_{k}-z^{*}\right\|^{2}$ exists.
Let $u_{\infty}$ be any cluster point of $\\{u_{k}\\}$, and $\\{u_{k_{j}}\\}$
be the subsequence of $\\{u_{k}\\}$ such that $u_{k_{j}}\rightharpoonup
u_{\infty}$. Since $\lim\limits_{k\to\infty}\left\|z_{k}-u_{k}\right\|^{2}=0$,
$z_{k_{j}}\rightharpoonup u_{\infty}$. As a result of Theorem 1,
$F(z_{k})+\tilde{G}_{k}\to 0$. Because of Proposition 2, $0\in T(u_{\infty})$.
By Proposition 1, we can show that $\\{u_{k}\\}$ converge weakly to a point in
$\mathrm{zero}(T)$. Also by
$\lim\limits_{k\to\infty}\left\|u_{k}-z_{k}\right\|^{2}=0$, $\\{z_{k}\\}$
converge weakly to a point in $\mathrm{zero}(T)$ and the weak limitations of
$\\{z_{k}\\}$ and $\\{u_{k}\\}$ are the same. ∎

However, the weak convergence property of the SFBS method requires that $F$ is
monotone because of Proposition 2. If one can prove a similar result to
Proposition 2 under comonotonicity assumption, the weak convergence property
of the SFBS method under comonotonicity assumption can be ensured.

The method to demonstrate the $o(1/k^{2})$ convergence rate and the weak
convergence property of the SPEG+ method is similar to the proof for Theorem 4
and Theorem 5.

######  Corollary 6.

Let $\\{z_{\frac{k}{2}}\\}$, $\\{\tilde{z}_{k+1}\\}$ and $\\{u_{k}\\}$ be the
sequences generated by

$\displaystyle\tilde{z}_{k+1}$
$\displaystyle=\dfrac{k}{k+r}z_{k}+\dfrac{r}{k+r}u_{k},$ $\displaystyle
z_{k+\frac{1}{2}}$
$\displaystyle=P_{C}\left(\tilde{z}_{k+1}-\dfrac{ks}{(k+r)}F(z_{k})\right),$
$\displaystyle z_{k+1}$
$\displaystyle=P_{C}\left(\tilde{z}_{k+1}-sF(z_{k+\frac{1}{2}})\right),$
$\displaystyle\tilde{C}_{k+1}$
$\displaystyle=s^{-1}\left(\tilde{z}_{k+1}-sF(z_{k+\frac{1}{2}})-z_{k+1}\right),$
$\displaystyle u_{k+1}$
$\displaystyle=u_{k}-\dfrac{D}{r}[F(z_{k+1})+\tilde{C}_{k+1}].$

If $F$ is $L-$Lipschitz continuous and monotone, $0<s<\dfrac{1}{L}$, $r>1$ and
$0<D<(r-1)s$, then we have

$\displaystyle\lim_{k\to\infty}\left\|z_{k}-u_{k}\right\|^{2}$
$\displaystyle=0,$
$\displaystyle\lim_{k\to\infty}\left\|u_{k}-z^{*}\right\|^{2}$
$\displaystyle\text{ exists for all }z^{*}\in\mathrm{zero}(T),$
$\displaystyle\lim_{k\to\infty}k^{2}\mathrm{dist}(0,T(z_{k}))^{2}$
$\displaystyle=0,$ $\displaystyle\lim_{k\to\infty}k\left\langle
F(z_{k})+\tilde{C}_{k},z_{k}-z^{*}\right\rangle$ $\displaystyle=0,\quad\forall
z^{*}\in\mathrm{zero}(T),$
$\displaystyle\lim_{k\to\infty}k^{2}\left\|z_{k+1}-z_{k}\right\|^{2}$
$\displaystyle=0.$

Moreover, both of the sequences $\\{z_{k}\\}$ and $\\{u_{k}\\}$ converge
weakly to a point in $\mathrm{zero}(T)$.

###### Proof.

The main difficultly is to estimate the error term
$\left\|F(z_{k+1})-F(z_{k+\frac{1}{2}})\right\|$. If

$\sum_{k=0}^{\infty}k\left\|F(z_{k+1})-F(z_{k+\frac{1}{2}})\right\|^{2}<+\infty$

is true, then by applying the proofing technique in the proof of Theorem 4, we
can obtain the results in Corollary 6. Since $F$ is $L-$Lipschitz continuous,
we have

$\left\|F(z_{k+1})-F(z_{k+\frac{1}{2}})\right\|^{2}\leqslant
L^{2}s^{2}\left\|F(z_{k+\frac{1}{2}})+\tilde{C}_{k+1}-\frac{k}{k+r}F(z_{k})-\tilde{C}_{k+\frac{1}{2}}\right\|^{2}.$

Since $s<\dfrac{1}{L}$, there exists a constant $C_{1}>1$ such that
$L^{2}s^{2}C_{1}<1$. By (35), there exists a constant $C_{2}$ such that

$\displaystyle\ \left\|F(z_{k+1})-F(z_{k+\frac{1}{2}})\right\|^{2}$
$\displaystyle\leqslant$ $\displaystyle\
L^{2}s^{2}C_{1}\left\|F(z_{k+1})-F(z_{k+\frac{1}{2}})\right\|^{2}$
$\displaystyle\
+L^{2}s^{2}C_{2}\left\|F(z_{k+1})+\tilde{C}_{k+1}-\frac{k}{k+r}F(z_{k})-\tilde{C}_{k+\frac{1}{2}}\right\|^{2}$
$\displaystyle\leqslant$ $\displaystyle\
L^{2}s^{2}C_{1}\left\|F(z_{k+1})-F(z_{k+\frac{1}{2}})\right\|^{2}+2L^{2}s^{2}C_{2}\left\|\frac{k}{k+r}\tilde{C}_{k}-\tilde{C}_{k+1}\right\|^{2}$
$\displaystyle\
+2L^{2}s^{2}C_{2}\left\|F(z_{k+1})+\tilde{C}_{k+1}-\frac{k}{k+r}F(z_{k})-\frac{k}{k+r}\tilde{C}_{k}\right\|^{2}.$

The proof of Theorem 2 shows that

$\sum_{k=0}^{\infty}(k+r)^{2}\left\|\frac{k}{k+r}\tilde{C}_{k}-\tilde{C}_{k+\frac{1}{2}}\right\|^{2}<+\infty.$

In conclusion,

$\sum_{k=0}^{\infty}k\left\|F(z_{k+1})-F(z_{k+\frac{1}{2}})\right\|^{2}<+\infty$

holds. ∎

##  5 Line Search Framework

The theorems presented in Section 3 indicate that the SEG+ type method
exhibits its maximum theoretical convergence speed when
$D=(r-1)\left(\dfrac{1}{2L}+\rho\right)$. This prompts the question as to
whether the SEG+ type method with $D=(r-1)\left(\dfrac{1}{2L}+\rho\right)$
indeed converges most rapidly in practical applications. We conduct a
straightforward numerical experiment aimed at verifying this question. Here we
consider the following min-max problem:

$\min_{x}\max_{y}f(x,y)=-\frac{1}{6}x^{2}+\frac{2\sqrt{2}}{3}xy+\frac{1}{6}y^{2}.$

Such min-max problem is considered in section 4.4 in [16]. The first-order
criteria of above min-max problem is

$0=F(x,y)=\begin{pmatrix}-\dfrac{1}{3}x+\dfrac{2\sqrt{2}}{3}y\\\
-\dfrac{2\sqrt{2}}{3}x-\dfrac{1}{3}y\end{pmatrix}.$ (36)

It is easily to verify that

$\displaystyle\left\|F(x,y)-F(x^{\prime},y^{\prime})\right\|$
$\displaystyle=\left\|(x,y)-(x^{\prime},y^{\prime})\right\|,\quad\forall(x,y),\
(x^{\prime},y^{\prime}),$ $\displaystyle\left\langle
F(x,y)-F(x^{\prime},y^{\prime}),x-y\right\rangle$
$\displaystyle=-\frac{1}{3}\left\|F(x,y)-F(x^{\prime},y^{\prime})\right\|^{2},\quad\forall(x,y),\
(x^{\prime},y^{\prime}).$

We apply Algorithm 1 with parameter $r=2$ and different parameters $D$ to
above zero-point problem until the termination condition is satisfied. The
required number of iterations of Algorithm 1 respect to $D$ is plotted in
Figure 1.

Figure 1: The required number of iterations Algorithm 1 with $G=0$ respect to
$D$. The termination condition is $\left\|F(x_{k},y_{k})\right\|\leqslant
10^{-6}$.

As we can see from Figure 1, when $D=(r-1)\left(\dfrac{1}{2L}+\rho\right)$, i.
e. $D=\dfrac{1}{6}$, the corresponding instance of Algorithm 1 requires least
number of iterations. However, the Lipschitz constant $L$ and the comonotone
index $\rho$ of the operator $F$ described in (36) can be deduced in advance.
In practice, the Lipschitz constant of most of the operators $F$ and the
comonotone index of most of the operators $T$ can not be determined. In
addition, even though we can determine the Lipschitz constant and the
comonotone index in advance, the operator $F$ may have smaller local Lipschitz
constant or the operator $T$ may have larger local comonotone index as $z_{k}$
approaching $\mathrm{zero}(T)$. Algorithm 1 can not catch these local
information. To overcome these problems, we apply the line search framework to
the SFBS method to estimate these local information.

Since there is a term $\left\langle
F(z_{k})+\tilde{G}_{k},z_{k}-u_{k}\right\rangle$ in the Lyapunov function,
when we consider the difference of $\left\langle
F(z_{k})+\tilde{G}_{k},z_{k}-u_{k}\right\rangle$, $\left\langle
F(z_{k+1})+\tilde{G}_{k+1}-F(z_{k})-\tilde{G}_{k},z_{k+1}-z_{k}\right\rangle$
appears. This is why we need to assume comonotonicity for the operator
$T=F+G$. Thus we propose the termination condition for $\rho_{k}$ is

$\rho_{k}\leqslant\frac{\left\langle
F(z_{k+1})+\tilde{G}_{k+1}-F(z_{k})+\tilde{G}_{k},z_{k+1}-z_{k}\right\rangle}{\left\|F(z_{k+1})+\tilde{G}_{k+1}-F(z_{k})-\tilde{G}_{k}\right\|^{2}}.$

Also, the idea that $F(z_{k+\frac{1}{2}})$ can be seen as an approximation of
$F(z_{k+1})$ inspires us that the Lipschitz continuity on $F$ helps us give an
estimation of the error $\left\|F(z_{k+\frac{1}{2}})-F(z_{k+1})\right\|$.
Because the parameter $L_{k}$ serves as an estimation of local Lipschitz
constant, the termination condition for $L_{k}$ should be

$L_{k}\geqslant\frac{\left\|F(z_{k+\frac{1}{2}})-F(z_{k+1})\right\|}{\left\|z_{k+\frac{1}{2}}-z_{k+1}\right\|}.$

By summarizing previous argument, we obtain Algorithm 3. The convergence
results of Algorithm 3 is given in the following theorems.

Input:  Operator $F$ and Operator $G$;

Initialize:  $z_{0},u_{0}=z_{0}$;

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

repeat

Choosing $\alpha_{k}$, $L_{k}$, $\rho_{k}$ with $\rho_{k}>-\dfrac{1}{2L_{k}}$;

$\tilde{z}_{k+1}=\alpha_{k}u_{k}+(1-\alpha_{k})z_{k}$;

$z_{k+\frac{1}{2}}=\tilde{z}_{k+1}-(1-\alpha_{k})\left(\dfrac{1}{L_{k}}+2\rho_{k}\right)(F(z_{k})+\tilde{G}_{k})$;

$z_{k+1}=J_{L_{k}G}\left(\tilde{z}_{k+1}-\dfrac{1}{L_{k}}F(z_{k+\frac{1}{2}})-(1-\alpha_{k})2\rho_{k}(F(z_{k})+\tilde{G}_{k})\right)$;

$\tilde{G}_{k+1}=L_{k}\left[\tilde{z}_{k+1}-z_{k+1}-\dfrac{1}{L_{k}}F(z_{k+\frac{1}{2}})-(1-\alpha_{k})2\rho_{k}(F(z_{k})+\tilde{G}_{k})\right]$;

until  _$\left\langle
F(z_{k+1})+\tilde{G}_{k+1}-F(z_{k})-\tilde{G}_{k},z_{k+1}-z_{k}\right\rangle\geqslant\rho_{k}\left\|F(z_{k+1})+\tilde{G}_{k+1}-F(z_{k})-\tilde{G}_{k}\right\|^{2}$
, $\left\|F(z_{k+1})-F(z_{k+\frac{1}{2}})\right\|\leqslant
L_{k}\left\|z_{k+1}-z_{k+\frac{1}{2}}\right\|$_;

$u_{k+1}=u_{k}-\dfrac{D}{r}\left(\dfrac{1}{2L_{k}}+\rho_{k}\right)(F(z_{k+1})+\tilde{G}_{k+1})$.

Algorithm 3 Line Search Framework for SEG+

######  Theorem 7.

Let $\\{z_{\frac{k}{2}}\\}$, $\\{\tilde{z}_{k+1}\\}$ and $\\{u_{k}\\}$ be the
sequences generated by Algorithm 3, and let $\\{\mathcal{E}(k)\\}$ be the
Lyapunov function such that

$\displaystyle\mathcal{E}(k)=$ $\displaystyle\
D\left[\left(\sum_{i=0}^{k-1}\frac{1}{2L_{i}}+\rho_{i}\right)^{2}-r\rho_{k-1}\left(\sum_{i=0}^{k-1}\frac{1}{2L_{i}}+\rho_{i}\right)\right]\left\|F(z_{k})+\tilde{G}_{k}\right\|^{2}$
$\displaystyle\
+Dr\left(\sum_{i=0}^{k-1}\frac{1}{2L_{i}}+\rho_{i}\right)\left\langle
F(z_{k})+\tilde{G}_{k},z_{k}-u_{k}\right\rangle+\frac{r^{3}-r^{2}}{2}\left\|u_{k}-z^{*}\right\|^{2},$

where $z^{*}\in\mathcal{H}$. If $r>1$, $0<D<2(r-1)$,

$\begin{gathered}\alpha_{k}=\frac{r\left(\cfrac{1}{2L_{k}}+\rho_{k}\right)}{\left(\sum_{i=0}^{k-1}\cfrac{1}{2L_{i}}+\rho_{i}\right)+r\left(\cfrac{1}{2L_{k}}+\rho_{k}\right)},\\\
\left\langle
F(z_{k+1})+\tilde{G}_{k+1}-F(z_{k})-\tilde{G}_{k},z_{k+1}-z_{k}\right\rangle\geqslant\rho_{k}\left\|F(z_{k+1})+\tilde{G}_{k+1}-F(z_{k})-\tilde{G}_{k}\right\|^{2},\\\
\left\|F(z_{k+1})-F(z_{k+\frac{1}{2}})\right\|\leqslant
L_{k}\left\|z_{k+1}-z_{k+\frac{1}{2}}\right\|,\end{gathered}$

$\rho_{k}>-\dfrac{1}{2L_{k}}$ and $\\{\rho_{k}\\}$ is non-decreasing, then the
upper bound of the difference $\mathcal{E}(k+1)-\mathcal{E}(k)$ is

$\displaystyle\ \mathcal{E}(k+1)-\mathcal{E}(k)$ $\displaystyle\leqslant$
$\displaystyle\
-\frac{D}{2}\left(\frac{1}{2L_{k}}+\rho_{k}\right)\left(r-1-\frac{D}{2}\right)\left[(r-1)\left(\frac{1}{2L_{k}}+\rho_{k}\right)+2\Sigma_{k+1}\right]\left\|F(z_{k+1})+\tilde{G}_{k+1}\right\|^{2}$
$\displaystyle\
+D(r^{2}-r)\left(\frac{1}{2L_{k}}+\rho_{k}\right)\left(\rho_{k}\left\|\tilde{T}(z_{k+1})\right\|^{2}-\left\langle\tilde{T}(z_{k+1}),z_{k+1}-z^{*}\right\rangle\right).$

###### Proof.

For the sake of simplicity, let
$\Sigma_{k}=\sum\limits_{i=0}^{k-1}\dfrac{1}{2L_{i}}+\rho_{i}$ and
$\tilde{T}(z_{k})=F(z_{k})+\tilde{G}_{k}$. First, we have

$\displaystyle\Sigma_{k}(z_{k+1}-z_{k})=$ $\displaystyle\
r\left(\frac{1}{2L_{k}}+\rho_{k}\right)(u_{k}-z_{k+1})-2\rho_{k}\Sigma_{k}\tilde{T}(z_{k})$
$\displaystyle\
-\frac{1}{L_{k}}\cdot\left[r\left(\frac{1}{2L_{k}}+\rho_{k}\right)+\Sigma_{k}\right](F(z_{k+\frac{1}{2}})+\tilde{G}_{k+1}),$
(37) $\displaystyle r\left(\frac{1}{2L_{k}}+\rho_{k}\right)(z_{k}-u_{k})=$
$\displaystyle\
-\left[r\left(\frac{1}{2L_{k}}+\rho_{k}\right)+\Sigma_{k}\right](z_{k+1}-z_{k})-2\rho_{k}\Sigma_{k}(F(z_{k})+\tilde{G}_{k})$
$\displaystyle\
-\frac{1}{L_{k}}\left[r\left(\frac{1}{2L_{k}}+\rho_{k}\right)+\Sigma_{k}\right](F(z_{k+\frac{1}{2}})+\tilde{G}_{k+1}).$
(38)

Next, we divide the difference $\mathcal{E}(k+1)-\mathcal{E}(k)$ into three
parts.

$\displaystyle\mathcal{E}(k+1)-\mathcal{E}(k)=$ $\displaystyle\
\underbrace{D(\Sigma_{k+1}^{2}-r\rho_{k}\Sigma_{k+1})\left\|\tilde{T}(z_{k+1})\right\|^{2}-D(\Sigma_{k}^{2}-r\rho_{k-1}\Sigma_{k})\left\|\tilde{T}(z_{k})\right\|^{2}}_{\text{I}}$
$\displaystyle\
+\underbrace{Dr\Sigma_{k+1}\left\langle\tilde{T}(z_{k+1}),z_{k+1}-u_{k+1}\right\rangle-
Dr\Sigma_{k}\left\langle\tilde{T}(z_{k}),z_{k}-u_{k}\right\rangle}_{\text{II}}$
$\displaystyle\
+\underbrace{\frac{r^{3}-r^{2}}{2}\left[\left\|u_{k+1}-z^{*}\right\|^{2}-\left\|u_{k}-z^{*}\right\|^{2}\right]}_{\text{III}}.$

The upper bound of II and III can be estimated as follows. First, we consider
II. We split II into three parts as follows:

$\displaystyle\text{II}=$ $\displaystyle\
Dr\left(\frac{1}{2L_{k}}+\rho_{k}\right)\left\langle\tilde{T}(z_{k+1}),z_{k+1}-u_{k+1}\right\rangle+Dr\Sigma_{k}\left\langle\tilde{T}(z_{k+1}),z_{k+1}-z_{k}-u_{k+1}+u_{k}\right\rangle$
$\displaystyle\
+Dr\Sigma_{k}\left\langle\tilde{T}(z_{k+1})-\tilde{T}(z_{k}),z_{k}-u_{k}\right\rangle.$

By (37), (38) and
$u_{k+1}=u_{k}-\dfrac{D}{r}\left(\dfrac{1}{2L_{k}}+\rho_{k}\right)\tilde{T}(z_{k+1})$,
we have

$\displaystyle\text{II}=$ $\displaystyle\
Dr\left(\frac{1}{2L_{k}}+\rho_{k}\right)\left\langle\tilde{T}(z_{k+1}),z_{k+1}-u_{k}\right\rangle+D^{2}\left(\frac{1}{2L_{k}}+\rho_{k}\right)\Sigma_{k+1}\left\|\tilde{T}(z_{k+1})\right\|^{2}$
$\displaystyle\
+Dr\left\langle\tilde{T}(z_{k+1}),r\left(\frac{1}{2L_{k}}+\rho_{k}\right)(u_{k}-z_{k+1})-2\rho_{k}\Sigma_{k}\tilde{T}(z_{k})\right\rangle$
$\displaystyle\
-Dr\left\langle\tilde{T}(z_{k+1}),\frac{1}{L_{k}}\left[r\left(\frac{1}{2L_{k}}+\rho_{k}\right)+\Sigma_{k}\right](F(z_{k+\frac{1}{2}})+\tilde{G}_{k+1})\right\rangle$
$\displaystyle\
-D\left(\frac{1}{2L_{k}}+\rho_{k}\right)^{-1}\Sigma_{k}\left[r\left(\frac{1}{2L_{k}}+\rho_{k}\right)+\Sigma_{k}\right]\left\langle\tilde{T}(z_{k+1})-\tilde{T}(z_{k}),z_{k+1}-z_{k}\right\rangle$
$\displaystyle\
-D\left(\frac{1}{2L_{k}}+\rho_{k}\right)^{-1}\Sigma_{k}\left\langle\tilde{T}(z_{k+1})-\tilde{T}(z_{k}),\frac{1}{L_{k}}\left[r\left(\frac{1}{2L_{k}}+\rho_{k}\right)+\Sigma_{k}\right](F(z_{k+\frac{1}{2}})+\tilde{G}_{k+1})\right\rangle$
$\displaystyle\
-D\left(\frac{1}{2L_{k}}+\rho_{k}\right)^{-1}\Sigma_{k}\left\langle\tilde{T}(z_{k+1})-\tilde{T}(z_{k}),2\rho_{k}\Sigma_{k}\tilde{T}(z_{k})\right\rangle.$

By the assumption

$\left\|F(z_{k+1})-F(z_{k+\frac{1}{2}})\right\|\leqslant
L_{k}\left\|z_{k+1}-z_{k+\frac{1}{2}}\right\|,$

we have

$\left\|F(z_{k+1})-F(z_{k+\frac{1}{2}})\right\|^{2}\leqslant\left\|F(z_{k+\frac{1}{2}})+\tilde{G}_{k+1}-\left(\Sigma_{k}+\frac{r}{2L_{k}}+r\rho_{k}\right)^{-1}\Sigma_{k}\tilde{T}(z_{k})\right\|^{2}.$

Combining previous estimation and the assumption

$\left\langle\tilde{T}(z_{k+1})-\tilde{T}(z_{k}),z_{k+1}-z_{k}\right\rangle\geqslant\rho_{k}\left\|\tilde{T}(z_{k+1})-\tilde{T}(z_{k})\right\|^{2},$

we can deduce the upper bound of II as follows:

$\displaystyle\text{II}\leqslant$ $\displaystyle\
-D\cfrac{\left[r\left(\cfrac{1}{2L_{k}}+\rho_{k}\right)+\Sigma_{k}\right]^{2}}{1+2L_{k}\rho_{k}}\left\|\tilde{T}(z_{k+1})\right\|^{2}+D^{2}\left(\frac{1}{2L_{k}}+\rho_{k}\right)\Sigma_{k+1}\left\|\tilde{T}(z_{k+1})\right\|^{2}$
$\displaystyle\
-D\rho_{k}\left(\frac{1}{2L_{k}}+\rho_{k}\right)^{-1}\Sigma_{k}\left[r\left(\frac{1}{2L_{k}}+\rho_{k}\right)+\Sigma_{k}\right]\left\|\tilde{T}(z_{k+1})\right\|^{2}$
$\displaystyle\
+D(\Sigma_{k}^{2}-r\rho_{k}\Sigma_{k})\left\|\tilde{T}(z_{k})\right\|^{2}+D(r^{2}-r)\left(\frac{1}{2L_{k}}+\rho_{k}\right)\left\langle\tilde{T}(z_{k+1}),u_{k}-z_{k+1}\right\rangle.$

Next, we consider III. By (18), we have

$\text{III}=\
-D(r^{2}-r)\left(\frac{1}{2L_{k}}+\rho_{k}\right)\left\langle\tilde{T}(z_{k+1}),u_{k}-z^{*}\right\rangle+\frac{D(r-1)}{2}\left(\frac{1}{2L_{k}}+\rho_{k}\right)^{2}\left\|\tilde{T}(z_{k+1})\right\|^{2}.$

Finally, we can estimate the upper bound of $\mathcal{E}(k+1)-\mathcal{E}(k)$.
Combining previous estimations and non-decreasing of $\\{\rho_{k}\\}$, we have

$\displaystyle\ \mathcal{E}(k+1)-\mathcal{E}(k)$ $\displaystyle\leqslant$
$\displaystyle\
-D\left[\frac{(r-1)^{2}}{2L_{k}}\left(\frac{1}{2L_{k}}+\rho_{k}\right)+\Sigma_{k+1}^{2}+\frac{r-1}{L_{k}}\Sigma_{k+1}-(r-1)\left(\frac{1}{2L_{k}}+\rho_{k}\right)\rho_{k}\right]\left\|\tilde{T}(z_{k+1})\right\|^{2}$
$\displaystyle\
+D\left[\Sigma_{k+1}^{2}-2(r-1)\rho_{k}\Sigma_{k+1}+D\left(\frac{1}{2L_{k}}+\rho_{k}\right)\Sigma_{k+1}+\frac{D(r-1)}{2}\left(\frac{1}{2L_{k}}+\rho_{k}\right)^{2}\right]\left\|\tilde{T}(z_{k+1})\right\|^{2}$
$\displaystyle\
-D(r^{2}-r)\left(\frac{1}{2L_{k}}+\rho_{k}\right)\left\langle\tilde{T}(z_{k+1}),z_{k+1}-z^{*}\right\rangle.$

By adding and subtracting
$D(r^{2}-r)\rho_{k}\left(\dfrac{1}{2L_{k}}+\rho_{k}\right)\left\|\tilde{T}(z_{k+1})\right\|^{2}$,
we have

$\displaystyle\mathcal{E}(k+1)-\mathcal{E}(k)\leqslant$ $\displaystyle\
-\frac{D}{2}\left(\frac{1}{2L_{k}}+\rho_{k}\right)\left(r-1-\frac{D}{2}\right)\left[(r-1)\left(\frac{1}{2L_{k}}+\rho_{k}\right)+2\Sigma_{k+1}\right]\left\|\tilde{T}(z_{k+1})\right\|^{2}$
$\displaystyle\
+D(r^{2}-r)\left(\frac{1}{2L_{k}}+\rho_{k}\right)\left(\rho_{k}\left\|\tilde{T}(z_{k+1})\right\|^{2}-\left\langle\tilde{T}(z_{k+1}),z_{k+1}-z^{*}\right\rangle\right).$

At this point, we obtain the desired result. ∎

By using Theorem 7, one can easily propose a sufficient condition to guarantee
the convergence of Algorithm 3.

######  Corollary 8.

Let $\\{z_{\frac{k}{2}}\\}$, $\\{\tilde{z}_{k+1}\\}$ and $\\{u_{k}\\}$ be the
sequences generated by Algorithm 3. If the parameters $\\{L_{k}\\}$,
$\\{\rho_{k}\\}$ and $D$ satisfy the assumptions in Theorem 7 and there exists
a $z^{*}$ such that the inequality

$\left\langle
F(z_{k+1}+\tilde{G}_{k+1},z_{k+1}-z^{*}\right\rangle\geqslant\rho_{k}\left\|F(z_{k+1})+\tilde{G}_{k+1}\right\|^{2}$

is hold for all $k=0$, $1$, $\cdots$, then we have

$\mathrm{dist}(0,T(z_{k}))^{2}\leqslant\cfrac{r^{2}(r-1)^{2}}{[2(r-1)D-D^{2}]\left(\sum\limits_{i=0}^{k-1}\cfrac{1}{2L_{i}}+\rho_{i}\right)^{2}}\left\|z_{0}-z^{*}\right\|^{2},\quad\forall
k\geqslant 1.$

###### Proof.

Consider the Lyapunov function $\mathcal{E}(k)$ defined in Theorem 7. Let
$z^{*}$ in $\mathcal{E}(k)$ be the point defined in Corollary 8. By the upper
bound of $\mathcal{E}(k+1)-\mathcal{E}(k)$ in Theorem 7 , the assumption
$D<2(r-1)$ and $\left\langle
F(z_{k+1})+\tilde{G}_{k+1},z_{k+1}-z^{*}\right\rangle\geqslant\rho_{k}\left\|F(z_{k+1})\right\|^{2}$,
we have

$\mathcal{E}(k+1)-\mathcal{E}(k)\leqslant 0.$

Next, we deduce the lower bound of $\mathcal{E}(k)$. Since $\left\langle
F(z_{k+1})+\tilde{G}_{k+1},z_{k+1}-z^{*}\right\rangle\geqslant\rho_{k}\left\|F(z_{k+1})+\tilde{G}_{k+1}\right\|^{2}$,
we have

$\displaystyle\mathcal{E}(k)\geqslant$
$\displaystyle\left(D-\frac{D^{2}}{2(r-1)}\right)\left(\sum_{i=0}^{k-1}\frac{1}{2L_{i}}+\rho_{i}\right)^{2}\left\|F(z_{k})+\tilde{G}_{k}\right\|^{2}$
$\displaystyle\
+\frac{1}{2}\left\|\frac{D}{\sqrt{r-1}}\left(\sum_{i=0}^{k-1}\frac{1}{2L_{i}}+\rho_{i}\right)F(z_{k})-\sqrt{r^{3}-r^{2}}(u_{k}-z^{*})\right\|^{2}.$

Thus

$\displaystyle\
\left(D-\frac{D^{2}}{2(r-1)}\right)\left(\sum_{i=0}^{k-1}\frac{1}{2L_{i}}+\rho_{i}\right)^{2}\mathrm{dist}(0,T(z_{k}))^{2}$
$\displaystyle\leqslant$ $\displaystyle\
\left(D-\frac{D^{2}}{2(r-1)}\right)\left(\sum_{i=0}^{k-1}\frac{1}{2L_{i}}+\rho_{i}\right)^{2}\left\|F(z_{k})+\tilde{G}_{k}\right\|^{2}$
$\displaystyle\leqslant$ $\displaystyle\
\mathcal{E}(k)\leqslant\mathcal{E}(0)=\frac{r^{3}-r^{2}}{2}\left\|z_{0}-z^{*}\right\|^{2}.$

By dividing
$\left(D-\dfrac{D^{2}}{2(r-1)}\right)\left(\sum\limits_{i=0}^{k-1}\dfrac{1}{2L_{i}}+\rho_{i}\right)^{2}$
on both sides of above inequality, we obtain the desired result. ∎

However, the assumption $\left\langle
F(z_{k+1})+\tilde{G}_{k+1},z_{k+1}-z^{*}\right\rangle\geqslant\rho_{k}\left\|F(z_{k+1})\right\|^{2}$
can not be determined in practice. To overcome such problem, we introduce an
upper bound constraint on $\rho_{k}$.

######  Corollary 9.

Let $\\{z_{\frac{k}{2}}\\}$, $\\{\tilde{z}_{k+1}\\}$ and $\\{u_{k}\\}$ be the
sequences generated by Algorithm 3. If the parameters $\\{L_{k}\\}$,
$\\{\rho_{k}\\}$ and $D$ satisfy the assumptions in Theorem 7 and there exists
a $z^{*}$ such that

$\begin{gathered}\left\langle
F(z_{k})+\tilde{G}_{k},z-z^{*}\right\rangle\geqslant\tilde{\rho}_{k}\left\|F(z_{k})+\tilde{G}_{k}\right\|^{2},\quad\forall
z,\\\
\rho_{k}-\tilde{\rho}_{k}\leqslant\frac{E_{k}}{r}\left(1-\frac{D}{2(r-1)}\right)\left(\sum_{i=0}^{k}\frac{1}{2L_{i}}+\rho_{i}\right),\quad
E_{k}\in[0,1],\end{gathered}$

then we have

$\displaystyle\
\sum_{k=0}^{\infty}\frac{D}{2}\left(\frac{1}{2L_{k}}+\rho_{k}\right)\left(r-1-\frac{D}{2}\right)\left[(r-1)\left(\frac{1}{2L_{k}}+\rho_{k}\right)+2(1-E_{k})\Sigma_{k+1}\right]\mathrm{dist}(0,T(z_{k+1}))^{2}$
$\displaystyle\leqslant$ $\displaystyle\
\frac{r^{3}-r^{2}}{2}\cdot\left\|z_{0}-z^{*}\right\|^{2},$
$\displaystyle(1-E_{k})\left(1-\frac{D}{2r-2}\right)\Sigma_{k}^{2}\mathrm{dist}(0,T(z_{k}))^{2}\leqslant\frac{r^{3}-r^{2}}{2D}\cdot\left\|z_{0}-z^{*}\right\|^{2},$

where $\Sigma_{k}=\sum\limits_{i=0}^{k-1}\dfrac{1}{2L_{i}}+\rho_{i}$.

###### Proof.

For the sake of simplicity, let $\tilde{T}(z_{k})=F(z_{k})+\tilde{G}_{k}$. Let
$z^{*}$ in Theorem 7 be the point such that
$\left\langle\tilde{T}(z_{k}),z_{k}-z^{*}\right\rangle\geqslant\tilde{\rho}_{k}\left\|\tilde{T}(z_{k})\right\|^{2}$,
$\forall k$. Then we have

$\displaystyle\mathcal{E}(k+1)-\mathcal{E}(k)\leqslant$ $\displaystyle\
-\frac{D}{2}\left(\frac{1}{2L_{k}}+\rho_{k}\right)\left(r-1-\frac{D}{2}\right)\left[(r+1)\left(\frac{1}{2L_{k}}+\rho_{k}\right)+2\Sigma_{k+1}\right]\left\|\tilde{T}(z_{k+1})\right\|^{2}$
$\displaystyle\
+D(r^{2}-r)\left(\frac{1}{2L_{k}}+\rho_{k}\right)(\rho_{k}-\tilde{\rho}_{k})\left\|\tilde{T}(z_{k+1})\right\|^{2}.$

By the assumption that
$\rho_{k}-\tilde{\rho}_{k}\leqslant\dfrac{E}{r}\left(1-\dfrac{D}{2(r-1)}\right)\Sigma_{k+1}$,
we have

$\displaystyle\ \mathcal{E}(k+1)-\mathcal{E}(k)$ $\displaystyle\leqslant$
$\displaystyle\
-\frac{D}{2}\left(\frac{1}{2L_{k}}+\rho_{k}\right)\left(r-1-\frac{D}{2}\right)\left[(r-1)\left(\frac{1}{2L_{k}}+\rho_{k}\right)+2(1-E_{k})\Sigma_{k+1}\right]\left\|\tilde{T}(z_{k+1})\right\|^{2}.zs$

In addition, the lower bound of $\mathcal{E}(k)$ can be estimated as follows:

$\mathcal{E}(k)\geqslant(1-E_{k})D\left(1-\frac{D}{2r-2}\right)\Sigma_{k}^{2}\left\|\tilde{T}(z_{k})\right\|^{2}+\frac{1}{2}\left\|\frac{D}{\sqrt{r-1}}\Sigma_{k}\tilde{T}(z_{k})-\sqrt{r^{3}-r^{2}}(u_{k}-z^{*})\right\|^{2}\geqslant
0.$

Thus, we have

$\displaystyle\
(1-E_{k})\left(1-\frac{D}{2r-2}\right)\Sigma_{k}^{2}\mathrm{dist}(0,T(z_{k}))^{2}$
$\displaystyle\leqslant$ $\displaystyle\
(1-E_{k})\left(1-\frac{D}{2r-2}\right)\Sigma_{k}^{2}\left\|\tilde{T}(z_{k})\right\|^{2}$
$\displaystyle\leqslant$ $\displaystyle\
\mathcal{E}(k)\leqslant\mathcal{E}(0)=\frac{r^{3}-r^{2}}{2}\left\|z_{0}-z^{*}\right\|^{2}.$

Also, by summing $\mathcal{E}(k+1)-\mathcal{E}(k)$ from 0 to $\infty$, we can
obtain the ergodic convergence rate of Algorithm 3. ∎

The line search framework of the SPEG+ method is similar to Algorithm 3, which
is described as follows along with its convergence results.

######  Corollary 10 (SPEG+ with line search).

Let $\\{z_{\frac{k}{2}}\\}$, $\\{\tilde{z}_{k+1}\\}$ and $\\{u_{k}\\}$ be the
sequences generated by the following recursive rule:

$\displaystyle\tilde{z}_{k+1}$
$\displaystyle=(1-\alpha_{k})z_{k}+\alpha_{k}u_{k},$ $\displaystyle
z_{k+\frac{1}{2}}$
$\displaystyle=P_{C}\left(\tilde{z}_{k+1}-(1-\alpha_{k})\frac{1}{L_{k}}F(z_{k})\right),$
$\displaystyle z_{k+1}$
$\displaystyle=P_{C}\left(\tilde{z}_{k+1}-\dfrac{1}{L_{k}}F(z_{k+\frac{1}{2}})\right),$
$\displaystyle\tilde{C}_{k+1}$
$\displaystyle=L_{k}(\tilde{z}_{k+1}-z_{k+1})-F(z_{k+\frac{1}{2}}),$
$\displaystyle u_{k+1}$
$\displaystyle=u_{k}-\dfrac{D}{2rL_{k}}[F(z_{k+1})+\tilde{C}_{k+1}].$

If $\alpha_{k}=\dfrac{rL_{k}^{-1}}{\sum_{i=0}^{k-1}L_{i}^{-1}+rL_{k}}$, $r>1$,
$0<D<2(r-1)$ and
$L_{k}\geqslant\dfrac{\left\|F(z_{k+\frac{1}{2}})-F(z_{k+1})\right\|}{\left\|z_{k+\frac{1}{2}}-z_{k+1}\right\|}$,
then we have

$\displaystyle\mathrm{dist}(0,T(z_{k}))^{2}$
$\displaystyle\leqslant\cfrac{r^{2}(r-1)^{2}}{[2(r-1)D-D^{2}]\left(\sum\limits_{i=0}^{k-1}\cfrac{1}{2L_{i}}\right)^{2}}\cdot\mathrm{dist}(z_{0},\mathrm{zero}(T))^{2},\quad\forall
k\geqslant 1,$ $\displaystyle\left\langle
F(z_{k})+\tilde{C}_{k},z_{k}-z^{*}\right\rangle$
$\displaystyle\leqslant\frac{r^{2}-r}{Dr\sum_{i=0}^{k-1}{L_{i}}^{-1}}\left\|z_{0}-z^{*}\right\|^{2},\quad\forall
z^{*}\in\mathrm{zero}(T).$

The proof for Corollary 10 is similar to the proof for Theorem 7 and Corollary
8. Thus, we omit the proof of Corollary 10.

Remark.  1) Although previous arguments suggest that when $D=r-1$, the
corresponding instance of Algorithm 3 may obtain the fastest numerical
performance, this result is not generally observed in practical numerical
experiment. The reason is that the inequalities

$\displaystyle\rho_{k}$ $\displaystyle\leqslant\frac{\left\langle
F(z_{k+1})+\tilde{G}_{k+1}-F(z_{k})+\tilde{G}_{k},z_{k+1}-z_{k}\right\rangle}{\left\|F(z_{k+1})+\tilde{G}_{k+1}-F(z_{k})-\tilde{G}_{k}\right\|^{2}},$
$\displaystyle L_{k}$
$\displaystyle\geqslant\frac{\left\|F(z_{k+\frac{1}{2}})-F(z_{k+1})\right\|}{\left\|z_{k+\frac{1}{2}}-z_{k+1}\right\|}$

are generally strict. Thus we encourage that $D>r-1$ when using Algorithm 3.

2) In Theorem 7, Algorithm 3 imposes a condition that the parameter $\rho_{k}$
is non-decreasing. Nonetheless, a problem may occur in practice, that is
$\rho_{k}$ may grow too large so that there does not exist a feasible point
$z_{k+1}$ such that the line search principle can be fulfilled. To circumvent
this problem, a simple solution is restarting the algorithm. Specifically, run
Algorithm 3 again with initial point $z_{k}$.

##  6 Numerical Experiments

###  6.1 Matrix Game Problem

Here, we consider the matrix game problem illustrated in Example 1. In our
experiment, we evaluate the numerical performance of the SPEG+ method with
line search. Specifically, the matrix $A\in\mathbb{R}^{1000\times 1000}$ is
randomly generated and the parameter $D$ in Algorithm 3 is set to $1.6$. For
comparison, both the Projected EG method with line search and the Projected
FEG method with line search are included in this experiment. Each algorithm
runs for a duration of 40 seconds. Subsequently, we depict the squared norm of
$\tilde{T}(z_{k})=F(z_{k})+\tilde{G}_{k}$ and the duality gap over time in
Figure 2. Here, the duality gap is defined as
$\max_{y\in\Delta_{n}}x_{k}^{\top}Ay-\min_{x\in\Delta_{m}}x^{\top}Ay_{k}$.

Figure 2: Evolution of duality gap and $\left\|\tilde{T}(z_{k})\right\|^{2}$
versus running time.

As we can see from Figure 2, in comparison to the projected EG method with
line search and the projected FEG method with line search, the SPEG+ method
with line search converges fastest.

Since the normal cone of a closed convex set is a maximally monotone operator,
we are interested in examining the numerical performance of the SPEG+ method
and the SFBS method. The test problem remains the matrix game. Following a
40-second runtime for each algorithm, we plot
$\left\|\tilde{T}(z_{k})\right\|^{2}$ and duality gap with respect to running
time in Figure 3, too.

Figure 3: Comparison of SFBS and SPEG+.

As Figure 3 illustrates, the SPEG+ method converges faster than the SFBS
method in practice. This suggests that the SPEG+ method may better exploit the
structure of (19). Consequently, we recommend utilizing the SPEG+ method for
solving (19) when projections onto $C$ can be easily computed.

###  6.2 Lasso Problem

Here, we consider the LASSO problem

$\min_{x}F(x):=\frac{1}{2}\left\|Ax-b\right\|^{2}+\mu\left\|x\right\|_{1}.$
(39)

(39) can be transformed into the following constrained optimization problem

$\begin{gathered}\min_{x,y}\frac{1}{2}\left\|Ax-b\right\|^{2}+\mu\left\|y\right\|_{1}\\\
s.\ t.\quad x=y.\end{gathered}$

The ADMM method is a powerful method to solve LASSO problem and the
convergence rate of ADMM was been proven to be $O(1/k^{2})$ when applied to
LASSO problem in the research work [30]. Since the ADMM method is an instance
of the proximal point algorithm, we can use Algorithm 3 with $F=0$ and
$L_{k}\equiv 1$ to obtain a new ADMM type method with line search. In our
experiment, we test the numerical performance of the new ADMM method with line
search. Here, the matrix $A\in\mathbb{R}^{1000\times 2000}$ and the vector
$b\in\mathbb{R}^{1000}$ are randomly generated, and the parameter $D$ in
Algorithm 3 is set to be $1.6$. The ADMM method is comparable in our
experiment. After running the algorithms, we graph the residual
$\left\|x_{k}-y_{k}\right\|$ and $F(y_{k})-F^{*}$ respect to running time in
the following figure, where $F^{*}$ represents the optimal value of the LASSO
problem (39) as determined by an alternative algorithm.

Figure 4: Evolution of $\left\|x_{k}-y_{k}\right\|$ and $F(y_{k})-F^{*}$
versus running time.

From Figure 4, it is evident that despite the theoretically established
$O(1/k^{2})$ convergence rate of ADMM, the new ADMM derived by Algorithm 3
exhibits even faster convergence in our experiment.

##  7 Conclusion and Further Discussion

In our paper, we introduce the symplectic extra-gradient type methods based on
the symplectic proximal point algorithm. By using the Lyapunov function
approach, we show these methods have a convergence rate of $O(1/k^{2})$. We
also prove they can achieve a faster $o(1/k^{2})$ convergence rate and show
weak convergence property under stronger assumptions. To improve computational
speed, we incorporate a line search technique into our symplectic extra-
gradient method.

Several theoretical questions around SEG type method remain. With the
heightened need for efficient Generative Adversarial Networks training,
studying a stochastic version of our method is intriguing. Furthermore,
inspired by Tseng’s method for more general monotone inclusion problems
discussed in [1], developing a more general SEG type method is of interest.
Finally, we are intrigued to explore whether symplectic acceleration can be
useful to derive a broader range of acceleration forms of algorithms that
designed to solve either minimax problems or inclusion problems.

Practically, creating efficient algorithms to find good values for $L_{k}$ and
$\rho_{k}$ in Algorithm 3, or just $L_{k}$ as in Corollary 10, is a concern.
Our LASSO problem tests indicate that the current line search for $\rho_{k}$
does not speed up calculations significantly. One suggestion from our analysis
in Corollary 9 is that $\rho_{k}$ shouldn’t greatly exceed the comonotone
index. Therefore, improving when to stop adjusting $\rho_{k}$ could be
beneficial.

##  Appendix A Convergence of Symplectic Extra-gradient Method

To proof convergence of the symplectic extra-gradient method, we need to study
the following Lyapunov function:

$\mathcal{E}(k)=\frac{A_{k}}{2}\left\|F(z_{k})\right\|^{2}+B_{k}\left\langle
F(z_{k}),z_{k}-u_{k}\right\rangle.$ (40)

The first thing we should do is to find out the sufficient condition to ensure
that $\mathcal{E}$ is a Lyapunov function, i. e. $\\{\mathcal{E}(k)\\}$ is
non-increasing. The conditions (41)-(43) are based on the conditions in Lemma
2 in [37].

######  Theorem 11.

Let $\\{z_{\frac{k}{2}}\\}$, $\\{\tilde{z}_{k}\\}$ and $\\{u_{k}\\}$ be the
sequences generated by (9). If

$\displaystyle A_{k}$ $\displaystyle=\frac{B_{k}\beta_{k}}{\alpha_{k}},$ (41)
$\displaystyle B_{k+1}$ $\displaystyle=\frac{B_{k}}{1-\alpha_{k}},$ (42)
$\displaystyle\beta_{k+1}+2C_{k}\alpha_{k+1}$
$\displaystyle=\frac{\beta_{k}\alpha_{k+1}(1-L^{2}\beta_{k}^{2}-\alpha_{k}^{2})}{\alpha_{k}(1-\alpha_{k})(1-L^{2}\beta_{k}^{2})},$
(43) $\displaystyle\beta_{k}$ $\displaystyle\in(0,\frac{1}{L}),\quad\forall
k\geqslant 0.\,$ (44)

then the sequence $\\{\mathcal{E}(k)\\}$ is non-increasing.

###### Proof.

Step 1: Dividing the difference $\mathcal{E}(k+1)-\mathcal{E}(k)$ into 2
parts.

$\displaystyle\mathcal{E}(k+1)-\mathcal{E}(k)=$ $\displaystyle\
\underbrace{\frac{A_{k+1}}{2}\left\|F(z_{k+1})^{2}\right\|-\frac{A_{k}}{2}\left\|F(z_{k})\right\|^{2}}_{\text{I}}$
$\displaystyle\ +\underbrace{B_{k+1}\left\langle
F(z_{k+1}),z_{k+1}-u_{k+1}\right\rangle-B_{k}\left\langle
F(z_{k}),z_{k}-u_{k}\right\rangle}_{\text{II}}.$

Step 2: Estimate the upper bound of II. II can be divided into the following
three pieces.

$\displaystyle\ B_{k+1}\left\langle F(z_{k+1}),z_{k+1}-u_{k+1}\right\rangle-
B_{k}\left\langle F(z_{k}),z_{k}-u_{k}\right\rangle$ $\displaystyle=$
$\displaystyle\ (B_{k+1}-B_{k})\left\langle
F(z_{k+1}),z_{k+1}-u_{k+1}\right\rangle+B_{k}\left\langle
F(z_{k+1}),z_{k+1}-z_{k}-u_{k+1}+u_{k}\right\rangle$
$\displaystyle+B_{k}\left\langle
F(z_{k+1})-F(z_{k}),z_{k}-u_{k}\right\rangle.$

Since

$z_{k+1}=\alpha_{k}u_{k}+(1-\alpha_{k})z_{k}-\beta_{k}F(x_{k+\frac{1}{2}}),$

we have

$B_{k}\left\langle
F(z_{k+1})-F(z_{k}),z_{k}-u_{k}\right\rangle=B_{k}\left\langle
F(z_{k+1})-F(z_{k}),-\frac{1}{\alpha_{k}}(z_{k+1}-z_{k})-\frac{\beta_{k}}{\alpha_{k}}F(z_{k+\frac{1}{2}})\right\rangle.$
(45)

Also, we have

$\begin{split}&\ B_{k}\left\langle
F(z_{k+1}),z_{k+1}-z_{k}-u_{k+1}+u_{k}\right\rangle\\\ =&\ B_{k}\left\langle
F(z_{k+1}),\frac{\alpha_{k}}{1-\alpha_{k}}(u_{k}-z_{k+1})-\frac{\beta_{k}}{1-\alpha_{k}}F(z_{k+\frac{1}{2}})\right\rangle+B_{k}C_{k}\left\|F(z_{k+1})\right\|^{2}.\end{split}$
(46)

In addition, we have

$(B_{k+1}-B_{k})\left\langle
F(z_{k+1}),z_{k+1}-u_{k+1}\right\rangle=(B_{k+1}-B_{k})C_{k}\left\|F(z_{k+1})\right\|^{2}+(B_{k+1}-B_{k})\left\langle
F(z_{k+1}),z_{k+1}-u_{k}\right\rangle.$ (47)

By summing (45), (46) and (47) and using (42), we obtain

$\displaystyle\text{II}=$ $\displaystyle\
B_{k+1}C_{k}\left\|F(x_{k+1})\right\|^{2}-\frac{B_{k}}{a_{k}}\left\langle
F(z_{k+1})-F(z_{k}),z_{k+1}-z_{k}\right\rangle$ $\displaystyle\
-\left(\frac{B_{k}\beta_{k}}{\alpha_{k}}+\frac{B_{k}\beta_{k}}{1-\alpha_{k}}\right)\left\langle
F(z_{k+1}),F(z_{k+\frac{1}{2}})\right\rangle+\frac{B_{k}\beta_{k}}{\alpha_{k}}\left\langle
F(z_{k}),F(z_{k+\frac{1}{2}})\right\rangle.$

Since $F$ is $L-$Lipschitz continuous, we have

$\displaystyle\left\|F(z_{k+1})-F(z_{k+\frac{1}{2}})\right\|^{2}$
$\displaystyle\leqslant
L^{2}\beta_{k}^{2}\left\|F(z_{k+\frac{1}{2}})-F(z_{k})\right\|^{2}.$

Because of the equality

$-\left\langle
F(z_{k+1}),F(z_{k+\frac{1}{2}})\right\rangle=\frac{1}{2}\left[\left\|F(z_{k+1})-F(z_{k+\frac{1}{2}})\right\|^{2}-\left\|F(z_{k+1})\right\|^{2}-\left\|F(z_{k+\frac{1}{2}})\right\|^{2}\right],$

we have

$\displaystyle\text{II}\leqslant$
$\displaystyle\left(B_{k+1}C_{k}-\frac{B_{k}\beta_{k}}{2\alpha_{k}L^{2}\beta_{k}^{2}}\right)\left\|F(z_{k+1})\right\|^{2}+\frac{B_{k}\beta_{k}}{2\alpha_{k}}\left\|F(z_{k})\right\|^{2}+\frac{B_{k}\beta_{k}}{2\alpha_{k}}(1-\frac{1}{L^{2}\beta_{k}^{2}})\left\|F(z_{k+\frac{1}{2}})\right\|^{2}$
$\displaystyle-\left(\frac{B_{k}\beta_{k}}{\alpha_{k}}(1-\frac{1}{L^{2}\beta_{k}^{2}})+\frac{B_{k}\beta_{k}}{1-\alpha_{k}}\right)\left\langle
F(z_{k+\frac{1}{2}}),F(z_{k+1})\right\rangle.$

Step 3: Estimate the upper bound of $\mathcal{E}(k+1)-\mathcal{E}(k)$. By
previous estimation and the equality (41), we have

$\displaystyle\mathcal{E}(k+1)-\mathcal{E}(k)\leqslant$ $\displaystyle\
\left(\frac{A_{k+1}}{2}+B_{k+1}C_{k}-\frac{B_{k}\beta_{k}}{2\alpha_{k}L^{2}\beta_{k}^{2}}\right)\left\|F(z_{k+1})\right\|^{2}+\frac{B_{k}\beta_{k}}{2\alpha_{k}}(1-\frac{1}{L^{2}\beta_{k}^{2}})\left\|F(z_{k+\frac{1}{2}})\right\|^{2}$
$\displaystyle\
-\left(\frac{B_{k}\beta_{k}}{\alpha_{k}}(1-\frac{1}{L^{2}\beta_{k}^{2}})+\frac{B_{k}\beta_{k}}{1-\alpha_{k}}\right)\left\langle
F(z_{k+\frac{1}{2}}),F(z_{k+1})\right\rangle.$

By (41), (42) and (43), we have

$\displaystyle\frac{A_{k+1}}{2}+B_{k+1}C_{k}$
$\displaystyle=\frac{B_{k+1}\beta_{k+1}}{2\alpha_{k+1}}+B_{k+1}C_{k}$
$\displaystyle=\frac{B_{k}\beta_{k+1}}{2\alpha_{k+1}(1-\alpha_{k})}+\frac{B_{k}C_{k}}{1-\alpha_{k}}$
$\displaystyle=\frac{B_{k}(\beta_{k+1}+2C_{k}\alpha_{k+1})}{2\alpha_{k+1}(1-\alpha_{k})}$
$\displaystyle=\frac{B_{k}\beta_{k}(1-L^{2}\beta_{k}^{2}-\alpha_{k}^{2})}{2\alpha_{k}(1-\alpha_{k})^{2}(1-L^{2}\beta_{k}^{2})}$
$\displaystyle=\frac{A_{k}(1-L^{2}\beta_{k}^{2}-\alpha_{k}^{2})}{2(1-\alpha_{k})^{2}(1-L^{2}\beta_{k}^{2})}.$

Also by (41), we have

$\displaystyle\frac{B_{k}\beta_{k}}{2\alpha_{k}}(1-\frac{1}{L^{2}\beta_{k}^{2}})$
$\displaystyle=\frac{A_{k}(L^{2}\beta_{k}^{2}-1)}{2L^{2}\beta_{k}^{2}},$
$\displaystyle-\frac{B_{k}\beta_{k}}{\alpha_{k}}(1-\frac{1}{L^{2}\beta_{k}^{2}})+\frac{B_{k}\beta_{k}}{1-\alpha_{k}}$
$\displaystyle=\frac{A_{k}(1-L^{2}\beta_{k}^{2}-\alpha_{k})}{2(1-\alpha_{k})L^{2}\beta_{k}^{2}}.$

In conclusion, we have

$\displaystyle\mathcal{E}(k+1)-\mathcal{E}(k)\leqslant$ $\displaystyle\
-\frac{A_{k}(1-L^{2}\beta_{k}^{2}-\alpha_{k})^{2}}{2(1-\alpha_{k})^{2}(1-L^{2}\beta_{k}^{2})L^{2}\beta_{k}^{2}}\left\|F(z_{k+1})\right\|^{2}-\frac{A_{k}(1-L^{2}\beta_{k}^{2})}{2L^{2}\beta_{k}^{2}}\left\|F(z_{k+\frac{1}{2}})\right\|^{2}$
$\displaystyle\
+\frac{A_{k}(1-L^{2}\beta_{k}^{2}-\alpha_{k})}{2(1-\alpha_{k})L^{2}\beta_{k}^{2}}\left\langle
F(z_{k+\frac{1}{2}}),F(z_{k+1})\right\rangle$ $\displaystyle=$ $\displaystyle\
-\frac{A_{k}}{2L^{2}\beta_{k}^{2}}\left\|\frac{(1-L^{2}\beta_{k}^{2}-\alpha_{k})}{(1-\alpha_{k})\sqrt{1-L^{2}\beta_{k}^{2}}}F(z_{k+1})-\sqrt{1-L^{2}\beta_{k}^{2}}F(z_{k+\frac{1}{2}})\right\|^{2}$
$\displaystyle\leqslant$ $\displaystyle\ 0.$

∎

However, unlike Theorem 2 in [37], we can not directly estimate the upper
bounds of $\left\|F(z_{k})\right\|^{2},$ and $\left\langle
F(z_{k}),z_{k}-z^{*}\right\rangle$. The main reason is that the lower bound of
$E(k)$ is

$\mathcal{E}(k)\geqslant\frac{A_{k}}{4}\left\|F(z_{k})\right\|^{2}+B_{k}\left\langle
F(z_{k}),z_{k}-z^{*}\right\rangle-\frac{B_{k}^{2}}{A_{k}^{2}}\left\|u_{k}-z^{*}\right\|^{2},$

which leads to that both $\left\|F(z_{k})\right\|^{2},$ and $\left\langle
F(z_{k}),z_{k}-z^{*}\right\rangle$ are bounded by both
$\left\|u_{k}-z^{*}\right\|^{2}$ and $\left\|z_{0}-z^{*}\right\|^{2}$. Because
determining all classes of SEG that satisfies (44) and admits $O(1/k^{2})$
convergence rate is complicated, we first focus on the following instance of
SEG, described in Algorithm 4.

Input: Operator $F$, $L\in(0,+\infty)$, ;

Initialization:  $z_{0}$, $u_{0}=z_{0}$;

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

$\tilde{z}_{k+1}=\dfrac{1}{k+r}z_{k}+\dfrac{k+r-1}{k+r}u_{k}$;

$z_{k+\frac{1}{2}}=\tilde{z}_{k+1}-\beta_{k}F(z_{k})$;

$z_{k+1}=\tilde{z}_{k+1}-\beta_{k}F(z_{k+\frac{1}{2}})$;

$u_{k+1}=u_{k}-D\cdot\dfrac{L^{2}\beta_{k}^{3}}{2(k+r-1)(1-L^{2}\beta_{k}^{2})}F(z_{k+1})$;

$\beta_{k+1}=\beta_{k}-(1+D)\cdot\dfrac{L^{2}\beta_{k}^{3}}{[(k+r)^{2}-1](1-L^{2}\beta_{k}^{2})}$;

Algorithm 4 SEG with Varying Step-size

Algorithm 4 can be seen as SEG with
$\alpha_{k}=\dfrac{1}{k+r},C_{k}=D\cdot\dfrac{L^{2}\beta_{k}^{3}}{2(k+r-1)(1-L^{2}\beta_{k}^{2})}$.
The first thing we need to do is propose the sufficient condition for SEG such
that (44) hold.

######  Lemma 12.

Let $\\{z_{\frac{k}{2}}\\}$, $\\{\tilde{z}_{k}\\}$ and $\\{u_{k}\\}$ be the
sequences generated by Algorithm 4. If

$\displaystyle\beta_{0}$ $\displaystyle\in(0,\dfrac{1}{L}),$ (48)
$\displaystyle-1<D$
$\displaystyle<\frac{r(r-1)(1-L^{2}\beta_{0}^{2})}{(2r-1)L^{2}\beta_{0}^{2}}-1$
(49)

hold, $\\{\beta_{k}\\}$ is a non-increasing sequence and
$\beta_{\infty}=\lim\limits_{k\to\infty}\beta_{k}>0$.

###### Proof.

Without loss of generalization, we presume $L=1$ because the general case can
be obtained by replacing $\beta_{k}$ by $L\beta_{k}$. By the assumption, the
difference $\beta_{k+1}-\beta_{k}$ is given as follows:

$\beta_{k+1}-\beta_{k}=-(1+D)\cdot\frac{\beta_{k}^{3}}{[(k+r)^{2}-1](1-\beta_{k}^{2})}.$

Next, we verify that $\beta_{k}>0$ by using mathematical induction. We assume
that $\beta_{i}>0$ is hold for all $i=0,\cdots,k$, then we have
$\beta_{i+1}-\beta_{i}\leqslant 0,\forall i=0,\cdots,k$. Since the function
$g(x)=\dfrac{x^{3}}{1-x^{2}}$ is non-increasing on $(0,1)$, we have

$\frac{\beta_{i}^{3}}{1-\beta_{i}^{2}}\leqslant\frac{\beta_{0}^{3}}{1-\beta_{0}^{2}}.$

Thus

$\displaystyle\beta_{k+1}-\beta_{0}$
$\displaystyle=\sum_{i=0}^{k}\beta_{i+1}-\beta_{i}$
$\displaystyle\geqslant-(1+D)\cdot\sum_{i=0}^{k}\frac{\beta_{0}^{3}}{(i+r-1)(i+r-1)(1-\beta_{0}^{2})}$
$\displaystyle\geqslant-\frac{(1+D)\beta_{0}^{3}}{(1-\beta_{0}^{2})}\sum_{i=0}^{\infty}\frac{1}{(i+r-1)(i+r+1)}$
$\displaystyle=-\frac{(2r-1)(1+D)\beta_{0}^{3}}{r(r-1)(1-\beta_{0}^{2})}.$

In conclusion, we have

$\beta_{k+1}\geqslant\left(1-\frac{(2r-1)(1+D)\beta_{0}^{2}}{r(r-1)(1-\beta_{0}^{2})}\right)\beta_{0}.$

∎

The following lemma is useful to show that $\left\|u_{k}-z^{*}\right\|^{2}$
can be uniformly bounded by $\left\|z_{0}-z^{*}\right\|^{2}$.

######  Lemma 13.

Let $\\{a_{k}\\}$ be a non-negative sequence. If there exists two positive
constants $E_{1},E_{2}$ such that

$\left(1-\frac{E_{1}}{(k+r)^{2}-1}\right)a_{k+1}\leqslant\frac{E_{2}}{(k+r-1)(k+r)}a_{0}+a_{k},\quad
E_{1}<r^{2}-1,$

the sequence $\\{a_{k}\\}$ can be uniformly bounded by $a_{0}$, i. e. there
exists a positive constant $E_{3}$ such that

$a_{k}\leqslant E_{3}a_{0},\quad\forall k\geqslant 1.$

###### Proof.

Deriving $1-\dfrac{E_{1}}{(k+r)^{2}-1}$ on both sides of the inequality in
Lemma 13, we have

$a_{k+1}\leqslant\frac{(k+r+1)E_{2}}{[(k+r-1)^{2}-E_{1}](k+r)}a_{0}+\frac{(k+r)^{2}-1}{(k+r)^{2}-1-E_{1}}a_{k}.$

Recursively using upper bound of $a_{k},a_{k-1},\cdots,a_{1}$, we have

$a_{k+1}\leqslant\sum_{i=0}^{k}\prod_{j=i+1}^{k}\frac{(j+r)^{2}-1}{(j+r)^{2}-1-E_{1}}\frac{(i+r+1)E_{2}}{[(i+r)^{2}-1-E_{1}](i+r)}a_{0},$

where $\prod\limits_{j=k+1}^{k}\dfrac{(j+r)^{2}-1}{(j+r)^{2}-1-E_{1}}=1$.
Since

$\prod_{j=i+1}^{k}\frac{(j+r)^{2}-1}{(j+r)^{2}-1-E_{1}}\leqslant\prod_{j=0}^{\infty}\frac{(j+r)^{2}-1}{(j+r)^{2}-1-E_{1}}<\infty,$

then we have

$a_{k+1}\leqslant E_{4}\frac{(i+r+1)E_{2}}{[(i+r)^{2}-1-E_{1}](i+r)}a_{0},$

where

$E_{4}=\prod_{j=0}^{\infty}\frac{(j+r)^{2}-1}{(j+r)^{2}-1-E_{1}}.$

Also, because

$\sum_{i=0}^{k}\frac{(i+r+1)E_{2}}{[(i+r)^{2}-1-E_{1}](i+r)}\leqslant\sum_{i=0}^{\infty}\frac{(i+r+1)E_{2}}{[(i+r)^{2}-1-E_{1}](i+r)}<\infty,$

we have

$a_{k+1}\leqslant E_{3}a_{0}$

where

$E_{3}=E_{4}E_{2}\sum_{i=0}^{\infty}\frac{i+r+1}{[(i+r)^{2}-1-E_{1}](i+r)}.$

∎

With Lemma 12 and Lemma 13, we can show that Algorithm 4 exhibits $O(1/k^{2})$
convergence rates.

######  Theorem 14.

Let $\\{z_{\frac{k}{2}}\\}$, $\\{\tilde{z}_{k}\\}$ and $\\{u_{k}\\}$ be the
sequences generated by Algorithm 4. If (48) and (49) hold, we have

$\displaystyle\left\|F(z_{k})\right\|^{2}$ $\displaystyle\leqslant
O\left(\frac{\mathrm{dist}(z_{0},F)^{2}}{(k+r-1)(k+r)}\right),$
$\displaystyle\left\langle F(z_{k}),z_{k}-z^{*}\right\rangle$
$\displaystyle\leqslant
O\left(\frac{\left\|z_{0}-z^{*}\right\|^{2}}{k+r-1}\right).$

###### Proof.

Let $B_{0}=1$. By (41) and (42), we have
$B_{k}=k+r-1,A_{k}=\beta_{k}(k+r-1)(k+r)$. By Theorem 11, we have

$\mathcal{E}(k)\leqslant\mathcal{E}(0)=\frac{(r-1)r\beta_{0}}{2}\left\|F(z_{0})\right\|^{2}\leqslant\frac{(r-1)rL^{2}\beta_{0}}{2}\left\|z_{0}-z^{*}\right\|^{2}.$

The lower bound of $\mathcal{E}(k)$ can be estimated as followed.

$\displaystyle\mathcal{E}(k)=$ $\displaystyle\
\frac{A_{k}}{2}\left\|F(z_{k})\right\|^{2}+B_{k}\left\langle
F(z_{k}),z_{k}-z^{*}\right\rangle+B_{k}\left\langle
F(z_{k}),z^{*}-u_{k}\right\rangle$ $\displaystyle\geqslant$ $\displaystyle\
\frac{A_{k}}{2}\left\|F(z_{k})\right\|^{2}+B_{k}\left\langle
F(z_{k}),z_{k}-z^{*}\right\rangle$
$\displaystyle+\frac{1}{2}\left[\left\|\sqrt{\frac{A_{k}}{2}}F(z_{k})-\sqrt{\frac{2B_{k}^{2}}{A_{k}}}(u_{k}-z^{*})\right\|^{2}-\frac{A_{k}}{2}\left\|F(z_{k})\right\|^{2}-\frac{2B_{k}^{2}}{A_{k}}\left\|u_{k}-z^{*}\right\|^{2}\right]$
$\displaystyle\geqslant$ $\displaystyle\
\frac{A_{k}}{4}\left\|F(z_{k})\right\|^{2}+B_{k}\left\langle
F(z_{k}),z_{k}-z^{*}\right\rangle-\frac{B_{k}^{2}}{A_{k}}\left\|u_{k}-z^{*}\right\|^{2}.$

Thus, we have

$\displaystyle\left\|F(z_{k})\right\|^{2}$
$\displaystyle\leqslant\frac{2(r-1)rL^{2}\beta_{0}}{\beta_{k}(k+r-1)(k+r)}\left\|z_{0}-z^{*}\right\|^{2}+\frac{4}{\beta_{k}^{2}(k+r)^{2}}\left\|u_{k}-z^{*}\right\|^{2},$
$\displaystyle\left\langle F(z_{k}),z_{k}-z^{*}\right\rangle$
$\displaystyle\leqslant\frac{(r-1)rL^{2}\beta_{0}}{2(k+r-1)}\left\|z_{0}-z^{*}\right\|^{2}+\frac{1}{\beta_{k}(k+r)}\left\|u_{0}-z^{*}\right\|^{2}.$

Since $\beta_{k}\geqslant\beta_{\infty}>0$, the remaining problem is showing
$\left\|u_{k}-z\right\|$ can be uniformly bounded by
$\left\|u_{0}-z\right\|=\left\|z_{0}-z^{*}\right\|$. By triangle inequality,
we have

$\left\|u_{k+1}-z^{*}\right\|\leqslant|C_{k}|\left\|F(z_{k+1})\right\|+\left\|u_{k}-z^{*}\right\|.$

By the definition of $C_{k}$ and (49), we have

$|C_{k}|\leqslant\frac{r(r-1)(1-L^{2}\beta_{0}^{2})}{(2r-1)L^{2}\beta_{0}^{2}}\cdot\frac{L^{2}\beta_{k}^{3}}{2(k+r-1)(1-L^{2}\beta_{k}^{3})}\leqslant\frac{r(r-1)}{(4r-2)(k+r-1)}\beta_{k}.$

Also by $\sqrt{a+b}\leqslant\sqrt{a}+\sqrt{b},\forall a>0,b>0$, we have

$\left\|u_{k+1}-z^{*}\right\|\leqslant\frac{r(r-1)}{(2r-1)[(k+r)^{2}-1]}\left\|u_{k+1}-z^{*}\right\|+\frac{r^{\frac{3}{2}}(r-1)^{\frac{3}{2}}L\beta_{0}}{\sqrt{2}(2r-1)(k+r-1)(k+r)}\left\|u_{0}-z^{*}\right\|+\left\|u_{k}-z^{*}\right\|.$

Let
$E_{1}=\dfrac{r(r-1)}{2r-1},E_{2}=\dfrac{r^{\frac{3}{2}}(r-1)^{\frac{3}{2}}L\beta_{0}}{\sqrt{2}(2r-1)},a_{k}=\left\|u_{k}-z^{*}\right\|$.
By using Lemma 13, we have $\left\|u_{k}-z^{*}\right\|\leqslant
E_{3}\left\|z_{0}-z^{*}\right\|$.

In conclusion, we have

$\displaystyle\left\|F(z_{k})\right\|^{2}$ $\displaystyle\leqslant
O\left(\frac{\left\|z_{0}-z^{*}\right\|^{2}}{(k+r-1)(k+r)}\right),$
$\displaystyle\left\langle F(z_{k}),z_{k}-z^{*}\right\rangle$
$\displaystyle\leqslant
O\left(\frac{\left\|z_{0}-z^{*}\right\|^{2}}{k+r-1}\right).$

By taking infimum respect to all $z^{*}\in\mathrm{zero}(F)$ in the first above
inequality, we obtain the desired results.

∎

Since the step-size of Nesterov’s accelerated gradient method can be constant,
we also discuss the SEG with constant step-size. It is easy to show that if
$\alpha_{k}=\dfrac{1}{k+r},C_{k}=-\dfrac{L^{2}\beta^{3}}{(k+r-1)(1-L^{2}\beta_{k}^{2})}$,
$\beta_{k}\equiv\beta$. In conclusion, we obtain the SEG with constant step-
size, described in Algorithm 5.

Input: Operator $F$, $L\in(0,+\infty)$, $\rho\in(-\dfrac{1}{2\rho},+\infty)$;

Initialization:  $z_{0}$, $u_{0}=z_{0}$;

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

$\tilde{z}_{k+1}=\dfrac{1}{k+r}z_{k}+\dfrac{k+r-1}{k+r}u_{k}$;

$z_{k+\frac{1}{2}}=\tilde{z}_{k+1}-\beta F(z_{k})$;

$z_{k+1}=\tilde{z}_{k+1}-\beta F(z_{k+\frac{1}{2}})$;

$u_{k+1}=u_{k}+\dfrac{L^{2}\beta^{3}}{2(k+r-1)(1-L^{2}\beta^{2})}F(z_{k+1})$;

Algorithm 5 SEG with Constant Step-size

The convergence results of Algorithm 5 is given in Corollary 15.

######  Corollary 15.

Let $\\{z_{k}\\}$, $\\{z_{k+\frac{1}{2}}\\}$, $\\{\tilde{z}_{k}\\}$ and
$\\{u_{k}\\}$ be the sequences generated by Algorithm 5 with
$\beta\in(0,\dfrac{1}{L})$. Then we have

$\displaystyle\left\|F(z_{k})\right\|^{2}$ $\displaystyle\leqslant
O\left(\frac{\mathrm{dist}(z_{0},\mathrm{zero}(F))^{2}}{(k+r-1)(k+r)}\right),$
$\displaystyle\left\langle F(z_{k}),z_{k}-z^{*}\right\rangle$
$\displaystyle\leqslant
O\left(\frac{\left\|z_{0}-z^{*}\right\|^{2}}{k+r-1}\right),\quad\forall
z^{*}\in\mathrm{zero}(F).$

##  Appendix B Discussion of Stochastic SEG+

###  B.1 Symplectic Stochastic Extragradient+ Method

In this section, we consider the following stochastic inclusion problem:

$0=F(z)=\mathop{\mathbb{E}}_{\zeta}[F(z;\zeta)].$

Such stochastic inclusion problem has been wildly used to train GANs and train
Adversarial training deep neural network classifiers. To solve the above
problem, we proposed the following stochastic SEG+ framework.

$\displaystyle\tilde{z}_{k+1}$
$\displaystyle=(1-\alpha_{k})z_{k}+\alpha_{k}u_{k},$ (50a) $\displaystyle
z_{k+\frac{1}{2}}$
$\displaystyle=\tilde{z}_{k+1}-(1-\alpha_{k})\beta_{k}[F(z_{k})+\zeta_{k}],$
(50b) $\displaystyle z_{k+1}$
$\displaystyle=\tilde{z}_{k+1}-\beta_{k}[F(z_{k+\frac{1}{2}})+\zeta_{k+\frac{1}{2}}],$
(50c) $\displaystyle u_{k+1}$
$\displaystyle=u_{k}-C_{k}[F(z_{k+1})+\zeta_{k+1}].$ (50d)

######  Theorem 16.

Let $\\{z_{\frac{k}{2}}\\}$, $\\{\tilde{z}_{k+1}\\}$ and $\\{u_{k}\\}$ be the
sequences generated by (50a)-(50d). If $F$ is $L-$Lipschitz continuous and
monotone, the parameters satisfy the following requirements:

$\displaystyle\beta_{k}$ $\displaystyle\in(0,\frac{1}{L}),$
$\displaystyle\frac{B_{k}\beta_{k}}{\alpha_{k}}$
$\displaystyle=\left(\frac{B_{k}\beta_{k}}{\alpha_{k}}+\frac{B_{k}\beta_{k}}{1-\alpha_{k}}\right)L^{2}\beta_{k}^{2}(1-\alpha_{k}),$
$\displaystyle\frac{B_{k}\beta_{k}}{2\alpha_{k}}+\frac{B_{k}\beta_{k}}{2-2\alpha_{k}}$
$\displaystyle\geqslant
B_{k+1}C_{k}+\frac{C_{k}(1-\alpha_{k})B_{k+1}-C_{k}B_{k}}{2-2\alpha_{k}}+A_{k+1},$
$\displaystyle\frac{B_{k}\beta_{k}}{2\alpha_{k}}$ $\displaystyle\geqslant
A_{k},\quad\frac{(1-\alpha_{k})B_{k+1}-B_{k}}{2C_{k}(1-\alpha_{k})}\text{ is
non-increasing},$

then we have

$\displaystyle\mathbb{E}\left[\mathcal{E}(k)\right]\leqslant$ $\displaystyle\
\mathbb{E}\left[\mathcal{E}(0)\right]+\sum_{i=0}^{k-1}\left(\frac{B_{i}\beta_{i}}{1-\alpha_{i}}+\frac{B_{i}\beta_{i}}{\alpha_{i}}\right)L\beta_{i}\sigma_{i+\frac{1}{2}}^{2}+\frac{C_{i}B_{i}-C_{k}(1-\alpha_{i})B_{i+1}}{2-2\alpha_{i}}\sigma_{i+1}^{2}$
$\displaystyle\
+\sum_{i=0}^{k-1}\left(\frac{B_{i}\beta_{i}}{2\alpha_{i}}+\frac{B_{i}\beta_{i}}{2-2\alpha_{i}}\right)[L^{2}\beta_{i}^{2}\sigma_{i+\frac{1}{2}}^{2}+L^{2}\beta_{i}^{2}(1-\alpha_{i})^{2}\sigma_{i}^{2}+2L^{3}\beta_{i}^{3}(1-\alpha_{i})^{2}\sigma_{i}^{2}].$

Input: Operator $F$, $L\in(0,+\infty),\rho\in(-\dfrac{1}{2\rho},+\infty)$;

Initialization: $z_{0},u_{0}=z_{0}$;

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

$\tilde{z}_{k+1}=\dfrac{k}{k+r}z_{k}+\dfrac{r}{k+r}u_{k}$;

$z_{k+\frac{1}{2}}=\tilde{z}_{k+1}-\dfrac{k}{k+r}\dfrac{1}{L}[F(z_{k})+\zeta_{k}]$;

$z_{k+1}=\tilde{z}_{k+1}-\dfrac{1}{L}[F(z_{k+\frac{1}{2}})+\zeta_{k+\frac{1}{2}}]$;

$u_{k+1}=u_{k}-\dfrac{D}{r}[F(z_{k+1})+\zeta_{k+1}]$.

Algorithm 6 Symplectic Stochastic Extragradient+ Method, SSEG+

######  Corollary 17.

Let $\\{z_{\frac{k}{2}}\\}$, $\\{\tilde{z}_{k+1}\\}$ and $\\{u_{k}\\}$ be the
sequences generated by Algorithm 6. If $F$ is $L-$Lipschitz continuous and
monotone, $r\geqslant 2$, $0<D\leqslant 1$, and there exists two positive
constant $E_{1}$ and $E_{2}$ such that $\sigma_{k}^{2}\leqslant
E_{1}\dfrac{\varepsilon}{rk}$, $\sigma_{k+\frac{1}{2}}^{2}\leqslant
E_{2}\dfrac{\varepsilon}{r(k+r)}$, there exists a positive constant $E_{3}$
such that

$\displaystyle\mathbb{E}\left[\left\|F(z_{k})\right\|^{2}\right]\leqslant\frac{L(r^{3}-r^{2})}{Dk^{2}}\mathrm{dist}(z_{0},\mathrm{zero}(F))^{2}+E_{3}\varepsilon.$

###  B.2 Proof of Theorem 16

Before proving Theorem 16, we need the following lemma.

######  Lemma 18.

Let $\\{z_{k}\\},\\{u_{k}\\}$ be the sequences generated by (50a)-(50d). If
the random sequence $\\{\zeta_{\frac{k}{2}}\\}$ satisfies
$\mathbb{E}\left[\zeta_{\frac{k}{2}}\right]=0$,
$\mathbb{E}\left[\zeta_{\frac{k}{2}}^{2}\right]=\sigma_{\frac{k}{2}}^{2}$ for
all $k\geqslant 0$, then we have

$\displaystyle\left|\mathbb{E}\left[F(z_{k+1}),\zeta_{k+\frac{1}{2}}\right]\right|$
$\displaystyle\leqslant L\beta_{k}\sigma_{k+\frac{1}{2}}^{2},$
$\displaystyle\left|\mathbb{E}\left[F(z_{k+\frac{1}{2}}),\zeta_{k}\right]\right|$
$\displaystyle\leqslant L(1-\alpha_{k})\beta_{k}\sigma_{k}^{2}.$

The proof for Lemma 18 is analogous to the proof for Lemma D.2 in [16]. We
refer the proof to [16].

The proof of Theorem 16 Consider the following Lyapunov function

$\mathcal{E}(k)=A_{k}\left\|F(z_{k})\right\|^{2}+B_{k}\left\langle
F(z_{k}),z_{k}-u_{k}\right\rangle+\frac{B_{k}-(1-\alpha_{k})B_{k+1}}{2(1-\alpha_{k})C_{k}}\left\|u_{k}-z^{*}\right\|^{2},$
(51)

where $z^{*}$ is the zero-point of $F$, i. e. $F(z^{*})=0$. We show that
$\\{\mathbb{E}\left[\mathcal{E}(k)\right]\\}$ is non-increasing.

Step 1: Divide the difference
$\mathbb{E}\left[\mathcal{E}(k+1)\right]-\mathbb{E}\left[\mathcal{E}(k)\right]$
into three parts.

$\displaystyle\mathbb{E}\left[\mathcal{E}(k+1)\right]-\mathbb{E}\left[\mathcal{E}(k)\right]$
$\displaystyle=$
$\displaystyle\underbrace{A_{k+1}\mathbb{E}\left[\left\|F(z_{k+1})\right\|^{2}\right]-A_{k}\mathbb{E}\left[\left\|F(z_{k})\right\|^{2}\right]}_{\text{I}}$
$\displaystyle+\underbrace{B_{k+1}\mathbb{E}\left[\left\langle
F(z_{k+1}),z_{k+1}-u_{k+1}\right\rangle\right]-B_{k}\mathbb{E}\left[\left\langle
F(z_{k}),z_{k}-u_{k}\right\rangle\right]}_{\text{II}}$
$\displaystyle+\underbrace{\frac{B_{k+1}-(1-\alpha_{k+1})B_{k+2}}{2(1-\alpha_{k+1})C_{k+1}}\mathbb{E}\left[\left\|u_{k+1}-z^{*}\right\|^{2}\right]-\frac{B_{k}-(1-\alpha_{k})B_{k+1}}{2(1-\alpha_{k})C_{k}}\mathbb{E}\left[\left\|u_{k}-z^{*}\right\|^{2}\right]}_{\text{III}}.$

Step 2: Reckon the upper bound of all three parts. First we consider II.

$\displaystyle\text{II}=$
$\displaystyle(B_{k+1}-B_{k})\mathbb{E}\left[\left\langle
F(z_{k+1}),z_{k+1}-u_{k+1}\right\rangle\right]+B_{k}\mathbb{E}\left[\left\langle
F(z_{k+1}),z_{k+1}-z_{k}-u_{k+1}+u_{k}\right\rangle\right]$
$\displaystyle+B_{k}\mathbb{E}\left[\left\langle
F(z_{k+1})-F(z_{k}),z_{k}-u_{k}\right\rangle\right].$

Since $\mathbb{E}\left[\zeta_{k+1}|z_{k+1}\right]=0$, we have

$\mathbb{E}\left[F(z_{k+1}),\zeta_{k+1}\right]=0.$

Combining the above equation, (50c) and (50d), we have

$\begin{split}&\ B_{k}\mathbb{E}\left[\left\langle
F(z_{k+1}),z_{k+1}-z_{k}-u_{k+1}+u_{k}\right\rangle\right]\\\ =&\
B_{k}\mathbb{E}\left[\left\langle
F(z_{k+1}),\frac{\alpha_{k}}{1-\alpha_{k}}(u_{k}-z_{k+1})-\frac{\beta_{k}}{1-\alpha_{k}}[F(z_{k+\frac{1}{2}})+\zeta_{k+\frac{1}{2}}]\right\rangle\right]+B_{k}C_{k}\mathbb{E}\left[\left\|F(z_{k+1})\right\|^{2}\right]\\\
\leqslant&B_{k}\mathbb{E}\left[\left\langle
F(z_{k+1}),\frac{\alpha_{k}}{1-\alpha_{k}}(u_{k}-z_{k+1})-\frac{\beta_{k}}{1-\alpha_{k}}F(z_{k+\frac{1}{2}})\right\rangle\right]+\frac{B_{k}L\beta_{k}^{2}}{1-\alpha_{k}}\sigma^{2}_{k+\frac{1}{2}}+B_{k}C_{k}\mathbb{E}\left[\left\|F(z_{k+1})\right\|^{2}\right].\\\
\end{split}$ (52)

In addition, because of (50b), we have

$\begin{split}&\ B_{k}\mathbb{E}\left[\left\langle
F(z_{k+1})-F(z_{k}),z_{k}-u_{k}\right\rangle\right]\\\ =&\
B_{k}\mathbb{E}\left[\left\langle
F(z_{k+1})-F(z_{k}),-\frac{1}{\alpha_{k}}(z_{k+1}-z_{k})-\frac{\beta_{k}}{\alpha_{k}}[F(z_{k+\frac{1}{2}})+\zeta_{k+\frac{1}{2}}]\right\rangle\right]\\\
\leqslant&\ B_{k}\mathbb{E}\left[\left\langle
F(z_{k+1})-F(z_{k}),-\frac{1}{\alpha_{k}}(z_{k+1}-z_{k})-\frac{\beta_{k}}{\alpha_{k}}F(z_{k+\frac{1}{2}})\right\rangle\right]+\frac{B_{k}L\beta_{k}^{2}\sigma_{k+\frac{1}{2}}^{2}}{\alpha_{k}}.\end{split}$
(53)

Also,

$\begin{split}&\ (B_{k+1}-B_{k})\mathbb{E}\left[\left\langle
F(z_{k+1}),z_{k+1}-u_{k+1}\right\rangle\right]\\\ =&\
(B_{k+1}-B_{k})C_{k}\mathbb{E}\left[\left\|F(z_{k+1})\right\|^{2}\right]+(B_{k+1}-B_{k})\mathbb{E}\left[\left\langle
F(z_{k+1}),z_{k+1}-u_{k}+C_{k}\zeta_{k+1}\right\rangle\right]\\\ =&\
(B_{k+1}-B_{k})C_{k}\mathbb{E}\left[\left\|F(z_{k+1})\right\|^{2}\right]+(B_{k+1}-B_{k})\mathbb{E}\left[\left\langle
F(z_{k+1}),z_{k+1}-u_{k}\right\rangle\right].\end{split}$ (54)

By summing (52), (53) and (54), we have

$\displaystyle\text{II}\leqslant$ $\displaystyle\
B_{k}\mathbb{E}\left[\left\langle
F(z_{k+1}),\frac{\alpha_{k}}{1-\alpha_{k}}(u_{k}-z_{k+1})-\frac{\beta_{k}}{1-\alpha_{k}}F(z_{k+\frac{1}{2}})\right\rangle\right]$
$\displaystyle\ +B_{k}\mathbb{E}\left[\left\langle
F(z_{k+1})-F(z_{k}),-\frac{1}{\alpha_{k}}(z_{k+1}-z_{k})-\frac{\beta_{k}}{\alpha_{k}}F(z_{k+\frac{1}{2}})\right\rangle\right]+\left(\frac{B_{k}\beta_{k}}{1-\alpha_{k}}+\frac{B_{k}\beta_{k}}{\alpha_{k}}\right)L\beta_{k}\sigma_{k+\frac{1}{2}}^{2}$
$\displaystyle\
+B_{k+1}C_{k}\mathbb{E}\left[\left\|F(z_{k+1})\right\|^{2}\right]+(B_{k+1}-B_{k})\mathbb{E}\left[\left\langle
F(z_{k+1}),z_{k+1}-u_{k}\right\rangle\right].$

Since $F$ is $L-$Lipschitz continuous, we have

$\left\|F(z_{k+1})-F(z_{k+\frac{1}{2}})\right\|^{2}\leqslant
L^{2}\left\|z_{k+1}-z_{k+\frac{1}{2}}\right\|^{2}.$

Due to (50b) and (50c), we have

$\left\|z_{k+1}-z_{k+\frac{1}{2}}\right\|^{2}=\beta_{k}^{2}\left\|F(z_{k+\frac{1}{2}})+\zeta_{k+\frac{1}{2}}-(1-\alpha_{k})[F(z_{k})+\zeta_{k}]\right\|^{2}.$

By using Lemma 18, we have

$\displaystyle\mathbb{E}\left[\left\|F(z_{k+1})-F(z_{k+\frac{1}{2}})\right\|^{2}\right]\leqslant$
$\displaystyle\
L^{2}\beta_{k}^{2}\mathbb{E}\left[\left\|F(z_{k+\frac{1}{2}})\right\|^{2}\right]+2L^{2}\beta_{k}^{2}(1-\alpha_{k})\mathbb{E}\left[\left\langle
F(z_{k+\frac{1}{2}}),F(z_{k})\right\rangle\right]+L^{2}\beta_{k}^{2}\sigma_{k+\frac{1}{2}}^{2}$
$\displaystyle\
+L^{2}\beta_{k}^{2}(1-\alpha_{k})^{2}\sigma_{k}^{2}+L^{2}\beta_{k}^{2}(1-\alpha_{k})^{2}\mathbb{E}\left[\left\|F(z_{k})\right\|^{2}\right]+2L^{3}\beta_{k}^{3}(1-\alpha_{k})^{2}\sigma_{k}^{2}.$

Because of the following equality

$-\left\langle
F(z_{k+1}),F(z_{k+\frac{1}{2}})\right\rangle=\frac{1}{2}\left[\left\|F(z_{k+1})-F(z_{k+\frac{1}{2}})\right\|^{2}-\left\|F(z_{k+1})\right\|^{2}-\left\|F(z_{k+\frac{1}{2}})\right\|^{2}\right]$

and the assumption

$\frac{B_{k}\beta_{k}}{\alpha_{k}}=\left(\frac{B_{k}\beta_{k}}{\alpha_{k}}+\frac{B_{k}\beta_{k}}{1-\alpha_{k}}\right)L^{2}\beta_{k}^{2}(1-\alpha_{k}),$

we obtain the following estimation of II:

$\displaystyle\text{II}\leqslant$ $\displaystyle\
-\left(\frac{B_{k}\beta_{k}}{2\alpha_{k}}+\frac{B_{k}\beta_{k}}{2-2\alpha_{k}}-B_{k+1}C_{k}\right)\mathbb{E}\left[\left\|F(z_{k+1})\right\|^{2}\right]-\left(\frac{B_{k}\beta_{k}}{2\alpha_{k}}+\frac{B_{k}\beta_{k}}{2-2\alpha_{k}}\right)(1-L^{2}\beta_{k}^{2})\mathbb{E}\left[\left\|F(z_{k+\frac{1}{2}})\right\|^{2}\right]$
$\displaystyle\
-\frac{B_{k}\beta_{k}}{2\alpha_{k}}\mathbb{E}\left[\left\|F(z_{k})\right\|^{2}\right]-\frac{B_{k}}{1-\alpha_{k}}\mathbb{E}\left[\left\langle
F(z_{k+1})-F(z_{k}),z_{k+1}-z_{k}\right\rangle\right]$ $\displaystyle\
+\underbrace{\left(B_{k+1}-\frac{B_{k}}{1-\alpha_{k}}\right)\mathbb{E}\left[\left\langle
F(z_{k+1}),z_{k+1}-u_{k}\right\rangle\right]}_{\text{II}_{1}}+\left(\frac{B_{k}\beta_{k}}{1-\alpha_{k}}+\frac{B_{k}\beta_{k}}{\alpha_{k}}\right)L\beta_{k}\sigma_{k+\frac{1}{2}}^{2}$
$\displaystyle\
+\left(\frac{B_{k}\beta_{k}}{2\alpha_{k}}+\frac{B_{k}\beta_{k}}{2-2\alpha_{k}}\right)[L^{2}\beta_{k}^{2}\sigma_{k+\frac{1}{2}}^{2}+L^{2}\beta_{k}^{2}(1-\alpha_{k})^{2}\sigma_{k}^{2}+2L^{3}\beta_{k}^{3}(1-\alpha_{k})^{2}\sigma_{k}^{2}].$

Now estimate III. Utilizing (18), we have

$\displaystyle\text{III}\leqslant$ $\displaystyle\
\frac{B_{k}-(1-\alpha_{k})B_{k+1}}{2(1-\alpha_{k})C_{k}}\mathbb{E}\left[\left\|u_{k+1}-z^{*}\right\|^{2}-\left\|u_{k}-z^{*}\right\|^{2}\right]$
$\displaystyle=$ $\displaystyle\
\underbrace{\frac{B_{k}-(1-\alpha_{k})B_{k+1}}{1-\alpha_{k}}\mathbb{E}\left[\left\langle
F(z_{k+1}),u_{k}-z^{*}\right\rangle\right]}_{\text{III}_{1}}+\frac{C_{k}B_{k}-C_{k}(1-\alpha_{k})B_{k+1}}{2-2\alpha_{k}}\left\\{\mathbb{E}\left[\left\|F(z_{k+1})\right\|^{2}\right]+\sigma_{k+1}^{2}\right\\}.$

Step 3: Deduce the upper bound of $\mathcal{E}(k+1)-\mathcal{E}(k)$. Noticing
that
$\text{II}_{1}+\text{III}_{1}=\dfrac{(1-\alpha_{k})B_{k+1}-B_{k}}{1-\alpha_{k}}\left\langle
F(z_{k+1}),z_{k+1}-z^{*}\right\rangle$, we can simplify the upper bound of
$\mathbb{E}\left[\mathcal{E}(k+1)\right]-\mathbb{E}\left[\mathcal{E}(k)\right]$
as follows:

$\displaystyle\
\mathbb{E}\left[\mathcal{E}(k+1)\right]-\mathbb{E}\left[\mathcal{E}(k)\right]$
$\displaystyle\leqslant$ $\displaystyle\
-\left(\frac{B_{k}\beta_{k}}{2\alpha_{k}}+\frac{B_{k}\beta_{k}}{2-2\alpha_{k}}-B_{k+1}C_{k}-\frac{C_{k}B_{k}-C_{k}(1-\alpha_{k})B_{k+1}}{2-2\alpha_{k}}-A_{k+1}\right)\mathbb{E}\left[\left\|F(z_{k+1})\right\|^{2}\right]$
$\displaystyle\
-\left(\frac{B_{k}\beta_{k}}{2\alpha_{k}}+\frac{B_{k}\beta_{k}}{2-2\alpha_{k}}\right)(1-L^{2}\beta_{k}^{2})\mathbb{E}\left[\left\|F(z_{k+\frac{1}{2}})\right\|^{2}\right]-\left(\frac{B_{k}\beta_{k}}{2\alpha_{k}}-A_{k}\right)\mathbb{E}\left[\left\|F(z_{k})\right\|^{2}\right]$
$\displaystyle\ -\frac{B_{k}}{1-\alpha_{k}}\mathbb{E}\left[\left\langle
F(z_{k+1})-F(z_{k}),z_{k+1}-z_{k}\right\rangle\right]+\left(B_{k+1}-\frac{B_{k}}{1-\alpha_{k}}\right)\mathbb{E}\left[\left\langle
F(z_{k+1}),z_{k+1}-z^{*}\right\rangle\right]$ $\displaystyle\
+\left(\frac{B_{k}\beta_{k}}{1-\alpha_{k}}+\frac{B_{k}\beta_{k}}{\alpha_{k}}\right)L\beta_{k}\sigma_{k+\frac{1}{2}}^{2}+\frac{C_{k}B_{k}-C_{k}(1-\alpha_{k})B_{k+1}}{2-2\alpha_{k}}\sigma_{k+1}^{2}$
$\displaystyle\
+\left(\frac{B_{k}\beta_{k}}{2\alpha_{k}}+\frac{B_{k}\beta_{k}}{2-2\alpha_{k}}\right)[L^{2}\beta_{k}^{2}\sigma_{k+\frac{1}{2}}^{2}+L^{2}\beta_{k}^{2}(1-\alpha_{k})^{2}\sigma_{k}^{2}+2L^{3}\beta_{k}^{3}(1-\alpha_{k})^{2}\sigma_{k}^{2}].$

$\Box$

## References

  * [1] Heinz H. Bauschke and Patrick L. Combettes, _Convex analysis and monotone operator theory in hilbert spaces (second edition)_ , Springer Cham, Cham, 03 2017\.
  * [2] Heinz H Bauschke, Walaa M Moursi, and Xianfu Wang, _Generalized monotone operators and their averaged resolvents_ , Mathematical Programming 189 (2021), 55–74.
  * [3] Aharon Ben-Tal, Laurent El Ghaoui, and Arkadi Nemirovski, _Robust optimization_ , vol. 28, Princeton university press, Princeton, 2009.
  * [4] Yang Cai, Argyris Oikonomou, and Weiqiang Zheng, _Accelerated algorithms for constrained nonconvex-nonconcave min-max optimization and comonotone inclusion_ , 2022.
  * [5] Jelena Diakonikolas, Constantinos Daskalakis, and Michael I. Jordan, _Efficient methods for structured nonconvex-nonconcave min-max optimization_ , International Conference on Artificial Intelligence and Statistics, PMLR, 2021, pp. 2746–2754.
  * [6] Yifeng Fan, Yongqiang Li, and Bo Chen, _Weaker mvi condition: Extragradient methods with multi-step exploration_ , The Twelfth International Conference on Learning Representations, 2023.
  * [7] Gauthier Gidel, Hugo Berard, Gaëtan Vignoud, Pascal Vincent, and Simon Lacoste-Julien, _A variational inequality perspective on generative adversarial networks_ , arXiv preprint arXiv:1802.10551 (2018).
  * [8] Ian J. Goodfellow, Jean Pouget-Abadie, Mehdi Mirza, Bing Xu, David Warde-Farley, Sherjil Ozair, Aaron Courville, and Yoshua Bengio, _Generative adversarial nets_ , Advances in neural information processing systems 27 (2014).
  * [9] Eduard Gorbunov, Hugo Berard, Gauthier Gidel, and Nicolas Loizou, _Stochastic extragradient: General analysis and improved rates_ , International Conference on Artificial Intelligence and Statistics, PMLR, 2022, pp. 7865–7901.
  * [10] Benjamin Halpern, _Fixed points of nonexpanding maps_ , Bulletin of the American Mathematical Society 73 (1967), 957–961.
  * [11] Alfredo N. Iusem, Alekandro Jofré, Roberto I. Oliveira, and Philip Thompson, _Extragradient method with variance reduction for stochastic variational inequalities_ , SIAM Journal on Optimization 27 (2017), no. 2, 686–724.
  * [12] Alexander Shapiro J. Frédéric Bonnans, Springer New York, New York, 05 2000\.
  * [13] Aswin Kannan and Uday V. Shanbhag, _Solving variational inequalities with stochastic mirror-prox algorithm_ , Stochastic Systems 1 (2011), no. 1, 17–58.
  * [14] Aswin Kannan and Uday V Shanbhag, _Optimal stochastic extragradient schemes for pseudomonotone stochastic variational inequality problems and their variants_ , Computational Optimization and Applications 74 (2019), no. 3, 779–820.
  * [15] Galina M Korpelevich, _The extragradient method for finding saddle points and other problems_ , Matecon 12 (1976), 747–756.
  * [16] Sucheol Lee and Donghwan Kim, _Fast extra gradient methods for smooth structured nonconvex-nonconcave minimax problems_ , Advances in Neural Information Processing Systems (A. Beygelzimer, Y. Dauphin, P. Liang, and J. Wortman Vaughan, eds.), 2021.
  * [17] Aleksander Madry, Aleksandar Makelov, Ludwig Schmidt, Dimitris Tsipras, and Adrian Vladu, _Towards deep learning models resistant to adversarial attacks_ , International Conference on Learning Representations, 2018.
  * [18] George J. Minty, _Monotone (nonlinear) operators in Hilbert space_ , Duke Mathematical Journal 29 (1962), no. 3, 341 – 346.
  * [19] Konstantin Mishchenko, Dmitry Kovalev, Egor Shulgin, Peter Richtárik, and Yura Malitsky, _Revisiting stochastic extragradient_ , International Conference on Artificial Intelligence and Statistics, PMLR, 2020, pp. 4573–4582.
  * [20] Aryan Mokhtari, Asuman Ozdaglar, and Sarath Pattathil, _A unified analysis of extra-gradient and optimistic gradient methods for saddle point problems: Proximal point approach_ , International Conference on Artificial Intelligence and Statistics, PMLR, 2020, pp. 1497–1507.
  * [21] Roger B. Myerson, _Game theory: Analysis of conflict_ , Harvard University Press, Cambridge, 09 1997.
  * [22] N. Nadezhkina and W. Takahashi, _Weak convergence theorem by an extragradient method for nonexpansive mappings and monotone mappings_ , Journal of Optimization Theory and Applications 128 (2006), 191–201.
  * [23] Arkadi Nemirovski, _Prox-method with rate of convergence $o(1/t)$ for variational inequalities with lipschitz continuous monotone operators and smooth convex-concave saddle point problems_, SIAM Journal on Optimization 15 (2004), no. 1, 229–251.
  * [24] Yurii Nesterov, _A method of solving a convex programming problem with convergence rate $o(1/k^{2})$_, Doklady Akademii Nauk SSSR 269 (1983), no. 3, 543.
  * [25] Thomas Pethick, Puya Latafat, Panos Patrinos, Olivier Fercoq, and Volkan Cevher, _Escaping limit cycles: Global convergence for constrained nonconvex-nonconcave minimax problems_ , International Conference on Learning Representations, 2022.
  * [26] Leonid D. Povov, _A modification of the arrow-hurwitz method of search for saddle points_ , Mat. Zametki 28 (1980), no. 5, 777–784.
  * [27] Huiqiang Qi and Hong-Kun Xu, _Convergence of halpern’s iteration method with applications in optimization_ , Numerical Functional Analysis and Optimization 42 (2021), no. 15, 1839–1854.
  * [28] Hugo Raguet, Jalal Fadili, and Gabriel Peyré, _A generalized forward-backward splitting_ , SIAM Journal on Imaging Sciences 6 (2013), no. 3, 1199–1226.
  * [29] J. E. Taylor and Martin P. Bendsøe, _An interpretation for min-max structural design problems including a method for relaxing constraints_ , International Journal of Solids and Structures 20 (1984), no. 4, 301–314.
  * [30] Wenyi Tian and Xiaoming Yuan, _An alternating direction method of multipliers with a worst-case $o(1/n^{2})$ convergence rate_, Mathematics of Computation 88 (2019), no. 318, 1685–1713.
  * [31] Quoc Tran-Dinh, _Sublinear convergence rates of extragradient-type methods: A survey on classical and recent developments_ , 2023.
  * [32] Paul Tseng, _On linear convergence of iterative methods for the variational inequality problem_ , Journal of Computational and Applied Mathematics 60 (1995), no. 1-2, 237–252.
  * [33] , _A modified forward-backward splitting method for maximal monotone mappings_ , SIAM Journal on Control and Optimization 38 (2000), no. 2, 431–446.
  * [34] Tuomo Valkonen, _A primal–dual hybrid gradient method for nonlinear operators with applications to mri_ , Inverse Problems 30 (2014), no. 5, 055012.
  * [35] F. P. Vasilyev, E. V. Khoroshilova, and A. S. Antipin, _An extragradient method for finding the saddle point in an optimal control problem_ , Moscow University Computational Mathematics and Cybernetics 34 (2010), 113–118.
  * [36] John von Neumann and Oskar Morgenstern, _Theory of games and economic behavior (2nd rev. ed.)_ , Princeton University Press, Princeton, 1947.
  * [37] TaeHo Yoon and Ernest K. Ryu, _Accelerated algorithms for smooth convex-concave minimax problems with $o(1/k^{2})$ rate on squared gradient norm_, International Conference on Machine Learning, PMLR, 2021, pp. 12098–12109.
  * [38] Ya-Xiang Yuan and Yi Zhang, _Symplectic discretization approach for developing new proximal point algorithms_ , 2023.
  * [39] Mingqiang Zhu and Tony Chan, _An efficient primal-dual hybrid gradient algorithm for total variation image restoration_ , Ucla Cam Report 34 (2008), no. 2.