Convergence of adaptive operator extrapolation method for operator inclusions in Banach Spaces

Abstract

   A novel iterative splitting algorithm for solving operator inclusions problem is considered in a real Banach space setting. The operator is a sum of the multivalued maximal monotone operator and the monotone Lipschitz continuous operator. The proposed algorithm is an adaptive modification of the “forward-reflected-backward algorithm” [14]. Step size update rule not require Lipschitz constant knowledge of the operator. Advantage of the proposed algorithm is a single calculation of the maximal monotone operator resolvent and value of the monotone Lipschitz continuous operator on each iterative step. Weak convergence of the method is proved for operator inclusions in 2-uniformly convex and uniformly smooth real Banach space.

Keywords

•  1  Maximal monotone operator
• operator inclusion
• variational inequality
• splitting algorithm
• convergence
• adaptability
• 2-uniformly convex Banach space
• uniformly smooth Banach space

1. Introduction 

Research and development of algorithms for operator inclusions ( 1 ) and related problems is a rapidly growing field of applied modern nonlinear analysis [1–4, 7–25].

The most well-known and popular iterative method for solving monotone operator inclusions ( 1 ) in

Hilbert space is the “forward-backward algorithm” (FBA) [1, 11, 12]

xn1  JA  xn   Bxn  , where JA   I   A1 is the operator resolvent, A : H  2H ,   0 .

Note that the FBA scheme includes well-known gradient method and proximal method as special cases [1]. For inverse strongly monotone (cocoercive) operators B : Н  Н FBA method is weakly converging [1]. However, FBA may diverge for Lipschitz continuous monotone operators B .

The condition of the inverse strong monotonicity of the operator B is a rather strong assumption.

To weaken it, Tseng [13] proposed the following modification of the FBA:

 yn  JA  xn   Bxn ,  xn1  yn    Byn  Bxn , where B : H  H – monotone and Lipschitz continuous operator with constant L  0 and  0, L1 . A main limitation of Tseng method is their two calls of B per iteration. Evolution of this idea resulted in the so-called “forward-reflected-backward algorithm” [14]: and related method [15]:  xn1  JA  xn   Bxn    Bxn  Bxn1  ,    0,  1 

 , 2L   xn1  JA  xn   Bxn     Bxn  Bxn1  ,    0,  1 

 . 3L 

A special case of this algorithm is the algorithm “optimistic gradient descent ascent”, which is popular among specialists in the field of Machine Learning [14, 15].

These schemes are naturally called operator extrapolation schemes. Note that in the three above algorithms there is a requirement to know operator’s Lipschitz constant – which is often unknown or difficult to estimate. To overcome these difficulties, adaptive rules for updating parameter   0 on each step have been proposed [16].

Some progress has been achieved recently in the study of splitting algorithms for operator inclusions in Banach spaces [2, 17–25]. This progress is mostly related to careful use of theoretical results and concepts from Banach spaces geometry [2, 26-29]. Book [2] contains an extensive material on this topic.

In the article [17] for the solution of inclusions ( 1 ) in the 2-uniformly convex and uniformly smooth Banach space the next algorithm is proposed: xn1  JA  J 1  Jxn   Bxn  ,  where JA   J   A1 J is the resolvent of operator A: E  2E ,   0 , J is the normalized duality mapping from E to E  . For inverse strongly monotone (cocoercive) operators B : E  E * method ( 2 ) weakly converges [17]. Recently, Shehu [18] extended Tseng's result to 2-uniformly convex and uniformly smooth Banach spaces. He proposed the following weakly converging process for approximating the solution of inclusion ( 1 ):  yn  JA  J 1  xn  n Bxn ,  xn1  J 1  Jyn  n  Byn  Bxn , where n  0 can be set using knowledge of Lipschitz constant of the operator B or calculated with linear search. Note that two values of operator B need to be calculated at the iteration step.

