Introduction

A popular direction of modern nonlinear analysis is the study of equilibrium problems (Ky Fan inequalities) of the form [1][2][3][4][5][6][7][8][9]:

find x С  :   ,0 F x y  y С  ,(1)

where С is nonempty subset of vector space H (usually Hilbert space), :

F C C R  is function such that   ,0 F x x 

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][6][7][8]. 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 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].

   

Preliminaries

Here are some concepts and facts related to metric Hadamard spaces. Details can be found in [32,39,40]. Let

 

, Xd be a metric space and x , yX  . Geodesic path connecting points

x and y is isometry x and y (or simply geodesic). Metric space   , Xd 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  

  : 0, , d x y X     such that   0 x   ,     , d x y y   . Set     0, , d x y X          , 1 , d z x t d x y  and     ,, d z y td x y  . Set CX  is called convex if for all x , yC  and   0,1 t  holds   1 tx t y C    .

The following inequality is useful property for

  0 CAT space   , Xd     2 1, d tx t y z              2 2 2 , 1 , 1 , td x z t d y z t t d x y     ,   ,, x y z X  ,   0,1 t  . (2) Important examples of   0 CAT

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   0 CAT space is called Hadamard space.

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 xX  there exists unique element

C Px from set C with the property     , min , C zC d P x x d z x  

, moreover the characterization takes place [32]:

C y P x   yC  and       2 2 2 , , , d y z d x z d y x  zC  .

Let  

, Xd be a metric space and   n x be a bounded sequence of elements from X . Let

      , lim , nn n r x x d x x   . The number         inf , n x X n r x r x x   is called asymptotical radius   n x and set               :, n n n A x x X r x x r x    is asymptotic center   n x . It is known that in Hadamard space     n Ax

it consists of one point [32]. Sequence   n x of elements from Hadamard space   , Xd converges weakly to an element

xX  if       k n A x x  for any sequence   k n

x . 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.  .

Let  

, Xd be an Hadamard space. Function  

: X R R      is called convex if for all points x , yX  and   0,1 t  holds     1 tx t y          

Equilibrium problems in Hadamard space

Let   , Xd be a Hadamard space. Consider an equilibrium problem for nonempty closed convex set СX  and bifunction :

F C C R  [34-37]: find x С  :   ,0 F x y  y С  .(3)

Assume that following conditions are satisfied: 1.

 

,0 F x x  for all x С  ; Further we assume that S .

Adaptive algorithms

For approximate solution of (3) we consider extraproximal algorithm with adaptive choice of step size [37].

Algorithm 1. Step 2. Calculate

Initialization. Choose element 1 x С  ,   0,1   ,   1 0,    . Set 1 n  . Step 1. Calculate        2        2 1 1 2 , prox arg min , , n nn n n y C n n Fy x x F y y d y x        . Step 3. Calculate                   11 22 1 1 11 , if , ,, 0, ,, min , , otherwise. 2

, , ,

n n n n n n n n n n n n n n n n n n n F x x F x y F y x d x y d x y F x x F x y F y x                           Set :1

nn  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

1 n   depends on location of points n x , n y , 1 n x  , values   1 , nn F x x  ,   , nn F x y and   1 , nn F y x  .

No information about constants a and b from inequality (4) is used. Obviously, the sequence   n  is non-decreasing. Also, it is lower bounded by

  1 min , 2 max , ab        . Indeed, we have       11 , , , n n n n n n F x x F x y F y x             22 1 max , , , n n n n a b d x y d x y   .

Let us prove the important inequality.

Lemma 2. For x С  and   , prox Fx xx    

, where 0   , the following inequality takes place

    ,, F x x F x y           2 2 2 1 , , ,2d y x d x x d x y    y С  . (7)

Proof. From the definition

      2 1 2 arg min , , yC x F x y d y x     it follows that         22 11 , , , ,22F x x d x x F x p d p x      p С  .(8)

