=Paper=
{{Paper
|id=Vol-2845/Paper_30.pdf
|storemode=property
|title=Convergence of Adaptive Methods for Equilibrium Problems in Hadamard Spaces
|pdfUrl=https://ceur-ws.org/Vol-2845/Paper_30.pdf
|volume=Vol-2845
|authors=Vladimir Semenov,Yana Vedel
|dblpUrl=https://dblp.org/rec/conf/iti2/SemenovV20
}}
==Convergence of Adaptive Methods for Equilibrium Problems in Hadamard Spaces==
https://ceur-ws.org/Vol-2845/Paper_30.pdf
Convergence of Adaptive Methods for Equilibrium Problems in
Hadamard Spaces
Vladimir Semenov, Yana Vedel
Taras Shevchenko National University of Kyiv, 64/13 Volodymyrska Street, Kyiv, 01161, Ukraine
Abstract
In this paper we consider equilibrium problems in metric Hadamard spaces. We propose and
study new adaptive algorithms for their approximate solution. For pseudomonotone
bifunctions of Lipschitz type, theorems on the weak convergence of sequences generated by
the algorithms are proved. The proofs are based on the use of Fejer properties of algorithms
with respect to the set of solutions to the problem. A new regularized adaptive extraproximal
algorithm is also proposed and studied. To regularize the basic extraproximal scheme, the
classical Halpern scheme was used. The proposed algorithms are applicable to
pseudomonotone variational inequalities in Hilbert spaces.
Keywords 1
Equilibrium problems, Hadamard space, pseudomonotonicity, adaptability, regularization,
convergence, extraproximal algorithm
1. Introduction
A popular direction of modern nonlinear analysis is the study of equilibrium problems (Ky Fan
inequalities) of the form [1-9]:
find x С : F x, y 0 y С , (1)
where С is nonempty subset of vector space H (usually Hilbert space), F : C C R is function
such that F x, x 0 x С (called bifunction). We can formulate mathematical programming
problems, variational inequalities, and many game theory problems in form (1).
The study of algorithms for solving equilibrium and related problems is actively continuing [5-8,
10-30]. In this article, we will focus only on methods of the extraproximal type. The following
analogue of G. Korpelevich extragradient method [15] for equilibrium problems [16] is called
extraproximal
yn prox n F xn , xn ,
xn 1 prox n F yn , xn ,
where n 0, , prox is proximal operator for function . In [19] two step proximal method
for solving equilibrium problems in Hilbert space was proposed
yn prox n F yn1 , xn ,
xn 1 prox n F yn , xn ,
where n 0, , which is adaptation for L. D. Popov method [20] for general equilibrium
programming problems (see also [21, 22]). Note that a version of this algorithm for variational
inequalities became known among machine learning specialists under the name “Extrapolation from
the Past” [31].
IT&I-2020 Information Technology and Interactions, December 02–03, 2020, KNU Taras Shevchenko, Kyiv, Ukraine
EMAIL: semenov.volodya@gmail.com (V. Semenov); yana.vedel@gmail.com (Y. Vedel)
ORCID: 0000-0002-3280-8245 (V. Semenov); 0000-0002-7160-9994 (Y. Vedel)
©️ 2020 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)
321
Recently, there has been an increased interest in the construction of theory and algorithms for
solving mathematical programming problems in metric Hadamard spaces [32] (also known as
CAT 0 spaces). A strong motivation for studying these problems is the ability to rewrite some
nonconvex problems in the form of convex (more precisely, geodesically convex) in a space with a
specially selected metric structure [32, 33]. Some authors began to study equilibrium problems in
Hadamard spaces [33-37]. For example, in [35], concluding from the results of [16], the authors
proposed and substantiated an analogue of the extraproximal method for pseudomonotone equilibrium
problems in Hadamard spaces.
In this paper, which continues and refines articles [36, 37], two new adaptive two-stage proximal
algorithms for the approximate solution of equilibrium problems in Hadamard spaces are described
and studied. The proposed rules for choosing the step size do not calculate the values of the bifunction
at additional points and do not require knowledge of the Lipschitz constants of the bifunction.
For pseudo-monotone bifunctions of Lipschitz type, theorems on the weak convergence of
sequences generated by the algorithms are proved. The proofs are based on the use of Fejer properties
of algorithms with respect to the set of solutions to the problem. A new regularized adaptive
extraproximal algorithm is also proposed and studied. To regularize the basic adaptive extraproximal
scheme [37], the classical Halpern scheme [38] was used, a version of which for Hadamard spaces
was studied in [32]. It is shown that the proposed algorithms are applicable to pseudomonotone
variational inequalities in Hilbert spaces.
2. Preliminaries
Here are some concepts and facts related to metric Hadamard spaces. Details can be found in [32,
39, 40].
Let X , d be a metric space and x , y X . Geodesic path connecting points x and y is
isometry : 0, d x, y X such that 0 x , d x, y y . Set 0, d x, y X is
denoted by x, y and called geodesic segment with ends x and y (or simply geodesic). Metric
space X , d is called geodesic space if it is possible to connect any two points of X by geodesic
and it is unique geodesic space if for any two points from X there exists exactly one geodesic to
connect them. Geodesic space X , d is called CAT 0 space if for any three points y0 , y1 ,
y2 X such that d 2 y1 , y0 d 2 y2 , y0 12 d 2 y1 , y2 the following inequality holds:
1 2 1 1
d 2 x, y0 d x, y1 d 2 x, y2 d 2 y1 , y2 x X .
2 2 4
It is known that CAT 0 space is unique geodesic [32]. For two points x and y from CAT 0
space X , d and t 0,1 we denote by tx 1 t y unique point z of x, y such that
d z, x 1 t d x, y and d z, y td x, y . Set C X is called convex if for all x , y C
and t 0,1 holds tx 1 t y C . The following inequality is useful property for CAT 0
space X , d
d 2 tx 1 t y, z td 2 x, z 1 t d 2 y, z t 1 t d 2 x, y , x, y, z X , t 0,1 . (2)
Important examples of CAT 0 spaces are Euclidean spaces, R -trees, Hadamard manifolds
(complete connected Riemannian manifolds of non-positive curvature) and Hilbert sphere with
hyperbolic metric [32, 39, 40].
Complete CAT 0 space is called Hadamard space.
322
As in a Hilbert space, the operator of metric projection onto a closed convex set is well defined in
Hadamard spaces C [32]. For each x X there exists unique element PC x from set C with the
property d PC x, x min d z, x , moreover the characterization takes place [32]:
zC
y PC x y C and d 2 y, z d 2 x, z d 2 y, x z C .
Let X , d be a metric space and xn be a bounded sequence of elements from X . Let
r x, xn lim d x, xn . The number r xn inf xX r x, xn is called asymptotical radius
n
xn and set A xn x X : r x, xn r xn is asymptotic center xn . It is known that
in Hadamard space A xn it consists of one point [32]. Sequence xn of elements from
Hadamard space X , d converges weakly to an element x X if A xn x for any k
sequence xnk . It is known that any sequence of elements from closed convex bounded subset K of
Hadamard space has subsequence which converges weakly to element from K [32, 39]. The well-
known analogue of Opial lemma is useful in proving the weak convergence of sequences of elements
of the Hadamard space.
Lemma 1 ([32, p. 60]). Let sequence xn of elements from Hadamard space X , d converges
weakly to an element x X . Then for all y X \ x we have lim d xn , x lim d xn , y .
n n
Let X , d be an Hadamard space. Function : X R R is called convex if for all
points x , y X and t 0,1 holds
tx 1 t y t x 1 t y .
For example, in Hadamard space functions y d y, x are convex [32]. If there exists 0 such
that for all x , y X and t 0,1 the following inequality is satisfied
tx 1 t y t x 1 t y t 1 t d 2 x, y ,
then function is called strongly convex. It is known that for convex functions lower semicontinuity
and weakly lower semicontinuity are equivalent [32, p. 64] and strongly convex semicontinuous
function reaches its minimum at unique point.
For convex proper and lower semicontinuous function : X R R proximal operator
is defined by [32]
prox x arg min yX y 12 d 2 y, x .
Since functions 12 d 2 , x are strongly convex the definition of proximal operator is correct, i.e.
for all x X there exists unique element prox x X .
3. Equilibrium problems in Hadamard space
Let X , d be a Hadamard space. Consider an equilibrium problem for nonempty closed convex
set С X and bifunction F : C C R [34-37]:
find x С : F x, y 0 y С . (3)
Assume that following conditions are satisfied:
1. F x, x 0 for all x С ;
323
2. functions F x, : C R are convex and lower semicontinuous for all x C ;
3. functions F , y : C R are upper weakly semicontinuous for all y C ;
4. bifunction F : C C R is pseudomonotone, i.e.
for all x , y C from F x, y 0 it follows that F y, x 0 .
5. bifunction F : C C R is Lipschitz type, i.e. there exist a 0 , b 0 , such that
F x, y F x, z F z, y ad 2 x, z bd 2 z, y x, y, z C . (4)
Remark 1. If F x, y Ax, y x , where A : C H , С is nonempty subset of Hilbert space
H , then problem (3) takes form of variational inequality
find x С : Ax, y x 0 y С . (5)
If set C H is convex and closed and operator A : C H pseudomonotone, Lipschitz
continuous and sequential weakly semicontinuous, then for (5) conditions 3–5 are satisfied.
Consider dual equilibrium problem:
find x С : F y, x 0 y С . (6)
*
We denote sets of solutions for problems (3) and (6) by S and S . If conditions 1–4 are satisfied
we have S S [34]. Moreover, set S is closed and convex.
* *
Further we assume that S .
4. Adaptive algorithms
For approximate solution of (3) we consider extraproximal algorithm with adaptive choice of step
size [37].
Algorithm 1.
Initialization. Choose element x1 С , 0,1 , 1 0, . Set n 1 .
Step 1. Calculate
yn prox n F xn , xn arg min yC F xn , y 21n d 2 y, xn .
If xn yn , then stop and xn S . Otherwise, go to step 2.
Step 2. Calculate
xn1 prox n F yn , xn arg min yC F yn , y 21n d 2 y, xn .
Step 3. Calculate
n , if F xn , xn 1 F xn , yn F yn , xn 1 0,
n 1 d 2 xn , yn d 2 xn 1 , yn
min , , otherwise.
2 F xn , xn 1 F xn , yn F yn , xn 1
n
Set n : n 1 and go to step 1.
Remark 2. On each step of algorithm 1 we need to solve two convex problems with strongly
convex functions.
In proposed algorithm parameter n 1 depends on location of points xn , yn , xn 1 , values
F xn , xn1 , F xn , yn and F yn , xn1 . No information about constants a and b from inequality
324
(4) is used. Obviously, the sequence n is non-decreasing. Also, it is lower bounded by
min 1 , . Indeed, we have
2 max a, b
F xn , xn1 F xn , yn F yn , xn1 max a, b d 2 xn , yn d 2 xn 1 , yn .
Let us prove the important inequality.
Lemma 2. For x С and x prox F x , x , where 0 , the following inequality takes place
F x, x F x, y
1
2
d 2 y , x d 2 x, x d 2 x , y y С . (7)
Proof. From the definition x arg min yC F x, y 21 d y, x it follows that
2
F x, x d x , x F x, p
1 2 1 2
d p, x p С . (8)
2 2
Setting in (8) p tx 1 t y , y С , t 0,1 , we obtain
F x, x d x , x F x, tx 1 t y d tx 1 t y, x
1 2 1 2
2 2
tF x, x 1 t F x, y
1
2
td 2 x , x 1 t d 2 y, x t 1 t d 2 x , y .
Thereby,
1 t F x, x 1 t F x, y
1
2
1 t d 2 x , x 1 t d 2 y, x t 1 t d 2 x , y . (9)
Dividing in (9) by 1 t and passing to the limit as t 1 we obtain (7). ■
From Lemma 2 it follows that for sequences xn , yn , generated by Algorithm 1 the following
inequalities hold
F xn , yn F xn , y
1
2n
d 2 y, xn d 2 xn , yn d 2 yn , y y С . (10)
F yn , xn1 F yn , y
1
2n
d 2 y, xn d 2 xn , xn1 d 2 xn1 , y y С . (11)
Inequality (10) provides a justification for the stopping rule for Algorithm 1. Indeed, for xn yn
from (10) it follows
F xn , y 0 y С ,
i.e., xn S .
Let us prove an important estimate relating the distances between the points generated by
Algorithm 1 to an arbitrary element of the set of solutions S .
Lemma 3. For sequences xn , yn , generated by Algorithm 1, the following inequality takes
place
325
d 2 xn1 , z d 2 xn , z 1 n d 2 xn1 , yn 1 n d 2 yn , xn , (12)
n1 n1
where z S .
Proof. Let z S . From pseudomonotonicity of bifunction F it follows that
F yn , z 0 . (13)
From (13) and (11)
2n F yn , xn1 d 2 z, xn d 2 xn , xn1 d 2 xn1 , z . (14)
From the calculation rule for n 1 we conclude
F xn , xn 1 F xn , yn F yn , xn 1
2n 1
d 2 xn , yn d 2 xn 1 , yn . (15)
Evaluating the left side of (14) from below using (15), we get
n
2n F xn , xn 1 F xn , yn
n 1
d 2 xn , yn d 2 xn 1 , yn
d 2 z, xn d 2 xn , xn1 d 2 xn1, z . (16)
For a lower bound 2n F xn , xn1 F xn , yn in (16) we use (10). We have
n
d 2 xn , yn d 2 yn , xn 1 d 2 xn 1 , xn
n 1
d 2 xn , yn d 2 xn1 , yn
d 2 z, xn d 2 xn , xn1 d 2 xn1, z . (17)
By regrouping (17), we get (12). ■
To prove the convergence of Algorithm 1, we need an elementary lemma about number sequences.
Lemma 4. Let an , bn be two sequences of non-negative numbers which satisfy
an1 an bn for all n N . Then exists a limit lim an and bn l1 .
n
Let us formulate one of the main results of the work.
Theorem 1. Let X , d be an Hadamard space, C X be a non-empty convex closed set, for
bifuntion F : C C R conditions 1–5 are satisfied and S . Then sequences xn , yn
generated by Algorithm 1 converge weakly to the solution z S of equilibrium problem (3),
moreover, lim d yn , xn lim d yn , xn1 0 .
n n
Proof. Let z S . Assume
an d z, xn , bn 1 n d 2 xn1 , yn 1 n d 2 yn , xn .
n1 n1
Inequality (12) takes form an1 an bn . Since there exists lim n 0 ,
n
n
1 1 0,1 , n .
n 1
From Lemma 4 we conclude that exists a limit lim d 2 z, xn and
n
d x , y d y , x .
n 1
2
n 1 n
2
n n
Whence we get boundedness of the sequence xn and
326
lim d yn , xn lim d xn1 , yn lim d xn1 , xn 0 . (18)
n n n
Consider subsequence x which converges weakly to the point z C . Then from (18) it
nk
converges weakly to z . Let us show that z S . We have
follows that ynk
F y , y F y , x
nk
1
2
d y, x d x , x d x
nk nk 1
nk
2
nk
2
nk nk 1
2
nk 1 ,y
F xnk , xnk 1 F xnk , ynk
2n 1
d x , y d x , y 21 d y, x d x , x d x
2
nk nk
2
nk 1 nk
nk
2
nk
2
nk nk 1
2
nk 1
,y
k
1
2
d x , x d x , y d y , x
nk
2
nk 1 nk
2
2
d x , y d x , y
nk nk
2
nk nk 1
nk 1
2
nk nk
2
nk 1 nk
1
2
d y, x d x , x d x , y y С .
nk
2
nk
2
nk nk 1
2
nk 1 (19)
Passing to the limit in (19) taking into account (18) and weakly upper semicontinuity of function
F , y : C R , we get F z, y lim F ynk , y 0 y С , i.e., z S .
k
Applying Opial lemma for Hadamard spaces (Lemma 1) we obtain the convergence of sequence
xn to the point z S . Indeed, we argue by contradiction. Let exists the subsequence xm , which k
converges weakly to some point z C and z z . It is clear that z S . We have
lim d xn , z lim d xnk , z lim d xnk , z lim d xn , z lim d xmk , z
n k k n k
lim d xmk , z lim d xn , z ,
k n
which is impossible. Therefore xn converges weakly to z S . From (18) it follows that sequence
yn also converges to z S . ■
Remark 3. We see from proof for Theorem 1 that for sequence xn starting from some number
N Fejer condition is satisfied with respect to the set of solutions S .
In recent paper [36] for solution of problem (3) the following algorithm was proposed
yn prox F y , xn arg min yC F yn1 , y 21 d 2 y, xn ,
n n1 n
(20)
x prox n F yn , xn arg min yC F yn , y 2n d 2 y, xn ,
n1
1
where values n 0 were set according to the requirement inf n n ,supn n 0, 2 2 a1b . I.e. the
information about constants from condition (4) was used. Based on the scheme (20) and works [28,
29, 37], we construct a two-stage proximal algorithm with adaptive choice of the value n .
Algorithm 2.
Initialization. Choose element x1 , y0 C , 0, 13 , 1 0, . Set n 1 .
Step 1. Calculate yn prox n F yn1 , xn arg min yC F yn 1 , y 21n d 2 y, xn .
Step 2. Calculate xn1 prox n F yn , xn arg min yC F yn , y 21n d 2 y, xn .
If xn 1 xn yn , then stop and xn S . Otherwise, go to step 3.
327
Step 3. Calculate
n , if F yn 1 , xn 1 F yn 1 , yn F yn , xn 1 0,
n 1 d 2 yn 1 , yn d 2 xn 1 , yn
min n , , otherwise.
2 F y n 1 , xn 1 F y n 1 , y n F y n , xn 1
Set n : n 1 and go to the step 1.
Let us present the main results on the convergence of the Algorithm 2.
Lemma 5. For sequences xn , yn , generated by Algorithm 2 the following inequality takes
place
d 2 xn1 , z d 2 xn , z 1 n d 2 xn1 , yn
n1
1 2 n d 2 yn , xn 2 n d 2 xn , yn1 ,
n1 n1
where z S .
Theorem 2. Let X , d be a Hadamard space, C X be a nonempty convex closed set, for
bifunction F : C C R conditions 1–5 are satisfied and S . Then sequences xn , yn
generated by Algorithm 2 converge weakly to the solution z S of problem (3).
5. Regularized adaptive algorithms
To ensure the convergence of the approximating sequences in the metric of space to the solution
of the equilibrium problem (3), we consider the extraproximal Algorithm 1, regularized using the
well-known Halpern scheme [32, 38], with adaptive choice of the step size.
Algorithm 3.
Initialization. Choose elements a C , x1 С , numbers 0,1 , 1 0, , and
sequence n , such that n 0,1 , lim n 0 , . Set n 1 .
n n 1 n
Step 1. Calculate yn prox n F xn , xn arg min yC F xn , y 21n d 2 y, xn .
Step 2. Calculate zn prox n F yn , xn arg min yC F yn , y 21n d 2 y, xn .
Step 3. Calculate xn1 n a 1 n zn .
Step 4. Calculate
n , if F xn , zn F xn , yn F yn , zn 0,
n 1 d 2 xn , yn d 2 zn , yn
min , , otherwise.
2 F xn , zn F xn , yn F yn , zn
n
Set n : n 1 and go to step 1.
328
The following known facts have an important role in proving the convergence of Algorithm 3.
Lemma 6 ([41]). Let sequence of numbers an has subsequence ank with property a a nk nk 1
for all k N . Then exists non-decreasing sequence mk of natural numbers such that mk
and amk amk 1 , ak amk 1 for all k n1 .
Lemma 7. Let an be a sequence of non-negative numbers satisfying the inequality
an1 1 n an n n for all n N ,
where sequences n and n have properties: n 0,1 , , lim 0 . Then
n
n
n
lim an 0 .
n
First, takes place
Lemma 8. For sequences xn , yn and zn generated by Algorithm 3 inequality holds
d 2 xn1 , z 1 n d 2 xn , z
1 n 1 n d 2 zn , yn 1 n 1 n d 2 yn , xn
n1 n1
n d 2 a, z n 1 n d 2 a, zn , (21)
where z S .
Proof. Let z S . From xn1 n a 1 n zn and inequality for strong convexity (2) the
estimation follows
d 2 xn1 , z n d 2 a, z 1 n d 2 zn , z n 1 n d 2 a, zn .
For upper estimation d 2 zn , z we use Lemma 3 and get (21). ■
Lemma 9. Sequences xn , yn and zn generated by Algorithm 3 are bounded.
Proof. Let z S . We have
d xn1 , z d n a 1 n zn , z n d a, z 1 n d zn , z .
Since exists lim n 0 , then
n
n
1 1 0,1 , n .
n 1
Using inequality from Lemma 3, we obtain
d xn1 , z n d a, z 1 n d xn , z max d a, z , d xn , z
for all n n0 . Hence d xn1 , z max d a, z , d xn0 , z for all n n0 . Thereby sequence
xn is bounded. So from Lemma 3 we conclude that yn and zn are bounded.
329
Theorem 3. Let X , d be a Hadamard space, C X be a nonempty convex closed set, for
bifunction F : C C R conditions 1–5 are satisfied and S . Then sequences xn , yn and
zn generated by Algorithm 3 converge to the element PS a .
Proof. Consider element z0 PS a . From Lemma 9 it follows that exists number 𝑀 > 0 such that
d 2 a, z0 1 n d 2 a, zn M for all n . Then from inequality of Lemma 8 we obtain the
estimation
d 2 xn1 , z0 1 n d 2 xn , z0 1 n 1 n d 2 zn , yn
n1
1 n 1 n d 2 yn , xn n M . (22)
n1
Consider sequence d xn , z0 . There are two options: a) there exists a number n N such that
d xn1, z0 d xn , z0 for all n n ; b) there exists increasing sequence of numbers ( nk ) such that
d xnk 1 , z0 d xnk , z0 for all k N .
First, consider option a). In that case there exists lim d xn , z0 R . Since
n
n
d 2 xn1 , z0 d 2 xn , z0 0 , 𝛼𝑛 → 0 and 1 1 0,1 , 𝑛 → ∞,
n 1
we have
d xn , yn 0 , (23)
d zn , yn 0 . (24)
x which converges weakly to the
Since xn is bounded it follows that exists a subsequence nk
point w X . Then from (23), (24) it follows that y and z converge weakly to w . So nk nk
w C . Let us show that w S . We have
F ynk , y F ynk , znk 21 d y, x d x , z d z , y
2
nk
2
nk nk
2
nk
nk
F xnk , znk F xnk , ynk
2n 1
d 2 xn , yn d 2 zn , yn
k k
1
2n k k
d 2 y, xn d 2 xn , zn d 2 zn , y k k k k
k k
2
1
nk
d z , x d x , y d y , z
2
nk nk
2
2
d x , y d z , y
nk nk
2
nk nk
nk 1
2
nk nk
2
nk nk
2
d y, x d x , z d z , y y С .
1
nk
2
nk
2
nk nk
2
nk (25)
Passing to the limit in (25) taking into account (23), (24) and weak upper semicontinuity of
function F , y : C R , we get
330
F z, y lim F ynk , y 0 y С ,
k
i.e., z S .
Let us prove that
lim d 2 a, z0 1 n d 2 a, zn 0 . (26)
n
Consider subsequence z nk such that
k
lim d 2 a, z0 1 nk d 2 a, znk lim d a, z 1 d a, z .
n
2
0 n
2
n
We can also assume that znk w S weakly. Then, using the weak lower semicontinuity of the
function d 2 a, , we obtain
k
lim d 2 a, z0 1 nk d 2 a, znk d a, z d a, w .
2
0
2
(27)
Since z0 PS a arg min wS d a, w , then from (27) follows (26).
Then from (26), inequality
d 2 xn1 , z0 1 n d 2 xn , z0 n d 2 a, z0 1 n d 2 a, zn ,
which takes place for big n and Lemma 7 we conclude that d xn , z0 0 . From (23), (24) we get
d yn , z0 0 and d zn , z0 0 .
Let us study option b). In that case consider sequence of numbers mk with properties (Lemma
6): i) mk
; ii) d xmk 1 , z0 d xmk , z0 k n ; iii) d x
1 mk 1
, z0 d xk , z0 k n1 .
From inequality of Lemma 8 and ii) it follows
m 2
m d 2 xm , z0 1 m 1 d z m , ym
k
k k k m 1 k k
k
mk 2
1 mk 1
d ymk , xmk mk d a, z0 mk 1 mk d a, zmk mk M .
2 2
mk 1
k
From where lim d xmk , ymk lim d zmk , ymk 0 . Arguments similar to the above, show that the
k
partial sequences weak limits x , y and z belongs to set S . As before, we get
mk mk mk
lim d 2 a, z0 1 mk d 2 a, zmk
k
0 .
For big numbers k we have
d 2 xmk 1 , z0 1 mk d 2 xmk , z0 mk d 2 a, z0 1 mk d 2 a, zmk
1 mk d 2 xmk 1 , z0 mk d 2 a, z0 1 mk d 2 a, zmk .
331
Whence, taking into account iii), we obtain
d 2 xk , z0 d 2 xmk 1 , z0 d 2 a, z0 1 mk d 2 a, zmk .
Thereby
lim d 2 xk , z0 lim d 2 a, z0 1 mk d 2 a, zmk 0 .
k k
So, lim d xn , z0 0 and lim d yn , z0 lim d zn , z0 0 . ■
n n n
Using this technique and idea of work [36] we can construct regularized variant of Algorithm 2
with adaptive step.
Algorithm 4.
Initialization. Choose elements x1 , y0 C , 0, 13 , 1 0, and sequence n
such that n 0,1 , lim n 0 , . Set n 1 .
n n 1 n
Step 1. Calculate zn n a 1 n xn .
Step 2. Calculate yn prox n F yn1 , zn arg min yC F yn 1 , y 21n d 2 y, zn .
Step 3. Calculate xn 1 prox n F yn , zn arg min yC F yn , y 21n d 2 y, zn .
Step 4. Calculate
n , if F yn 1 , xn 1 F yn 1 , yn F yn , xn 1 0,
n 1 d 2 yn 1 , yn d 2 xn 1 , yn
min
n , , otherwise.
2 F y n 1 , xn 1 F y n 1 , y n F y n , xn 1
Set n : n 1 and go to step 1.
Remark 4. Unfortunately, now we do not have a proof of the convergence of Algorithm 4 under
the condition that the bifunction is pseudomonotone.
6. Modification of Algorithm 3 for variational inequalities
Consider a particular case of the equilibrium problem: the variational inequality in the real Hilbert
space H :
find x С : Ax, y x 0 y С . (28)
We assume that following conditions are satisfied
C H is convex and closed;
operator A : C H is pseudomonotone, Lipschitz continuous, and sequentially weakly
continuous;
the set of solutions (28) is not empty.
Let PC be a metric projection operator on convex closed set C , i.e. PC x is an unique element of
set C with property
PC x x min z x .
zC
For variational inequalities (28) Algorithm 3 takes the following form.
332
Algorithm 5.
Initialization. Choose elements a C , x1 С , numbers 0,1 , 1 0, and
sequence n , such that n 0,1 , lim n 0 , . Set n 1 .
n n 1 n
Step 1. Calculate yn PC xn n Axn .
Step 2. Calculate zn PC xn n Ayn .
Step 3. Calculate xn1 n a 1 n zn .
Step 4. Calculate
n , if Axn Ayn , zn yn 0,
n 1 xn yn 2 zn yn 2
min n , 2 Ax Ay , z y , otherwise.
n n n n
Set n : n 1 and go to step 1.
From theorem 3 the following result follows.
Theorem 4. Let H be a Hilbert space, C X be an nonempty convex closed set, operator
A : C H pseudomonotone, Lipschitz continuous, sequentially weakly continuous and there are
solutions (28). Then the sequences generated by Algorithm 5 xn , yn and zn strongly converge
to projection of element a on the set of solutions (28).
Remark 5. If operator A is monotone, then the result of Theorem 4 is valid without the
assumption of the sequential weak continuity of the operator A . Similar results take place for
modifications of algorithms 1, 2, and 4.
7. Conclusions
In this paper, which continues and refines articles [36, 37], two new adaptive two-stage proximal
algorithms for the approximate solution of equilibrium problems in Hadamard spaces are described
and studied. The proposed rules for choosing the step size do not calculate the values of the bifunction
at additional points and do not require knowledge of the Lipschitz constants of the bifunction. For
pseudo-monotone bifunctions of Lipschitz type, theorems on the weak convergence of sequences
generated by the algorithms are proved. A new regularized adaptive extraproximal algorithm is also
proposed and studied. To regularize the basic adaptive extraproximal scheme [37], the classical
Halpern scheme [38] was used, a version of which for Hadamard spaces was studied in [32]. It is
shown that the proposed algorithms are applicable to pseudomonotone variational inequalities in
Hilbert spaces. In the coming papers, we plan to consider more special versions of algorithms for
variational inequalities and minimax problems on Hadamard manifolds (for example, on the manifold
of symmetric positive definite matrices). The construction of randomized versions of algorithms is
also of interest.
Acknowledgements
This work was supported by Ministry of Education and Science of Ukraine (project “Mathematical
modeling and optimization of dynamical systems for defense, medicine and ecology”, 0219U008403).
333
References
[1] G. Kassay, V. D. Radulescu, Equilibrium Problems and Applications, Academic Press, London,
2019.
[2] C. Baiocchi, A. Capello, Variational and Quasi-Variational Inequalities. Applications to Free
Boundary Problems, Wiley, New York, 1984.
[3] D. Kinderlehrer, G. Stampacchia, An introduction to variational inequalities and their
applications, Academic Press, New York, 1980.
[4] E. Blum, W. Oettli, From optimization and variational inequalities to equilibrium problems,
Math. Stud. 63 (1994) 123–145.
[5] P. N. Anh, Strong convergence theorems for nonexpansive mappings and Ky Fan inequalities, J.
Optim. Theory Appl. 154 (2021) 303–320.
[6] P. L. Combettes, S. A. Hirstoaga, Equilibrium Programming in Hilbert Spaces, J. Nonlinear
Convex Anal. 6 (2005) 117–136.
[7] A. S. Antipin, Equilibrium programming: Gradient methods, Autom. Remote Control 58 (1997)
1337–1347.
[8] A. S. Antipin, Equilibrium programming: Proximal methods, Comput. Math. Math. Phys. 37
(1997) 1285–1296. doi:10.1134/S0965542507120044.
[9] G. Mastroeni, On auxiliary principle for equilibrium problems, in: P. Daniele et al. (Eds.),
Equilibrium Problems and Variational Models, Kluwer Academic Publishers, Dordrecht, 2003,
pp. 289–298. doi:10.1007/978-1-4613-0239-1.
[10] S. D. Flam, A. S. Antipin, Equilibrium programming using proximal-like algorithms, Math.
Program. 78 (1997) 29–41.
[11] A. N. Iusem, W. Sosa, On the proximal point method for equilibrium problems in Hilbert spaces,
Optimization 59 (2010) 1259–1274.
[12] A. Moudafi, Proximal point methods extended to equilibrium problems, J. Nat. Geom. 15 (1999)
91–100.
[13] S. Takahashi, W. Takahashi, Viscosity approximation methods for equilibrium problems and
fixed point problems in Hilbert spaces, J. Math. Anal. Appl. 331 (2007), 506–515.
[14] N. Nadezhkina, W. Takahashi, Weak convergence theorem by an extragradient method for
nonexpansive mappings and monotone mappings, J. Optim. Theory Appl. 128 (2006) 191–201.
[15] G. M. Korpelevich, An extragradient method for finding saddle points and for other problems,
Matecon. 12 (1976) 747–756.
[16] T. D. Quoc, L. D. Muu, N. V. Hien, Extragradient algorithms extended to equilibrium problems,
Optimization. 57 (2008) 749–776. doi:10.1080/02331930601122876.
[17] P. T. Vuong, J. J. Strodiot, V. H. Nguyen, Extragradient methods and linesearch algorithms for
solving Ky Fan inequalities and fixed point problems, J. Optim. Theory Appl. 155 (2012) 605–
627.
[18] P. Tseng, A modified forward-backward splitting method for maximal monotone mappings,
SIAM Journal on Control and Optimization 38 (2000) 431–446.
[19] S. I. Lyashko, V. V. Semenov, A New Two-Step Proximal Algorithm of Solving the Problem of
Equilibrium Programming, in: B. Goldengorin (Ed.), Optimization and Its Applications in
Control and Data Sciences, volume 115 of Springer Optimization and Its Applications, Springer,
Cham, 2016, pp. 315–325. doi:10.1007/978-3-319-42056-1_10.
[20] 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.
doi:10.1007/BF01141092.
[21] 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.
[22] 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.
334
[23] 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.
[24] 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.
[25] F. S. Stonyakin, On the adaptive proximal method for a class of variational inequalities and
related problems, Trudy Inst. Mat. i Mekh. UrO RAN. 25 (2019) 185–197. doi:10.21538/0134-
4889-2019-25-2-185-197.
[26] F. Bach, K. Y. Levy, A Universal Algorithm for Variational Inequalities Adaptive to Smoothness
and Noise, arXiv preprint arXiv:1902.01637. (2019).
[27] J. Diakonikolas, Halpern iteration for near-optimal and parameter-free monotone inclusion and
strong solutions to variational inequalities, arXiv preprint arXiv:2002.08872. (2020).
[28] S. V. Denisov, V. V. Semenov, P. I. Stetsyuk, Bregman Extragradient Method with Monotone
Rule of Step Adjustment, Cybernetics and Systems Analysis. 55 (2019) 377–383.
doi:10.1007/s10559-019-00144-5.
[29] 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.
[30] S. I. Lyashko, D. A. Klyushin, D. A. Nomirovsky, V. V. Semenov, Identification of age-
structured contamination sources in ground water, In: R. Boucekkline, N. Hritonenko, and Y.
Yatsenko (Eds.), Optimal Control of Age-Structured Populations in Economy, Demography, and
the Environment, Routledge, London–New York, 2013, pp. 227–292.
[31] G. Gidel, H. Berard, P. Vincent, S. Lacoste-Julien, A Variational Inequality Perspective on
Generative Adversarial Networks. arXiv preprint arXiv:1802.10551. (2018).
[32] M. Bacak, Convex Analysis and Optimization in Hadamard Spaces, De Gruyter, Berlin, 2014.
[33] V. Colao, G. Lopez, G. Marino, V. Martin-Marquez, Equilibrium problems in Hadamard
manifolds, Journal of Mathematical Analysis and Applications. 388 (2012) 61–77.
doi:10.1016/j.jmaa.2011.11.001.
[34] H. Khatibzadeh, V. Mohebbi, Monotone and pseudo-monotone equilibrium problems in
Hadamard spaces, J. of the Australian Math. Soc. (2019). doi:10.1017/S1446788719000041.
[35] H. Khatibzadeh, V. Mohebbi, Approximating solutions of equilibrium problems in Hadamard
spaces, Miskolc Mathematical Notes. 20 (2019) 281–297. doi:10.18514/MMN.2019.2361.
[36] Y. I. Vedel, G. V. Sandrakov, V. V. Semenov, L. M. Chabak, Convergence of a Two-Stage
Proximal Algorithm for the Equilibrium Problem in Hadamard Spaces, Cybernetics and Systems
Analysis. 56 (2020) 784–792. doi:10.1007/s10559-020-00299-6.
[37] Y. I. Vedel, E. N. Golubeva, V. V. Semenov, L. M. Chabak, Adaptive extraproximal algorithm
for the equilibrium problem in Hadamard spaces, Journal of Automation and Information
Sciences. 52 (2020) 46–58. doi:10.1615/JAutomatInfScien.v52.i8.40.
[38] B. Halpern, Fixed points of nonexpanding maps, Bull. Amer. Math. Soc. 73 (1967) 957–961.
doi:10.1090/S0002-9904-1967-11864-0.
[39] W. Kirk, N. Shahzad, Fixed point theory in distance spaces, Springer, Cham, 2014.
doi:10.1007/978-3-319-10927-5.
[40] D. Burago, Yu. Burago, S. Ivanov, A Course in Metric Geometry, volume 33 of Graduate
Studies in Mathematics, AMS, Providence, 2001.
[41] P.-E. Mainge, Strong convergence of projected subgradient methods for nonsmooth and
nonstrictly convex minimization, Set-Valued Analysis. 16 (2008) 899–912. doi:10.1007/s11228-
008-0102-z.
335