In this article we study a new splitting algorithm for solving operator inclusion ( 1 ) in Banach space. The algorithm is an adaptive modification of the well-known Malitsky–Tam “forward-reflectedbackward algorithm” [14], where the step size update rule not require Lipschitz continuous constant ( 2 ) ( 3 ) knowledge for operator B . It’s advantage is a single computation of maximal monotone operator A resolvent and B operator value on each iterative step. The method weak convergence theorem is proved for operator inclusions in 2-uniformly convex and uniformly smooth Banach space.

The article structure is the following. Section 2 provides the necessary information from the areas of geometry of Banach spaces and theory of monotonous operators. The proposed adaptive operator extrapolation algorithm is described in section 3. Proof of weak convergence is presented in section 4. Theoretical applications to nonlinear operator equations, convex minimization problems and variational inequalities are given in sections 5 and 6. Some results of numerical experiments are also presented in section 7.

2. Preliminaries 

x  y 2  1 ( 4 )

To formulate and prove our results about convergence of algorithms we need some concepts and important facts about the geometry of real Banach space [26–33].

Consider real Banach space E with norm  . Space E is the dual space for E . Let x, x is a value of linear bounded mapping x  E on x  E (i.e. x, x  x  x ). Let’s   be dual norm in dual space E .

Let SE  x  E : x  1 . Space E is strictly convex, if  x, y  SE , x  y we have [26]. The modulus of convexity of Banach space E is defined as [27]

 x  y   E    inf 1  : x, y  SE , x  y     2   0, 2 .

Space E is uniformly convex, if  E    0   0, 2 [27]. Space E is 2-uniformly convex, if there exists such c  0 that  E    c 2   0, 2 [27]. It is known that 2-uniform convexity implies uniform convexity. Also the uniform convexity of real Banach space implies its reflexivity [26].

A space E is smooth if the limit lim t0 x  ty  x

t exists for all x, y  SE [26]. A space E is uniformly smooth if the limit ( 4 ) exists uniformly over x, y  SE [26].

Convexity type and smoothness type of spaces E and E are in duality relationship [26, 27]: dual space E is strictly convex  space E is smooth [26]; dual space E is smooth  space E is strictly convex [26]; space E is uniformly convex  dual space E is uniformly smooth [26]; space E is uniformly smooth  dual space E is uniformly convex [27]. We can reverse the first two implications if the space E is reflexive [26].

Widely used functional spaces Lp (1  p  2 ) and real Hilbert spaces are uniformly smooth (spaces

Lp are uniformly smooth for p 1,  ) and 2-uniformly convex [26–29].

 Also recall [1, 28, 31, 32] that a multivalued operator A: E  2E is called monotone if x, y  E u  v, x  y  0 u  Ax, v  Ay .

A monotone operator A: E  2E

B : E  2E we have that   A    B implies   A    B , where

is called maximal monotone if for any monotone operator  A   x,u  E  E : u  Ax is a graph of A [1, 28, 31].

 Lemma 1 ([1, 28]). Let A: E  2E be a maximal monotone operator, x  E , u  E  . Then is called normalized duality mapping [30]. We also use the next facts [28, 30, 32, 33]: if Banach space E is smooth then operator J is single-valued [30]; if real Banach space E is strongly convex then operator J is one-to-one and strongly monotone [28]; if Banach space E is reflexive then operator J is onto [28]; if Banach space E is uniformly smooth then on all bounded subsets of E operator J is uniformly continuous [30].

Remark 1. For a Hilbert space J  I . Explicit form of operator J for Banach spaces  p , Lp , and Wpm ( p 1,  ) is provided in [28, 32].

Consider reflexive, strictly convex and smooth space E [26]. The maximal monotonicity of operator  A: E  2E is equivalent to equality  for all   0 [31]. For maximal monotone operator A: E  2E and   0 resolvent JA : E  E is defined as follows [31]

R  J   A  E

JAx   J   A1 Jx , x  E , where J is normalized duality mapping from E to E . It is known that

A10  F  JA   x  E : JA x  x   0 .

