=Paper=
{{Paper
|id=Vol-3137/paper16
|storemode=property
|title=Convergence of Adaptive Operator Extrapolation Method for Operator Inclusions In Banach Spaces
|pdfUrl=https://ceur-ws.org/Vol-3137/paper16.pdf
|volume=Vol-3137
|authors=Vladimir Semenov,Serhii Denysov
|dblpUrl=https://dblp.org/rec/conf/cmis/SemenovD22
}}
==Convergence of Adaptive Operator Extrapolation Method for Operator Inclusions In Banach Spaces==
https://ceur-ws.org/Vol-3137/paper16.pdf
Convergence of adaptive operator extrapolation method for
operator inclusions in Banach Spaces
Serhii Denysov, Vladimir Semenov
Taras Shevchenko National University of Kyiv, 64/13 Volodymyrska Street, Kyiv, 01161, Ukraine
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
Consider real Banach space E . Denote it’s dual space as E . We study monotone operator
inclusion:
find x E : 0 A B x , (1)
E
where A : E 2 is multivalued maximal monotone operator, B : E E * is monotone, single-valued,
and Lipschitz continuous operator.
Many actual problems can be written in the form of (1). Among them are variational inequalities
and optimization problems from various fields of optimal control, inverse problem theory, machine
learning, image processing, operations research, and mathematical physics [1–6]. Prominent example
is the saddle problem that plays an important role in mathematical economics:
min max F p, q ,
pP qQ
where F : P Q R is a smooth convex-concave function, P R n , Q R m – closed convex sets,
which can be formulated as
find x such that 0 A B x ,
where x p, q R n m and
NP p 1 F p, q
Ax , Bx ,
NQ q 2 F p, q
NP ( NQ ) is a normal cone operator for closed convex set P ( Q ) [1].
CMIS-2022: The Fifth International Workshop on Computer Modeling and Intelligent Systems, May 12, 2022, Zaporizhzhia, Ukraine
EMAIL: denisov.univ@gmail.com (S. Denysov); semenov.volodya@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)
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 is the operator resolvent, A : H 2 H , 0 .
1
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, L1 .
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]:
1
xn 1 J A xn Bxn Bxn Bxn 1 , 0, ,
2L
and related method [15]:
1
xn 1 J A xn Bxn Bxn Bxn 1 , 0, .
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 , (2)
where J A J A J is the resolvent of operator A : E 2 , 0 , J is the normalized duality
1
E
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 ,
(3)
xn 1 J Jyn n Byn Bxn ,
1
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-reflected-
backward algorithm” [14], where the step size update rule not require Lipschitz continuous constant
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
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 .
x y
Let S E x E : x 1 . Space E is strictly convex, if x, y S E , x y we have 1
2
[26]. The modulus of convexity of Banach space E is defined as [27]
x y
E inf 1 : x, y S E , x y 0,2 .
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
x ty x
lim (4)
t 0 t
exists for all x, y S E [26]. A space E is uniformly smooth if the limit (4) exists uniformly over
x, y S E [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].
E
Also recall [1, 28, 31, 32] that a multivalued operator A : E 2 is called monotone if x , y E
u v, x y 0 u Ax, v Ay .
A monotone operator A : E 2 is called maximal monotone if for any monotone operator
E
B : E 2E we have that A B implies A B , where
A x, u E E : u Ax
is a graph of A [1, 28, 31].
E
Lemma 1 ([1, 28]). Let A : E 2 be a maximal monotone operator, x E , u E . Then
u v, x y 0 y, v A x, u A .
It is known that if A : E 2 is maximal monotone operator, B : E E * is Lipschitz continuous
E
monotone operator, then A B is maximal monotone operator [28, 31].
Let us also recall [1] that operator A : E E * is called inverse strongly monotone (cocoercive) if
there exists such a number 0 (the constant of inverse strong monotonicity) that
2
Ax Ay, x y Ax Ay .
Inverse strongly monotone operator is Lipschitz continuous, but not every Lipschitz continuous
operator is inverse strongly monotone.
E
Multivalued mapping J : E 2 , which acts as
Jx x E : x , x x x
2 2
,
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
W pm ( 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
R J A E
E
for all 0 [31]. For maximal monotone operator A : E 2 and 0 resolvent J A : E E is
defined as follows [31]
J A x J A Jx , x E ,
1
where J is normalized duality mapping from E to E . It is known that
A1 0 F J A x E : J A x x 0 .
1
It is also known that the set A 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 Jy, x y
2 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 x, y, z E .
For strictly convex Banach space E and x , y E [32]:
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 Jxn Jyn 0 D xn , yn 0 .
Lemma 3 ([24, 25]). Let E be a smooth Banach space and 2-uniformly convex. Then for some 1
we have:
1
D x, y
2
x y x, y E .
1
Remark 2. For Banach spaces p , Lp and W pm ( 1 p 2 ) we have [29]. And for a Hilbert
p 1
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 2 E , 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 0 set of solutions of this operator inclusion.
1
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 0 is nonempty.
1
Operator inclusion (5) can be formulated as the problem of finding a fixed point:
find x E : x J A J 1 Jx Bx , (6)
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
with extrapolation term
Bxn Bxn 1 .
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.
Algorithm 1.
Choose some x0 E , x1 E , 0, 1
2 and 0 , 1 0 . Set n 1 .
1. Compute
xn 1 J An J 1 Jxn n Bxn n 1 Bxn Bxn 1 .
2. If xn 1 xn xn 1 , then xn A B 0 , else return to 3.
1
3. Compute
xn 1 xn
min n , , if Bxn 1 Bxn ,
n 1 Bxn 1 Bxn *
n , otherwise.
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
min 1 , L1 .
So, we have lim n 0 .
n
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):
n
D z , xn 1 2n Bxn Bxn 1 , xn 1 z D xn 1 , xn
n 1
n 1
D z , xn 2n 1 Bxn 1 Bxn , xn z D xn , xn 1
n
1 n 1 n D xn 1 , xn ,
n n 1
1
where z A B 0 .
1
Proof. Let z A B 0 . Then
Bz Az .
Equality xn 1 J n J Jxn n Bxn n 1 Bxn Bxn 1 can be formulated as
A 1
Jxn n Bxn n 1 Bxn Bxn 1 Jxn 1 n Axn 1 .
From monotonicity of A
Jxn 1 n Bxn Bz n 1 Bxn Bxn 1 Jxn , z xn 1 0 . (7)
Let’s write 3-point identity
D z , xn D z, xn 1 D xn 1 , xn 2 Jxn 1 Jxn , z xn 1 . (8)
Using (8) withing (7) we get
D z, xn 1 D z, xn D xn 1 , xn 2 n Bxn Bz n 1 Bxn Bxn 1 , z xn 1 . (9)
Using monotonicity of operator B . We have
n Bxn Bz n1 Bxn Bxn 1 , z xn 1 n Bxn Bxn1 , z xn 1
n 1 Bxn Bxn 1 , z xn 1 n Bxn 1 Bz , z xn 1
0
n Bxn Bxn 1 , z xn 1 n 1 Bxn Bxn 1 , z xn
n 1 Bxn Bxn 1 , xn xn 1 . (10)
Using (10) withing (9) we get
D z, xn 1 D z, xn D xn 1 , xn 2n Bxn Bxn 1 , z xn 1
2n 1 Bxn Bxn 1 , z xn 2n 1 Bxn Bxn 1 , xn xn 1 . (11)
Using the rule for n recalculation, we can estimate term 2n 1 Bxn Bxn 1 , xn xn 1 in (11) from
above. We get
n 1
2n 1 Bxn Bxn 1 , xn xn 1 2n 1 Bxn Bxn 1 * xn xn 1 2 xn xn 1 xn 1 xn
n
n 1 xn xn 1 n 1 xn xn 1 n 1 D xn , xn 1 n 1 D xn 1 , xn .
2 2
n n n n
So, we came to inequality
n
D z , xn 1 2n Bxn Bxn 1 , xn 1 z D xn 1 , xn
n 1
n 1
D z , xn 2n 1 Bxn 1 Bxn , xn z D xn , xn 1 1 n1 n D xn1 , xn ,
n n n 1
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 0 . Then we have weak convergence of sequence xn generated by adaptive operator
1
extrapolation method (Algorithm 1) to a point z A B 0 .
1
Proof. Let z A B 0 . Denote
1
n 1
an D z , xn 2n 1 Bxn 1 Bxn , xn z 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 lim n 0 exists, we have
n
n 1
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
n 1
an D z , xn 2n 1 Bxn 1 Bxn , xn z
D xn , xn 1
n
1 2 2
xn z 2n 1 Bxn 1 Bxn * xn z n 1 xn 1 xn
n
1 2 n 1 2 1 2
xn z 2 xn xn 1 xn z n 1 xn 1 xn n 1 xn z .
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 2n 1 Bxn 1 Bxn , xn z n 1 D xn , xn 1 ,
n
n
and
n 1 n
1
D xn 1 , xn .
n n 1
n 1
So the generated sequence xn is bounded. Also we have
lim xn1 , xn lim xn 1 xn 0 .
n n
From the fact
lim 2n 1 Bxn 1 Bxn , xn z n 1 D xn , xn 1 0 ,
n
n
we get convergence of sequences z , xn for all z A B 0 .
1
Let us show that all weak partial limits of xn sequence belong to set A B 0 . Consider a
1
subsequence xnk that weakly converges to some point z E . Let’s show that
z A B 0 .
1
If we take any point y, v A B then v By Ay . We have
Jxnk nk Bxnk nk 1 Bxnk Bxnk 1 Jxnk 1 nk Axnk 1 .
Using monotonicity of A operator, we get
n v Jxn 1 n Bxn By n 1 Bxn Bxn 1 Jxn , y xn 1 0 .
k k k k k k k k k
And then, using monotonicity of B operator, we can obtain the following estimation
v, y xnk v, xnk xnk 1
v, y xnk 1 By
1
n
Jx Jx
nk nk 1
nk Bxnk nk 1 Bxnk Bxnk 1 , y xnk 1
k
1 n 1
Jxnk Jxnk 1 , y xnk 1 Bxn Bxn 1 , y xn 1
k
n k
n k
k k k
By Bxnk 1 , y xnk 1 Bxnk 1 Bxnk , y xnk 1
1 n 1
Jxnk Jxnk 1 , y xnk 1 k
Bxn Bxn 1 , y xn 1 Bxnk 1 Bxnk , y xnk 1 .
n k
n k
k k k
From
lim xn xn 1 0 ,
n
and the Lipschitz continuity of B we have
lim Bxn Bxn1 * 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 0 (Lemma 1).
1
We need to prove that the sequence xn weakly converges to point z . Let’s argue by contradiction.
Let there exist a subsequence x that weakly converges to z , z z . Obviously that
mk
z A B 0 . We have the equality
1
2 Jxn , z z D z , xn D z, xn z z .
2 2
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.
1
Select some points x0 E , x1 E , and 0,0.5 L1 . Set n 1 .
1. Compute
xn 1 J A J 1 Jxn 2 Bxn Bxn 1 .
2. If xn 1 xn xn 1 , then xn A B 0 . Else set n n 1 and return to 1.
1
Consider the problem of finding the zero of a nonlinear monotone Lipschitz continuous operator
B : E E* :
find x E : Bx 0 .
For such case Algorithm 1 becomes
Algorithm 3.
Choose some x0 E , x1 E , 0, 2
1
and , 0 . Set n 1 .
0 1
1. Compute
xn 1 J 1 Jxn n Bxn n 1 Bxn Bxn 1 .
2. If xn 1 xn xn 1 , then xn B 1 0 . Else go to 3.
3. Compute
xn 1 xn
min n , , if Bxn 1 Bxn ,
n 1 Bxn 1 Bxn *
n , otherwise.
Set n n 1 and return to 1.
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, B1 0 . If J (normalized duality mapping) is
sequentially weakly continuous, then the sequence xn converges weakly to some point z B 1 0 .
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)
xE
We can formulate variant of Algorithm 3 for (12), which is a smooth convex minimization problem.
Algorithm 4.
Choose some x0 E , x1 E , 0, 1
2 and 0 , 1 0 . Set n 1 .
1. Compute
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
xn 1 xn
min n , , if f xn 1 f xn ,
n 1 f xn 1 f xn *
n , 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.
w H : w, y x 0 y C , x C ,
NC x
, otherwise.
It is known that
J A I A I NC PC ,
1 1
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 .
1. Compute
xn 1 PC xn n Bxn n 1 Bxn Bxn 1 .
2. If xn 1 xn xn 1 , then STOP and xn VI B, C . Else go to 3.
3. Compute
xn 1 xn
min n , , if Bxn 1 Bxn ,
n 1 Bxn 1 Bxn
n , otherwise.
Set n n 1 and return to 1.
For variational inequality case, from Theorem 1 we get
Theorem 4. Let H be a real Hilbert space, C is a non-empty, convex and closed subset of H ,
B : H H is a monotone Lipschitz continuous operator, VI B, C . Then the sequence xn
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
С x 5,5 : x1 x2 x3 0 R 3 ,
3
and operator B : R R be defined as
3 3
2 0 2
2
x
Bx e 0, 2 0 3 0 x
2 0 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 non-
adaptive 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 Extra Past (lip) Extra Past Alg. 5 (lip) Alg. 5
1 1010 0.0308 0.0174 0.0181 0.0087
1 1013 0.0419 0.0251 0.0245 0.0129
1 1016 0.0555 0.0352 0.0331 0.0182
As we see from Table 1, for this problem Algorithm 5 outperforms other variants.
On the figure below we can see convergence behavior.
Figure 1: Convergence in terms of iterations
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 2-
uniform 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 is theoretically
1
n
possible.
Acknowledgements
This work was supported by the MES of Ukraine (project "Computational algorithms and
optimization for artificial intelligence, medicine and defense", 0122U002026).
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.
[14] 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.
[15] 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.
[16] S. Denisov, V. Semenov, Convergence of Adaptive Forward-Reflected-Backward Algorithm for
Solving Variational Inequalities, in: CEUR Workshop Proceedings, vol. 3106, 2021, pp. 116–127.
URL: http://ceur-ws.org/Vol-3106/Paper_11.pdf.
[17] 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.
[18] Y. Shehu, Convergence Results of Forward-Backward Algorithms for Sum of Monotone Operators
in Banach Spaces, Results Math. 74 (2019). doi:10.1007/s00025-019-1061-4.
[19] 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.
[20] J. Yang, P. Cholamjiak, P. Sunthrayuth, Modified Tseng's splitting algorithms for the sum of two
monotone operators in Banach spaces, AIMS Mathematics 6(5) (2021) 4873–4900.
doi:10.3934/math.2021286.
[21] P. Cholamjiak, Y. Shehu, Inertial forward-backward splitting method in Banach spaces with
application to compressed sensing, Appl. Math. 64 (2019) 409–435.
[22] H. A. Abass, C. Izuchukwu, O. T. Mewomo, Q. L. Dong, Strong convergence of an inertial
forward-backward splitting method for accretive operators in real Banach space, Fixed Point
Theory 21 (2020) 397–412.
[23] S. Takahashi, W. Takahashi, Split common null point problem and shrinking projection method
for generalized resolvents in two Banach spaces, J. Nonlinear Convex Anal. 17 (2016) 2171–2182.
[24] 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.
[25] T. Bonesky, K. S. Kazimierski, P. Maass, F. Schopfer, T. Schuster, Minimization of Tikhonov
Functionals in Banach Spaces, Abstr. Appl. Anal. (2008) Article ID 192679. https://doi.org/
10.1155/2008/192679.
[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] 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.
[30] M. M. Vainberg, Variational Method and Method of Monotone Operators in the Theory of
Nonlinear Equations, Wiley, New York, 1974.
[31] V. Barbu, Nonlinear Semigroups and Differential Equations in Banach Spaces, Springer,
Netherlands, 1976.
[32] 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.
[33] R. P. Agarwal, D. O’Regan, D. R. Sahu, Fixed Point Theory for Lipschitzian-type Mappings with
Applications, Springer, New York, 2009.