In this paper, we consider the relaxed gradient projection algorithm to solve the split equality problem in Hilbert spaces, and we investigate its linear convergence. In particular, we use the concept of the bounded linear regularity property for the split equality problem to prove the linear convergence property for the above algorithm. Furthermore, we conclude the linear convergence rate of the relaxed gradient projection algorithm. Finally, some numerical experiments are given to test the validity of our results.
Notes
Publisher’s Note
Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.
1 Introduction
Let C and Q be nonempty closed convex subsets of real Hilbert spaces \(H_{1}\) and \(H_{2}\), respectively, and let \(A:H_{1}\rightarrow H_{3}\) and \(B:H_{2}\rightarrow H_{3}\) be two bounded linear operators, \(H_{3}\) is also a real Hilbert spaces. The split equality problem (SEP for short), as an important extension of the split feasibility problem, was first presented by Moudafi [1]. It can be mathematically characterized by finding points \(x\in C\) and \(y\in Q\) that satisfy the property
$$ Ax=By, $$
(1.1)
which allows for asymmetric and partial relations between the variables x and y.
The split equality problem has received plenty attention due to its extraordinary practicality and wide applicability in many fields of applied mathematics; examples of such problems include decomposition methods for partial differential equations, applications in game theory and intensity-modulated radiation therapy (IMRT for short), for which comprehensive references are available [2, 3]. In fact, various algorithms have been used in studies extensively to find a solution to the split equality problem. One of the most original and important algorithms is the alternating CQ algorithm (ACQA for short), which was proposed by Moudafi [1], and it has the following iterative form:
Then one proved the weak convergence of ACQA (1.2) provided that the solution set of SEP (1.1) is nonempty.
Advertisement
Since the ACQ algorithm involves two projections \(P_{C}\) and \(P_{Q}\), it might be difficult to calculate in the case where one of them does not have a closed-form expression. To solve this problem, Moudafi [4] proposed the relaxed alternating CQ algorithm (RACQA for short) by using orthogonal projections onto half-spaces to replace the original closed convex sets, and it has the following iterative form:
Meanwhile, one proved that the above algorithm can converge weakly to a solution of SEP (1.1).
In the RACQA, the step size parameters do not vary. Then, as a quite important generalization of the RACQA, Moudafi [5] presented the relaxed simultaneous iterative algorithm (RSSEA for short), whose parameters are allowed to vary, and obtained a weak convergence result:
The above basic methods for solving the split equality problem are well known. For more information with regard to methods solving the split equality problem, see [7‐9]. However, the convergence results of the above algorithms are not good enough and the convergence rate of these algorithms have not been explicitly estimated.
Advertisement
Recently, Shi et al. [10] presented the varying step size gradient projection algorithm for solving the SEP and obtained a linear convergence result. In particular, they conclude the linear convergent rate of the varying step size gradient projection algorithm. However, this algorithm is not easy to implement.
Let \(S=C\times Q\subseteq H_{1}\times H_{2}=:H\), \(G=[A,-B]:H\rightarrow H_{3}\), and the adjoint operator of G is denoted by \(G^{*}\). Then the problem (1.1) can be reformulated as to find \(w=(x,y)\in S\) which satisfies \(Gw=0\). And then the relaxed simultaneous iterative algorithm (RSSEA) reduces to the following relaxed gradient projection algorithm (in short, RGPA):
Recall that the RGPA is an easily implementable algorithm that uses orthogonal projection onto half-spaces at each step. In this paper, what attracts us is to study RGPA for solving the split equality problem. In particular, to the best of our knowledge, in order to get the linear convergence property for the CQ algorithm which is to solve the split feasibility problem, Wang et al. [11] presented the linear regularity property for the split feasibility problem. Motivated and inspired by their work, we devote our work to proving the linear convergence property for the RGPA with the bounded linear regularity property for SEP (1.1). For this purpose, we introduce the notion of the bounded linear regularity property for SEP (1.1), and use some suitable types of step sizes to prove the linear convergence property for the RGPA. In addition, we conclude the linear convergence rate of RGPA. Finally, some numerical experiments are given to test the validity of our results.
2 Preliminaries
For convenience, we introducing several notations. Throughout the whole paper, we assume that H is a real Hilbert space whose inner product and norm are denoted by \(\langle\cdot,\cdot\rangle\) and \(\| \cdot\|\), respectively. I denotes the identity operator on H. Let S be a nonempty subset of H, the relative interior of S is denoted by riS. \(T^{*}\) is the adjoint operators of T. We denote by B and \(\overline{\mathbf{B}}\) the unit open ball and the unit closed ball with center at the origin, respectively, that is,
$$\mathbf{B}:=\bigl\{ v\in{H}: \Vert v \Vert < 1\bigr\} \quad \mbox{and} \quad \overline{\mathbf {B}}:=\bigl\{ v\in{H}: \Vert v \Vert \leq1\bigr\} . $$
There are several definitions and basic results that will be used in the proofs of our main results.
$$\Vert Tx-Ty \Vert ^{2}\leq\langle x-y,Tx-Ty\rangle,\quad \forall x,y\in H. $$
For an element \(w\in{H}\) and a set \(S\subset H\), the distance of w onto S and the orthogonal projection from w onto S, denoted by \(d_{S}(w)\) and \(P_{S}(w)\), respectively, are defined by
By the Cauchy–Schwarz inequality, we can easily see that a firmly non-expansive mapping is non-expansive. From Proposition 2.2, it can be deduced that \(P_{S}\) is firmly non-expansive and non-expansive.
Let \(G: H\rightarrow H_{3}\) be a bounded linear operator. The kernel of G is denoted \(\ker G=\{y\in{H}:Gy=0\}\), and the orthogonal complement of kerG is denoted \((\ker G)^{\bot}=\{x\in{H}:\langle y,x\rangle =0, \forall y\in{\ker G}\}\). As is well known, both kerG and \((\ker G)^{\bot}\) are closed subspaces of H. Throughout this paper, we use Γ to denote the solution set of SEP (1.1), that is,
We assume that the SEP is consistent, thus, Γ is a closed, convex, and nonempty set.
Recall that a sequence \(\{w_{k}\}\) in H is called linearly convergent to its limit \(w^{*}\) (with rate \(\alpha\in{[0, 1)})\), if there exist \(\beta>0\) and a positive integer N such that
$$\bigl\Vert w_{k}-w^{*} \bigr\Vert \leq\beta \alpha^{k}\quad \mbox{for all }k\geq N. $$
To investigate the linear convergence property of the projection algorithm for solving convex feasibility problems, Zhao et al. [13] presented the linear regularity for a family of closed convex subsets in a real Hilbert space, as defined below.
Let \(\{S_{i}\}_{i\in{I}}\) be a family of closed convex subsets of a real Hilbert space H and \(S=\bigcap_{i\in{I}}S_{i}\neq\emptyset\). The family \(\{S_{i}\}_{i\in{I}}\) is called bounded linearly regular if, for each \(a>0\), there exists a constant \(\gamma_{a}>0\) such that
$$d_{S}(w)\leq\gamma_{a}\sup\bigl\{ d_{S_{i}}(w):i \in{I}\bigr\} \quad \mbox{for all }w\in{a\mathbf{B}}. $$
Bauschke [14] proved the following lemma for the case H is the Euclidean space. It provides sufficient conditions for the bounded linear regularity property for two closed convex subsets of H.
Shi et al. [10] construct some moderate sufficient conditions to ensure the bounded linear regularity property for SEP (1.1). This is shown in the lemma below.
Let\(\{x_{i}\}_{i\in{I}}\)be a finite family inH, and\(\{\lambda _{i}\}_{i\in{I}}\)be a finite family inRwith\(\sum_{i\in {I}}\lambda_{i}=1\), then the following equality holds:
In this section, we mainly use the bounded linear regularity property for SEP (1.1) to prove the linear convergence of the relaxed gradient projection algorithm when using different types of step sizes.
We start by reviewing the relaxed gradient projection algorithm in detail. Note that Moudafi [5] presented the relaxed simultaneous iterative algorithm (RSSEA) for solving the approximate SEP and established its weak convergence:
where \(c:H_{1}\rightarrow{R}\) and \(q:H_{2}\rightarrow{R}\) are convex, sub-differentiable functions, and where the sub-differentials are bounded on bounded sets. Applying the definition of sub-differential, one finds that \(C\subseteq C_{k}\) and \(Q\subseteq Q_{k}\), where C and Q are two nonempty closed convex level sets:
$$C=\bigl\{ x\in{H_{1}}:c(x)\leq0\bigr\} , $$
and
$$Q=\bigl\{ y\in{H_{2}}:q(y)\leq0\bigr\} . $$
For convenience, we define \(h:H_{1}\times H_{2}\) to be
Moreover, let \(S=C\times Q\subseteq H=H_{1}\times H_{2}\). \(G=[A,-B]:H\rightarrow H_{3}\). The adjoint operator of G is denoted by \(G^{*}\). Then G and \(G^{*}G\) have the following matrix form:
On that basis, the original problem (1.1) can be modified as
$$ \mbox{to find }w=(x,y)\in S\mbox{ such that }Gw=0 . $$
(3.2)
And then the algorithm (3.1) reduces to the following relaxed gradient projection algorithm (in short, RGPA):
The lemma below will be a powerful tool in our proof later.
Lemma 3.1
Assume that a vector\(x^{k}\)in\(S_{k}\)minimizes the function\(f(t)=\frac{1}{2}\|Gt\|^{2} \)over alltin\(S_{k}\). Then\(x^{k}=P_{S_{k}}(x^{k}-\gamma_{k}\nabla f(x^{k}))\)with\(\gamma_{k}\in (0,+\infty)\).
Proof
Since a vector \(x^{k}\) in \(S_{k}\) minimizes the function \(f(t)=\frac {1}{2}\|Gt\|^{2}\) over all t in \(S_{k}\) we have \(\langle\nabla f(x^{k}), t-x^{k}\rangle\geq0\), where \(\nabla f(x^{k})=G^{*}Gx^{k}\). This is equivalent to \(\langle x^{k}-(x^{k}-\gamma_{k}\nabla f(x^{k})), t-x^{k}\rangle\geq0\) from which we infer that \(x^{k}=P_{S_{k}}(x^{k}-\gamma_{k}\nabla f(x^{k}))\). The proof is complete. □
Now we give the main theorem and proof of this paper.
Theorem 3.2
Assume that SEP (3.2) satisfies the bounded linear regularity property. Then the sequence\(\{w_{k}\}\)generated by RGPA (3.3) with\(\gamma _{k}\in(0,+\infty)\)converges to a solution\(w^{*}\)of SEP (1.1) such that
Consequently, \(\{w_{k}\}\)converges to\(w^{*}\)linearly in the case when (a) or (b) is supposed.
Proof
Without loss of generality, we assume that \(w_{k}\) is not in Γ for all \(k\geq1\). Otherwise, RGPA (3.3) terminates in finite number of iterates, and then the conclusions follow clearly.
Firstly, we will show that the sequence \(\{w_{k}\}\) is Fejér monotone with respect to Γ and the sequence \({\|Gw_{k}\|^{2}}\) converges to zero.
Let \(z\in\varGamma\), then \(Gz=0\), that is, z minimizes \(f(t)=\frac {1}{2}\|Gt\|^{2}\) over \(t\in S_{k}\), for all k. From Lemma 3.1,
for any \(k\geq M\), if (a), (b), (c) are assumed. Substituting (3.8) in (3.7), we see that \({\|w_{k}-z\|}_{k\geq M}\) is monotone decreasing. From Definition 2.11, we infer that the sequence \(\{w_{k}\}\) is Fejér monotone with respect to Γ. Hence \(\lim_{k\rightarrow \infty}\|w_{k}-z\|\) exists and the sequence \({\|Gw_{k}\|^{2}}\) converges to zero.
Then we show that the sequence \(\{\|w_{k}-w_{k+1}\|\}\) converges to zero.
In view of the property of the orthogonal projection, we infer
Since the sequence \(\{\|w_{k}-z\|\}\) is bounded, the right hand side converges to zero. Therefore, the sequence \(\{\|w_{k}-w_{k+1}\|\}\) converges to zero.
Next, we show that \(\{w_{k}\}\) converges to a solution \(w^{*}\) of SEP and (3.4) holds. Because \(w_{k+1}\in S_{k}\), we get
Then there exists \(L\in\mathbf{N}\), when \(k\geq L\), and by virtue of the sequence \(\{\|w_{k}-w_{k+1}\|\}\) converging to zero, it follows that \(h(w_{k})\leq0\). Consequently, \(w_{k}\in S \) for any \(k\geq L\).
Since the SEP satisfies the bounded linear regularity property and \(w_{k}\in S\) for all \(k\geq L\), there exists \(\beta>0\) such that
By virtue of \(\sum^{\infty}_{k=1}\gamma_{k}=\infty\), \(\{w_{k}\}\) is a Cauchy sequence and converges to a solution \(w^{\ast}\) of SEP (1.1) satisfying
$$\bigl\Vert w_{k+1}-w^{\ast} \bigr\Vert \leq2d_{\varGamma}(w_{N})p^{\sum^{k}_{i=N+1}\gamma _{i}}, \quad\mbox{for all }k\geq N. $$
Moreover, if (a) or (b) is assumed, then \(\lim_{k\rightarrow\infty }\inf\gamma_{k}>0\). One can derive that \(\{w_{k}\}\) converges to \(w^{\ast}\) linearly. This completes the proof. □
As a direct consequence of Lemma 2.7 and Theorem 3.2, we propose the following corollary.
Corollary 3.3
Assume that one of statements (a)–(e) of Lemma 2.7holds. Then the sequence\(\{w_{k}\}\)generated by RGPA (3.3) with\(\gamma_{k}\in (0,+\infty)\)converges to a solution\(w^{*}\)of SEP (3.2) satisfying (3.4), provided that one of the conditions in (3.5) is assumed. In particular, \(\{w_{k}\}\)converges to\(w^{*}\)linearly in the case when (a) or (b) in (3.5) is assumed.
4 Numerical experiments
In this section, we give an example to verify the validity of our results. All codes were written in Wolfram Mathematica (version 10.3). All the numerical procedures were performed on a personal Asus computer with AMD A9-9420 RADEON R5, 5 COMPUTE. CORES 2C+3G 3.00 GHz and RAM 8.00 GB.
Let \(H_{1}=R\), \(H_{2}=R^{2}\) and \(H_{3}=R^{3}\). We have the SEP with \(C=C_{k}=\{x\in{H_{2}}:\|x\|\leq20\}\), \(Q=Q_{k}=\{x\in{H_{1}}:\|X\| \leq10\}\), and \(A:H_{2}\rightarrow H_{3}\), \(B:H_{1}\rightarrow H_{3}\) are defined by
$$A(x,y)=(x,y,0)\quad\mbox{and}\quad B(z)=(0,z,0), \quad\mbox{for all }x,y,z\in R, $$
respectively. Let \(S=C\times Q \subseteq R^{3}\). Define an operator \(G=[A,-B]:S\rightarrow H_{3}\) by
$$G(x,y,z)=(x,y-z,0), \mbox{for all }(x,y,z)\in S. $$
Then \(\operatorname{ker} G\cap \operatorname{ri} S =\{(0,z,z),z\in Q\}\neq\emptyset\), S is finite codimensional, G has closed range, and the solution set of the SEP is \(\varGamma=(C\times Q )\cap \operatorname{ker} G=\{(0,z,z):z\in Q\}\). By Lemma 2.7 it is easy to show that the SEP satisfies the bounded linear regularity property.
In algorithm (3.3), we take \(\gamma_{n}=\frac{1}{2}, \frac{n}{n+1}\), respectively. Moreover, we select the error value to be 10−10, 10−20, and initial value \(w_{0}=(3,2,8)\). Then we get the numerical results displayed in Figs. 1 and 2.
×
×
Acknowledgements
The authors would like to express their sincere thanks to the editors and reviewers for their noteworthy comments, suggestions, and ideas, which helped to improve this paper.
Availability of data and materials
All data generated or analysed during this study are included in this published article.
Competing interests
The authors declare that they have no competing interests.
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.
Publisher’s Note
Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.