It is also known that the set A1 0 is closed and convex [1, 31].

Consider smooth Banach space E [26]. Yakov Alber introduced the convenient real-valued functional [32]

D  x, y  x 2  2 Jy, x  y 2 x, y  E .

Definition of D implies a useful 3-point identity:

D  x, y  D  x, z   D  z, y  2 Jz  Jy, x  z For strictly convex Banach space E and x, y  E [32]: x, y, z  E .

D  x, y  0  x  y .

Lemma 2 ([31]). Let E be a uniformly convex and uniformly smooth Banach space  xn  ,  yn  – bounded sequences of elements from Banach space E . Then xn  yn  0   D  xn , yn   0 .

Jxn  Jyn   0

Lemma 3 ([24, 25]). Let E be a smooth Banach space and 2-uniformly convex. Then for some   1 we have:

D  x, y   1 x  y 2  x, y  E .

Remark 2. For Banach spaces  p , Lp and Wpm (1  p  2 ) we have   [29]. And for a Hilbert space inequality for Lemma 3 becomes identity.

3. Algorithm 

Let real Banach space E be a uniformly smooth and 2-uniformly convex [27]. Let A be a multivalued operator acting from E into 2E , and B an operator acting from E into E* .

Consider the next operator inclusion problem:

find x  E : 0 A  B x , ( 5 )

Let us denote  A  B1 0 set of solutions of this operator inclusion.

Suppose that the next assumptions hold [20]:

  A: E  2E is a maximal monotone operator;  B : E  E * is a monotone and Lipschitz continuous operator with Lipschitz constant L  0 ;  Set  A  B1 0 is nonempty.

Operator inclusion ( 5 ) can be formulated as the problem of finding a fixed point:

find x  E : x  JA  J 1  Jx   Bx , where   0 . Formulation ( 6 ) is useful, as it leads to well-known simple algorithmic idea. Calculation scheme

xn1  JA  J 1  Jxn   Bxn  was studied in [17] for inverse strongly monotone operators B : E  E * . However, the scheme generally does not converge for Lipschitz continuous monotone operators. Let's use the idea of work [14] and consider modified scheme xn1  JA  J 1  Jxn   Bxn    Bxn  Bxn1      ( 6 ) with extrapolation term

And let’s use update rule for   0 similar to one from [16] to exclude explicit use of Lipschitz constant of operator B .

We will assume that we know constant   1 from Lemma 3.

  Bxn  Bxn1  .

Algorithm 1.

Choose some x0  E , x1  E ,  0, 21  and 0 , 1  0 . Set n 1. 1. Compute xn1  JA  J 1  Jxn  n Bxn  n1  Bxn  Bxn1  .

n 2. If xn1  xn  xn1 , then xn  A  B1 0 , else return to 3. 3. Compute   min n , n1     n , xn1  xn 

, if Bxn1  Bxn , Bxn1  Bxn * 

Set n  n 1 and return to 1.

Step size sequence n  which is created by rule on step 3 is non-increasing and bounded from below by

So, we have lnimn  0 .

Let us prove convergence result for proposed Algorithm 1.

4. Proof of convergence 

The following lemma contains inequality which is crucial to proof weak convergence of adaptive operator extrapolation method (Algorithm 1).

Lemma 4. The next inequality holds for the sequence  xn  , generated by adaptive operator extrapolation method (Algorithm 1): Using the rule for n recalculation, we can estimate term 2n1 Bxn  Bxn1, xn  xn1 in ( 11 ) from above. We get n1 Bxn  Bxn1, xn  xn1 . ( 10 ) ( 7 ) ( 8 ) ( 9 ) 2n1 Bxn  Bxn1, xn  xn1  2n1 Bxn  Bxn1 * xn  xn1  2 n1 xn  xn1 xn1  xn  n which was required to prove.

The next theorem states our main result.