Setting in ( 8)

  1 p tx t y     , y С  ,   0,1 t  , we obtain             22 11 , , ,1 1 , 22F x x d x x F x tx t y d tx t y x                    , 1 , tF x x t F x y                  2 2 2 1 , 1 , 1 , 2 td x x t d y x t t d x y       . Thereby,         1 , 1 , t F x x t F x y                    2 2 2 1 1 , 1 , 1 , 2 t d x x t d y x t t d x y          . (9)

Dividing in ( 9) by 1 t  and passing to the limit as 1 t  we obtain (7). ■ From Lemma 2 it follows that for sequences   n x ,   n y , generated by Algorithm 1 the following inequalities hold

    ,, n n n F x y F x y          2 2 2 1 , , , 2 n n n n n d y x d x y d y y   y С  . (10)     1 ,, n n n F y x F y y          2 2 2 11                 ,(12)

where zS  . Proof. Let zS  . From pseudomonotonicity of bifunction F it follows that

  ,0 n F y z  .(13)

From ( 13) and ( 11)

  1 2, n n n F y x          2 2 2 11

, , ,

n n n n d z x d x x d x z   . (14)

From the calculation rule for

1 n   we conclude             22 1 1 1 1 , , , , , 2 n n n n n n n n n n n F x x F x y F y x d x y d x y           . (15)

Evaluating the left side of ( 14) from below using (15), we get

            22 11 1 2 , , , , n n n n n n n n n n n F x x F x y d x y d x y                 2 2 2 11

, , ,

n n n n d z x d x x d x z   . (16)

For a lower bound

      1 2 , , n n n n n F x x F x y   

in (16) we use (10). We have

            2 2 2 2 2 1 1 1 1 , , , , , n n n n n n n n n n n n d x y d y x d x x d x y d x y                    2 2 2 11

, , ,

n n n n d z x d x x d x z   .(17)

By regrouping (17), we get (12). ■ To prove the convergence of Algorithm 1, we need an elementary lemma about number sequences.

    1 lim , lim , 0 n n n n nn d y x d y x     . Proof. Let zS  . Assume   , nn a d z x  ,     22 1 11 1 , 1 , nn n n n n n nn b d x y d y x                      . Inequality (12) takes form 1 n n n a a b  . Since there exists lim 0 n n    , 1 1 n n      1     0,1  , n .

From Lemma 4 we conclude that exists a limit  

            2 2 2 1 1 1 1 , , , , ,2k k k k k k k k n n n n n n n n F y y F y x d y x d x x d x y              1 ,, k k k k n n n n F x x F x y                   2 2 2 2 2 1 1 1 1 1 , , , , , 22 k k k k k k k k kk n n n n n n n n nn d x y d x y d y x d x x d x y                           2 2 2 2 2 1 1 1 1 1 , , , , , 22 k k k k k k k k k k kk n n n n n n n n n n nn d x x d x y d y x d x y d x y                      2 2 2 11 1 , , ,2k k k k k n n n n n d y x d x x d x y      y С  . (19)

Passing to the limit in (19) taking into account (18) and weakly upper semicontinuity of function

 

,: x 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

F y C R  , we get     , lim,          lim , lim, lim , lim , lim ,k k k n n n n m n k k n k d x z d x z d x z d x z d x z               lim ,                1 2 1 1 2 ,                  1 1 1 1 22 1 11 1 1 1 1 , if , ,, 0, ,, min , , otherwise. 2 ,

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 aC  , 1

x С  , numbers

  0,1   ,   1 0,    , and sequence   n  , such that   0,1 n   , lim 0 n n    , 1 n n       . Set 1 n  . Step 1. Calculate         2 1 2 , prox arg min , , n nn n n y C n n Fx y x F x y d y x        . Step 2. Calculate         2 1 2 , prox arg min , , n nn n n y C n n Fy z x F y y d y x        . Step 3. Calculate   1 1 n n n n x a z      . Step 4. Calculate                   22 1 , if , ,, 0, ,, min , , otherwise. 2

, , ,

n n n n n n n n n n n n n n n n n n n F x z F x y F y z d x y d z y F x z F x y F y z                        Set :1

nn  and go to step 1.

The following known facts have an important role in proving the convergence of Algorithm 3.

