Weak convergence theorems of the modified relaxed projection algorithms for the split feasibility problem in Hilbert spaces

Abstract

In this paper, we introduce a modified relaxed projection algorithm and a modified variable-step relaxed projection algorithm for the split feasibility problem in infinite-dimensional Hilbert spaces. The weak convergence theorems under suitable conditions are proved. Finally, some numerical results are presented, which show the advantage of the proposed algorithms.

1 Introduction

Let $C$ and $Q$ be the nonempty closed convex subsets of the real Hilbert spaces $\mathcal H _1$ and $\mathcal H _2$, respectively. The split feasibility problem (SFP) is formulated as finding a point $x^*$ with the property

$$\begin{aligned} x^*\in C\quad \text{ and}\quad Ax^*\in Q, \end{aligned}$$

(1)

where $A :\mathcal{H }_1\rightarrow \mathcal{H }_2$ is a bounded linear operator. The SFP in finite-dimensional Hilbert spaces was first introduced by Censor and Elfving [1] for modeling inverse problems which arise from phase retrievals and in medical image reconstruction [2]. Many researchers studied the SFP and introduced various algorithms to solve it (see [2–12] and references therein).

For the split feasibility problem in the finite-dimensional real Hilbert spaces, Byrne [2, 3] presented the so-called CQ algorithm for solving the SFP, that does not involve matrix inverses. Take an initial guess $x_0\in \mathcal{H }_1$ arbitrarily, and define $\{x_n\}$ recursively as

$$\begin{aligned} x_{n+1}=P_C(I-\gamma A^*(I-P_Q)A)x_n, \end{aligned}$$

(2)

where $0 < \gamma < 2/L$, and where $P_C$ denotes the metric projection onto $C$ and $L$ is the spectral radius of the operator $A^*A$. Then the sequence $\{x_n\}$ generated by (2) converges strongly to a solution of SFP whenever $\mathcal{H }_1$ is finite-dimensional and whenever there exists a solution to SFP (1). In the CQ algorithm, Byrne assumed that the projections $P_C$ and $P_Q$ are easily calculated. However, in some cases it is impossible or needs too much work to exactly compute the metric projection. Yang [13] presented a relaxed CQ algorithm, in which $P_C$ and $P_Q$ are replaced by $P_{C_n}$ and $P_{Q_n}$, which are the metric projections onto two halfspaces $C_n$ and $Q_n$, respectively. Clearly, Yang’s algorithm is easy to implement.

Recently, based on work of Yang [13] and Qu and Xiu [14], Wang et al. [15] presented two relaxed inexact projection methods and a variable-step relaxed inexact projection method. The second relaxed inexact projection methods (Algorithm 3.2 in [15]) is to find $x_{n+1}$ satisfying

$$\begin{aligned} \Vert x_{n+1}-P_{C_n}(I-\gamma A^*(I-P_{Q_n})A)x_n\Vert \le \epsilon _n\Vert (I-P_{Q_n})Ax_n\Vert ,\,n=0,1,\ldots . \end{aligned}$$

(3)

So $x_{n+1}$ is in the ball $B(s,r)$ with $s=P_{C_n}(x_n-\gamma A^*(I-P_{Q_n})Ax_n)$ and $r =\epsilon _n\Vert (I-P_{Q_n})Ax_n\Vert$. In the proofs of the convergence theorems, Wang et al. [15] used the fact that, from (3) and $\lim _{n\rightarrow \infty }\Vert (I-P_{Q_n})Ax_n\Vert =0$, it follows that for sufficiently large $n,\,x_{n+1}$ is the projection of $x_{n}$ in $C_n$. However, it is obvious that $x_{n+1}$ may not in $C_n$ if $P_{C_n}(x_n-\gamma A^*(I-P_{Q_n})Ax_n)\in \partial C_n,$ since $C_n$ is a half-space. To overcome the gap, we modify the algorithms of [13] and [14] and proposed a relaxed projection algorithm as follows

$$\begin{aligned} x_{n+1}=\alpha _nP_{C_n}x_n+(1-\alpha _n)P_{C_n}(I-\gamma A^*(I-P_{Q_n})A)x_n, \end{aligned}$$

(4)

and a variable-step relaxed projection algorithm in infinite-dimensional real Hilbert space. From the following remark, it is easy to see that the algorithm (4) is the special case of (3) proposed by Wang et al. [15].

Remark 1.1

It follows, from (4),

$$\begin{aligned} \Vert x_{n+1}\!-\!P_{C_n}(I\!-\!\gamma A^*(I\!-\!P_{Q_n})A)x_n\Vert&\!=\!\alpha _n\Vert P_{C_n}x_n\!-\!P_{C_n}(x_n\!-\!\gamma A^* (I\!-\!P_{Q_n})Ax_n)\Vert \\&\!\le \alpha _n\Vert \gamma A^*(I\!-\!P_{Q_n})Ax_n\Vert \\&\!\le \alpha _n\gamma \sqrt{L}\Vert (I\!-\!P_{Q_n})Ax_n\Vert . \end{aligned}$$

Let $\epsilon _n=\alpha _n\gamma \sqrt{L}$ and then (3) is derived.

This paper is organized as follows. In Sect. 2, we review some concepts and existing results. In Sect. 3, we present a modified relaxed projection methods for the SFP and establish the convergence of the algorithm. A modified variable-step relaxed inexact projection algorithm is presented in Sect. 4. In Sect.  5, we report some computational results with the proposed algorithms.

2 Preliminaries

In this section, we review some definitions and lemmas which will be used in this paper.

Definition 2.1

Let $F$ be a mapping from a set $\Omega \subset \mathcal{H }$ into $\mathcal{H }$. Then