Theorem 1. Let Banach space E be a uniformly smooth and 2-uniformly convex, A : E  2E be a multivalued maximal monotone operator, B : E  E* be a monotone and Lipschitz continuous operator. Suppose that J (normalized duality map) is sequentially weakly continuous and  A  B1 0   . Then we have weak convergence of sequence  xn  generated by adaptive operator extrapolation method (Algorithm 1) to a point z  A  B1 0 .

Proof. Let z A  B1 0 . Denote an  D  z, xn   2n1 Bxn1  Bxn , xn  z  n1 D  xn , xn1  ,

n bn  1 n1  n  D  xn1, xn    n n1 

Inequality from Lemma 4 becomes

an1  an  bn .

As lnimn  0 exists, we have 1  n1  n 1  2 0,1 when n   .

 n n1 Let’s show, that an  0 for all big enough n  N . We have an  D  z, xn   2n1 Bxn1  Bxn , xn  z  n1 D  xn , xn1  

n  1   1  xn  z 2  2n1 Bxn1  Bxn * xn  z  n1 xn1  xn 2 

n xn  z 2  2 n1 xn  xn1 xn  z  n1 xn1  xn 2  1    n1  xn  z 2 .

n n   n  We can find such n0  N that 1  n1  0 for all n  n0 ,  n so an  0 for all n  n0 .

Now we can conclude that the next limit exists

  lim  D  z, xn   2n1 Bxn1  Bxn , xn  z  n1 D xn , xn1   , n  n  and subsequence  xnk  that weakly converges to some point z  E . Let’s show that

nk v  Jxnk 1  nk  Bxnk  By  nk 1  Bxnk  Bxnk 1   Jxnk , y  xnk 1  0 .

And then, using monotonicity of B operator, we can obtain the following estimation v, y  xnk  v, xnk  xnk 1  Let us show that all weak partial limits of  xn  sequence belong to set  A  B1 0 . Consider a  v, y  xnk 1  By  1nk  Jxnk  Jxnk 1  nk Bxnk  nk 1  Bxnk  Bxnk 1 , y  xnk 1   1 nk

Jxnk  Jxnk 1, y  xnk 1  nk 1 Bxnk  Bxnk 1, y  xnk 1 

nk  By  Bxnk 1, y  xnk 1  Bxnk 1  Bxnk , y  xnk 1   1 nk

Jxnk  Jxnk 1, y  xnk 1  nk 1 Bxnk  Bxnk 1, y  xnk 1  Bxnk 1  Bxnk , y  xnk 1 .

nk

From

lnim xn  xn1  0 , and the Lipschitz continuity of B we have lim Bxn  Bxn1 *  0 . n

Due to the uniform continuity on bounded sets of the J [30], we obtain

lim Jxn  Jxn1 *  0 . n

Thus

v, y  z  lim v, y  xnk  0 .

k The maximal monotonicity of operator A  B and arbitrariness of  y,v  A  B imply z  A  B1 0 (Lemma 1).

We need to prove that the sequence  xn  weakly converges to point z . Let’s argue by contradiction. Let there exist a subsequence  xmk  that weakly converges to z , z  z . Obviously that z A  B1 0 . We have the equality

So the next limit exists

lim Jxn , z  z .

n Due to the sequential weak continuity of the normalized duality mapping J , we obtain Jz, z  z  lim Jxnk , z  z  lim Jxmk , z  z  Jz, z  z ,

k k so

Jz  Jz, z  z  0 .

As a result we get the contradiction – z  z .

5. Algorithm variants 

For completeness, let us formulate a modification of the proposed algorithm with a fixed step size parameter   0 .

Algorithm 2.

Select some points x0  E , x1  E , and    0, 0.5 1 L1  . Set n  1 .    

xn1  J 1  Jxn  n Bxn  n1  Bxn  Bxn1 . 2. If xn1  xn  xn1 , then xn  B10 . Else go to 3.

3. Compute

  min n , n1     n ,

Set n  n  1 and return to 1.

xn1  xn , if Bxn1  Bxn , Bxn1  Bxn *  otherwise.

