Abstract
It is well known that many problems in image recovery, signal processing, and machine learning can be modeled as finding zeros of the sum of maximal monotone and Lipschitz continuous monotone operators. Many papers have studied forward-backward splitting methods for finding zeros of the sum of two monotone operators in Hilbert spaces. Most of the proposed splitting methods in the literature have been proposed for the sum of maximal monotone and inverse-strongly monotone operators in Hilbert spaces. In this paper, we consider splitting methods for finding zeros of the sum of maximal monotone operators and Lipschitz continuous monotone operators in Banach spaces. We obtain weak and strong convergence results for the zeros of the sum of maximal monotone and Lipschitz continuous monotone operators in Banach spaces. Many already studied problems in the literature can be considered as special cases of this paper.
Similar content being viewed by others
Avoid common mistakes on your manuscript.
1 Introduction
Let E be a real Banach space with norm \(\Vert .\Vert ,\) we denote by \(E^*\) the dual of E and \(\langle f,x\rangle \) the value of \(f\in E^*\) at \(x\in E.\) Let \(B:E\rightarrow 2^{E^*}\) be a maximal monotone operator and \(A:E\rightarrow E^*\) be a Lipschitz continuous monotone operator. We consider the following inclusion problem: find \(x\in E\) such that
Throughout this paper, we denote the solution set of the inclusion problem (1) by \((A+B)^{-1}(0)\).
The inclusion problem (1) contains, as special cases, convexly constrained linear inverse problem, split feasibility problem, convexly constrained minimization problem, fixed point problems, variational inequalities, Nash equilibrium problem in noncooperative games, and many more. See, for instance, [11, 15, 28, 33, 35, 36] and the references therein.
A popular method for solving problem (1) in real Hilbert spaces, is the well-known forward-backward splitting method introduced by Passty [35] and Lions and Mercier [28]. The method is formulated as
under the condition that \(Dom(B) \subset Dom(A)\). It was shown, see for example [11], that weak convergence of (2) requires quite restrictive assumptions on A and B, such that the inverse of A is strongly monotone or B is Lipschitz continuous and monotone and the operator \(A + B\) is strongly monotone on Dom(B). Tseng in [48], weakened these assumptions and included an extra step per each step of (2) (called Tseng’s splitting algorithm) and obtained weak convergence result in real Hilbert spaces. Quite recently, Gibali and Thong [18] have obtained strong convergence result by modifying Tseng’s splitting algorithm in real Hilbert spaces.
In this paper, we extend Tseng’s result [48] to a Banach space. We first prove the weak convergence of the sequence generated by our proposed method, assuming that the duality mapping is weakly sequentially continuous. This weak convergence is a generalization of Theorem 3.4 given in [48]. We next prove the strong convergence result for problem (1) under some mild assumptions and this extends Theorems 1 and 2 in [18] to Banach spaces. Finally, we apply our convergence results to the composite convex minimization problem in Banach spaces.
2 Preliminaries
In this section, we define some concepts and state few basic results that we will use in our subsequent analysis. Let \(S_E\) be the unit sphere of E, and \(B_E\) the closed unit ball of E.
Let \(\rho _E:[0,\infty )\rightarrow [0,\infty )\) be the modulus of smoothness of E defined by
A Banach space E is said to be 2-uniformly smooth, if there exists a fixed constant \(c>0\) such that \(\rho _E(t)\le ct^2\). The space E is said to be smooth if
exists for all \(x,y\in S_E\). The space E is also said to be uniformly smooth if (3) converges uniformly in \(x,y\in S_E\). It is well known that if E is 2-uniformly smooth, then E is uniformly smooth. It is said to be strictly convex if \(\Vert (x + y)/2\Vert <1\) whenever \(x,y\in S_E\) and \(x\ne y\). It is said to be uniformly convex if \(\delta _E(\epsilon ) >0\) for all \(\epsilon \in (0,2]\), where \( \delta _E\) is the modulus of convexity of E defined by
for all \(\epsilon \in [0,2]\). The space E is said to be 2-uniformly convex if there exists \(c >0\) such that \(\delta _E(\epsilon )\ge c\epsilon ^2\) for all \(\epsilon \in [0,2]\). It is obvious that every 2-uniformly convex Banach space is uniformly convex. It is known that all Hilbert spaces are uniformly smooth and 2-uniformly convex. It is also known that all the Lebesgue spaces \(L_p\) are uniformly smooth and 2-uniformly convex whenever \(1<p\le 2\) (see [7]).
The normalized duality mapping of E into \(E^*\) is defined by
for all \(x\in E\). The normalized duality mapping J has the following properties (see, e.g., [47]):
if E is reflexive and strictly convex with the strictly convex dual space \(E^*\), then J is single-valued, one-to-one and onto mapping. In this case, we can define the single-valued mapping \(J^{-1}:E^*\rightarrow E\) and we have \(J^{-1}=J_{*}\), where \(J_{*}\) is the normalized duality mapping on \(E^*\);
if E is uniformly smooth, then J is uniformly norm-to-norm continuous on each bounded subset of E.
Let us recall from [1, 13] some examples for the normalized duality mapping J in the uniformly convex and uniformly smooth Banach spaces \(\ell _p\) and \(L_p, 1< p <\infty \).
For \(\ell _p: Jx=\Vert x\Vert _{\ell _p}^{2-p}y \in \ell _q\), where \( x=(x_j)_{j\ge 1}\) and \(y=(x_j|x_j|^{p-2})_{j\ge 1}\), \(\frac{1}{p}+\frac{1}{q}=1\).
For \(L_p: Jx=\Vert x\Vert _{L_p}^{2-p}|x|^{p-2}x \in L_q\), \(\frac{1}{p}+\frac{1}{q}=1\).
Now, we recall some fundamental and useful results.
Lemma 2.1
The space E is 2-uniformly convex if and only if there exists \(\mu _E \ge 1\) such that
for all \(x,y\in E\).
The minimum value of the set of all \(\mu _E \ge 1\) satisfying (5) for all \(x,y\in E\) is denoted by \(\mu \) and is called the 2-uniform convexity constant of E; see [5]. It is obvious that \(\mu =1\) whenever E is a Hilbert space.
Lemma 2.2
([4]). Let \(\displaystyle \frac{1}{p}+\frac{1}{q}=1,\ p,q>1\). The space E is q-uniformly smooth if and only if its dual \(E^*\) is p-uniformly convex.
Lemma 2.3
([51]). Let E be a real Banach space. The following are equivalent:
- (1)
E is 2-uniformly smooth
- (2)
There exists a constant \(\kappa >0\) such that \(\forall \ x,y\in E\),
$$\begin{aligned} \Vert x+y\Vert ^2\le \Vert x\Vert ^2+2\langle y,J(x)\rangle +2\kappa ^2\Vert y\Vert ^2, \end{aligned}$$where \(\kappa \) is the 2-uniform smoothness constant. In Hilbert spaces, \(\kappa =\frac{1}{\sqrt{2}}\).
Definition 2.4
Let \( X \subseteq E \) be a nonempty subset. Then a mapping \( A: X \rightarrow E^* \) is called
- (a)
strongly monotone with modulus \(\gamma >0\) on X if
$$\begin{aligned} \langle Ax-Ay, x-y\rangle \ge \gamma \Vert x-y\Vert ^2, \forall x,y \in X. \end{aligned}$$In this case, we say that A is \(\gamma \)-strongly monotone;
- (b)
monotone on X if
$$\begin{aligned} \langle Ax-Ay, x-y\rangle \ge 0, \forall x,y \in X; \end{aligned}$$ - (c)
Lipschitz continuous on X if there exists a constant \( L > 0 \) such that \( \Vert Ax - Ay \Vert \le L \Vert x-y \Vert \) for all \( x, y \in X \).
We give some examples of monotone operator in Banach spaces as given in [2].
Example 2.5
Let \(G\subset \mathbb {R}^n\) be a bounded measurable domain. Define the operator \(A:L^p(G)\rightarrow L^q(G),~~\frac{1}{p}+\frac{1}{q} = 1, ~~p>1\), by the formula
where the function \(\varphi (x,s)\) is measurable as a function of x for every \(s\in [0,\infty )\) and continuous for almost all \(x\in G\) as a function on \(s, |\varphi (x,s)|\le M\) for all \(s\in [0,\infty )\) and for almost all \(x\in G\). Observe that the operator A really maps \(L^p(G)\) to \(L^q(G)\) because of the inequality \(|Ay|\le M|y|^{p-1}\). Then it can be shown that A is a monotone map on \(L^p(G)\).
Let us consider another example from quantum mechanics.
Example 2.6
Define the operator
where \(\triangle :=\sum _{i=1}^3 \frac{\partial ^2}{\partial x_i^2}\) is the Laplacian in \(\mathbb {R}^3\), a and b are constants, \(g(x)=g_0(x)+g_1(x),~~g_0(x) \in L^{\infty }(\mathbb {R}^3), g_1(x) \in L^2(\mathbb {R}^3)\). Let \(A:= L+B\), where the operator L is the linear part of A (it is the Schrödinger operator) and B is defined by the last term. It is known that B is a monotone operator on \(L^2(\mathbb {R}^3)\) (see p. 23 of [2]) and this implies that \(A:L^2(\mathbb {R}^3)\rightarrow L^2(\mathbb {R}^3)\) is also a monotone operator.
Example 2.7
This example gives one of the perhaps most famous example of monotone operators, viz. the p-Laplacian \(-\mathrm{div}(|\nabla u|^{p-2}\nabla u): W^1_0(L_p(\Omega ))\rightarrow \Big (W^1_0(L_p(\Omega ))\Big )^*\), where \(u:\Omega \rightarrow \mathbb {R}\) is a real function defined on a domain \(\Omega \subset \mathbb {R}^n\). The p-Laplacian operator is a monotone operator for \(1<p<\infty \) (in fact, it is strongly monotone for \(p \ge 2\), and strictly monotone for \(1< p < 2\)). The p-Laplacian operator is an extremely important model in many topical applications and certainly played an important role in the development of the theory of monotone operators.
Definition 2.8
A multi-valued operator \(B:E \rightarrow 2^{E^*}\) with graph \(G(T)= \{(x,x^*): x^* \in Tx\}\) is said to be monotone if for any \(x,y \in D(T),x^* \in Tx\) and \(y^* \in Ty\)
A monotone operator B is said to be maximal if \(B =S\) whenever \(S:E \rightarrow 2^{E^*}\) is monotone and \(G(B)\subset G(S)\).
Let E be a reflexive, strictly convex and smooth Banach space and let \(B:E \rightarrow 2^{E^*}\) be a maximal monotone operator. Then for each \(r > 0\) and \(x \in E\), there corresponds a unique element \(x_r \in E\) such that
We define this unique element \(x_r\), the resolvent of B, denoted by \(J^B_rx\). In other words, \(J_r^B=(J +rB)^{-1}J\) for all \(r > 0\). It is easy to show that \(B^{-1}0 = F(J^B_r)\) for all \(r > 0\), where \(F(J^B_r)\) denotes the set of all fixed points of \(J^B_r\). We can also define, for each \(r > 0\), the Yosida approximation of B by \(A_r=\frac{J-JJ^B_r}{r}\). For more details, see, for instance [6].
Suppose E is a smooth Banach space. We introduce the functional studied in [1, 25, 38]: \(\phi :E \times E\rightarrow \mathbb {R}\) defined by:
Clearly,
The following lemma gives some identities of functional \(\phi \) defined in (6).
Lemma 2.9
(See [1, 3]). Let E be a real uniformly convex, smooth Banach space. Then, the following identities hold:
- (i)
$$\begin{aligned} \phi (x,y)= \phi (x,z)+ \phi (z,y)+2\langle x-z, Jz-Jy\rangle , \quad \forall x,y,z\in E. \end{aligned}$$
- (ii)
$$\begin{aligned} \phi (x,y)+\phi (y,x) = 2\langle x-y, Jx-Jy\rangle , \quad \forall x,y\in E. \end{aligned}$$
Let \(C \subseteq E \) be a nonempty, closed and convex subset of a real, uniformly convex Banach space E. Let us introduce the functional \(V(x,y):E \times E^{*}\rightarrow \mathbb {R}\) by the formula:
Then, it is easy to see that
In the next lemma, we describe the property of the operator V(., .) defined in (7).
Lemma 2.10
([1]).
The lemma that follows is stated and proven in [3, Lemma 2.2].
Lemma 2.11
Suppose that E is 2-uniformly convex Banach space. Then, there exists \(\mu \ge 1\) such that
The following lemma was given in [21].
Lemma 2.12
Let S be a nonempty, closed convex subset of a uniformly convex, smooth Banach space E. Let \(\{x_n\}\) be a sequence in E. Suppose that, for all \(u\in S\),
Then \(\{\Pi _S(x_n)\}\) is a Cauchy sequence.
The following property of \(\phi (.,.)\) was given in [1, Theorem 7.5] (see also [16, 17]).
Lemma 2.13
Let E be a uniformly smooth Banach space which is also uniformly convex. If \(\Vert x\Vert \le c, \Vert y\Vert \le c\), then
where \(L_1 (1< L_1 < 3.18)\) is the Figiel’s constant.
We next recall some existing results from the literature to facilitate our proof of strong convergence. The first is taken from [31].
Lemma 2.14
Let \(\{a_n\}\) be sequence of real numbers such that there exists a subsequence \(\{n_i\}\) of \(\{n\}\) such that \(a_{n_i} < a_{{n_i}+1}\), for all \(i\in \mathbb {N}\). Then there exists a nondecreasing sequence \(\{m_k\}\subset \mathbb {N}\) such that \(m_k\rightarrow \infty \) and the following properties are satisfied by all (sufficiently large) numbers \(k\in \mathbb {N}\)
In fact, \(m_k=\max \{j\le k : a_j<a_{j+1}\}\).
Lemma 2.15
([52]). Let \(\{a_n\}\) be a sequence of nonnegative real numbers satisfying the following relation:
where
- (a)
\(\{\alpha _n\}\subset [0,1],\) \( \sum _{n=1}^{\infty } \alpha _n=\infty ;\)
- (b)
\(\limsup \sigma _n \le 0\);
- (c)
\(\gamma _n \ge 0 \ (n \ge 1),\) \( \sum _{n=1}^{\infty } \gamma _n <\infty .\)
Then, \(a_n\rightarrow 0\) as \(n\rightarrow \infty \).
The following lemma is needed in our proof to show that the weak limit point is a solution to the inclusion problem (1).
Lemma 2.16
([6]). Let \(B:E \rightarrow 2^{E^*} \) be a maximal monotone mapping and \( A: E \rightarrow E^* \) be a Lipschitz continuous and monotone mapping. Then the mapping \(A+B\) is a maximal monotone mapping.
The following result gives an equivalence of fixed point problem and problem (1).
Lemma 2.17
Let \(B:E \rightarrow 2^{E^*} \) be a maximal monotone mapping and \( A: E \rightarrow E^* \) be a mapping. Define a mapping
Then \(F(T_\lambda )=(A+B)^{-1}(0),\) where \(F(T_\lambda )\) denotes the set of all fixed points of \(T_\lambda \).
Proof
Let \(x \in F(T_\lambda )\). Then
\(\square \)
We shall adopt the following notation in this paper:
. \(x_n\rightarrow x\) means that \(x_n\rightarrow x\) strongly.
. \(x_n\rightharpoonup x\) means that \(x_n\rightarrow x\) weakly.
3 Approximation Method
In this section, we propose our method and state certain conditions under which we obtain the desired convergence for our proposed methods. First, we give the conditions governing the cost function and the sequence of parameters below.
Assumption 3.1
-
(a)
Let E be a real 2-uniformly convex Banach space which is also uniformly smooth.
-
(b)
Let \(B:E \rightarrow 2^{E^*} \) be a maximal monotone operator; \( A: E \rightarrow E^* \) a monotone and L-Lipschitz continuous.
-
(c)
The solution set \( (A+B)^{-1}(0) \) of the inclusion problem (1) is nonempty.
Throughout this paper, we assume that the duality mapping J and the resolvent \(J_{\lambda _n}^B:=(J+\lambda _nB)^{-1} J\) of maximal monotone operator B are easy to compute.
Assumption 3.2
Suppose the sequence \( \{ \lambda _n \}_{n=1}^\infty \) of step-sizes satisfies the following condition:
where
\(\mu \) is the 2-uniform convexity constant of E;
\(\kappa \) is the 2-uniform smoothness constant of \(E^*\);
L is the Lipschitz constant of A.
Assumption 3.2 is satisfied, e.g., for \( \lambda _n = a+\frac{n}{n+1}\Big (\frac{1}{\sqrt{2\mu }\kappa L}-a\Big )\) for all \( n \ge 1\).
We now give our proposed method below.
Algorithm 3.3
Step 0 Let Assumptions 3.1 and 3.2 hold. Let \( x_1 \in E \) be a given starting point. Set \( n := 1 \).
Step 1 Compute \(y_n:=J_{\lambda _n}^BoJ^{-1}(Jx_n - \lambda _nAx_n)\). If \(x_n-y_n=0\): STOP.
Step 2 Compute
Step 3 Set \( n \leftarrow n+1 \), and go to Step 1.
We observe that in real Hilbert spaces, the duality mapping J becomes the identity mapping and our Algorithm 3.3 reduces to the algorithm proposed by Tseng in [48].
Note that both sequences \(\{y_n\}\) and \(\{x_n\}\) are in E. Furthermore, by Lemma 2.17, we have that if \(x_n=y_n\), then \(x_n\) is a solution of problem (1).
To the best of our knowledge, the proposed Algorithm 3.3 is the only known algorithm which can solve monotone inclusion problem (1) without the inverse-strongly monotonicity of A. We consider some various cases of Algorithm 3.3.
When \(A=0\) in Algorithm 3.3, then Algorithm 3.3 reduces to the methods proposed in [6, 20, 24, 26,27,28, 32, 35, 38, 39, 43]. In this case, the assumption that E is 2-uniformly convex Banach space and uniformly smooth is not needed. In fact, the convergence can be obtained in reflexive Banach spaces in this case. However, we do not know if the convergence of Algorithm 3.3 can be obtained in a more general reflexive Banach space for problem (1).
When \(B=N_C\), the normal cone for closed and convex subset C of E (\(N_C(x):=\{x^* \in E^*:\langle y-x,x^*\rangle \le 0, \forall y \in C \}\)), then the inclusion problem (1) reduces to a variational inequality problem (i.e., find \(x \in C: \langle Ax,y-x\rangle \ge 0,~\forall y \in C\)). It is well known that \(N_C=\partial \delta _C\), where \(\delta _C\) is the indicator function of C at x, defined by \(\delta _C(x)=0\) if \(x \in C\) and \(\delta _C(x)=+\infty \) if \(x \notin C\) and \(\partial (.)\) is the subdifferential, defined by \(\partial f(x):=\{x^* \in E^*: f(y)\ge f(x)+\langle x^*, y-x\rangle ,~~\forall y \in E\}\) for a proper, lower semicontinuous convex functional f on E. Using the theorem of Rockafellar in [40, 41], \(N_C=\partial \delta _C\) is maximal monotone. Hence,
$$\begin{aligned} Jz \in J (J_{\lambda _n}^B)+\lambda _n \partial \delta _C(J_{\lambda _n}^B),\quad \forall z \in E. \end{aligned}$$This implies that
$$\begin{aligned} 0\in \partial \delta _C(J_{\lambda _n}^B)+\frac{1}{\lambda _n}J (J_{\lambda _n}^B)-\frac{1}{\lambda _n}Jz =\partial \left( \delta _C+\frac{1}{2\lambda _n}\Vert .\Vert ^2-\frac{1}{\lambda _n}Jz \right) J_{\lambda _n}^B. \end{aligned}$$Therefore,
$$\begin{aligned} J_{\lambda _n}^B(z)=\mathop {\mathrm{argmin}}\limits _{{y \in E}}\left\{ \delta _C(y)+\frac{1}{2\lambda _n}\Vert y\Vert ^2-\frac{1}{\lambda _n}\langle y,Jz\rangle \right\} \end{aligned}$$and \(y_n\) in Algorithm 3.3 reduces to
$$\begin{aligned} y_n= \mathop {\mathrm{argmin}}\limits _{{y \in E}}\left\{ \delta _C(y)+\frac{1}{2\lambda _n}\Vert y\Vert ^2-\frac{1}{\lambda _n}\langle y,Jx_n - \lambda _nAx_n\rangle \right\} . \end{aligned}$$
However, in implementing our proposed Algorithm 3.3, we assume that the resolvent \((J+\lambda _nB)^{-1} J\) is easy to compute and the duality mapping J is easily computable as well. On the other hand, one has to obtain the Lipschitz constant, L, of the monotone mapping A (or an estimate of it). In a case when the Lipschitz constant cannot be accurately estimated or overestimated, this might result in too small step-sizes \(\lambda _n\). This is a drawback of our proposed Algorithm 3.3. One way to overcome this obstacle is to introduce linesearch in our Algorithm 3.3. This case will be considered in Algorithm 3.8.
3.1 Convergence Analysis
In this section, we give the convergence analysis of the proposed Algorithm 3.3. First, we establish the boundedness of the sequence of iterates generated by Algorithm 3.3.
Lemma 3.4
Let Assumptions 3.1 and 3.2 hold. Assume that \(x^*\in (A+B)^{-1}(0)\) and let the sequence \( \{x_n\}_{n=1}^\infty \) be generated by Algorithm 3.3. Then \(\{x_n\}\) is bounded.
Proof
By the Lyaponuv functional \(\phi \), we have
Using Lemma 2.2, we get that \(E^*\) is 2-uniformly smooth and so by Lemma 2.3, we get
Substituting (10) into (9), we get
Using Lemma 2.9 (i), we get
Putting (12) into (11), we get
Using Lemma 2.9 (ii), we get
Substituting (14) into (13), we have
Since \(y_n= (J+\lambda _nB)^{-1} JoJ^{-1}(Jx_n - \lambda _nAx_n)\), we have \(Jx_n - \lambda _nAx_n \in (J+\lambda _nB)y_n\). Using the fact that B is maximal monotone, then there exists \(v_n \in By_n\) such that \(Jx_n - \lambda _nAx_n=Jy_n+\lambda _n v_n\). Therefore
On the other hand, we know that \(0 \in (Ax^*+Bx^*)\) and \(Ay_n +v_n \in (A+B)y_n\). Since \(A+B\) is maximal monotone, we obtain
Putting (16) into (17), we get
Now, using (18) in (15), we get
Using Assumption 3.2, we get
which shows that \(\lim \phi (x^*, x_n)\) exists and hence, \(\{\phi (x^*, x_n)\}\) is bounded. Therefore \(\{x_n\}\) is bounded. \(\square \)
Definition 3.5
The duality mapping J is weakly sequentially continuous if, for any sequence \(\{x_n\}\subset E\) such that \(x_n\rightharpoonup x\) as \(n\rightarrow \infty \), then \(Jx_n\rightharpoonup ^* Jx\) as \(n\rightarrow \infty \). It is known that the normalized duality map on \(\ell _p\) spaces, \(1< p <\infty \), is weakly sequentially continuous.
We now obtain the weak convergence result of Algorithm 3.3 in the next theorem.
Theorem 3.6
Let Assumptions 3.1 and 3.2 hold. Assume that J is weakly sequentially continuous on E and let the sequence \( \{x_n\}_{n=1}^\infty \) be generated by Algorithm 3.3. Then \(\{x_n\}\) converges weakly to \(z\in (A+B)^{-1}(0)\). Moreover, \(z:=\underset{n\rightarrow \infty }{\lim }\Pi _{(A+B)^{-1}(0)}(x_n)\).
Proof
Let \(x^*\in (A+B)^{-1}(0)\). From (19), we have
Since \(\lim _{n\rightarrow \infty }\phi (x^*, x_n)\) exists, we obtain from (21) that
Applying Lemma 2.11, we get
Since E is uniformly smooth, the duality mapping J is uniformly norm-to-norm continuous on each bounded subset of E. Hence, we have
Since \(\{x_n\}\) is bounded by Lemma 3.4, there exists a subsequence \(\{x_{n_i}\}\) of \(\{x_n\}\) and \(z\in C\) such that \(x_{n_i}\rightharpoonup z\). Since \(\lim _{n\rightarrow \infty } \Vert x_n-y_n\Vert =0\), it follows that \(x_{{n_i}+1}\rightharpoonup z\). We now show that \(z\in (A+B)^{-1}(0)\).
Suppose \((v,u) \in \text {Graph}(A+B)\). This implies that \(Ju-Av \in Bv\). Furthermore, we obtain from \(y_{n_i}= (J+\lambda _{n_i}B)^{-1} JoJ^{-1}(Jx_{n_i} - \lambda _{n_i}Ax_{n_i})\) that
and thus
Using the fact that B is maximal monotone, we obtain
Therefore,
By the fact that \(\lim _{n\rightarrow \infty } \Vert x_n-y_n\Vert =0\) and A is Lipschitz continuous, we obtain \(\lim {n\rightarrow \infty } \Vert Ax_n-Ay_n\Vert =0\). Consequently, we obtain that
By the maximal monotonicity of \(A+B\), we have \(0\in (A+B)z\). Hence, \(z \in (A+B)^{-1}(0)\).
Let \(u_n:=\Pi _{(A+B)^{-1}(0)} (x_n)\). By (20) and Lemma 2.12, we have that \(\{u_n\}\) is a Cauchy sequence. Since \((A+B)^{-1}(0)\) is closed, we have that \(\{u_n\}\) converges strongly to \( w \in (A+B)^{-1}(0)\). By the uniform smoothness of E, we also have \(\lim _{n\rightarrow \infty } \Vert Ju_n-Jw\Vert =0\). We then show that \(z=w\). Using Lemma 2.10 (i), \(u_n=\Pi _{(A+B)^{-1}(0)} (x_n)\) and \( z \in (A+B)^{-1}(0)\), we have
Therefore,
where \(M:=\sup _{n \ge 1}\Vert Jx_n-Ju_n\Vert \). Using \(n=n_{i}\) in \(\lim _{n\rightarrow \infty }\Vert u_n-w\Vert =0, \lim _{n\rightarrow \infty }\Vert Ju_n-Jw\Vert =0\) and the weakly sequential continuity of J, we obtain
as \(i\rightarrow \infty \). Therefore, \( \langle z-w,Jz-Jw\rangle = 0\). Since E is strictly convex, we have \(z = w\). Therefore, the sequence \(\{x_n\}\) converges weakly to \(z=\lim _{n\rightarrow \infty } \Pi (A+B)^{-1}(0) (x_n)\). This completes the proof. \(\square \)
It is easy to see from Algorithm 3.3 above and Lemma 2.17 that \(x_n=y_n\) if and only if \(x_n \in (A+B)^{-1}(0)\). Also, we have already established that \(\Vert x_n-y_n\Vert \rightarrow 0\) holds when \((A+B)^{-1}(0)\ne \emptyset \). Therefore, using the \(\Vert x_n-y_n\Vert \) as a measure of convergence rate, we obtain the following non asymptotic rate of convergence of our proposed Algorithm 3.3.
Theorem 3.7
Let Assumptions 3.1 and 3.2 hold. Let the sequence \( \{x_n\}_{n=1}^\infty \) be generated by Algorithm 3.3. Then \(\min _{1\le k\le n}\Vert x_k-y_k\Vert =O(1/\sqrt{n})\).
Proof
We obtain from (19) that
Hence, we have from Lemma 2.11 that
By Assumption 3.2, we get
Therefore,
This implies that
\(\square \)
Next, we propose another iterative method such that the sequence of step-sizes does not depend on the Lipschitz constant of monotone operator A in problem (1).
Algorithm 3.8
Step 0 Let Assumption 3.1 hold. Given \(\gamma >0, l \in (0,1)\) and \(\theta \in (0,\frac{1}{\sqrt{2\mu }\kappa })\). Let \( x_1 \in E \) be a given starting point. Set \( n := 1 \).
Step 1 Compute \(y_n:= J_{\lambda _n}^BJ^{-1}(Jx_n - \lambda _nAx_n)\), where \(\lambda _n\) is chosen to be the largest
satisfying
If \(x_n-y_n=0\): STOP.
Step 2 Compute
Step 3 Set \( n \leftarrow n+1 \), and go to Step 1.
Before we establish the weak convergence analysis of Algorithm 3.8, we first show that the line search rule given in (22) is well-defined in this lemma.
Lemma 3.9
The line search rule (22) in Algorithm 3.8 is well-defined and
Proof
Using the Lipschitz continuity of A on E, we obtain
This implies that
Therefore, (22) holds whenever \(\lambda _n \le \frac{\theta }{L}\). Hence, \( \lambda _n\) is well-defined.
From the way \( \lambda _n\) is chosen, we can clearly see that \( \lambda _n \le \gamma \). Now, suppose \( \lambda _n=\gamma \), then (22) is satisfied and the lemma is proved. Suppose \( \lambda _n<\gamma \). Then \(\frac{ \lambda _n}{l}\) violates (22) and we get
This implies that \(\lambda _n > \frac{\theta l}{L}\). This completes the proof. \(\square \)
We now give a weak convergence result using Algorithm 3.8 in the next theorem.
Theorem 3.10
Let Assumptions 3.1. Assume that J is weakly sequentially continuous on E and let the sequence \( \{x_n\}_{n=1}^\infty \) be generated by Algorithm 3.8. Then \(\{x_n\}\) converges weakly to \(z\in (A+B)^{-1}(0)\). Moreover, \(z:=\lim _{n\rightarrow \infty } \Pi _{(A+B)^{-1}(0)}(x_n)\).
Proof
Using the same line of arguments as in the proof of Lemma 3.4, we can obtain from (19) that
Since \(\theta ^2 <\frac{1}{2\kappa ^2\mu }\), we get
which shows that \(\lim \phi (x^*, x_n)\) exists and hence, \(\{\phi (x^*, x_n)\}\) is bounded. Therefore \(\{x_n\}\) is bounded. The rest of the proof follows by using the same arguments as in the proof of Theorem 3.6. The completes the proof. \(\square \)
Finally, we give a modification of Algorithm 3.3 and consequently obtain the strong convergence analysis below.
Algorithm 3.11
Step 0 Let Assumptions 3.1 and 3.2 hold. Suppose that \(\{\alpha _n\}\) is a real sequence in (0,1) and let \( x_1 \in E \) be a given starting point. Set \( n := 1 \).
Step 1 Compute \(y_n:= J_{\lambda _n}^BJ^{-1}(Jx_n - \lambda _nAx_n)\). If \(x_n-y_n=0\): STOP.
Step 2 Compute
and
Step 3: Set \( n \leftarrow n+1 \), and go to Step 1.
Theorem 3.12
Let Assumptions 3.1 and 3.2 hold. Suppose that \(\lim _{n \rightarrow \infty } \alpha _n = 0 \) and \( \sum _{n = 1}^{\infty } \alpha _n = \infty \). Let the sequence \( \{x_n\}_{n=1}^\infty \) be generated by Algorithm 3.11. Then \(\{x_n\}\) converges strongly to \(z=\Pi _{(A+B)^{-1}(0)}(x_1)\).
Proof
By Lemma 3.4, we have that \(\{x_n\}\) is bounded. Furthermore, using Lemma 2.10 with (26) and (27), we have
Set \(a_n:=\phi (x_n,z)\) and divide the rest of the proof into two parts as follows.
Case 1 Suppose that there exists \(n_0 \in \mathbb {N}\) such that \(\{\phi (z,x_n)\}_{n=n_0}^{\infty }\) is non-increasing. Then \(\{\phi (z,x_n)\}_{n=1}^{\infty }\) converges, and we therefore obtain
This implies from (30) that
for some \(M_1>0\). Thus,
Hence,
Consequently, \( \Vert x_n-y_n\Vert \rightarrow 0,\ n\rightarrow \infty .\) By (26), we get
Therefore, \(\Vert w_n-y_n\Vert \rightarrow 0,\ n\rightarrow \infty .\) Moreover, we obtain from (27) that
for some \(M_2>0\). Since \(J^{-1}\) is norm-to-norm uniformly continuous on bounded subsets of \(E^*\), we have that
Now,
Since \(\{x_n\}\) is a bounded sunset of E, we can choose a subsequence \(\{x_{n_k}\}\) of \(\{x_n\}\) such that \(x_{n_k}\rightharpoonup p \in E\) and
Since \(z=\Pi _C x_1\), we get
This implies that
Using Lemma 2.15 and (32) in (28), we obtain \(\lim _{n \rightarrow \infty }\phi (z,x_n)=0.\) Thus, \(x_n\rightarrow z\), \(n \rightarrow \infty \).
Case 2 Suppose that there exists a subsequence \(\{x_{n_j}\}\) of \(\{x_n\}\) such that
From Lemma 2.14, there exists a nondecreasing sequence \(\{n_k\}\) of \(\mathbb {N}\) such that \(\lim _{k\rightarrow \infty }\lim n_k=\infty \) and the following inequalities hold for all \(k \in \mathbb {N}\):
Observe that
Since \(\lim _{n\rightarrow \infty }\alpha _n=0\), we get
Since \(\{x_{n_k}\}\) is bounded, there exists a subsequence of \(\{x_{n_k}\}\) still denoted by \(\{x_{n_k}\}\) which converges weakly to \( p\in E\). Repeating the same arguments as in Case 1 above, we can show that
Similarly, we can conclude that
It then follows from (28) and (33) that
Since \(\alpha _{n_k}>0\), we get
By (34), we have that
Therefore, \(x_k\rightarrow z,~~k\rightarrow \infty .\) This concludes the proof. \(\square \)
Remark 3.13
Our proposed Algorithms 3.3 and 3.11 are more applicable than the proposed methods in [10, 12, 23, 29, 30, 42, 44,45,46, 49] even in Hilbert spaces. The methods proposed in [12, 23, 29, 30, 42, 44,45,46, 49] are only applicable for solving problem (1) in the case when B is maximal monotone and A is inverse-strongly monotone (co-coercive) operator in real Hilbert spaces. Our Algorithms 3.3 and 3.11 are applicable for the case when B is maximal monotone and A is monotone operator even in 2-uniformly convex and uniformly smooth Banach spaces (e.g., \(L_p, 1<p\le 2\)). Our results in this paper also complement the results of [14, 22].
4 Application
In this section, we apply our results to the minimization of composite objective function of the type
where \(f:E\rightarrow \mathbb {R}\cup \{ +\infty \}\) is proper, convex and lower semi-continuous functional and \(g:E\rightarrow \mathbb {R}\) is convex functional.
Many optimization problems from image processing [9], statistical regression, machine learning (see, e.g., [50] and the references contained therein), etc can be adapted into the form of (35). In this setting, we assume that g represents the “smooth part” of the functional where f is assumed to be non-smooth. Specifically, we assume that g is G\(\hat{a}\)teaux-differentiable with derivative \(\nabla g\) which is Lipschitz-continuous with constant L. Then by [37, Theorem 3.13], we have
Therefore, \(\nabla g\) is monotone and Lipschitz continuous with Lipschitz constant L. Observe that problem (35) is equivalent to find \( \in E\) such that
Then problem (36) is a special case of inclusion problem (1) with \(A:=\nabla g\) and \(B:=\partial f\).
Next, we obtain the resolvent of \(\partial f\). Let us fix \(r>0\) and \(z \in E\). Suppose \(J_r^{\partial f}\) is the resolvent of \(\partial f\). Then
Hence we obtain
Therefore,
We can then write \(y_n\) in Algorithm 3.3 as
We obtain the following weak and strong convergence results for problem (35).
Theorem 4.1
Let E be a real 2-uniformly convex Banach space which is also uniformly smooth and the solution set S of problem (35) be nonempty. Suppose \( \{ \lambda _n \}_{n=1}^\infty \) satisfies the condition \(0<a\le \lambda _n\le b<\displaystyle \frac{1}{\sqrt{2\mu }\kappa L}\). Assume that J is weakly sequentially continuous on E and let the sequence \( \{x_n\}_{n=1}^\infty \) be generated by
Then \(\{x_n\}\) converges weakly to \(z\in S\). Moreover, \(z:=\lim _{n\rightarrow \infty } \Pi _S(x_n)\).
Theorem 4.2
Let E be a real 2-uniformly convex Banach space which is also uniformly smooth and the solution set S of problem (35) be nonempty. Suppose \( \{ \lambda _n \}_{n=1}^\infty \) satisfies the condition \(0<a\le \lambda _n\le b<\displaystyle \frac{1}{\sqrt{2\mu }\kappa L}\). Suppose that \(\{\alpha _n\}\) is a real sequence in (0, 1) with \(\lim _{n \rightarrow \infty } \alpha _n = 0 \) and \( \sum _{n = 1}^{\infty } \alpha _n = \infty \). Let the sequence \( \{x_n\}_{n=1}^\infty \) be generated by
Then \(\{x_n\}\) converges strongly to \(z=\Pi _S(x_1)\).
Remark 4.3
-
Our result in Theorems 4.1 and 4.2 complement the results of Bredies [9, 19]. Consequently, our results in Sect. 3.1 extend the results of Bredies [9, 19] to inclusion problem (1). In particular, we do not assume boundedness of \(\{x_n\}\) (which was imposed on the results of [9, 19]) in our results. Therefore, our result improves on the results of [9, 19].
-
The minimization problem (35) in this section extends the problem studied in [8, 15, 34, 50] and other related papers from Hilbert spaces to Banach spaces.
5 Conclusion
We study the Tseng-type algorithm for finding a solution to monotone inclusion problem involving a sum of maximal monotone and a Lipschitz continuous monotone mapping in 2-uniformly convex Banach space which is also uniformly smooth. We prove both weak and strong convergence of sequences of iterates to the solution of the inclusion problem under some appropriate conditions. Many results on monotone inclusion problems with single maximal monotone operator can be considered as special cases of the problem studied in this paper. As far as we know, this is the first time an inclusion problem involving sum of maximal monotone and Lipschitz continuous monotone operators will be studied in Banach spaces. Therefore, the results of this paper open up many forthcoming results regarding the inclusion problem studied in this paper. Our next project involves the following.
The results in this paper exclude \(L_p\) spaces with \(p > 2\). Therefore, extension of the results in this paper to a more general reflexive Banach space will be desired.
How to effectively compute the duality mapping J and the resolvent of maximal monotone mapping B during implementations of our proposed algorithms will be considered further.
The numerical implementations of problem (1) arising from signal processing, image reconstruction, etc will be studied;
Other ways of implementation of the step-sizes \(\lambda _n\) to give faster convergence of the proposed methods in this paper will be given.
References
Alber, Y.I.: Metric and Generalized Projection Operators in Banach Spaces: Properties and Applications. Theory and Applications of Nonlinear Operators of Accretive and Monotone Type, pp. 15–50, Lecture Notes in Pure and Appl. Math., 178, Dekker, New York (1996)
Alber, Y., Ryazantseva, I.: Nonlinear ILL-Posed Problems of Monotone Type. Springer, Dordrecht (2006). xiv+410 pp. ISBN: 978-1-4020-4395-6; 1-4020-4395-3
Aoyama, K., Kohsaka, F.: Strongly relatively nonexpansive sequences generated by firmly nonexpansive-like mappings. Fixed Point Theory Appl. 2014, 95 (2014). 13 pp
Avetisyan, K., Djordjević, O., Pavlović, M.: Littlewood–Paley inequalities in uniformly convex and uniformly smooth Banach spaces. J. Math. Anal. Appl. 336(1), 31–43 (2007)
Ball, K., Carlen, E.A., Lieb, E.H.: Sharp uniform convexity and smoothness inequalities for trace norms. Invent. Math. 115(3), 463–482 (1994)
Barbu, V.: Nonlinear Semigroups and Differential Equations in Banach Spaces. Editura Academiei R.S.R, Bucharest (1976)
Beauzamy, B.: Introduction to Banach Spaces and Their Geometry, 2nd edn. North-Holland Mathematics Studies, 68. Notas de Matemática [Mathematical Notes], 86. North-Holland Publishing Co., Amsterdam (1985). xv+338 pp. ISBN: 0-444-87878-5
Beck, A., Teboulle, M.: A fast iterative shrinkage-thresholding algorithm for linear inverse problems. SIAM J. Imaging Sci. 2(1), 183–202 (2009)
Bredies, K.: A forward-backward splitting algorithm for the minimization of non-smooth convex functionals in Banach space. Inverse Probl. 25(1), 015005 (2009). 20 pp
Briceño-Arias, L.M.: Forward-partial inverse-forward splitting for solving monotone inclusions. J. Optim. Theory Appl. 166(2), 391–413 (2015)
Chen, G.H.-G., Rockafellar, R.T.: Convergence rates in forward-backward splitting. SIAM J. Optim. 7(2), 421–444 (1997)
Cho, S.Y., Qin, X., Wang, L.: Strong convergence of a splitting algorithm for treating monotone operators. Fixed Point Theory Appl. 2014, 94 (2014). 15 pp
Cioranescu, I.: Geometry of Banach Spaces, Duality Mappings and Nonlinear Problems. Mathematics and Its Applications, Vol. 62. Kluwer Academic Publishers Group, Dordrecht (1990). xiv+260 pp. ISBN: 0-7923-0910-3
Combettes, P.L., Nguyen, Q.V.: Solving composite monotone inclusions in reflexive Banach spaces by constructing best Bregman approximations from their Kuhn-Tucker set. J. Convex Anal. 23(2), 481–510 (2016)
Combettes, P., Wajs, V.R.: Signal recovery by proximal forward-backward splitting. Multiscale Model. Simul. 4(4), 1168–1200 (2005)
Diestel, J.: Geometry of Banach Spaces-Selected Topics. Lecture Notes in Mathematics, vol. 485. Springer, Berlin (1975)
Figiel, T.: On the moduli of convexity and smoothness. Studia Math. 56(2), 121–155 (1976)
Gibali, A., Thong, D.V.: Tseng type methods for solving inclusion problems and its applications. Calcolo 55(4), 55:49 (2018)
Guan, W.-B., Song, W.: The generalized forward-backward splitting method for the minimization of the sum of two functions in Banach spaces. Numer. Funct. Anal. Optim. 36(7), 867–886 (2015)
Güler, O.: On the convergence of the proximal point algorithm for convex minimization. SIAM J. Control Optim. 29, 403–419 (1991)
Iiduka, H., Takahashi, W.: Weak convergence of a projection algorithm for variational inequalities in a Banach space. J. Math. Anal. Appl. 339(1), 668–679 (2008)
Iusem, A.N., Svaiter, B.F.: Splitting methods for finding zeroes of sums of maximal monotone operators in Banach spaces. J. Nonlinear Convex Anal. 15(2), 379–397 (2014)
Jiao, H., Wang, F.: On an iterative method for finding a zero to the sum of two maximal monotone operators. J. Appl. Math. (2014), Art. ID 414031, 5 pp
Kamimura, S., Kohsaka, F., Takahashi, W.: Weak and strong convergence theorems for maximal monotone operators in a Banach space. Set-Valued Anal. 12, 417–429 (2004)
Kamimura, S., Takahashi, W.: Strong convergence of a proximal-type algorithm in a Banach space. SIAM J. Optim. 13 (2002)(3), 938–945 (2003)
Kohsaka, F., Takahashi, W.: Strong convergence of an iterative sequence for maximal monotone operators in a Banach space. Abstr. Appl. Anal. 3, 239–249 (2004)
Lions, P.L.: Une méthode itérative de résolution d’une inéquation variationnelle. Israel J. Math. 31, 204–208 (1978)
Lions, P.L., Mercier, B.: Splitting algorithms for the sum of two nonlinear operators. SIAM J. Numer. Anal. 16, 964–979 (1979)
Lin, L.-J., Takahashi, W.: A general iterative method for hierarchical variational inequality problems in Hilbert spaces and applications. Positivity 16(3), 429–453 (2012)
López, G., Martín-Márquez, V., Wang, F., Xu, H.-K.: Forward-backward splitting methods for accretive operators in Banach spaces. Abstr. Appl. Anal. (2012), Art. ID 109236, 25 pp
Maingé, P.-E.: Strong convergence of projected subgradient methods for nonsmooth and nonstrictly convex minimization. Set-Valued Anal. 16(7–8), 899–912 (2008)
Martinet, B.: Régularisation d’inéquations variationnelles par approximations successives. (French) Rev. Française Informat. Recherche Oérationnelle 4 (1970), Sér. R-3, 154–158
Moudafi, A., Thera, M.: Finding a zero of the sum of two maximal monotone operators. J. Optim. Theory Appl. 94, 425–448 (1997)
Nguyen, T.P., Pauwels, E., Richard, E., Suter, B.W.: Extragradient method in optimization: convergence and complexity. J. Optim. Theory Appl. 176(1), 137–162 (2018)
Passty, G.B.: Ergodic convergence to a zero of the sum of monotone operators in Hilbert spaces. J. Math. Anal. Appl. 72, 383–390 (1979)
Peaceman, D.H., Rachford, H.H.: The numerical solutions of parabolic and elliptic differential equations. J. Soc. Ind. Appl. Math. 3, 28–41 (1955)
Peypouquet, J.: Convex Optimization in Normed Spaces. Theory, Methods and Examples. With a foreword by Hedy Attouch. Springer Briefs in Optimization. Springer, Cham (2015). xiv+124 pp. ISBN: 978-3-319-13709-4; 978-3-319-13710-0
Reich, S.: A weak convergence theorem for the alternating method with Bregman distances. In: Kartsatos, A.G. (ed.) Theory and Applications of Nonlinear Operators of Accretive and Monotone Type. Lecture Notes Pure Appl. Math., vol. 178, pp. 313–318. Dekker, New York (1996)
Rockafellar, R.T.: Monotone operators and the proximal point algorithm. SIAM J. Control. Optim. 14, 877–898 (1976)
Rockafellar, R.T.: Characterization of the subdifferentials of convex functions. Pac. J. Math. 17, 497–510 (1966)
Rockafellar, R.T.: On the maximal monotonicity of subdifferential mappings. Pac. J. Math. 33, 209–216 (1970)
Shehu, Y., Cai, G.: Strong convergence result of forward-backward splitting methods for accretive operators in Banach spaces with applications. Rev. R. Acad. Cienc. Exactas Fís. Nat. Ser. A Math. RACSAM 112(1), 71–87 (2018)
Solodov, M.V., Svaiter, B.F.: Forcing strong convergence of proximal point iterations in a Hilbert space. Math. Program. 87, 189–202 (2000)
Takahashi, S., Takahashi, W., Toyoda, M.: Strong convergence theorems for maximal monotone operators with nonlinear mappings in Hilbert spaces. J. Optim. Theory Appl. 147(1), 27–41 (2010)
Takahashi, W., Wong, N.-C., Yao, J.-C.: Two generalized strong convergence theorems of Halpern’s type in Hilbert spaces and applications. Taiwanese J. Math. 16(3), 1151–1172 (2012)
Takahashi, W.: Strong convergence theorems for maximal and inverse-strongly monotone mappings in Hilbert spaces and applications. J. Optim. Theory Appl. 157(3), 781–802 (2013)
Takahashi, W.: Nonlinear Functional Analysis. Yokohama Publishers, Yokohama (2000)
Tseng, P.: A modified forward-backward splitting method for maximal monotone mappings. SIAM J. Control Optim. 38(2), 431–446 (2000)
Wang, Y., Wang, F.: Strong convergence of the forward-backward splitting method with multiple parameters in Hilbert spaces. Optimization 67(4), 493–505 (2018)
Wang, Y., Xu, H.-K.: Strong convergence for the proximal-gradient method. J. Nonlinear Convex Anal. 15(3), 581–593 (2014)
Xu, H.K.: Inequalities in Banach spaces with applications. Nonlinear Anal. 16(12), 1127–1138 (1991)
Xu, H.K.: Iterative algorithms for nonlinear operators. J. Lond. Math. Soc. (2) 66(1), 240–256 (2002)
Acknowledgements
Open access funding provided by Institute of Science and Technology (IST Austria).
Author information
Authors and Affiliations
Corresponding author
Additional information
Publisher's Note
Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.
The research of this author is supported by the Postdoctoral Fellowship from Institute of Science and Technology (IST), Austria.
Rights and permissions
Open Access This article is distributed under the terms of the Creative Commons Attribution 4.0 International License (http://creativecommons.org/licenses/by/4.0/), which permits unrestricted use, distribution, and reproduction in any medium, provided you give appropriate credit to the original author(s) and the source, provide a link to the Creative Commons license, and indicate if changes were made.
About this article
Cite this article
Shehu, Y. Convergence Results of Forward-Backward Algorithms for Sum of Monotone Operators in Banach Spaces. Results Math 74, 138 (2019). https://doi.org/10.1007/s00025-019-1061-4
Received:
Accepted:
Published:
DOI: https://doi.org/10.1007/s00025-019-1061-4
Keywords
- Inclusion problem
- 2-uniformly convex Banach space
- forward-backward algorithm
- weak convergence
- strong convergence