• $F$ is said to be monotone on $\Omega$, if

  $$\begin{aligned} \langle F(x)-F(y),x-y\rangle \ge 0,\quad \forall x,y\in \Omega ; \end{aligned}$$

• $F$ is said to be $\alpha$-inverse strongly monotone ($\alpha$-ism), with $\alpha >0$, if

  $$\begin{aligned} \langle F(x)-F(y),x-y\rangle \ge \alpha \Vert F(x)-F(y)\Vert ^2,\quad \forall x,y\in \Omega ; \end{aligned}$$

• $F$ is said to be Lipschitz continuous on $\Omega$ with constant $\lambda > 0$, if

  $$\begin{aligned} \Vert F(x)-F(y)\Vert \le \lambda \Vert x-y\Vert ,\quad \forall x,y\in \Omega . \end{aligned}$$

The projection is an important tool for our work in this paper. Let ${\Omega }$ be a closed convex subset of real Hilbert space $\mathcal{H }$. Recall that the (nearest point or metric) projection from $H$ onto $\Omega$, denoted $P_{\Omega }$, is defined in such a way that, for each $x\in \mathcal{H },\,P_{\Omega }x$ is the unique point in $\Omega$ such that

$$\begin{aligned} \Vert x-P_{\Omega }x\Vert =\min \{\Vert x-z\Vert : z \in {\Omega }\} \end{aligned}$$

The following two lemmas are useful characterizations of projections.

Lemma 2.1

Given $x \in \mathcal{H }$ and $z \in \Omega$. Then $z = P_{\Omega }x$ if and only if

$$\begin{aligned} \langle x-z,y-z\rangle \le 0,\quad \text{ for} \text{ all} \quad y\in \Omega . \end{aligned}$$

Lemma 2.2

For any $x, y\in \mathcal{H }$ and $z \in \Omega$, it holds

• (i) $\Vert P_{\Omega }(x)-P_{\Omega }(y)\Vert ^2 \le \langle P_{\Omega }(x)-P_{\Omega }(y), x-y\rangle ;$

• (ii) $\Vert P_{\Omega }(x)-z\Vert ^2\le \Vert x-z\Vert ^2-\Vert P_{\Omega }(x)-x\Vert ^2$.

Remark 2.1

From Lemma 2.2 (i), we know that $P_{\Omega }$ is a monotone, 1-ism and nonexpansive (i.e., $\Vert P_{\Omega }(x)-P_{\Omega }(y)\Vert \le \Vert x-y\Vert$) operator. Moreover, it is easily verified that the operator $I- P_{\Omega }$ is also 1-ism, where $I$ denotes the identity operator, i.e., for all $x, y \in \mathcal{H }$:

$$\begin{aligned} \langle (I-P_{\Omega })x-(I-P_{\Omega })y,x-y\rangle \ge \Vert (I-P_{\Omega })x-(I-P_{\Omega })y\Vert ^2. \end{aligned}$$

(5)

Let $F$ denote a mapping on $\mathcal{H }$. For any $x \in \mathcal{H }$ and $\alpha > 0$, define:

$$\begin{aligned} x(\alpha )=P_{\Omega }(x-\alpha F(x)),\quad e(x,\alpha )=x-x(\alpha ). \end{aligned}$$

From the nondecreasing property of $\Vert e(x,\alpha )\Vert$ on $\alpha > 0$ by Toint [16] (see Lemma 2(1)) and the nonincreasing property of $\Vert e(x,\alpha )\Vert /\alpha$ on $\alpha > 0$ by Gafni and Bertsekas [17] (see Lemma 1a), we immediately conclude a useful lemma.

Lemma 2.3

Let $F$ be a mapping on $\mathcal{H }$. For any $x \in \mathcal{H }$ and $\alpha > 0$, we have:

$$\begin{aligned} \min \{1,\alpha \}\Vert e(x,1)\Vert \le \Vert e(x,\alpha )\Vert \le \max \{1,\alpha \}\Vert e(x,1)\Vert . \end{aligned}$$

For the SFP, we firstly assume that the following conditions are satisfied:

• (1) The solution set of the SFP denoted by $\Gamma :=\{x\in C: Ax\in Q\}$ is nonempty.

• (2) The set $C$ is given by

  $$\begin{aligned} C =\{x\in \mathcal{H }_1 : c(x) \le 0\}, \end{aligned}$$

  where $c :\mathcal{H }_1\rightarrow \mathbb R$ is a convex function, and $C$ is nonempty. The set $Q$ is given by

  $$\begin{aligned} Q=\{y\in \mathcal{H }_2 : q(y) \le 0\}, \end{aligned}$$

  where $q :\mathcal{H }_2\rightarrow \mathbb{R }$ is a convex function, and $Q$ is nonempty.

• (3) $c$ and $q$ are subdifferentiable on $C$ and $Q$. (Note that the convex function is subdifferentiable everywhere in $\mathbb R ^N$.) For any $x\in \mathcal{H }_1$, at least one subgradient $\xi \in \partial c(x)$ can be calculated, where $\partial c(x)$ is defined as follows:

  $$\begin{aligned} \partial c(x)=\{z\in \mathcal{H }_1:c(u)\ge c(x)+ \langle u-x,z\rangle ,\quad \text{ for} \text{ all}\,\,u\in \mathcal{H }_1\}. \end{aligned}$$

  For any $y\in \mathcal{H }_2$, at least one subgradient $\eta \in \partial q(y)$ can be calculated, where

  $$\begin{aligned} \partial q(y)=\{w\in \mathcal{H }_2:q(v)\ge q(y)+ \langle v-y,w\rangle ,\quad \text{ for} \text{ all}\,\, v\in \mathcal{H }_2\}. \end{aligned}$$

