Perturbed projections and subgradient projections for the multiple-sets split feasibility problem. (English) Zbl 1253.90211

Summary: We study the multiple-sets split feasibility problem that requires to find a point closest to a family of closed convex sets in one space such that its image under a linear transformation will be closest to another family of closed convex sets in the image space. By casting the problem into an equivalent problem in a suitable product space we are able to present a simultaneous subgradients projections algorithm that generates convergent sequences of iterates in the feasible case. We further derive and analyze a perturbed projection method for the multiple-sets split feasibility problem and, additionally, furnish alternative proofs to two known results.


90C30 Nonlinear programming
65K10 Numerical optimization and variational techniques
90C47 Minimax problems in mathematical programming
Full Text: DOI


[1] Baillon, J.B.; Bruck, R.E.; Reich, S., On the asymptotic behavior of nonexpansive mappings and semigroups in Banach spaces, Houston J. math., 4, 1-9, (1978) · Zbl 0396.47033
[2] Bauschke, H.H.; Borwein, J.M., On projection algorithms for solving convex feasibility problems, SIAM rev., 38, 367-426, (1996) · Zbl 0865.47039
[3] Bauschke, H.H.; Combettes, P.L.; Kruk, S.G., Extrapolation algorithm for affine-convex feasibility problems, Numer. algorithms, 41, 239-274, (2006) · Zbl 1098.65060
[4] Bruck, R.E.; Reich, S., Nonexpansive projections and resolvents of accretive operators in Banach spaces, Houston J. math., 3, 459-470, (1977) · Zbl 0383.47035
[5] Byrne, C., Bregman – legendre multidistance projection algorithms for convex feasibility and optimization, (), 87-100 · Zbl 0990.90094
[6] Byrne, C., Iterative oblique projection onto convex sets and the split feasibility problem, Inverse problems, 18, 441-453, (2002) · Zbl 0996.65048
[7] Byrne, C., A unified treatment of some iterative algorithms in signal processing and image reconstruction, Inverse problems, 20, 103-120, (2004) · Zbl 1051.65067
[8] Byrne, C.; Censor, Y., Proximity function minimization using multiple Bregman projections, with applications to split feasibility and kullback – leibler distance minimization, Ann. oper. res., 105, 77-98, (2001) · Zbl 1012.90035
[9] A. Cegielski, Convergence of the projected surrogate constraints method for the linear split feasibility problems, J. Convex Anal. 14 (2007), in press · Zbl 1128.65039
[10] A. Cegielski, Projection methods for the linear split feasibility problems, Technical Report, September 14, 2004, Institute of Mathematics, University of Zielona Góra, Zielona Góra, Poland · Zbl 1148.65037
[11] Censor, Y., Row-action methods for huge and sparse systems and their applications, SIAM rev., 23, 444-466, (1981) · Zbl 0469.65037
[12] Censor, Y.; Bortfeld, T.; Martin, B.; Trofimov, A., A unified approach for inversion problems in intensity-modulated radiation therapy, Phys. medicine biology, 51, 2353-2365, (2006)
[13] Censor, Y.; Elfving, T., A multiprojection algorithm using Bregman projections in a product space, Numer. algorithms, 8, 221-239, (1994) · Zbl 0828.65065
[14] 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
[15] Censor, Y.; Gordon, D.; Gordon, R., BICAV: A block-iterative, parallel algorithm for sparse systems with pixel-related weighting, IEEE trans. medical imaging, 20, 1050-1060, (2001)
[16] Censor, Y.; Lent, A., Cyclic subgradient projections, Math. programming, 24, 233-235, (1982) · Zbl 0491.90077
[17] Censor, Y.; Zenios, S.A., Parallel optimization: theory, algorithms, and applications, (1997), Oxford University Press New York · Zbl 0945.90064
[18] Crombez, G., Non-monotoneous parallel iteration for solving convex feasibility problems, Kybernetika, 39, 547-560, (2003) · Zbl 1249.65040
[19] G. Crombez, A sequential iteration algorithm with non-monotoneous behaviour in the method of projections onto convex sets, Czechoslovak Math. J., in press · Zbl 1164.47399
[20] Golshtein, E.; Tretyakov, N., Modified Lagrangians and monotone maps in optimization, (1996), John Wiley & Sons New York · Zbl 0848.49001
[21] Aslam Noor, M., Some developments in general variational inequalities, Appl. math. comput., 152, 197-277, (2004) · Zbl 1134.49304
[22] Pierra, G., Decomposition through formalization in a product space, Math. programming, 28, 96-115, (1984) · Zbl 0523.49022
[23] Qu, B.; Xiu, N., A note on the CQ algorithm for the split feasibility problem, Inverse problems, 21, 1655-1665, (2005) · Zbl 1080.65033
[24] Reich, S., Averaged mappings in the Hilbert ball, J. math. anal. appl., 109, 199-206, (1985) · Zbl 0588.47061
[25] P.S.M. Santos and S. Scheimberg, A projection algorithm for general variational inequalities with perturbed constraint sets, Appl. Math. Comput. (2006), in press · Zbl 1148.65308
[26] Stark, H.; Yang, Y., Vector space projections: A numerical approach to signal and image processing, neural nets, and optics, (1998), John Wiley & Sons New York · Zbl 0903.65001
[27] Yamada, I., Hybrid steepest descent method for variational inequality problem over the fixed point set of certain quasi-nonexpansive mappings, Numer. funct. anal. optim., 25, 619-655, (2004) · Zbl 1095.47049
[28] Yang, Q., The relaxed CQ algorithm solving the split feasibility problem, Inverse problems, 20, 1261-1266, (2004) · Zbl 1066.65047
[29] Yang, Q., On variable-step relaxed projection algorithm for variational inequalities, J. math. anal. appl., 302, 166-179, (2005) · Zbl 1056.49018
[30] Yang, Q.; Zhao, J., Generalized KM theorems and their applications, Inverse problems, 22, 833-844, (2006) · Zbl 1117.65081
[31] Zhao, J.; Yang, Q., Several solution methods for the split feasibility problem, Inverse problems, 21, 1791-1799, (2005) · Zbl 1080.65035
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.