Weak convergence of Algorithm 3 follows from Theorem 1.

Theorem 2. Let Banach space E be uniformly smooth and 2-uniformly convex, B : E  E* – monotone and Lipschitz continuous operator, B10   . If J (normalized duality mapping) is sequentially weakly continuous, then the sequence  xn  converges weakly to some point z  B10 .

Remark 3. In [17], the following algorithm was proposed to find the zero of a reverse strongly monotone operator B : E  E* :

xn1  J 1  Jxn  n Bxn  , x1  E ,    where n a,b   0,  ,   0 – the constant of inverse strong monotonicity of operator B . This    algorithm generally does not converge for Lipschitz continuous monotone operators, but it converges weakly ergodic.

Using Theorem 2, let us consider the problem of minimizing a convex continuously Frechet differentiable functional f  x  min . ( 12 )

xE We can formulate variant of Algorithm 3 for ( 12 ), which is a smooth convex minimization problem. Choose some x0  E , x1  E ,  0, 21  and 0 , 1  0 . Set n  1 .

xn1  J 1  Jxn  nf  xn   n1 f  xn   f  xn1 . 2. If xn1  xn  xn1 , then xn arg min f . Else return to 3. 3. Compute   min n , n1     n ,

xn1  xn , if f  xn1   f  xn , f  xn1   f  xn  * 

otherwise.

Set n  n  1 and return to 1.

For this variant of the algorithm, from Theorem 2 we get

Theorem 3. Let Banach space E be uniformly smooth and 2-uniformly convex, f : E  R – convex continuously Frechet differentiable functional with Lipschitz continuous derivative, and arg min f is non-empty. Assume that J is sequentially weakly continuous. Then sequence  xn  generated by Algorithm 4 converges weakly to a point z arg min f .

6. Application to variational inequalities 

Consider real Hilbert space H . Let C is a non-empty, convex and closed subset of space H , B : H  H is a monotone and Lipschitz continuous operator. Consider the next variational inequality problem: find x  C such that  Bx, y  x  0 y C , ( 13 )

Let VI  B,C be a solution set of problem ( 13 ). Variational inequality ( 13 ) is equivalent to the operator inclusion [1]

find x  H such that 0 A  B x , where A  NC is a normal cone for convex and closed set C , i.e.

It is known that

w  H :  w, y  x  0 y  C, x  C, NC x   ,

JA   I   A1   I   NC 1  PC , where PC is projection operator onto the set C [1].

For variational inequality problem ( 13 ), adaptive operator extrapolation method (Algorithm 1) takes the following form:

Algorithm 5.

Choose some x1  H , x2  H ,   0, 0.5 and 1, 2  0 . Set n  2 . generated by Algorithm 5 converges weakly to a point z VI  B,C  .

7. Numerical experiments 

The numerical experiments are performed in Python 3.8.5 with NumPy 1.19 on a 64-bit PC with an Intel Core i7-1065G7 1.3 – 3.9GHz and 16GB RAM. As the test example we consider a toy variational inequality with pseudo-monotone operator.

Example. Let

and operator B : R3  R3 be defined as С  x 5, 53 : x1  x2  x3  0  R3 ,

 2 Bx  e x 2  0, 2 0   2 0 3 0 2  0  x 4 

The variational inequality problem of finding x C :  Bx, y  x  0  yC has unique solution x*  0, 0, 0 . Also, Lipschitz constant for the operator B is known – L  10.136 . We compare adaptive and non-adaptive (marked as “lip” on figures) variants of “Extrapolation from the Past” algorithm [9] and Algorithm 5. For stopping criteria and error estimation we use Euclidian distance to known solution Dn  xn  x* . For this example, we use x0  (4,3,5) as starting point,   0.9( 2  1) / L for nonadaptive version of “Extrapolation from the Past” and   0.9 / 2L for non-adaptive version of Algorithm 5. Also, we use   0.3 and  0.45 (nearly maximal feasible values) for adaptive versions of “Extrapolation from the Past” and Algorithm 5 accordingly.