• (4) $c$ and $q$ are bounded on bounded sets. (Note that this condition is automatically satisfied if $\mathcal{H }_1$ and $\mathcal{H }_2$ are finite dimensional.)

From Banach-Steinhaus Theorem (see Theorem 2.5 in [18]), it is easy to get the following result.

Remark 2.2

Assumption (4) guarantees that if $\{x_n\}$ is a bounded sequence in $\mathcal{H }_1$ (resp. $\mathcal{H }_2$) and $\{x_n^*\}$ is a sequence in $\mathcal{H }_1$ (resp. $\mathcal{H }_2$) such that $x_n^*\in \partial c(x_n)$ (resp. $x_n^*\in \partial q(x_n)$) for each $n$, then $\{x_n^*\}$ is bounded.

Lemma 2.4

[19] Let $\{a_n\}$ be a sequence of nonnegative number such that

$$\begin{aligned} a_{n+1}\le (1+\lambda _n)a_n , \end{aligned}$$

where $\{\lambda _n\}$ satisfies $\sum _{n=1}^{\infty }\lambda _n<+\infty$. Then $\lim _{n\rightarrow \infty }a_n$ exists.

Lemma 2.5

[20] Let $K$ be a nonempty closed convex subset of a Hilbert space $\mathcal{H }$. Let $\{x_n\}$ be a bounded sequence which satisfies the following properties:

• every weak limit point of $\{x_n\}$ lies in $K$;

• $\lim _{n\rightarrow \infty }\Vert x_n-x\Vert$ exists for every $x \in K$.

Then $\{x_n\}$ converges weakly to a point in $K$.

3 A modified relaxed projection algorithm

In this section we propose a modified relaxed algorithm and prove the weak convergence of the proposed algorithm.

Algorithm 3.1

Let $x_0$ be arbitrary. Let $\{\alpha _n\}\subset (0,\infty )$, and

$$\begin{aligned} x_{n+1}=\alpha _nP_{C_n}x_n+(1-\alpha _n)P_{C_n}(I-\gamma A^*(I-P_{Q_n})A)x_n, \end{aligned}$$

(6)

where $\gamma \in (0, M),$ $M:=\min \{2/\Vert A\Vert ^2,{\sqrt{2}}/{\Vert A\Vert }\}$, and $\{C_n\}$ and $\{Q_n\}$ are the sequences of closed convex sets constructed as follows:

$$\begin{aligned} C_n=\left\{ x\in \mathcal{H }_1:c(x_n)+\langle \xi _n,x-x_n\rangle \le 0 \right\} \!, \end{aligned}$$

where $\xi _n\in \partial c(x_n)$, and

$$\begin{aligned} Q_n=\left\{ y\in \mathcal{H }_2:q(Ax_n)+\langle \eta _n,y-Ax_n\rangle \le 0 \right\} \!, \end{aligned}$$

where $\eta _n\in \partial q(Ax_n)$.

Remark 3.1

By the definition of subdifferentials, it is clear that $C \subset C_n$ and $Q \subset Q_n$. Also note that $C_n$ and $Q_n$ are half-space, thus, the projections $P_{C_n}$ and $P_{Q_n}$ have closed-form expression.

Theorem 3.1

Let $\{x_n\}$ be the sequence generated by the Algorithm 3.1 Let $\{\alpha _n\}\subset (0,\infty )$ satisfy

$$\begin{aligned} \sum ^\infty _{n=0}\alpha _n^2<+\infty . \end{aligned}$$

Then $\{x_n\}$ converges weakly to a solution of SFP(1).

Proof

Set $\sigma =\gamma ^2\Vert A\Vert ^2-2\gamma ,$ then $\sigma <0.$ Let $\delta _n=\sqrt{-\frac{2}{\sigma }}\alpha _n.$ From (6), we have

$$\begin{aligned}&\Vert x_{n+1}-P_{C_n}(I-\gamma A^*(I-P_{Q_n})A)x_n\Vert \nonumber \\&\quad =\alpha _n\Vert P_{C_n}x_n-P_{C_n}(x_n-\gamma A^*(I-P_{Q_n})Ax_n)\Vert \nonumber \\&\quad \le \alpha _n\Vert \gamma A^*(I-P_{Q_n})Ax_n\Vert \nonumber \\&\quad \le \alpha _n\gamma \Vert A\Vert \Vert (I-P_{Q_n})Ax_n\Vert . \end{aligned}$$

(7)

Take arbitrarily $x^*\in \Gamma$, then we have

$$\begin{aligned}&\Vert x_{n+1}-x^*\Vert ^2=\Vert x_{n+1}-P_C(I-\gamma A^*(I-P_{Q_n})A)x_n\Vert ^2\nonumber \\&\quad +\, \Vert P_C(I-\gamma A^*(I-P_{Q_n})A)x_n-x^*\Vert ^2\nonumber \\&\quad +\,2\langle x_{n+1}-P_C(I-\gamma A^*(I-P_{Q_n})A)x_n, P_C(I-\gamma A^*(I-P_{Q_n})A)x_n-x^* \rangle .\nonumber \\ \end{aligned}$$

(8)

From Cauchy-Schwarz inequality and arithmetic and geometric means inequality, it is follows

$$\begin{aligned}&2\langle x_{n+1}-P_C(I-\gamma A^*(I-P_{Q_n})A)x_n, P_C(I-\gamma A^*(I-P_{Q_n})A)x_n-x^* \rangle \nonumber \\&\quad \le \frac{1}{\delta _n^2}\Vert x_{n+1}-P_C(I-\gamma A^*(I-P_{Q_n})A)x_n\Vert ^2\nonumber \\&\quad +\delta _n^2\Vert P_C(I-\gamma A^*(I-P_{Q_n})A)x_n-x^*\Vert ^2. \end{aligned}$$

