
Journal of Convex Analysis 14 (2007), No. 1, 169183 Copyright Heldermann Verlag 2007 Convergence of the Projected Surrogate Constraints Method for the Linear Split Feasibility Problems Andrzej Cegielski Faculty of Mathematics, Computer Science and Econometrics, University of Zielona Góra, Zielona Góra, Poland a.cegielski@wmie.uz.zgora.pl The surrogate constraints method (SCmethod) for linear feasibility problems (LFP) is an important tool in convex optimization, especially in large scale optimization. The classical version of the SCmethod converges to a solution if the LFP is feasible [see K. Yang and K. G. Murty, J. Optim. Theory Appl. 72 (1992) 163185]. Unfortunately, in applications the LFP is often infeasible. Such a situation occurs in computer tomography and in intensity modulated radiation therapy which can be modelled as LFP [see C. Byrne, Inverse Problems 18 (2002) 441453; or Y. Censor, D. Gordon and R. Gordon, Parallel Computing 27 (2001) 777808; or H. W. Hamacher and K.H. Küfer, Discrete Applied Mathematics 118 (2002) 145161; or Y. Xiao, D. Michalski, Y. Censor and J. M. Galvin, Physics in Medicine and Biology 49 (2004) 32273245]. In this case one can apply the simultaneous projection method (SPmethod) [see A. Auslender, "Optimisation, Méthodes Numériques", Mason, Paris 1983; or D. Butnariu and Y. Censor, Int. J. Comp. Math. 34 (1990) 7994; A. R. De Pierro and A. N. Iusem, Linear Algebra and Applications 64 (1985) 243252] which is actually a short step version of a special case of the SCmethod [see A. Cegielski, "Projection methods for the linear split feasibility problems", submitted]. The SPmethod converges to a solution if the LFP is feasible and to an approximate solution in other case. Because of long steps, the SCmethod converges faster than the SPmethod if the LFP is feasible. Unfortunately, the SCmethod diverges if the problem is infeasible. We deal in this paper with the linear split feasibility problems (LSFP) which are more general than the LFP. We analyze the convergence of various versions of the projected surrogate constraints method (PSCmethod) for the LSFP in dependence on the step size and on the choice of weights. We show also that the convergence of the SCmethod of YangMurty [see K. Yang and K. G. Murty, J. Optim. Theory Appl. 72 (1992) 163185] and of the CQmethod of C. Byrne [Inverse Problems 18 (2002) 441453] applied to the LSFP follows from our main result. Keywords: Split feasibility problem, surrogate constraints, Fejér monotonicity, convergence. MSC: 65K05, 90C06, 90C25 [ Fulltextpdf (142 KB)] for subscribers only. 