Abstract
In this paper, our aim is to introduce a viscosity type algorithm for solving proximal split feasibility problems and prove the strong convergence of the sequences generated by our iterative schemes in Hilbert spaces. First, we prove strong convergence result for a problem of finding a point which minimizes a convex function f such that its image under a bounded linear operator A minimizes another convex function g. Secondly, we prove another strong convergence result for the case where one of the two involved functions is prox-regular. In all our results in this work, our iterative schemes are proposed by way of selecting the step sizes such that their implementation does not need any prior information about the operator norm because the calculation or at least an estimate of the operator norm \(\|A\|\) is not an easy task. Finally, we give a numerical example to study the efficiency and implementation of our iterative schemes. Our results complement the recent results of Moudafi and Thakur (Optim. Lett. 8:2099-2110, 2014, doi:10.1007/s11590-013-0708-4) and other recent important results in this direction.
Similar content being viewed by others
1 Introduction
In this paper, we shall assume that H is a real Hilbert space with inner product \(\langle\cdot,\cdot\rangle\) and norm \(\|\cdot\|\). Let I denote the identity operator on H. Let C and Q be nonempty, closed, and convex subsets of real Hilbert spaces \(H_{1}\) and \(H_{2}\), respectively. The split feasibility problem (SFP) is to find a point
where \(A:H_{1}\rightarrow 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]. The SFP attracts the attention of many authors due to its application in signal processing. Various algorithms have been invented to solve it (see, for example, [3–9] and references therein). For a more current and up-to-date survey on split feasibility problems, please see [10].
Note that the split feasibility problem (1.1) can be formulated as a fixed point equation by using the fact
that is, \(x^{*}\) solves the SFP (1.1) if and only if \(x^{*}\) solves the fixed point equation (1.2) (see [11] for the details). This implies that we can use fixed point algorithms (see [12–14]) to solve SFP. A popular algorithm that solves the SFP (1.1) is due to Byrne’s CQ algorithm [2] which is found to be a gradient-projection method (GPM) in convex minimization. Subsequently, Byrne [3] applied Krasnoselskii-Mann iteration to the CQ algorithm, and Zhao and Yang [15] applied Krasnoselskii-Mann iteration to the perturbed CQ algorithm to solve the SFP. It is well known that the CQ algorithm and the Krasnoselskii-Mann algorithm for a split feasibility problem do not necessarily converge strongly in the infinite-dimensional Hilbert spaces.
Our goal in this paper is to study the more general case of proximal split minimization problems and to investigate the strong convergence properties of the associated numerical solutions. To begin with, let us consider the following problem: Find a solution \(x^{*}\in H_{1}\) such that
where \(H_{1}\), \(H_{2}\) are two real Hilbert spaces, \(f:H_{1}\rightarrow\mathbb {R}\cup\{+\infty\}\), \(g:H_{2} \rightarrow\mathbb{R}\cup\{+\infty\}\) two proper, convex, lower-semicontinuous functions and \(A:H_{1}\rightarrow H_{2}\) a bounded linear operator, \(g_{\lambda}(y) = \min_{u\in H_{2}} \{g(u) + \frac{1}{2 \lambda}\|u-y\|^{2}\}\) stands for the Moreau-Yosida approximate of the function g of parameter λ.
Observe that by taking \(f =\delta_{C}\) (defined as \(\delta_{C}(x) = 0\) if \(x\in C\) and +∞ otherwise), \(g =\delta_{Q}\) the indicator functions of two nonempty, closed, and convex sets C, Q of \(H_{1}\) and \(H_{2}\), respectively, problem (1.3) reduces to
which, when \(C\cap A^{-1}(Q)\neq\emptyset\), is equivalent to (1.1).
By the differentiability of the Yosida approximate \(g_{\lambda}\), see for instance [16], we have the additivity of the subdifferentials and thus we can write
This implies that the optimality condition of (1.3) can then be written as
where \(\operatorname{prox}_{\lambda g} = \operatorname{argmin}_{u\in H_{2}} \{g(u) + \frac{1}{2 \lambda}\|u-y\|^{2}\}\) stands for the proximal mapping of g and the subdifferential of f at x is the set
The inclusion (1.5) in turn yields the following equivalent fixed point formulation:
To solve (1.3), (1.6) suggests us to consider the following split proximal algorithm:
Based on an idea introduced in work of Lopez et al. [17], Moudafi and Thakur [18] recently proved weak convergence results for solving (1.3) in the case \(\operatorname{argmin} f\cap A^{-1}(\operatorname{argmin} g)\neq\emptyset\), or in other words: in finding a minimizer \(x^{*}\) of f such that \(Ax^{*}\) minimizes g, namely
f, g being two proper, lower-semicontinuous convex functions, \(\operatorname{argmin} f:= \{ \bar{x} \in H_{1}: f(\bar{x})\leq f(x), \forall x \in H_{1}\}\) and \(\operatorname{argmin} g:= \{ \bar{y} \in H_{2}: g( \bar{y}) \leq g(y), \forall y \in H_{2}\}\). We will denote the solution set of (1.8) by Γ. Concerning problem (1.8), Moudafi and Thakur [18] introduced a new way of selecting the step sizes: Set \(\theta (x_{n}):=\sqrt{\|\nabla h(x)\|^{2}+\|\nabla l(x)\|^{2}}\) with \(h(x)=\frac {1}{2}\|(I-\operatorname{prox}_{\lambda g})Ax\|^{2}\), \(l(x)=\frac{1}{2}\|(I-\operatorname{prox}_{\lambda\mu_{n} f})x\|^{2}\) and introduced the following split proximal algorithm.
Split proximal algorithm 1
Given an initial point \(x_{1}\in H_{1}\). Assume that \(x_{n}\) has been constructed and \(\theta(x_{n}) \neq0\), then compute \(x_{n+1}\) via the rule
where the step size \(\mu_{n}:=\rho_{n}\frac{h(x_{n})+l(x_{n})}{\theta^{2}(x_{n})}\) with \(0<\rho_{n}<4\). If \(\theta(x_{n})=0\), then \(x_{n+1}=x_{n}\) is a solution of (1.3) and the iterative process stops, otherwise, we set \(n:= n + 1\) and go to (1.9).
Using the split proximal algorithm (1.9), Moudafi and Thakur [18] proved the following weak convergence theorem for approximating a solution of (1.8).
Theorem 1.1
Assume that f and g are two proper convex lower-semicontinuous functions and that (1.8) is consistent (i.e., \(\Gamma \neq\emptyset\)). If the parameters satisfy the conditions \(\epsilon \leq\rho_{n} \leq\frac{4 h(x_{n})}{h(x_{n})+l(x_{n})}-\epsilon\) (for some \(\epsilon>0\) small enough), then the sequence \(\{x_{n}\}\) generated by (1.9) weakly converges to a solution of (1.8).
Furthermore, Moudafi and Thakur [18] assumed f to be convex and allowed the function g to be nonconvex. In the case of indicator functions of subsets with \(A = I\), such a situation is encountered in a numerical solution to phase retrieval problem in inverse scattering [19] and is therefore of great practical interest. They considered the more general problem of finding a minimizer \(\bar{x}\) of f such that \(A\bar{x}\) is a critical point of g, namely
where \(\partial_{pg}\) stands for the proximal subdifferential of g (see Definition 4.1 for definition of a proximal subdifferential). In particular, they studied the convergence properties of the following algorithm.
Split proximal algorithm 2
Given an initial point \(x_{1}\in H_{1}\). Assume that \(x_{n}\) has been constructed and \(\theta(x_{n}) \neq0\), then compute \(x_{n+1}\) via the rule
where the step size \(\mu_{n}:=\rho_{n}\frac{h(x_{n})+l(x_{n})}{\theta^{2}(x_{n})}\) with \(0<\rho_{n}<4\). If \(\theta(x_{n})=0\), then \(x_{n+1}=x_{n}\) is a solution of (1.10) and the iterative process stops, otherwise, we set \(n:= n + 1\) and go to (1.11).
Using (1.11), Moudafi and Thakur [18] proved the following weak convergence theorem for the approximation of the solution of (1.10).
Theorem 1.2
Assume that f is a proper convex lower-semicontinuous function, g is locally lower-semicontinuous at \(A\bar{x}\), prox-bounded, and prox-regular at \(A\bar{x}\) for \(\bar{v}= 0\) with \(\bar{x}\) a point which solves (1.10) and A a bounded linear operator which is surjective with a dense domain. If the parameters satisfy the following conditions: \(\sum_{n=1}^{\infty}\lambda_{n}<\infty\) and \(\inf_{n}\rho_{n} (\frac{4 h(x_{n})}{h(x_{n})+l(x_{n})}-\rho_{n})>0\) and if \(\|x_{1}-\bar{x}\|\) is small enough, then the sequence \(\{x_{n}\}\) generated by (1.11) weakly converges to a solution of (1.10).
Remark 1.3
We comment here that the split proximal algorithm (1.9) introduced Moudafi and Thakur [18] for approximating a solution of (1.8) has, in general, weak convergence only, unless the underlying Hilbert space is finite-dimensional. Indeed, based on the results of Hundal [20], we can construct a counterexample as follows.
Example 1.4
In the real Hilbert space \(H = \ell_{2}\), Hundal [20] constructed two closed and convex subsets C and Q such that (see also [21–23])
-
(i)
\(C\cap Q \neq\emptyset\);
-
(ii)
the sequence \(\{x_{n}\}_{n=1}^{\infty}\) generated by alternating projections,
$$ x_{n}=(P_{C} \circ P_{Q})^{n} x_{1},\quad n \geq1 $$(1.12)with \(x_{1} \in C\), converges weakly, but not strongly.
(Hundal’s counterexample settles in the negative the question whether alternating projections onto closed convex subsets of a Hilbert space can have strong convergence, which remained open for nearly 40 years.) Now in problem (1.8), let us take \(f =\delta_{C}\) and \(g =\delta _{Q}\) the indicator functions of two nonempty, closed, and convex sets C, Q of \(H_{1}\) and \(H_{2}\), respectively, where \(H_{1}=\ell_{2}=H_{2}\). Then \(\operatorname{prox}_{\lambda\mu_{n} f}(x)=P_{C}(x)\) and \(\operatorname{prox}_{\lambda g}(x)=P_{Q}(x)\). Furthermore, take \(A=I=A^{*}\), where I is an identity mapping on \(\ell_{2}\). Taking an initial guess \(x_{1} \in C\) and \(\mu_{n} = 1\), \(\forall n \geq1\), we see that the split proximal algorithm (1.9) generates a sequence \(\{x_{n}\}_{n=1}^{\infty}\) which coincides with the sequence \(\{ x_{n}\}_{n=1}^{\infty}\) given in (1.12). Therefore, the split proximal algorithm (1.9) generates weakly (not strongly) convergent sequences to a solution of problem (1.8), in general, in infinite-dimensional real Hilbert spaces.
Example 1.4 naturally gives rise to this question.
Question
Can we appropriately modify the split proximal algorithm (1.9) so as to have strong convergence?
It is our aim in this paper to answer the above question in the affirmative. Thus, motivated by the results of Lopez et al. [17] and Moudafi and Thakur [18], our aim in this paper is to introduce new iterative schemes for solving problems (1.8) and (1.10) and prove strong convergence of the sequences generated by our schemes in real Hilbert spaces. Our results complement the results of Moudafi and Thakur [18] and Shehu [24–26].
2 Preliminaries
We state the following well-known lemmas which will be used in the sequel.
Lemma 2.1
Let H be a real Hilbert space. Then we have the following well-known results:
Lemma 2.2
(Xu [27])
Let \(\{a_{n}\}\) be a sequence of nonnegative real numbers satisfying the following relation:
where
-
(i)
\(\{a_{n}\}\subset[0,1]\), \(\sum\alpha_{n}=\infty\);
-
(ii)
\(\limsup\sigma_{n} \leq0\);
-
(iii)
\(\gamma_{n} \geq0\) (\(n \geq1\)), \(\sum\gamma_{n} <\infty\).
Then \(a_{n}\rightarrow0\) as \(n\rightarrow\infty\).
3 Strong convergence for convex minimization feasibility problem
In this section, we modify algorithm (1.9) above so as to have strong convergence. Below we include such modification. Let \(r:H_{1}\rightarrow H_{1}\) be a contraction mapping with constant \(\alpha\in(0,1)\). Set \(\theta(x):=\sqrt{\|\nabla h(x)\|^{2}+\|\nabla l(x)\|^{2}}\) with \(h(x)=\frac{1}{2}\|(I-\operatorname{prox}_{\lambda g})Ax\|^{2}\), \(l(x)=\frac{1}{2}\|(I-\operatorname{prox}_{\lambda\mu _{n} f})x\|^{2}\) and introduce the following modified split proximal algorithm.
Modified split proximal algorithm 1
Given an initial point \(x_{1}\in H_{1}\). Assume that \(x_{n}\) has been constructed and \(\theta(x_{n}) \neq0\), then compute \(x_{n+1}\) via the rule
where the step size \(\mu_{n}:=\rho_{n}\frac{h(x_{n})+l(x_{n})}{\theta^{2}(x_{n})}\) with \(0<\rho_{n}<4\). If \(\theta(x_{n})=0\), then \(x_{n+1}=x_{n}\) is a solution of (1.8) and the iterative process stops, otherwise, we set \(n:= n + 1\) and go to (3.1).
Using (3.1), we prove the following strong convergence theorem for approximation of solutions of problem (1.8).
Theorem 3.1
Assume that f and g are two proper convex lower-semicontinuous functions and that (1.8) is consistent (i.e., \(\Gamma \neq\emptyset\)). If the parameters satisfy the following conditions:
-
(a)
\(\lim_{n\rightarrow\infty} \alpha_{n} =0\);
-
(b)
\(\sum_{n=1}^{\infty} \alpha_{n} =\infty\);
-
(c)
\(\epsilon\leq\rho_{n} \leq\frac{4 h(x_{n})}{h(x_{n})+l(x_{n})}-\epsilon \) for some \(\epsilon>0\),
the sequence \(\{x_{n}\}\) generated by (3.1) strongly converges to a solution of (1.8) which is also the unique solution of the variational inequality (VI),
In other words, \(x^{*}\) is the unique fixed point of the contraction \(\operatorname{Proj}_{\Gamma}r\), \(x^{*}=(\operatorname{Proj}_{\Gamma}r)x^{*}\).
Proof
Let \(x^{*}\in\Gamma\). Observe that \(\nabla h(x)= A^{*}(I-\operatorname{prox}_{\mu _{n} g})Ax\), \(\nabla l(x) = (I-\operatorname{prox}_{\mu_{n} \lambda f})x\). Using the fact that \(\operatorname{prox}_{\mu_{n} \lambda f}\) is nonexpansive, \(x^{*}\) verifies (1.8) (since minimizers of any function are exactly fixed points of its proximal mapping) and having in hand
thanks to the fact that \(I-\operatorname{prox}_{\mu_{n} g}\) is firmly nonexpansive, we can write
From (3.1) and (3.3), we obtain
Therefore, \(\{x_{n}\}\) and \(\{y_{n}\}\) are bounded.
The rest of the proof will be divided into two parts.
Case 1. Suppose that there exists \(n_{0} \in\mathbb{N}\) such that \(\{\|y_{n}-x^{*}\|\}_{n=n_{0}}^{\infty}\) is nonincreasing. Then \(\{ \|y_{n}-x^{*}\|\}_{n=1}^{\infty}\) converges and \(\|y_{n}-x^{*}\|^{2}-\|y_{n+1}-x^{*}\|^{2}\rightarrow0\), \(n\rightarrow\infty\). From (3.3) and (3.4), we have
Condition (a) above implies that
Hence, we obtain
Consequently, we have
because \(\theta^{2}(x_{n})=\|\nabla h(x_{n})\|^{2}+\|\nabla l(x_{n})\|^{2}\) is bounded. This follows from the fact that ∇h is Lipschitz continuous with constant \(\|A\|^{2}\), ∇l is nonexpansive and \(\{x_{n}\}\) is bounded. More precisely, for any \(x^{*}\) which solves (1.9), we have
We observe that
implies that \(\mu_{n} \rightarrow0\), \(n\rightarrow\infty\). Hence, we have from (3.1) that
for some \(M_{1}>0\).
From \(\lim_{n\rightarrow\infty}\frac{1}{2}\|(I-\operatorname{prox}_{\lambda\mu_{n} f})x_{n}\|^{2}=\lim_{n\rightarrow\infty} l(x_{n})=0\) and \(\lim_{n\rightarrow\infty}\|y_{n}-x_{n}\|=0\), we have
So,
and
Also, observe that from (3.1), we obtain \(\|x_{n+1}-\operatorname{prox}_{\lambda\mu_{n} f}y_{n}\|\rightarrow0\), \(n\rightarrow\infty\). We then have
Now, let z be a weak cluster point of \(\{x_{n}\}\), there exists a subsequence \(\{x_{n_{j}}\}\) which weakly converges to z. The lower-semicontinuity of h then implies that
That is \(h(z)=\frac{1}{2}\|(I- \operatorname{prox}_{\lambda g})Az\|= 0\), i.e., Az is a fixed point of the proximal mapping of g or equivalently \(0\in\partial g(Az)\). In other words, Az is a minimizer of g.
Likewise, the lower-semicontinuity of l implies that
That is, \(l(z)=\frac{1}{2}\|(I- \operatorname{prox}_{\mu_{n}\lambda f})z\|= 0\), i.e., z is a fixed point of the proximal mapping of f or equivalently \(0\in\partial f(z)\). In other words, z is a minimizer of f. Hence, \(z \in\Gamma\).
Next, we prove that \(\{x_{n}\}\) converges strongly to \(x^{*}\), where \(x^{*}\) is the unique solution of the VI (3.2). First observe that there is some \(z\in\omega _{w}(x_{n})\subset\Gamma\) (where \(\omega_{w}(x_{n}):= \{x: \exists x_{n_{j}}\rightharpoonup x\}\) is the weak w-limit set of the sequence \(\{x_{n}\}_{n=1}^{\infty}\)) such that
Applying Lemma 2.1(ii) to (3.1), we have
Now, using Lemma 2.2 in (3.7), we have \(\| x_{n}-x^{*}\| \rightarrow0\). That is, \(x_{n}\rightarrow x^{*}\), \(n\rightarrow\infty\).
Case 2. Assume that \(\{\| y_{n}-x^{*}\|\}\) is not a monotonically decreasing sequence. Set \(\Gamma_{n}=\|y_{n}-x^{*}\|^{2}\) and let \(\tau:\mathbb {N}\rightarrow\mathbb{N}\) be a mapping for all \(n\geq n_{0}\) (for some \(n_{0}\) large enough) by
Clearly, τ is a nondecreasing sequence such that \(\tau (n)\rightarrow\infty\) as \(n \rightarrow\infty\) and
This implies that \(\|y_{\tau(n)}-x^{*}\|\leq\|y_{\tau(n)+1}-x^{*}\|\), \(\forall n\geq n_{0}\). Thus \(\lim_{n\rightarrow\infty}\|y_{\tau (n)}-x^{*}\|\) exists.
Using condition (a) in the last inequality above, we have
Hence, we obtain
Consequently, we have
Furthermore, we observe that
implies that \(\mu_{\tau(n)} \rightarrow0\), \(n\rightarrow\infty\). This implies from (3.1) that
for some \(M^{*}>0\). Since \(\{x_{\tau(n)}\}\) is bounded, there exists a subsequence of \(\{x_{\tau(n)}\}\), still denoted by \(\{x_{\tau(n)}\}\), which converges weakly to z. Observe that since \(\lim_{n\rightarrow\infty}\|x_{\tau(n)}-y_{\tau(n)}\|=0\), we also have \(y_{\tau(n)}\rightharpoonup z\). By similar argument as above in Case 1, we can show that \(z \in\Gamma\) and \(\lim_{n\rightarrow\infty} \|x_{\tau(n)+1}-x_{\tau(n)}\|=0\). Using (3.3) and (3.1), we obtain
which implies that, for all \(n\geq n_{0}\),
Thus, we have
Hence, we obtain (noting that \(x^{*}\) is the unique solution of the VI (3.2))
which implies that
Therefore,
Furthermore, for \(n\geq n_{0}\), it is easy to see that \(\Gamma_{\tau (n)}\leq\Gamma_{\tau(n)+1}\) if \(n\neq\tau(n)\) (that is, \(\tau(n)< n\)), because \(\Gamma_{j}\geq\Gamma_{j+1}\) for \(\tau(n)+1\leq j\leq n\). As a consequence, we obtain for all \(n\geq n_{0}\),
Hence, \(\lim\Gamma_{n}=0\), that is, \(\{y_{n}\}\) converges strongly to \(x^{*}\). Hence, \(\{x_{n}\}\) converges strongly to \(x^{*}\). This completes the proof. □
Taking \(r(x)=u\) in (3.1), we have the following algorithm.
Given an initial point \(x_{1}\in H_{1}\). Assume that \(x_{n}\) has been constructed and \(\theta(x_{n}) \neq0\), then compute \(x_{n+1}\) via the rule
where the step size \(\mu_{n}:=\rho_{n}\frac{h(x_{n})+l(x_{n})}{\theta^{2}(x_{n})}\) with \(0<\rho_{n}<4\). If \(\theta(x_{n})=0\), then \(x_{n+1}=x_{n}\) is a solution of (1.8) and the iterative process stops, otherwise, we set \(n:= n + 1\) and go to (3.9).
Corollary 3.2
Assume that f and g are two proper convex lower-semicontinuous functions and that (1.8) is consistent (i.e., \(\Gamma \neq\emptyset\)). If the parameters satisfy the following conditions:
-
(a)
\(\lim_{n\rightarrow\infty} \alpha_{n} =0\);
-
(b)
\(\sum_{n=1}^{\infty} \alpha_{n} =\infty\);
-
(c)
\(\epsilon\leq\rho_{n} \leq\frac{4 h(x_{n})}{h(x_{n})+l(x_{n})}-\epsilon \) for some \(\epsilon>0\),
the sequence \(\{x_{n}\}\) generated by (3.9) strongly converges to a solution of (1.8) which is closest to u from the solution set Γ. In other words, \(x^{*}\) is the unique fixed point of the contraction \(\operatorname{Proj}_{\Gamma}r\), \(x^{*}=(\operatorname{Proj}_{\Gamma})u\).
4 Strong convergence for nonconvex minimization feasibility problem
Throughout this section g is assumed to be prox-regular. The following problem:
is very general in the sense that it includes, as special cases, g is convex and g is a lower-\(C^{2}\) function which is of great importance in optimization and can be locally expressed as a difference \(g-\frac{r}{2}\|\cdot\|^{2}\), where g is a finite convex function, hence a large core of problems of interest in variational analysis and optimization. It should be noticed that examples abound of practitioners needing algorithms for solving nonconvex problems, for instance, in crystallography, astronomy, and, more recently in inverse scattering; see, for example, [28]. In what follows, we shall represent the set of solutions of (4.1) by Γ.
Definition 4.1
Let \(g:H_{2}\rightarrow\mathbb{R}\cup\{+\infty\}\) be a function and let \(\bar{x} \in \operatorname{dom} g\), i.e., \(g(\bar{x})<+\infty\). A vector v is in proximal subdifferential \(\partial_{p g}(\bar{x})\) if there exist some \(r>0\) and \(\epsilon> 0\) such that for all \(x\in B(\bar {x},\epsilon)\),
When \(g(\bar{x})=+\infty\), one puts \(\partial_{p g}(\bar{x})=\emptyset\).
Before stating the definition of prox-regularity of g and properties of its proximal mapping, we recall that g is locally l.s.c. at \(\bar{x}\) if its epigraph is closed relative to a neighborhood of \((\bar{x}, g(\bar{x}))\), prox-bounded if g is minorized by a quadratic function, and recall that for \(\epsilon> 0\), the g-attentive ϵ-localization of \(\partial_{p g}(\bar{x})\) around \((\bar{x},\bar{v})\), is the mapping \(T_{\epsilon}:H_{2}\rightarrow2^{H_{2}}\) defined by
Definition 4.2
A function g is said to be prox-regular at \(\bar{x}\) for \(\bar{v}\in \partial_{p g}(\bar{x})\) if there exist some \(r > 0\) and \(\epsilon> 0\) such that for all \(x,x' \in B(\bar{x},\epsilon)\) with \(|g(x)-g(x')| < \epsilon\) and all \(v\in B(\bar{v},\epsilon)\) with \(v \in\partial_{p g}(\bar{x})\) one has
If the property holds for all vectors \(\bar{v}\in\partial_{p g}(\bar {x})\), the function is said to be prox-regular at \(\bar{x}\).
Fundamental insights into the properties of a function g come from the study of its Moreau-Yosida regularization \(g_{\lambda}\) and the associated proximal mapping \(\operatorname{prox}_{\lambda g}\) defined for \(\lambda> 0\), respectively, by
The latter is a fundamental tool in optimization and it was shown that a fixed point iteration on the proximal mapping could be used to develop a simple optimization algorithm, namely, the proximal point algorithm.
Note also, see, for example, Section 1 in [29], that local minima are zeros of the proximal subdifferential and that the proximal subdifferential and the convex one coincide in the convex case.
Now, let us state the following key property of the proximal mapping complement, which was proved in Remark 3.2 of Moudafi and Thakur [18].
Lemma 4.3
(Moudafi and Thakur [18])
Suppose that g is locally lower-semicontinuous at \(\bar{x}\) and prox-regular at \(\bar{x}\) for \(\bar{v}=0\) with respect to r and ϵ. Let \(T_{\epsilon}\) be the g-attentive ϵ-localization of \(\partial_{pg}\) around \((\bar{x},\bar{v})\). Then for each \(\lambda\in(0,\frac{1}{r})\) and \(x_{1}\), \(x_{2}\) in a neighborhood \(U_{\lambda}\) of \(\bar{x}\), one has
Observe that when \(r = 0\), which amounts to saying that g is convex, we recover the fact that the mapping \(I-\operatorname{prox}_{\lambda g}\) is firmly nonexpansive.
Now, the regularization parameters λ are allowed to vary in algorithm (3.1), namely considering possibly variable parameters \(\lambda\in(0,\frac{1}{r}-\epsilon)\) (for some \(\epsilon> 0\) small enough) and \(\mu_{n} > 0\), our interest is in studying the convergence properties of the following algorithm.
Modified split proximal algorithm 2
Let \(r:H_{1}\rightarrow H_{1}\) be a contraction mapping with constant \(\alpha\in(0,1)\). Given an initial point \(x_{1}\in H_{1}\). Assume that \(x_{n}\) has been constructed and \(\theta(x_{n}) \neq0\), then compute \(x_{n+1}\) via the rule
where the step size \(\mu_{n}:=\rho_{n}\frac{h(x_{n})+l(x_{n})}{\theta^{2}(x_{n})}\) with \(0<\rho_{n}<4\). If \(\theta(x_{n})=0\), then \(x_{n+1}=x_{n}\) is a solution of (4.1) and the iterative process stops, otherwise, we set \(n:= n + 1\) and go to (4.2).
Theorem 4.4
Assume that f is a proper convex lower-semicontinuous function, g is locally lower-semicontinuous at \(A\bar{x}\), prox-bounded and prox-regular at \(A\bar{x}\) for \(\bar{v}=0\) with \(\bar{x}\) a point which solves (4.1) and A a bounded linear operator which is surjective with a dense domain. If the parameters satisfy the following conditions:
-
(a)
\(\lim_{n\rightarrow\infty} \alpha_{n} =0\);
-
(b)
\(\sum_{n=1}^{\infty} \alpha_{n} =\infty\);
-
(c)
\(\epsilon\leq\rho_{n} \leq\frac{4 h(x_{n})}{h(x_{n})+l(x_{n})}-\epsilon\) for some \(\epsilon>0\);
-
(d)
\(\sum_{n=1}^{\infty}\lambda_{n}<\infty\);
and if \(\|x_{1}-\bar{x}\|\) is small enough, then the sequence \(\{x_{n}\}\) generated by (4.2) strongly converges to a solution of (4.1) which is also the unique solution of the variational inequality (VI)
In other words, \(\bar{x}\) is the unique fixed point of the contraction \(\operatorname{Proj}_{\Gamma}r\), \(\bar{x}=(\operatorname{Proj}_{\Gamma}r)\bar{x}\).
Proof
Using the fact that \(\operatorname{prox}_{\lambda_{n} \mu_{n} f}\) is nonexpansive, \(\bar{x}\) verifies (4.1) (critical points of any function are exactly fixed points of its proximal mapping) and having in mind Lemma 4.3, we can write
Recall that A is surjective with a dense domain \(\Leftrightarrow \exists\gamma> 0\) such that \(\|A^{*}x\|\geq\gamma\|x\|\) (see, for example, Theorem II.19 of Brézis [30]). This ensures that
The conditions on the parameters \(\lambda_{n}\) and \(\rho_{n}\) assure the existence of a positive constant M such that
Using (4.5) in (4.2) (taking into account that \(1+x\leq e^{x}\), \(x\geq0\)), we obtain
Therefore, \(\{x_{n}\}\) and \(\{y_{n}\}\) are bounded.
Following the method of proof of Theorem 3.1, we can show that
If z is a weak cluster point of \(\{x_{n}\}\), then there exists a subsequence \(\{x_{n_{j}}\}\) which weakly converges to z. From the proof of Theorem 3.1, we can show that \(0\in\partial f(z)\) such that \(0\in\partial_{pg}(Az)\).
Finally, from (4.2), we have
for some \(M_{1}>0\), from which one concludes that the sequence \(\{x_{n}\}\) strongly converges to a solution of (4.1) using Lemma 2.2. □
Remark 4.5
From Example 1.4, we recall that if \(f =\delta_{C}\) and \(g =\delta _{Q}\) the indicator functions of two nonempty, closed, and convex sets C, Q of \(H_{1}\) and \(H_{2}\), respectively, where \(H_{1}=\ell_{2}=H_{2}\), then \(\operatorname{prox}_{\lambda\mu_{n} f}(x)=P_{C}(x)\) and \(\operatorname{prox}_{\lambda g}(x)=P_{Q}(x)\). Furthermore, if \(A=I=A^{*}\), where I is an identity mapping on \(\ell_{2}\), \(\mu_{n} = 1\), \(\forall n \geq1\), then our modified split proximal algorithm (3.1) for approximation of solutions of problem (1.8) becomes \(x_{1} \in C\),
Noting that \(y_{n}=P_{Q}x_{n}\) in (3.1) and following the same method of proof as in Theorem 3.1, we see that our algorithm (4.7) converges strongly to a solution of problem (1.8).
We see from Example 1.4 and the above remark that the split proximal algorithm (1.9) generates weakly (not strongly) convergent sequences in general in infinite-dimensional spaces, while our modified split proximal algorithm (3.1) generates strongly convergent sequences in infinite-dimensional real Hilbert spaces.
5 Numerical results
In this section, we provide some concrete example including numerical results of the problem considered in Section 3 of this paper. All codes were written in Matlab 2012b and run on HP i5 Dual Core 8.00 GB (7.78 GB usable) RAM laptop.
Example 5.1
Let \(C=Q=\{x\in\mathbb{R}^{3}:\|x\|_{2}\leq1\}\) and take
In problem (1.8), let \(f =\delta_{C}\) and \(g =\delta_{Q}\) be the indicator functions of two nonempty, closed, and convex sets C, Q of \(\mathbb{R}^{3}=H_{1}=H_{2}\). Then
Hence problem (1.8) becomes: Find some point x in C such that \(Ax \in Q\). Now, take \(\rho_{n}=2\), \(\alpha_{n}=\frac{1}{n+1}\). Also, \(h(x_{n})= \frac{1}{2}\|(I-P_{Q})Ax_{n}\|_{2}^{2}\), \(l(x_{n})= \frac {1}{2}\|(I-P_{C})x_{n}\|_{2}^{2}\) and \(\theta(x_{n}):=\sqrt{\|\nabla h(x_{n})\|_{2}^{2}+\|\nabla l(x_{n})\|_{2}^{2}}\) with \(\|\nabla h(x_{n})\|_{2}^{2}=\| A^{T}(I-P_{Q})Ax_{n}\|_{2}^{2}\), \(\|\nabla l(x_{n})\|_{2}^{2} = \|(I-P_{C})x_{n}\|_{2}^{2}\). In the implementation, we took \(\| A^{T}(I-P_{Q})Ax_{n}\|_{2}^{2}+\|(I-P_{C})x_{n}\|_{2}^{2}<\frac{1}{10^{4}}\) as the stopping criterion.
Our iterative scheme (3.1) then becomes
Let \(r(x)=\frac{1}{2}(x_{1},x_{2},x_{3})\), \(x=(x_{1},x_{2},x_{3})\). We consider initial values for the problem considered in this example.
Case I: Take \(x_{1}=(0.1,0.1,0.1)\). The numerical result of this problem using our algorithm (5.1) with this initial value is listed in Table 1 and the graph is given in Figure 1.
Case II: Take \(x_{1}=(0.4,0.4,0.4)\). The numerical result of this problem using our algorithm (5.1) with this initial value is listed in Table 2 and the graph is given in Figure 2.
Case III: Take \(x_{1}=(0.55,0.55,0.55)\). The numerical result of this problem using our algorithm (5.1) with this initial value is listed in Table 3 and the graph is given in Figure 3.
References
Censor, Y, Elfving, T: A multiprojection algorithm using Bregman projections in a product space. Numer. Algorithms 8(2-4), 221-239 (1994)
Byrne, C: Iterative oblique projection onto convex sets and the split feasibility problem. Inverse Probl. 18(2), 441-453 (2002)
Byrne, C: A unified treatment of some iterative algorithms in signal processing and image reconstruction. Inverse Probl. 20(1), 103-120 (2004)
Maingé, PE: The viscosity approximation process for quasi-nonexpansive mappings in Hilbert spaces. Comput. Math. Appl. 59(1), 74-79 (2010)
Qu, B, Xiu, N: A note on the CQ algorithm for the split feasibility problem. Inverse Probl. 21(5), 1655-1665 (2005)
Xu, H-K: A variable Krasnosel’skii-Mann algorithm and the multiple-set split feasibility problem. Inverse Probl. 22(6), 2021-2034 (2006)
Yang, Q: The relaxed CQ algorithm solving the split feasibility problem. Inverse Probl. 20(4), 1261-1266 (2004)
Yang, Q, Zhao, J: Generalized KM theorems and their applications. Inverse Probl. 22(3), 833-844 (2006)
Yao, Y, Jigang, W, Liou, Y-C: Regularized methods for the split feasibility problem. Abstr. Appl. Anal. 2012, Article ID 140679 (2012)
Ansari, QH, Rehan, A: Split feasibility and fixed point problems. In: Ansari, QH (ed.) Nonlinear Analysis: Approximation Theory, Optimization and Applications, pp. 281-322. Springer, New York (2014)
Xu, H-K: Iterative methods for the split feasibility problem in infinite-dimensional Hilbert spaces. Inverse Probl. 26(10), Article ID 105018 (2010)
Yao, Y, Chen, R, Liou, Y-C: A unified implicit algorithm for solving the triple-hierarchical constrained optimization problem. Math. Comput. Model. 55(3-4), 1506-1515 (2012)
Yao, Y, Cho, Y-J, Liou, Y-C: Hierarchical convergence of an implicit double-net algorithm for nonexpansive semigroups and variational inequalities. Fixed Point Theory Appl. 2011, Article ID 101 (2011)
Yao, Y, Liou, Y-C, Kang, SM: Two-step projection methods for a system of variational inequality problems in Banach spaces. J. Glob. Optim. 55(4), 801-811 (2013)
Zhao, J, Yang, Q: Several solution methods for the split feasibility problem. Inverse Probl. 21(5), 1791-1799 (2005)
Rockafellar, RT, Wets, R: Variational Analysis. Springer, Berlin (1988)
Lopez, G, Martin-Marquez, V, Wang, F, Xu, H-K: Solving the split feasibility problem without prior knowledge of matrix norms. Inverse Probl. 28, Article ID 085004 (2012)
Moudafi, A, Thakur, BS: Solving proximal split feasibility problems without prior knowledge of operator norms. Optim. Lett. 8, 2099-2110 (2014). doi:10.1007/s11590-013-0708-4
Luke, DR, Burke, JV, Lyon, RG: Optical wavefront reconstruction: theory and numerical methods. SIAM Rev. 44, 169-224 (2002)
Hundal, H: An alternating projection that does not converge in norm. Nonlinear Anal. 57, 35-61 (2004)
Bauschke, HH, Burke, JV, Deutsch, FR, Hundal, HS, Vanderwerff, JD: A new proximal point iteration that converges weakly but not in norm. Proc. Am. Math. Soc. 133, 1829-1835 (2005)
Bauschke, HH, Matouskova, E, Reich, S: Projections and proximal point methods: convergence results and counterexamples. Nonlinear Anal. 56, 715-738 (2004)
Matouskova, E, Reich, S: The Hundal example revisited. J. Nonlinear Convex Anal. 4, 411-427 (2003)
Shehu, Y: Approximation of common solutions to proximal split feasibility problems and fixed point problems. Fixed Point Theory (accepted)
Shehu, Y: Iterative methods for convex proximal split feasibility problems and fixed point problems. Afr. Math. (2015). doi:10.1007/s13370-015-0344-5
Shehu, Y, Ogbuisi, FU: Convergence analysis for proximal split feasibility problems and fixed point problems. J. Appl. Math. Comput. 48, 221-239 (2015)
Xu, H-K: Iterative algorithm for nonlinear operators. J. Lond. Math. Soc. 66(2), 1-17 (2002)
Luke, DR: Finding best approximation pairs relative to a convex and prox-regular set in Hilbert space. SIAM J. Optim. 19(2), 714-729 (2008)
Clarke, ZFH, Ledyaev, YS, Stern, RJ, Wolenski, PR: Nonsmooth Analysis and Control Theory. Springer, New York (1998)
Brézis, H: Analyse Fonctionnelle: Théorie et Applications. Masson, Paris (1983)
Acknowledgements
This work was supported by the NSF of China (No. 11401063) and Natural Science Foundation of Chongqing (cstc2014jcyjA00016).
Author information
Authors and Affiliations
Corresponding author
Additional information
Competing interests
The authors declare that there is no conflict of interests regarding this manuscript.
Authors’ contributions
All authors contributed equally to the writing of this paper. All authors read and approved the final manuscript.
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., Cai, G. & Iyiola, O.S. Iterative approximation of solutions for proximal split feasibility problems. Fixed Point Theory Appl 2015, 123 (2015). https://doi.org/10.1186/s13663-015-0375-5
Received:
Accepted:
Published:
DOI: https://doi.org/10.1186/s13663-015-0375-5