(9)

Substituting (9) into (8), we obtain

$$\begin{aligned}&\Vert x_{n+1}-x^*\Vert ^2\le (1+\delta _n^2) \Vert P_{C_n}(I-\gamma A^*(I-P_{Q_n})A)x_n-x^*\Vert ^2\nonumber \\&\quad +\left(1+\frac{1}{\delta _n^2}\right) \Vert x_{n+1}-P_{C_n}(I-\gamma A^*(I-P_{Q_n})A)x_n\Vert ^2. \end{aligned}$$

(10)

Since $x^*\in {C_n}$, we have

$$\begin{aligned}&\Vert P_{C_n}(I-\gamma A^*(I-P_{Q_n})A)x_n-x^*\Vert ^2 \le \Vert (x_n-x^*)-\gamma A^*(I-P_{Q_n})Ax_n\Vert ^2\nonumber \\&\quad = \Vert x_n-x^*\Vert ^2+\gamma ^2\Vert A^*(I-P_{Q_n})Ax_n\Vert ^2-2 \gamma \langle x_n-x^*,A^*(I-P_{Q_n})Ax_n\rangle \nonumber \\&\quad \le \Vert x_n-x^*\Vert ^2+\gamma ^2\Vert A\Vert ^2\Vert (I-P_{Q_n})Ax_n\Vert ^2-2 \gamma \langle Ax_n-Ax^*,Ax_n-P_{Q_n}Ax_n\rangle .\nonumber \\ \end{aligned}$$

(11)

It is easily seen that

$$\begin{aligned}&\langle Ax_n-Ax^*,Ax_n-P_{Q_n}Ax_n\rangle \nonumber \\&\quad =\Vert (I-P_{Q_n})Ax_n\Vert ^2+ \langle P_{Q_n}Ax_n-Ax^*,Ax_n-P_{Q_n}Ax_n\rangle . \end{aligned}$$

(12)

Since $Ax^*\in Q\subset Q_n$, by Lemma 2.1, we get

$$\begin{aligned} \langle P_{Q_n}Ax_n-Ax^*,Ax_n-P_{Q_n}Ax_n\rangle \ge 0. \end{aligned}$$

(13)

Combining (11)–(13), we have

$$\begin{aligned}&\Vert P_{C_n}(I-\gamma A^*(I-P_{Q_n})A)x_n-x^*\Vert ^2\nonumber \\&\quad \le \Vert x_n-x^*\Vert ^2+(\gamma ^2\Vert A\Vert ^2-2\gamma )\Vert (I-P_{Q_n})Ax_n\Vert ^2\nonumber \\&\quad =\Vert x_n-x^*\Vert ^2+\sigma \Vert (I-P_{Q_n})Ax_n\Vert ^2 \end{aligned}$$

(14)

Applying (7), (10) and (14), we obtain

$$\begin{aligned}&\Vert x_{n+1}-x^*\Vert ^2 \le (1+\delta _n^2) \Vert x_n-x^*\Vert ^2\nonumber \\&\quad +\left[\sigma (1+\delta _n^2)+\gamma ^2\Vert A\Vert ^2\alpha _n^2\left(1+\frac{1}{\delta _n^2}\right) \right]\Vert (I-P_{Q_n})Ax_n\Vert ^2\nonumber \\&\quad \le \left(1+\left(-\frac{2}{\sigma }\right)\alpha _n^2\right)\Vert x_n-x^*\Vert ^2\nonumber \\&\quad +\left(\gamma ^2\Vert A\Vert ^2-2\right)\left(\alpha _n^2-\frac{1}{2}\sigma \right)\Vert (I-P_{Q_n})Ax_n\Vert ^2, \end{aligned}$$

(15)

which with $\sigma <0$ and $\gamma \le \sqrt{2}/\Vert A\Vert$ implies

$$\begin{aligned} \Vert x_{n+1}-x^*\Vert ^2 \le \left(1+\left(-\frac{2}{\sigma }\right)\alpha _n^2\right)\Vert x_n-x^*\Vert ^2. \end{aligned}$$

(16)

So, using Lemma 2.4, we have $\lim _{n\rightarrow \infty }\Vert x_{n}-x^*\Vert$ exists, and hence $\{x_n\}$ is bounded. From (15), it follows that

$$\begin{aligned}&\sigma \left(\frac{\gamma ^2\Vert A\Vert ^2}{2}-1\right)\Vert (I-P_{Q_n})Ax_n\Vert ^2 \le \left(\Vert x_n-x^*\Vert ^2-\Vert x_{n+1}-x^*\Vert ^2\right)\nonumber \\&\qquad +\left(-\frac{2}{\sigma }\right)\alpha _n^2\Vert x_n-x^*\Vert ^2. \end{aligned}$$

Consequently we get by $\alpha _n\rightarrow 0$,

$$\begin{aligned} \lim _{n\rightarrow \infty }\Vert Ax_n-P_{Q_n}Ax_n\Vert =0. \end{aligned}$$

(17)

Set

$$\begin{aligned} u_n=A^*(I-P_{Q_n})Ax_n\rightarrow 0. \end{aligned}$$

(18)

We next demonstrate that

$$\begin{aligned} \Vert x_{n+1}-x_n\Vert \rightarrow 0. \end{aligned}$$

To see this, we note the identity

$$\begin{aligned} \Vert x_{n+1}-x_n\Vert ^2=\Vert x_n-x^*\Vert ^2-\Vert x_{n+1}-x^*\Vert ^2+ 2\langle x_{n+1}-x_n, x_{n+1}-x^*\rangle . \end{aligned}$$

(19)

