=Paper=
{{Paper
|id=Vol-3179/Paper_14
|storemode=property
|title=Theoretical Bound of the Complexity of Someextragradient-Type Algorithms for Variational Inequalities in Banach Spaces
|pdfUrl=https://ceur-ws.org/Vol-3179/Paper_14.pdf
|volume=Vol-3179
|authors=Serhii Denysov,Vladimir Semenov
|dblpUrl=https://dblp.org/rec/conf/iti2/DenysovS21
}}
==Theoretical Bound of the Complexity of Someextragradient-Type Algorithms for Variational Inequalities in Banach Spaces==
https://ceur-ws.org/Vol-3179/Paper_14.pdf
Theoretical Bound of the Complexity of Some Extragradient-
Type Algorithms for Variational Inequalities in Banach Spaces
Serhii Denysov and Vladimir Semenov
Taras Shevchenko National University of Kyiv, 64/13 Volodymyrska Street, Kyiv, 01161, Ukraine
Abstract
The work presents a study of three new extragradient-type algorithms for solving variational
inequalities in a Banach space. Two algorithms are natural modifications of Tseng method and
“Extrapolation from the Past” method for problems in Banach spaces, based on the generalized
Alber projection. The third algorithm, called the operator extrapolation method, is a variant of
forward-reflected-backward algorithm, where the generalized Alber projection is also used
instead of the metric projection onto the admissible set. Advantage of the latter algorithm is
only one calculation of the operator value and the generalized projection onto the feasible set
on each iteration. For variational inequalities with monotone Lipschitz operators acting in a 2-
uniformly convex and uniformly smooth Banach space O 1 estimates for the complexity in
terms of the gap function are proved.
Keywords 1
variational inequality, monotone operator, extragradient algorithm, Extrapolation from the
Past, gap function, complexity, 2-uniformly convex Banach space, uniformly smooth Banach
space
1. Introduction
Areas of operations research, data analysis, and mathematical physics produces many problems,
which can be written in the form of variational inequalities [1–5]. Prominent example is the saddle
problem that plays an important role in mathematical economics:
min max L p, q ,
pP qQ
where L : P Q R is a smooth convex-concave function, P R n , Q Rm – convex closed sets,
which can be formulated as
find x C : Ax , x x 0 x C ,
where x p, q R n m , C P Q Rnm , and mapping A : P Q Rnm has the next form:
1 L p, q
Ax
L p, q
.
2
Let's recall another important example related to ranking and search on the Web. The problem of
finding the PageRank vector can be rewritten as follows
minn Px x ,
x
where P is an n n column-stochastic matrix, n x R n : i 1 xi 1, xi 0 , and p max pi .
n
i 1,..., n
And the minimization problem can be transformed into a saddle point problem
minn max y, Px x ,
x y 1 1
Information Technology and Implementation (IT&I-2021), December 01–03, 2021, Kyiv, Ukraine
EMAIL: denisov.univ@gmail.com (S. Denysov); volodya.semenov@gmail.com (V. Semenov)
ORCID: 0000-0003-4397-4617 (S. Denysov); 0000-0002-3280-8245 (V. Semenov)
©️ 2022 Copyright for this paper by its authors.
Use permitted under Creative Commons License Attribution 4.0 International (CC BY 4.0).
CEUR Workshop Proceedings (CEUR-WS.org)
144
where p 1 i 1 pi . The last saddle point problem can be rewritten as a bilinear minmax problem on
n
the product of standard simplexes
minn max
x v
2n
Jv, Px x ,
where J is an n 2n -matrix of the form I I , where I is the identity matrix. We got the following
variational inequality problem
find x n , v 2n : P* I J v , x x J * I P x , v v 0 x n v 2n .
Note that often nonsmooth optimization problems can be effectively solved with algorithms for
variational inequalities, if former are reformulated as saddle point problems [6]. With the growing
popularity of generative adversarial networks (GANs) and other adversarial learning models, a steady
interest in algorithms for solving variational inequalities has arisen among specialists in the field of
machine learning [7, 8].
The most widely known method for solving variational inequalities is so called Korpelevich
extragradient algorithm [9]. Many publications are devoted to the study of this algorithm and its
modifications [6, 10–16].
An effective modern version of the extragradient method is Nemirovski mirror-prox method [6].
This method can be interpreted as a variant of the extragradient method with projection understood in
the sense of Bregman divergence. One more interesting method of dual extrapolation for solving
variational inequalities was proposed by Nesterov [10]. Adaptive variants of the Nemirovski proximal
mirror method were studied in [11–13].
In the early 1980s, Popov proposed a modification of the classical Arrow-Hurwitz algorithm for
finding saddle points of convex-concave functions [17]. Recently Popov's algorithm for variational
inequalities has become well known among machine learning specialists under the name “Extrapolation
from the Past” [7, 8].
A modification of Popov's method for solving variational inequalities with monotone operators was
studied in [18]. And in the article [19], a two-stage proximal algorithm for solving the equilibrium
programming problem is proposed, which is an adaptation of the method [17] to the general Ky Fan
inequalities. The algorithm from [19] uses Bregman divergence instead of Euclidean distance. Further
development of this circle of ideas led to the emergence of the so-called forward-reflected-backward
algorithm [20]:
xn1 PC xn n Axn n1 Axn Axn1 ,
and similar method [21]:
xn1 PC xn n Axn n1 Axn Axn1 .
Recently, using theory of Banach spaces and constructions of their geometry [26–30], progress has
been achieved in the research of algorithms for problems above in Banach spaces [3, 23–25]. Extensive
material on this topic is contained in the book [3]. The next algorithm for solving variational inequalities
in a 2-uniformly convex and uniformly smooth Banach space was proposed in [22]:
xn1 C J 1 Jxn Axn ,
where С is Alber generalized projection operator [23], 0 , J is normalized dual mapping from
E to E * . This method weakly converges for inversely strongly monotone (cocoercive) operators
A : E E * . Shehu [24] has recently extended Tseng’s result to 2-uniformly convex and uniformly
smooth Banach spaces. He proposed the next weakly converging process:
yn C J 1 xn n Axn ,
xn 1 J Jyn n Ayn Axn ,
1
where n 0 is either chosen based on operator A Lipschitz constant value or calculated with a kind
of linear search procedure.
145
It should be noted that the early research on algorithms for solving variational inequalities was
usually concentrated on the study of convergence of algorithms and related questions of an asymptotic
nature [13–15, 17, 19–25].
More recent studies are focused on estimating the number of iterations of algorithms required to
obtain an approximate solution of a given quality [6, 8, 10–12, 16, 18]. This direction of research was
initiated by the work of Nemirovski [6], where mentioned earlier mirror-prox algorithm was proposed
and O 1 complexity estimate in terms of the gap function was obtained for the class of problems with
monotone Lipschitz continuous operator.
A fundamental question arose about the construction of an algorithm with O 1 complexity
estimation and single computation of the operator's value and projection onto the feasible set at the
iteration step. Algorithm [20] answers this question in the case of a Hilbert space.
This work is devoted to the study of three new extragradient type algorithms for solving monotone
variational inequalities in a Banach space. The first two algorithms are natural modifications of Tseng's
method [14] and “Extrapolation from the Past” method [18] for problems in Banach spaces using the
generalized Alber projection. Iteration of each of these algorithms is more economical than iteration of
the extragradient method, because the first one uses single projection on iteration, and the second one
needs only one operator calculation. The third algorithm, called operator extrapolation method, is a
variant of the forward-reflected-backward algorithm, proposed by Malitsky and Tam [20]. Operator
extrapolation method also uses generalized Alber projection onto the feasible set. An attractive feature
of the algorithm is only one computation at the iterative step of the operator value and the generalized
projection. The O 1 complexity estimations are proved in terms of the gap function for variational
inequalities with monotone Lipschitz operators acting in a 2-uniformly convex and uniformly smooth
Banach space.
The article has the following structure. Section 2 contains the necessary information on the geometry
of Banach spaces. Section 3 is devoted to variational inequalities. The algorithms are described in
Section 4. The formulations and proofs of complexity estimations are presented in Section 5.
2. Preliminaries
Let us remind some basic terms and results from Banach spaces geometry, which are needed for us
to formulate and prove our results [23, 25–30].
Everywhere later E is a real Banach space with norm , E – dual space for E , x , x – value
of functional x E on element x E . Let’s also denote norm in E .
Let SE x E : x 1 . Banach space E is called strictly convex, if for all x, y S E and x y
x y
we have 1 . Convexity module of E is defined as
2
x y
E inf 1 : x, y S E , x y , 0, 2 .
2
Banach space E is called uniformly convex, if E 0 0, 2 [26, 27]. Banach space E is
called 2-uniformly convex, if exists c 0 such that E c 2 for all 0, 2 [27]. Obviously 2-
uniformly convex space is uniformly convex. It’s known that uniformly convex Banach space is
reflexive [26-28].
Banach space E is called smooth, if
x ty x
lim (1)
t 0 t
exists for all x, y S E [26]. Banach space E is called uniformly smooth if limit (1) exists uniformly
for x, y S E [26]. There is a duality between convexity and smoothness of E and it’s dual space E
146
[26,27]: E – strictly convex E – smooth; E – smooth E – strictly convex; E – uniformly
convex E – uniformly smooth; E – uniformly smooth E – uniformly convex. The first two
implications can be reversed for reflexive space E .
Smoothness module of space E is defined as
x ty x ty
E t sup 1: x, y S E t 0 .
2
Uniform smoothness of Banach space E is equivalent to the relation limt 0 E t t 1 0 [27, 28].
Banach space E is called 2-uniformly smooth, if exists c 0 such that E t ct 2 for all t 0 [27,
28]. Banach space E is 2-uniformly convex if and only if E is 2-uniformly smooth [27–29].
It is known, that Hilbert spaces and spaces L p ( 1 p 2 ) are 2-uniformly convex and uniformly
smooth ( L p are uniformly smooth for p 1, and 2-uniformly smooth for p 2, ) [27, 28].
Multivalued mapping J : E 2E , which has the form
Jx x E : x , x x x
2 2
,
is called normalized dual mapping [27, 28].
For Hilbert space J I (identity). It is known [23, 27, 28] that: if space E is smooth, then mapping
J is single-valued; if E is strictly convex, then J is injective and strictly monotone; if space E is
reflexive, then mapping J is surjective; if E is uniformly smooth, then J is uniformly continuous on
bounded subsets of E . The explicit form of the mapping J for spaces p , L p and W pm ( p 1, ) is
given in [3, 23, 27, 28].
Let E be a smooth Banach space. Let’s consider functional, introduced by Y. Alber in [23]:
d x, y x 2 Jy, x y x, y E.
2 2
The next useful 3-point identity follows from the definition above:
d x, y d x, z d z, y 2 Jz Jy, x z x, y, z E.
If space E is strictly convex, then for x, y E we have
d x, y 0 x y .
Lemma 1 ([25]). Let E be a 2-uniformly convex smooth Banach space. Then for some 1
1
d x, y x y x, y E .
2
1
For Banach spaces p , L p and W pm ( 1 p 2 ) we have [29, 30]. For a Hilbert space,
p 1
inequality from Lemma 1 becomes identity with 1 .
Lemma 2 ([29]). Let E be a 2-uniformly smooth Banach space. Then for some 0
x y x 2 Jx, y y x, y E .
2 2 2
For Banach spaces p , L p and W pm ( 2 p ) we have p 1 [29, 30]. For a Hilbert space,
inequality from Lemma 2 becomes identity with 1 .
Let K be a non-empty closed and convex subset of a reflexive, strictly convex and smooth space
E . It is known [23] that for each x E there exists unique point z K such that
d z , x inf d y , x .
yK
147
This point z is denoted by K x , and the corresponding operator K : E K is called generalized
projection of E onto K (generalized Alber projection) [23]. Note that for a Hilbert space K
coincides with the metric projection onto the set K .
Lemma 3 ([23]). Let K – closed and convex subset of a reflexive, strictly convex and smooth space
E , x E , z K . Then
z K x Jz Jx, y z 0 y K .
Inequality from Lemma 3 is equivalent to the next one [23]:
d y, K x d K x, x d y, x y K .
Remark 1. The main element of the algorithms studied below is the calculation of a new point
x K J 1 Jx x
by known x E and x E . From Lemma 3 and mentioned 3-point identity follows the inequality
fundamental for the analysis of algorithms.
d y, x d y, x d x , x 2 x , y x y K .
Basic information about monotone operators and variational inequalities in Banach spaces can be
found in [1, 3, 23, 28].
3. Variational inequalities
Let E be a 2-uniformly convex and uniformly smooth Banach space, C is a non-empty subset of
space E , A is an operator, acting from E to E * . Let’s consider the variational inequality:
find x C : Ax, y x 0 y C . (2)
Let’s denote set of solutions of (2) as S .
We need the next assumptions:
set C E is convex and closed;
operator A : E E * is a monotone and Lipschitz continuous with constant L 0 on C ;
set S is non-empty.
Let’s consider dual variational inequality:
find x C : Ay, x y 0 y C . (3)
We will denote set of solutions of (3) as S d . Note that set S d is convex and closed. Inequality (3)
is sometimes called weak or dual formulation of (2) (or Minty inequality), and solutions of (3) are called
weak solutions for (2). For monotone operator A we always have S S d . In our setting we have
S d S [1].
Variational inequality (2) can be formulated as a fixed-point problem [23]:
x C J 1 Jx Ax , (4)
with 0 . Formulation (4) is useful, as it leads to obvious algorithmic idea. Procedure
xn1 C J 1 Jxn Axn (5)
was studied in [22] for inversely strongly monotone operators A : E E * . However, for Lipschitz
continuous monotone operators, algorithm (5) generally does not converge. Numerous modifications
of the extragradient algorithm [6, 9–16,24] can be used for such conditions.
In this paper, we focus on three algorithms: the Tseng method [14], the extrapolation from the past
method [18] and more recent forward-reflected-backward algorithm [20]. We consider their natural
148
modifications for problems in Banach spaces using Alber generalized projection instead of the metric
projection.
The goal is to estimate the number of iterations of algorithms necessary to obtain an approximate
solution of a given quality. The quality of approximate solution x C of variational inequality (2) will
be measured using the non-negative gap function [6]
Gap x sup Ay, x y . (6)
yC
Obviously, for definition (6) to be correct, feasible set C should be bounded.
The next lemma holds:
Lemma 4. Let operator A be monotone. If x C is a solution of (2), then Gap x 0 . And vice
versa, if for some x C we have Gap x 0 , then x is a solution of (2).
Everywhere below we assume, that set C E is bounded.
4. Algorithms
Let us study the next iterative extragradient-type algorithms for finding solutions of variational
inequality problem (2).
Algorithm 1. Modified Tseng method ([24]).
Select x1 E , n 0 . Set n 1 .
1. Calculate
yn C J 1 Jxn n Axn .
2. If yn xn , then STOP. Else calculate
xn1 J 1 Jyn n Ayn Axn .
3. Set n : n 1 and go to step 1.
Algorithm 1 is a modification of forward-backward-forward method by P. Tseng [14] for problems
in Banach spaces, where generalized Alber projection is used instead of the metric one.
The weak convergence of the Algorithm 1 in 2-uniformly convex and uniformly smooth Banach
space is proved in [24].
Note that in the case of a Hilbert space and without constraints, the Algorithm 1 coincides with the
Korpelevich extragradient method.
Algorithm 2. Extrapolation from the Past.
Select x1 y0 E , n 0 . Set n 1 .
1. Calculate
yn C J 1 Jxn n Ayn 1 .
2. Calculate
xn1 C J 1 Jxn n Ayn ,
if xn 1 yn xn , then STOP. Else set n : n 1 and go to step 1.
Algorithm 2 is a modification of L.D. Popov algorithm [17] for problems in Banach spaces using
generalized Alber projection operator instead of the metric one.
The convergence of Algorithm 2 in a Hilbert space and in Euclidean space with Bregman divergence
instead of Euclidean distance is proved in [18, 19].
Algorithm 3. Operator extrapolation.
Select x0 x1 E , n 0 . Set n 1 .
1. Calculate
xn1 C J 1 Jxn n Axn n1 Axn Axn1 .
2. If xn 1 xn xn 1 , then STOP. Else set n : n 1 and go to step 1.
Algorithm 3 is a modification of modern "forward-reflected-backward algorithm" [20] for
variational inequalities in Banach spaces.
Remark 2. Some text Algorithm 3 can be represented in form, which is similar to Algorithm 2:
149
xn C J 1 Jyn n 1 Axn 1 ,
yn 1 J Jxn n 1 Axn Axn 1 .
1
This formulation indicates conceptual similarity of Algorithms 1 and 3. More precisely, the operator
extrapolation algorithm is obtained from Algorithm 1 in the same way, as Algorithm 2 can be obtained
from the analogue of the extragradient algorithm
yn C J 1 Jxn n Axn ,
xn 1 C J Jxn n Ayn .
1
Now let us turn to the analysis of the algorithms, namely, to the estimation of the number of iterations
required to obtain an approximate solution of the variational inequality (2) with a given value of the
gap function.
5. Analysis
We will prove, that Algorithms 1 – 3, mentioned above, require O LD
iterations to obtain feasible
point x C , for which Gap x , where 0 and D supa ,bC d a, b .
Theorem 1. Let xn , yn are sequences, generated by Algorithm 1. Suppose that n 0,
1
L
.
y the next inequality holds
N
Then for the sequence of Cesaro means z N n 1 n n
N
n 1 n
1
Gap z N sup yC d y, x1 .
2 n 1 n
N
Proof. For arbitrary y C we have
d y, xn 1 d y , J 1 Jyn n Ayn Axn
y 2 Jyn n Ayn Axn , y Jyn n Ayn Axn *
2 2
y 2 Jyn , y 2n Ayn Axn , y Jyn n Ayn Axn *
2 2
d y, yn yn 2n Ayn Axn , y Jyn n Ayn Axn * .
2 2
Using Lemma 2, we get an estimation
d y, xn 1 d y, yn 2n Ayn Axn , yn y n2 Ayn Axn * .
2
(7)
Let’s use 3-point identity to transform d y, yn
d y, yn d y, xn d xn , yn 2 Jxn Jyn , y xn .
and now use this in (7)
d y, xn1 d y, xn d xn , yn
2 Jxn Jyn , y xn 2n Ayn Axn , yn y n2 Ayn Axn * .
2
From Lipschitz continuity of A , equality d xn , yn 2 Jyn Jxn , yn xn d yn , xn and Lemma 1
we have
d y, xn 1 d y, xn 1 n2 L2 d yn , xn
2 Jxn Jyn n Axn n Ayn , yn y .
Identity
yn C J 1 Jxn n Axn
is equivalent to inequality
Jxn n Axn Jyn , yn y 0 .
150
So, we have
d y, xn 1 d y, xn 1 n2 L2 d yn , xn 2n Ayn , yn y .
From monotonicity of A operator it follows
d y, xn 1 d y, xn 1 n2 L2 d yn , xn 2n Ay, yn y . (8)
Let’s transform (8) as
2n Ay, yn y d y, xn d y, xn 1 1 n2 L2 d yn , xn . (9)
Summing (9) over n from 1 to N , we get
N
2 n Ay, yn y d y, x1 ,
n 1
which leads to
1
Ay, z N y d y, x1 , (10)
2 n 1 n
N
y . Passing in (10) to the supremum over y C , we obtain
N
where z n 1 n n
N N
n 1 n
1
Gap z N sup yC d y, x1 ,
2 n 1 n
N
which was required to prove. ■
Corollary 1. Let xn , yn are the sequences, generated by Algorithm 1 with n 2
1
L
. Then
for the sequence of means z N N1 n 1 yn the next inequality holds:
N
L sup yC d y, x1
Gap z N .
N
For algorithm 2 we have the next result.
Theorem 2. Let xn , yn are the sequences, generated by Algorithm 2. Let n 0, 2L1 . Then
y the next inequality holds:
N
for the Cesaro means sequence z N n 1 n n
N
n 1 n
sup yC d y, x1 1L d x1 , y0
Gap zN .
2 n1 n
N
Proof. For arbitrary y C we have
d y, xn1 d y, xn d xn1 , xn 2n Ayn , y xn1 .
From monotonicity of A follows
Ayn , y xn1 Ayn , y yn Ayn , yn xn1 Ay, y yn Ayn , yn xn 1 .
So, we have
d y, xn 1 d y, xn d xn1 , xn 2n Ayn , yn xn 1 2n Ay, y yn
d y, xn d xn 1 , xn 2n Ayn1 , yn xn 1
2n Ayn Ayn1 , yn xn 1 2n Ay, y yn . (11)
Let’s write 2n Ayn 1 , yn xn 1 as
2n Ayn1 , yn xn1 2 Jxn n Ayn1 Jyn , xn1 yn 2 Jyn Jxn , xn 1 yn .
From the inclusion xn 1 C and Lemma 3 follows inequality
Jxn n Ayn1 Jyn , xn1 yn 0 .
As a result, we have
151
2n Ayn1 , yn xn1 2 Jyn Jxn , xn1 yn d xn1 , xn d xn1 , yn d yn , xn . (12)
Estimating the right side of (11) with (12), we come to the next inequality:
d y, xn 1 d y, xn d xn 1 , yn d yn , xn
2n Ayn Ayn1 , yn xn 1 2n Ay, y yn . (13)
Now let’s estimate term 2n Ayn Ayn1 , yn xn1 . We get
2n Ayn Ayn 1 , yn xn 1 2n Ayn 1 Ayn * xn 1 yn 2n L yn 1 yn xn 1 yn
1 1 2
2n L yn 1 yn xn 1 yn
2
2 2 2
L
n
2
2 L
2 yn 1 xn 2 2 xn yn n xn 1 yn
2 2
2
2
n L yn 1 xn
2
1 2 x y n n
2
2 xn 1 yn
2
. (14)
Here we have used auxiliary inequalities
ab 2 a2 21 2 b2 , a b 2a2 2 2 b2 .
2 2
Estimating norms in (14) using inequality from Lemma 1, we get
2n Ayn Ayn1 , yn xn 1 n L d xn , yn 1
n L 1 2 d yn , xn n L 2 d xn1 , yn . (15)
Using (15) in (13), we get
y, xn 1 d y, xn 1 n L 2 d xn 1 , yn 1 n L 1 2 d yn , xn
n L d xn , yn1 2n Ay, y yn . (16)
Let’s rewrite (16) as
2n Ay, yn y d y, xn n L d xn , yn1 d y, xn1 n1L d xn1 , yn
1 L n 1 2n d x , y 1 L 1 2 d y , x . (17)
n 1 n n n n
Summing (17) over n from 1 to N , we get
N
2 n Ay, yn y d y, x1 1 L d x1 , y0 ,
n 1
and so
d y, x1 1 L d x1 , y0
Ay, z N y , (18)
2 n1 n
N
y . Passing in (18) to the supremum over y C , we obtain
N
where z n 1 n n
N N
n 1 n
sup yC d y, x1 1L d x1 , y0
Gap zN ,
2 n1 n
N
which was required to prove. ■
Corollary 2. Let xn , yn are sequences, generated by Algorithm 2 with n 3 1 L . Then for the
means sequence z N N1 n 1 yn the next inequality holds:
N
L 32 sup yC d y, x1 16 d x1 , y0
Gap z N .
N
Let’s study Algorithm 3.
152
Theorem 3. Let xn be a sequence, generated by Algorithm 3. Let n 0, 2 1 L . Then for the
x
N
n 1 n n 1
sequence of Cesaro means z N 1 the next inequality holds
N
n 1 n
1
Gap z N 1 sup d y, x1 .
2 n 1 n yC
N
Proof. For sequence xn , generated by algorithm 3, the next inequality holds
2 n Axn n1 Axn Axn1 , y xn1 d y, xn d xn1 , xn d y, xn1 y С . (19)
Let’s rewrite (19) the next way:
d y, xn d y, xn1 2n Axn1 , xn1 y 2n Axn 1 Axn , xn 1 y
2n 1 Axn Axn 1 , xn y 2n1 Axn Axn 1 , xn 1 xn d xn 1 , xn . (20)
Summing (20) over n from 1 to N , we get
d y, x1 d y, xN 1
N
2 n Axn 1 , xn 1 y 2N AxN 1 AxN , xN 1 y
n 1
N
2n 1 Axn Axn 1 , xn 1 xn d xn 1 , xn . (21)
n 1
Using Lipschitz continuity of A and Lemma 1 we get
N
2 L Ax Ax , x
n 1
n 1 n n 1 n 1 xn d xn 1 , xn
N
1 1 2 1
2n 1 L xn xn 1 xn 1 xn xn 1 xn xn xn 1 xN 1 xN
2 2
n 1 2 2 2
1
xN 1 xN .
2
2
Using this estimation in (21), we get
N
d y, x1 d y, xN 1 2 n Axn 1 , xn 1 y 2N AxN 1 AxN , xN 1 y
n 1
1
xN 1 xN
2
2
N
1
2 n Axn 1 , xn 1 y 2N L xN 1 xN xN 1 y xN 1 xN
2
n 1 2
N
2 n Axn 1 , xn 1 y N L xN 1 y .
2
n 1
So, we can come to inequality
N
2 n Axn 1 , xn 1 y N L xN 1 y d y, xN 1 d y, x1 y С .
2
(22)
n 1
Using monotonicity of A , we get
N N
N
Ax , x
n 1
n n 1 n 1 y n Ay, xn 1 y n Ay, zN 1 y ,
n 1 n 1
(23)
x
N
n 1 n n 1
where z N 1 . Using estimation (22) in (23), we come to inequality
N
n 1 n
N
1
2 n Ay, z N 1 y N L xN 1 y d y, x1 y С ,
2
n 1
from which follows
153
1
N
Gap z N 1 sup Ay, z N 1 y 2 n sup d y, x1 ,
yC n 1 yC
which was required to prove. ■
1
Corollary 3. Let xn be a sequence, generated by Algorithm 3 with n . Then for the means
2 L
sequence z N 1 N1 n 1 xn 1 the next inequality holds
N
L
Gap z N 1 sup d y, x1 .
N yC
6. Conclusions
Three new extragradient-type algorithms for solving monotone variational inequalities in a Banach
space are studied in the paper.
The first two algorithms are natural modifications of Tseng's method [14] and “Extrapolation from
the Past” method [18] for problems in Banach spaces using generalized Alber projection. Iteration of
each of these algorithms is more economical than iteration of the extragradient method. The first
algorithm has less projections, the second has less operator calculations.
The third algorithm, called the method of operator extrapolation, is a variant of the Malitsky–Tam
forward-reflected-backward algorithm [20]. Generalized Alber projection is used instead of the metric
projection onto feasible set. An attractive feature of the algorithm is only one computation of the
operator value and of the generalized projection onto the feasible set at the iterative step. For variational
inequalities with monotone Lipschitz operators acting in a 2-uniformly convex and uniformly smooth
Banach space, O 1 complexity bounds are proved in terms of the gap function.
Let us point out two actual questions, related to the current research. First, fast and stable algorithms
for computing generalized Alber projection for a wide range of sets are needed to efficiently apply
algorithms to nonlinear problems in Banach spaces. Second, all results were obtained for the class of
2-uniformly convex and uniformly smooth Banach spaces, which does not contain spaces L p and W pm
( 2 p ), which are important for applications. It is highly desirable to get rid of this limitation.
Acknowledgements
This work was supported by the Ministry of Education and Science of Ukraine (project
“Mathematical modeling and optimization of dynamic systems for defense, medicine and ecology”,
state registration number 0119U100337) and the National Academy of Sciences of Ukraine (project
“New methods of research of correctness and solution search for discrete optimization problems,
variational inequalities and their applications”, state registration number 0119U101608).
References
[1] D. Kinderlehrer, G. Stampacchia, An Introduction to Variational Inequalities and Their Applications,
Society for Industrial and Applied Mathematics, Philadelphia, 2000.
[2] A. Nagurney, Network economics: A variational inequality approach, Kluwer Academic Publishers,
Dordrecht, 1999.
[3] Y. Alber, I. Ryazantseva, Nonlinear Ill Posed Problems of Monotone Type, Springer, Dordrecht, 2006.
[4] F. Facchinei, J. S. Pang, Finite-Dimensional Variational Inequalities and Complementarity Problems,
Springer Series in Operations Research, vol. I, Springer, New York, 2003.
[5] S. I. Lyashko, D. A. Klyushin, D. A. Nomirovsky, V. V. Semenov, Identification of age-structured
contamination sources in ground water, in: R. Boucekkine, N. Hritonenko, Y. Yatsenko, Y. (Eds.),
Optimal Control of Age-Structured Populations in Economy, Demography, and the Environment,
Routledge, London–New York, 2013, pp. 277–292.
[6] A. 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
J. Optim. 15 (2004) 229–251. doi:10.1137/S1052623403425629.
154
[7] G. Gidel, H. Berard, P. Vincent, S. Lacoste-Julien, A Variational Inequality Perspective on Generative
Adversarial Networks, arXiv preprint arXiv:1802.10551. (2018).
[8] M. Liu, W. Zhang, Y. Mroueh, X. Cui, J. Ross, T. Yang, P. Das, A decentralized parallel algorithm for
training generative adversarial nets, arXiv preprint arXiv:1910.12999. (2020).
[9] G. M. Korpelevich, An extragradient method for finding saddle points and for other problems,
Matecon. 12 (1976) 747–756.
[10] Yu. Nesterov, Dual extrapolation and its applications to solving variational inequalities and related
problems, Mathematical Programming 109 (2007), 319–344.
[11] F. S. Stonyakin, E. A. Vorontsova, M. S. Alkousa, New Version of Mirror Prox for Variational
Inequalities with Adaptation to Inexactness, in: Jacimovic M., Khachay M., Malkova V., Posypkin M.
(Eds.), Optimization and Applications, OPTIMA 2019, volume 1145 of Communications in Computer
and Information Science, Springer, Cham, 2020, 427–442. doi:10.1007/978-3-030-38603-0_31.
[12] F. Bach, K. Y. Levy, A Universal Algorithm for Variational Inequalities Adaptive to Smoothness and
Noise, arXiv preprint arXiv:1902.01637. (2019).
[13] S. V. Denisov, D. A. Nomirovskii, B. V. Rublyov, V. V. Semenov, Convergence of Extragradient
Algorithm with Monotone Step Size Strategy for Variational Inequalities and Operator Equations,
Journal of Automation and Information Sciences. 51 (2019) 12–24.
doi:10.1615/JAutomatInfScien.v51.i6.20.
[14] P. Tseng, A modified forward-backward splitting method for maximal monotone mappings, SIAM
Journal on Control and Optimization 38 (2000) 431–446.
[15] V. V. Semenov, A Strongly Convergent Splitting Method for Systems of Operator Inclusions with
Monotone Operators, Journal of Automation and Information Sciences 46(5) (2014) 45–56.
https://doi.org/10.1615/JAutomatInfScien.v46.i5.40.
[16] V. V. Semenov, Modified Extragradient Method with Bregman Divergence for Variational
Inequalities, Journal of Automation and Information Sciences 50(8) (2018) 26–37.
doi:10.1615/JAutomatInfScien.v50.i8.30.
[17] L. D. Popov, A modification of the Arrow-Hurwicz method for search of saddle points, Mathematical
notes of the Academy of Sciences of the USSR. 28 (1980) 845–848.
[18] D. A. Nomirovskii, B. V. Rublyov, V. V. Semenov, Convergence of Two-Stage Method with Bregman
Divergence for Solving Variational Inequalities, Cybernetics and Systems Analysis 55 (2019) 359–
368. doi:10.1007/s10559-019-00142-7.
[19] L. Chabak, V. Semenov, Y. Vedel, A New Non-Euclidean Proximal Method for Equilibrium Problems,
In: O. Chertov et al. (Eds.), Recent Developments in Data Science and Intelligent Analysis of
Information, volume 836 of Advances in Intelligent Systems and Computing, Springer, Cham, 2019,
pp. 50–58. doi:10.1007/978-3-319-97885-7_6.
[20] Y. Malitsky, M. K. Tam, A Forward-Backward Splitting Method for Monotone Inclusions Without
Cocoercivity, SIAM Journal on Optimization 30 (2020) 1451–1472. doi:10.1137/18M1207260.
[21] E. R. Csetnek, Y. Malitsky, M. K. Tam, Shadow Douglas-Rachford Splitting for Monotone Inclusions,
Appl Math Optim. 80 (2019) 665–678. doi:10.1007/s00245-019-09597-8.
[22] H. Iiduka, W. Takahashi, Weak convergence of a projection algorithm for variational inequalities in a
Banach space, Journal of Mathematical Analysis and Applications 339(1) (2008) 668–679.
https://doi.org/10.1016/j.jmaa.2007.07.019.
[23] Y. I. Alber, Metric and generalized projection operators in Banach spaces: properties and applications.
in: Theory and Applications of Nonlinear Operators of Accretive and Monotone Type, vol. 178,
Dekker, New York, 1996, pp. 15–50.
[24] Y. Shehu, Single projection algorithm for variational inequalities in Banach spaces with application to
contact problem, Acta Math. Sci. 40 (2020) 1045–1063. doi:10.1007/s10473-020-0412-2.
[25] K. Aoyama, F. Kohsaka, Strongly relatively nonexpansive sequences generated by firmly
nonexpansive-like mappings, Fixed Point Theory Appl. 95 (2014). doi:10.1186/1687-1812-2014-95.
[26] J. Diestel, Geometry of Banach Spaces, Springer-Verlag, Berlin–Heidelberg, 1975.
[27] B. Beauzamy, Introduction to Banach Spaces and Their Geometry, North-Holland, Amsterdam, 1985.
[28] I. Cioranescu, Geometry of Banach Spaces, Duality Mappings and Nonlinear Problems, Kluwer
Academic, Dordrecht, 1990.
[29] H. K. Xu, Inequalities in Banach spaces with applications, Nonlinear Anal. 16(12) (1991) 1127–1138.
[30] Z. B. Xu, G. F. Roach, Characteristic inequalities of uniformly convex and uniformly smooth Banach
spaces, Journal of Mathematical Analysis and Applications 157(1) (1991) 189–210.
155