Time measurements below are got by averaging 100 runs for each algorithm.

Table 1  Time to reach desired error rate  Dn , seconds    error\algorithm    11010     11013     11016  

Extra Past (lip)  0.0308 

As we see from Table 1, for this problem Algorithm 5 outperforms other variants.

On the figure below we can see convergence behavior.

As it can be seen, both adaptive algorithms behave very closely. But it should be noted that Algorithm 5 has only one projection on each iteration instead of two for “Extrapolation from the Past” algorithm [9]  yn  PC  xn   n Byn1 ,  xn1  PC  xn   n Byn .

8. Conclusions 

In this paper new iterative splitting algorithm for solving an operator inclusion with the sum of a maximal monotone operator and a monotone Lipschitz continuous operator in a real Banach space is investigated.

Algorithm 1 is an improvement of the well-known “forward-reflected-backward algorithm” of Malitsky–Tam [14] with adaptive step size, where the step update rule does not require a priori knowledge of the Lipschitz constant of operator B [16].

The algorithm advantage is a single computation of the resolvent of the maximal monotone operator A and the value of the monotone Lipschitz continuous operator B at the iteration step.

Method weak convergence theorem is proved for operator inclusions in Banach space with 2uniform convexity and uniform smoothness [27]. Theoretical applications to operator equations, convex minimization problems, and variational inequalities are presented.

An interesting challenge for the future is the development of a strongly convergent modification for

Algorithm 1.

In connection with the study we will point out two topical issues. First, all results are obtained for the class 2-uniformly convex and uniformly smooth real Banach spaces [27], which does not contain important for applications spaces Lp and Wpm ( 2  p   ). It is highly desirable to get rid of this limitation. Second, fast and robust algorithms for computing the resolvent for a wide range of maximal monotone operators are needed to effectively apply algorithms for nonlinear problems in Banach spaces.

An interesting question is the study of the behavior of Algorithm 1 in the situation A  I . Namely, the question of asymptotic behavior of Bxn * . Note that an estimate Bxn *  O 1n  is theoretically possible.

Acknowledgements 

This work was supported by the MES of Ukraine (project "Computational algorithms and optimization for artificial intelligence, medicine and defense", 0122U002026).

References 

References

[1] H. H. Bauschke , P. L. Combettes , Convex Analysis and Monotone Operator Theory in Hilbert Spaces . Berlin; Heidelberg; New York, Springer, 2017 .

[2] Y. Alber , I. Ryazantseva , Nonlinear Ill Posed Problems of Monotone Type, Springer, Dordrecht, 2006 .

[3] H. Raguet , J. Fadili , G. Peyre , A generalized forward-backward splitting , SIAM J. Imaging Sci. 6 ( 2013 ) 1199 - 1226

[4] D. R. Luke , C. Charitha , R. Shefi , Y. Malitsky , Efficient, Quantitative Numerical Methods for Statistical Image Deconvolution and Denoising . In: Salditt T., Egner A. , Luke D.R . (eds.) Nanoscale Photonic Imaging. Topics in Applied Physics , vol 134 . Springer, Cham, 2020 , pp. 313 - 338 .

[5] R. Tibshirani , Regression shrinkage and selection via the lasso , J. Royal Statist. Soc . 58 ( 1996 ) 267 - 288 .

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

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

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

[9] 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 .

[10] 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 .

[11] P. L. Lions , B. Mercier , Splitting algorithms for the sum of two nonlinear operators , SIAM J. Numer. Anal . 16 ( 1979 ) 964 - 979 .

[12] G. B. Passty , Ergodic Convergence to a Zero of the Sum of Monotone Operators in Hilbert Spaces , Journal of Mathematical Analysis and Applications 72 ( 1979 ) 383 - 390 .

[13] P. Tseng , A modified forward-backward splitting method for maximal monotone mappings , SIAM Journal on Control and Optimization 38 ( 2000 ) 431 - 446 .