On the other hand, using $x_{n+1} = \alpha _nP_{C_n}x_n+(1-\alpha _n)P_{C_n}(x_n-\gamma u_n)$, we have

$$\begin{aligned}&\langle x_{n+1}-x_n, x_{n+1}-x^*\rangle =\alpha _n \langle P_{C_n}x_n-x_n,x_{n+1}-x^*\rangle \nonumber \\&\quad +\alpha _n(1-\alpha _n) \langle P_{C_n}(x_n-\gamma u_n)-x_n, P_{C_n}x_n-x^*\rangle \nonumber \\&\quad + (1-\alpha _n)^2 \langle x_n-P_{C_n}(x_n-\gamma u_n), x^*-P_{C_n}(x_n-\gamma u_n)\rangle . \end{aligned}$$

(20)

Since $x^*\in C\subset C_{n},$ we have by Lemma 2.1

$$\begin{aligned} \langle (x_n-\gamma u_n)-P_{C_n}(x_n-\gamma u_n),x^*-P_{C_n}(x_n-\gamma u_n)\rangle \le 0. \end{aligned}$$

Therefore,

$$\begin{aligned}&\langle x_n-P_{C_n}(x_n-\gamma u_n), x^*-P_{C_n}(x_n-\gamma u_n)\rangle \nonumber \\&\quad = \langle (x_n-\gamma u_n)-P_{C_n}(x_n-\gamma u_n),x^*-P_{C_n}(x_n-\gamma u_n)\rangle \nonumber \\&\qquad +\langle \gamma u_n,x^*-P_{C_n}(x_n-\gamma u_n)\rangle \nonumber \\&\quad \le \langle \gamma u_n,x^*-P_{C_n}(x_n-\gamma u_n)\rangle \nonumber \\&\quad \le \gamma \Vert u_n\Vert \Vert x^*-P_{C_n}(x_n-\gamma u_n)\Vert . \end{aligned}$$

(21)

Since $\{x_n\}$ is bounded, by $\alpha _n\rightarrow 0$ and (18), (20), (21), we get

$$\begin{aligned}&\langle x_{n+1}-x_n, x_{n+1}-x^*\rangle \le \alpha _n \langle P_{C_n}x_n-x_n,x_{n+1}-x^*\rangle \\&\quad +\alpha _n(1-\alpha _n) \langle P_{C_n}(x_n-\gamma u_n)-x_n,\\&P_{C_n}x_n-x^*\rangle +(1-\alpha _n)^2\gamma \Vert u_n\Vert \Vert x^*-P_C(x_n-\gamma u_n)\Vert \\&\quad \rightarrow 0, \end{aligned}$$

which by (19) and existence of $\lim _{n\rightarrow \infty }\Vert x_n-x^*\Vert$ yields

$$\begin{aligned} \Vert x_{n+1}-x_n\Vert \rightarrow 0. \end{aligned}$$

(22)

Since $\{x_n\}$ is bounded, which implies that $\{\xi _n\}$ is bounded, we see that the set of weak limit points of $\{x_n\}$, $\omega _w(x_n)$, is nonempty. We now show$\square$

Claim

$\omega _w(x_n)\subset \Gamma$.

Indeed, assume $\hat{x}\in \omega _w(x_n)$ and $\{x_{n_j}\}$ is a subsequence of $\{x_n\}$ which converges weakly to $\hat{x}$. Since $x_{n_j+1}\in C_{n_j}$, we obtain

$$\begin{aligned} c(x_{n_j})+\langle \xi _{n_j},x_{n_j+1}-x_{n_j}\rangle \le 0. \end{aligned}$$

Thus,

$$\begin{aligned} c(x_{n_j})\le -\langle \xi _{n_j},x_{n_j+1}-x_{n_j}\rangle \le \xi \Vert x_{n_j+1}-x_{n_j}\Vert , \end{aligned}$$

where $\xi$ satisfies $\Vert \xi _{n_j}\Vert \le \xi$ for all $n$. By virtue of the lower semicontinuity of $c$, we get by (22)

$$\begin{aligned} c(\hat{x})\le \liminf _{j\rightarrow \infty }c(x_{n_j})\le 0, \end{aligned}$$

Therefore, $\hat{x}\in C.$

Next we show that $A\hat{x}\in Q.$ To see this, by (17), set $y_n=Ax_n-P_{Q_n}Ax_n\rightarrow 0$ and let $\eta$ be such that $\Vert \eta _n\Vert \le \eta$. Then, since $Ax_{n_j}-y_{n_j}=P_{Q_{n_j}}Ax_{n_j}\in Q_{n_j},$ we get

$$\begin{aligned} q(Ax_{n_j})+\langle \eta _{n_j}, (Ax_{n_j}-y_{n_j})-Ax_{n_j} \rangle \le 0. \end{aligned}$$

Hence,

$$\begin{aligned} q(Ax_{n_j})\le \langle \eta _{n_j}, y_{n_j} \rangle \le \eta \Vert y_{n_j}\Vert \rightarrow 0. \end{aligned}$$

By the weak lower semicontinuity of $q$ and the fact that $Ax_{n_j}\rightarrow A\hat{x}$ weakly, we arrive at the conclusion

$$\begin{aligned} q(A\hat{x})\le \liminf _{j\rightarrow \infty }q(Ax_{n_j})\le 0. \end{aligned}$$

Namely, $A\hat{x}\in Q.$

Therefore, $\hat{x}\in \Gamma$. Now we can apply Lemma 2.5 to $K:=\Gamma$ to get that the full sequence $\{x_n\}$ converges weakly to a point in $\Gamma$.

4 A modified variable-step relaxed projection algorithm