Lemma 6 ([41]

). Let sequence of numbers   Proof. Let zS  . We have

      22 1 , 1 , n n n d x z d x z              2 2 1 1 1 1 , 1 1 , n n n n n n n n n n d z y d y x                                  22 , 1 , n n n n d a z d a z       ,(21)      1 , 1 , n n n n d x z d a z z             , 1 , n n n d a z d z z   . Since exists lim 0 n n    , then 1 1 n n      1     0,1  , n .

Using inequality from Lemma 3, we obtain . From Lemma 9 it follows that exists number 𝑀 > 0 such that

  1 , n d x z         , 1 , n n n d a z d x z         max , , , n d a z d x z  for all 0 nn  . Hence   1 , n d x z         0 max , , ,      22 0 , 1 , nn d a z d a z M    

for all n . Then from inequality of Lemma 8 we obtain the estimation

          2 2 2 1 0 0 1 , 1 ,1 1

,

n n n n n n n n d x z d x z d z y                     2 1 1 1 , n n n n n n d y x M              . (22)

Consider sequence

    0 , n d x z .

There are two options: a) there exists a number nN  such that

    1 0 0 ,, nn d x z d x z   for all

nn  ; b) there exists increasing sequence of numbers ()

k n such that     1 0 0 ,, kk nn d x z d x z   for all kN  .

First, consider option a). In that case there exists

  0 lim , n n d x z R   . Since     22 1 0 0 , , 0 nn d x z d x z   , 𝛼 𝑛 → 0 and 1 1 n n      1     0,1  , 𝑛 → ∞, we have   ,0 nn d x y  ,(23)

 

,0

nn d z y  .(24)

Since   n x is bounded it follows that exists a subsequence  

            2 2 2 1 , , , , ,2k k k k k k k k n n n n n n n n F y y F y z d y x d x z d z y           ,, k k k k n n n n F x z F x y                  2 2 2 2 2 1 1 , , , , , 22 k k k k k k k k kk n n n n n n n n nn d x y d z y d y x d x z d z y                        2 2 2 2 2 1 1 , , , , , 22 k k k k k k k k k k kk n n n n n n n n n n nn d z x d x y d y z d x y d z y                   2 2 2 1 , , ,2k k k k k n n n n n d y x d x z d z y     y С  . (25)

Passing to the limit in (25) taking into account (23), (24) 27) follows (26).

Then from (26), inequality From inequality of Lemma 8 and ii) it follows For big numbers k we have

  2 10 , n d x z               2 2 2 00 1 ,, 1 ,      22 0 1 , 1 1 , k k k k k k k m m m m m m m d x z d z y                         2 2 2 0 1 1 1 , , 1 , k k k k k k k k k k m m m m m m m m m m d y x d a z d a z M                     .  2 10 , k m d x z              2 2 2 00 1 , , 1 , k k k k k m m m m m d x z d a z d a z                     2 2 2 1 0 0 1 , , 1 , k k k k k m m m m m d x z d a z d a z          .

Whence, taking into account iii), we obtain Using this technique and idea of work [36] we can construct regularized variant of Algorithm 2 with adaptive step.

  2 0 , k d x z    2 10 , k m d x z        22

Algorithm 4. Initialization. Choose elements 1

x , 0 yC  ,   1 3 0,   ,   1 0,    and sequence   n  such that   0,1 n   , lim 0 n n    , 1 n n       . Set 1 n  . Step 1. Calculate   1 n n n n z a x     . Step 2. Calculate         1 2 1 1 2 , prox arg min , , n nn n n y C n n Fy y z F y y d y z         . Step 3. Calculate         2 1 1 2 , prox arg min , , n nn n n y C n n Fy x z F y y d y z        . Step 4. Calculate                   1 1 1 1 22 1 11 1 1 1 1 , if , ,, 0, ,, min , , otherwise. 2 ,                               Set :1

nn  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.

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 С  :   ,0 Ax y x  y С  .(28)

We assume that following conditions are satisfied to projection of element a on the set of solutions (28).

 CH  is convex

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.

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.