Modified projection methods for the split feasibility problem and the multiple-sets split feasibility problem. (English) Zbl 1291.90179

Summary: The split feasibility problem is to find \(x\in C\) with \(Ax\in Q\), if such points exist, where \(A\) is a given \(M\times N\) real matrix, \(C\) and \(Q\) are nonempty closed convex sets in \(\mathbb{R}^{N}\) and \(\mathbb{R}^{M}\), respectively. C. Byrne [Inverse Probl. 18, No. 2, 441–453 (2002; Zbl 0996.65048)] proposed a well-known CQ algorithm for solving this problem. In this paper, we propose a modification for the CQ algorithm, which computes the stepsize adaptively, and performs an additional projection step onto some simple closed convex set \(X\subseteq \mathbb{R}^{N}\) in each iteration. We further give a relaxation scheme for this modification to make it more easily implemented. Convergence results of both algorithms are analyzed, and preliminary numerical results are reported. We also extend these modified algorithms to solve the multiple-sets split feasibility problem, which is to find a point closest to the intersection of a family of closed convex sets in one space such that its image under a linear transformation will be closest to the intersection of another family of closed convex sets in the image space.


90C25 Convex programming
47J25 Iterative procedures involving nonlinear operators


Zbl 0996.65048
Full Text: DOI


[1] Censor, Y.; Elfving, T., A multiprojection algorithm using Bregman projections in a product space, Numer. algor., 8, 221-239, (1994) · Zbl 0828.65065
[2] Byrne, C., Iterative oblique projection onto convex sets and the split feasibility problem, Inverse problems, 18, 441-453, (2002) · Zbl 0996.65048
[3] Byrne, C., A unified treatment of some iterative algorithms in signal processing and image reconstruction, Inverse problems, 20, 103-120, (2004) · Zbl 1051.65067
[4] Qu, B.; Xiu, N., A note on the CQ algorithm for the split feasibility problem, Inverse problems, 21, 1655-1665, (2005) · Zbl 1080.65033
[5] Qu, B.; Xiu, N., A new halfspace-relaxation projection method for the split feasibility problem, Linear algebr. appl., 428, 1218-1229, (2008) · Zbl 1135.65022
[6] Yang, Q., The relaxed CQ algorithm solving the split feasibility problem, Inverse problems, 20, 1261-1266, (2004) · Zbl 1066.65047
[7] Censor, Y.; Elfving, T.; Kopf, N.; Bortfeld, T., The multiple-sets split feasibility problem and its applications for inverse problems, Inverse problems, 21, 2071-2084, (2005) · Zbl 1089.65046
[8] W. Zhang, D. Han, Z. Li, A self-adaptive projection method for solving the multiple-sets split feasibility problem, Inverse Problems 25 (2009) 115001 (16pp). · Zbl 1185.65102
[9] He, B.; He, X.; Liu, H.; Wu, T., Self-adaptive projection method for co-coercive variational inequalities, Eur. J. operat. res., 196, 43-48, (2009) · Zbl 1163.58305
[10] Tseng, P., A modified forward – backward splitting method for maximal monotone mappings, SIAM J. control optim., 38, 431-446, (2000) · Zbl 0997.90062
[11] E.H. Zarantonello, Projections on convex sets in Hilbert space and spectral theory, Contributions to Nonlinear Functional Analysis, ed E.H. Zarantonello (New York: Academic), 1971. · Zbl 0281.47043
[12] Iusem, A.N., An iterative algorithm for the variational inequality problem, Mat. appl. comput., 13, 103-114, (1994) · Zbl 0811.65049
[13] Korpelevich, G.M., The extragradient method for finding saddle points and other problems, Matecon, 12, 747-756, (1976) · Zbl 0342.90044
[14] M.V. Solodov, P. Tseng, Modified projection-type methods for monotone variational inequalities, SIAM J. Control Optim. 34 (1996) No. 5, 1814-1830. · Zbl 0866.49018
[15] Fukushima, M., On the convergence of a class of outer approximation algorithms for convex programs, J. comput. appl. math., 10, 147-156, (1984) · Zbl 0532.65047
[16] Fukushima, M., A relaxed projection method for variational inequalities, Math. program., 35, 58-70, (1986) · Zbl 0598.49024
[17] He, B., Inexact implicit methods for monotone general variational inequalities, Math. program., 86, 199-217, (1999) · Zbl 0979.49006
[18] Rockafellar, R.T., Convex analysis, (1970), Princeton University Press Princeton, NJ · Zbl 0229.90020
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.