In the Algorithm 3.1, the stepsizes $\gamma$ are all fixed. In this section, based on the algorithm of Qu and Xiu [14], we present a modified variable-step projection method which needs not compute the spectral radius of the operator $A^*A$, and the objective function can sufficiently decrease at each iteration.

For every $n$, using $Q_n$ we define the function $F_n : \mathcal{H }_1\rightarrow \mathcal{H }_1$ by

$$\begin{aligned} F_n(x) =A^*(I-P_{Q_n})Ax. \end{aligned}$$

The variable-step relaxed projection algorithm is defined as follows:

Algorithm 4.1

Given constants $\gamma > 0,\,l\in (0, 1),\,\mu \in (0, \sqrt{2}/2)$. Let $x_0$ be arbitrary. Let $\{\alpha _n\}\subset (0,\infty )$, and let

$$\begin{aligned} y_n=P_{C_n}(x_n-\beta _n F_n(x_n)), \end{aligned}$$

where $\beta _n=\gamma l^{m_n}$ and $m_n$ is the smallest nonnegative integer $m$ such that

$$\begin{aligned} \Vert F_n(x_n)-F_n(y_n)\Vert \le \mu \frac{\Vert x_n-y_n\Vert }{\beta _n}. \end{aligned}$$

(23)

Let

$$\begin{aligned} x_{n+1}=\alpha _ny_n+(1-\alpha _n)P_{C_n}(x_n-\beta _n F_n(y_n)), \end{aligned}$$

(24)

where $\{C_n\}$ and $\{Q_n\}$ are the sequences of closed convex sets constructed as follows:

$$\begin{aligned} C_n=\left\{ x\in \mathcal{H }_1:c(x_n)+\langle \xi _n,x-x_n\rangle \le 0 \right\} \!, \end{aligned}$$

where $\xi _n\in \partial c(x_n)$, and

$$\begin{aligned} Q_n=\left\{ y\in \mathcal{H }_2:q(Ax_n)+\langle \eta _n,y-Ax_n\rangle \le 0 \right\} \!, \end{aligned}$$

where $\eta _n\in \partial q(Ax_n)$.

Although $C_n, Q_n$ and $F_n$ depend on $n$, we have the following two nice lemmas (see [14]).

Lemma 4.1.

For all $n = 0, 1, 2,\ldots ,$ $F_n$ is Lipschitz continuous on $\mathcal{H }_1$ with constant $L$ and $1/L$-ism on $\mathcal{H }_1$, where $L$ is the spectral radius of the operator $A^*A$. Therefore, Armijo-like search rule (23) is well defined.

Lemma 4.2

For all $n=0,1,\ldots ,$

$$\begin{aligned} \frac{\mu l}{L}<\beta _n\le \gamma . \end{aligned}$$

Theorem 4.1

Let $\{x_n\}$ be the sequence generated by the Algorithm 4.1 Let $\{\alpha _n\}\subset (0,\infty )$ satisfy

$$\begin{aligned} \sum ^\infty _{n=0}\alpha _n^2<+\infty . \end{aligned}$$

Then $\{x_n\}$ converges weakly to a solution of SFP(1).

Proof

From (23) and (24), it is easily seen that

$$\begin{aligned}&\Vert x_{n+1}-P_{C_n}(x_n-\beta _n F_n(y_n))\Vert =\alpha _n \Vert y_n-P_{C_n}(x_n-\beta _n F_n(y_n))\Vert \nonumber \\&\quad =\alpha _n \Vert P_{C_n}(x_n-\beta _n F_n(x_n))-P_{C_n}(x_n-\beta _n F_n(y_n))\Vert \nonumber \\&\quad \le \alpha _n\beta _n\Vert F_n(x_n)-F_n(y_n)\Vert \nonumber \\&\quad \le \alpha _n\mu \Vert x_n-y_n\Vert . \end{aligned}$$

(25)

Let $x^*$ be a solution of the SFP (1), using the similar procedure in the proof of Theorem 3.1, we obtain

$$\begin{aligned}&\Vert x_{n+1}-x^*\Vert ^2\le (1+\alpha _n^2) \Vert P_{C_n}(x_n-\beta _n F_n(y_n))-x^*\Vert ^2\nonumber \\&\quad +\left(1+\frac{1}{\alpha _n^2}\right) \Vert x_{n+1}-P_{C_n}(x_n-\beta _n F_n(y_n))\Vert ^2. \end{aligned}$$

(26)

Following the line of the proof of (7) in [14], we have

$$\begin{aligned} \Vert P_{C_n}(x_n-\beta _n F_n(y_n))-x^*\Vert ^2\le \Vert x_n-x^*\Vert ^2-(1-\mu ^2)\Vert x_n-y_n\Vert ^2. \end{aligned}$$

(27)

Combining (25)–(27), we get

$$\begin{aligned}&\Vert x_{n+1}-x^*\Vert ^2 \le (1+\alpha _n^2) \Vert x_n-x^*\Vert ^2\nonumber \\&\qquad +\left[\alpha _n^2 \mu ^2\left(1+\frac{1}{\alpha _n^2}\right)-(1+\alpha _n^2)(1-\mu ^2) \right]\Vert x_n-y_n\Vert ^2\nonumber \\&\quad \le \left(1+\alpha _n^2\right)\Vert x_n-x^*\Vert ^2+ (1+\alpha _n^2)(2\mu ^2-1)\Vert x_n-y_n\Vert ^2, \end{aligned}$$

(28)

which with $\mu \in (0, \sqrt{2}/2)$ yields

$$\begin{aligned} \Vert x_{n+1}-x^*\Vert ^2 \le \left(1+\alpha _n^2\right)\Vert x_n-x^*\Vert ^2. \end{aligned}$$

So, using Lemma 2.4, we get that $\lim _{n\rightarrow \infty }\Vert x_{n}-x^*\Vert$ exists, and hence $\{x_n\}$ is bounded. From (28), it follows that

$$\begin{aligned} (1-2\mu ^2)\Vert x_n-y_n\Vert ^2 \le \Vert x_n-x^*\Vert ^2-\Vert x_{n+1}-x^*\Vert ^2+ \alpha _n^2\Vert x_n-x^*\Vert ^2. \end{aligned}$$

(29)

Consequently we get

$$\begin{aligned} \lim _{n\rightarrow \infty }\Vert x_n-y_n\Vert =0. \end{aligned}$$

(30)

We next demonstrate that

$$\begin{aligned} \Vert x_{n+1}-x_n\Vert \rightarrow 0. \end{aligned}$$

(31)

Using (23), we obtain

$$\begin{aligned}&\Vert x_{n+1}-x_n\Vert ^2\le 2( \Vert x_{n+1}-y_n\Vert ^2+\Vert y_n-x_n\Vert ^2)\\&\quad =2(1-\alpha _n)^2\Vert P_{C_n}(x_n-\beta _n F_n(y_n))-y_n\Vert ^2+2\Vert y_n-x_n\Vert ^2\\&\quad =2(1-\alpha _n)^2\Vert P_{C_n}(x_n-\beta _n F_n(y_n))- P_{C_n}(x_n-\beta _n F_n(x_n))\Vert ^2+2\Vert y_n-x_n\Vert ^2\\&\quad \le 2(1-\alpha _n)^2\beta _n^2\Vert F_n(x_n)-F_n(y_n)\Vert ^2+2\Vert y_n-x_n\Vert ^2\\&\quad \le 2[\mu ^2(1-\alpha _n)^2+1]\Vert x_n-y_n\Vert ^2, \end{aligned}$$

which by (30) yields (31).

Since $\{x_n\}$ is bounded, we see that the set of weak limit points of $\{x_n\},\,\omega _w(x_n)$, is nonempty and $\{Ax_n\}$ is bounded which implies that $\{\eta _n\}$ is bounded. Let $\eta$ be such that $\Vert \eta _n\Vert \le \eta .$ We now show $\square$

Claim

$\omega _w(x_n)\subset \Gamma$.

Assume $\hat{x}\in \omega _w(x_n)$ and $\{x_{n_i}\}$ is a subsequence of $\{x_n\}$ which converges weakly to $\hat{x}$. Using the similar procedure in the proof of Theorem 3.1, by (31), we get $\hat{x}\in C.$

Next we show that $A(\hat{x})\in Q.$ Define

$$\begin{aligned} e_n(x,\beta )=x-P_{C_n}(x-\beta F_n(x)),\quad n=0,1,2,\ldots . \end{aligned}$$

Then from Lemmas 2.3 and 4.2, and Eq. (30), we have:

$$\begin{aligned} \min \left\{ 1,\frac{\mu l}{L}\right\} \Vert e_{n_i}(x_{n_i},1)\Vert \le \Vert e_{n_i}(x_{n_i},\beta _{n_i})\Vert =\Vert x_{n_i}-y_{n_i}\Vert \rightarrow 0, \end{aligned}$$

which implies

$$\begin{aligned} \lim _{i\rightarrow \infty }\Vert e_{n_i}(x_{n_i},1)\Vert =0. \end{aligned}$$

(32)

Using Lemma 2.1 and $x^*\in C\subset C_{n_i}$, we have for all $i = 1,2,\ldots ,$

$$\begin{aligned} \langle x_{n_i}-F_{n_i}(x_{n_i})-P_{C_{n_i}}(x_{n_i}-F_{n_i}(x_{n_i})), P_{C_{n_i}}(x_{n_i}-F_{n_i}(x_{n_i}))-x^*\rangle \ge 0, \end{aligned}$$

which implies

$$\begin{aligned} \langle e_{n_i}(x_{n_i},1)-F_{n_i}(x_{n_i}), x_{n_i}-x^*- e_{n_i}(x_{n_i},1)\rangle \ge 0, \end{aligned}$$

which implies

$$\begin{aligned} \langle x_{n_i}-x^*,e_{n_i}(x_{n_i},1)\rangle&\ge \Vert e_{n_i}(x_{n_i},1)\Vert ^2 -\langle F_{n_i}(x_{n_i}),e_{n_i}(x_{n_i},1)\rangle \nonumber \\&+\langle F_{n_i}(x_{n_i}),x_{n_i}-x^*\rangle \end{aligned}$$

(33)

From (5), it follows

$$\begin{aligned} \langle F_{n_i}(x_{n_i})-F_{n_i}(x^*),x_{n_i}{-}x^*\rangle&= \langle A^*(I-P_{Q_{n_i}})Ax_{n_i}{-}A^*(I-P_{Q_{n_i}})A x^*,x_{n_i}-x^*\rangle \nonumber \\&= \langle (I-P_{Q_{n_i}})Ax_{n_i}-(I-P_{Q_{n_i}})A x^*,Ax_{n_i}-Ax^*\rangle \nonumber \\&\ge \Vert (I-P_{Q_{n_i}})Ax_{n_i}-(I-P_{Q_{n_i}})A x^*\Vert ^2\nonumber \\&= \Vert (I-P_{Q_{n_i}})Ax_{n_i}\Vert ^2 \end{aligned}$$

(34)

Combining (33) and (34), we have

$$\begin{aligned} \langle x_{n_i}-x^*,e_{n_i}(x_{n_i},1)\rangle&\ge \Vert e_{n_i}(x_{n_i},1)\Vert ^2 -\langle F_{n_i}(x_{n_i}),e_{n_i}(x_{n_i},1)\rangle \nonumber \\&+ \Vert (I-P_{Q_{n_i}})Ax_{n_i}\Vert ^2. \end{aligned}$$

(35)

Since

$$\begin{aligned} \Vert F_{n_i}(x_{n_i})\Vert =\Vert F_{n_i}(x_{n_i})-F_{n_i}(x^*)\Vert \le L\Vert x_{n_i}-x^*\Vert ,\quad \forall i=1,2,\ldots , \end{aligned}$$

and $\{x_{n_i}\}$ is bounded, the sequence $\{F_{n_i}(x_{n_i})\}$ is also bounded. Therefore, from (32) and (35), we get

$$\begin{aligned} \lim _{n_i\rightarrow \infty }\Vert P_{Q_{n_i}}(Ax_{n_i})-Ax_{n_i}\Vert =0. \end{aligned}$$

By $P_{Q_{n_i}}(Ax_{n_i})\in Q_{n_i}$, we have

$$\begin{aligned} q(Ax_{n_i})+\langle \eta _{n_i},P_{Q_{n_i}}(Ax_{n_i})-Ax_{n_i}\rangle \le 0. \end{aligned}$$

Hence,

$$\begin{aligned} q(Ax_{n_i})\le -\langle \eta _{n_i},P_{Q_{n_i}}(Ax_{n_i})-Ax_{n_i}\rangle \le \eta \Vert P_{Q_{n_i}}(Ax_{n_i})-Ax_{n_i}\Vert \rightarrow 0. \end{aligned}$$

By the weak lower semicontinuity of $q$ and the fact that $Ax_{n_j}\rightarrow A\hat{x}$ weakly, we arrive at the conclusion

$$\begin{aligned} q(A\hat{x})\le \liminf _{j\rightarrow \infty }q(Ax_{n_j})\le 0. \end{aligned}$$

Namely, $A\hat{x}\in Q.$

Therefore, $\hat{x}\in \Gamma$. Now we can apply Lemma 2.5 to $K:=\Gamma$ to get that the full sequence $\{x_n\}$ converges weakly to a point in $\Gamma$.

5 Numerical results

In this section, we will present the results of numerical tests for a problem (see [15]). We consider the following problem:

Table 1 MRCQ and RCQ applied for (P)

(P) Let $C=\{x\in R^{10}|c(x)\le 0 \}$ where $c(x)=-x_1+x_2^2+\cdots +x_{10}^2$ and $Q=\{y\in R^{20}|q(y)\le 0\}$ where $q(x)=y_1+y_2^2+\cdots +y_{20}^2-1$. Note that $C$ is the set above the function $x_1=x_2^2+\cdots +x_{10}^2$ and $Q$ is the set below the function $y_1=-y_2^2-\cdots -y_{20}^2+1$. $A\in R^{20\times 10}$ is a random matrix where every element of $A$ is in $(0,1)$ satisfying $A(C)\cap Q\ne \emptyset$. Let $x_0$ be a random vector in $R^{10}$ where every element of $x_0$ is in $(0,1)$.

Table 2 MRCQ applied to (P) with different stepsizes

The terminal condition is that $\Vert x_n-x^*\Vert \le \epsilon$, where $x^*$ is a solution of (P). Let $\alpha _n = 1/n^2, n = 0,1,\ldots ,$ in the Algorithms 3.1 and 4.1 In the tables, $\epsilon$ denotes the tolerance of the solution point of the problem, ’Iter.’ and ’InIt’ denote the terminating iterative numbers and the number of total iterations of finding suitable $\beta _n$ in (23), respectively. $C(x)$ and $Q(Ax)$ denote the value of $c(x)$ and $q(Ax)$ at the terminal point, respectively.

We compare the algorithms 3.1 and 4.1 with the relaxed CQ algorithm in [13] and the variable-step CQ algorithm in [14], respectively.

Firstly, we compare the modified relaxed projection algorithm 3.1 (MRCQ) with relaxed CQ algorithm (RCQ) in [13] applied to (P). Let $\gamma =0.99M$ where $M=\min \{2/\Vert A\Vert ^2,\sqrt{2}/\Vert A\Vert \}$. In Table 1 we display the iteration history when using three different values of $\epsilon$ and for each $\epsilon$ four different start vectors (chosen at random). We see from Table 1 that none of the two tested algorithms come out as the best. We next use three different values of the stepsize $\gamma$. For each test the same start vector was used. The results, Table 2, show that ’Iter.’ decreases slowly as the stepsize approaches $M$.

Table 3 MVRCQ and VRCQ applied for (P)

Secondly, we compare the modified variable-step relaxed projection 4.1 (MVRCQ) with variable-step CQ algorithm (VRCQ) in [14] applied to (P). Let $\gamma =0.5, l=0.4, \mu =0.7.$ From Table 3, we first note that ’Iter.’ and ’InIt.’ are slightly smaller for (MVRCQ) than that of (VRCQ); secondly we see that the iteration is not sensitive to the tolerance. It is also observed that the numbers of steps needed in Table 3 are larger than that of Table 2. This phenomenon might be caused by the choice of $\beta _n$ in (23) which maybe be much smaller than $M$. This issue is left for future studies.

6 Concluding remarks

In this paper, a modified relaxed projection algorithm and a modified variable-step relaxed projection algorithm with Armijo-like searches for solving the split feasibility problem have been presented. For the two algorithms, the orthogonal projections can be calculated directly. The algorithm 4.1 does not need to compute or estimate the norm of the matrix and the stepsize can be computed using a number of steps of the power method. Moreover, the objective function can decrease significantly at each iteration in these algorithms. In the feasible case of the SFP, the corresponding convergence properties have been established. We perform some numerical experiments, which have confirmed the theoretical results obtained.