Journal of Convex Analysis 14 (2007), No. 1, 169--183
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 (SC-method) for linear feasibility problems (LFP) is an important tool in convex optimization, especially in large scale optimization. The classical version of the SC-method converges to a solution if the LFP is feasible [see K. Yang and K. G. Murty, J. Optim. Theory Appl. 72 (1992) 163--185]. 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) 441--453; or Y. Censor, D. Gordon and R. Gordon, Parallel Computing 27 (2001) 777--808; or H. W. Hamacher and K.-H. Küfer, Discrete Applied Mathematics 118 (2002) 145--161; or Y. Xiao, D. Michalski, Y. Censor and J. M. Galvin, Physics in Medicine and Biology 49 (2004) 3227--3245]. In this case one can apply the simultaneous projection method (SP-method) [see A. Auslender, "Optimisation, Méthodes Numériques", Mason, Paris 1983; or D. Butnariu and Y. Censor, Int. J. Comp. Math. 34 (1990) 79--94; A. R. De Pierro and A. N. Iusem, Linear Algebra and Applications 64 (1985) 243--252] which is actually a short step version of a special case of the SC-method [see A. Cegielski, "Projection methods for the linear split feasibility problems", submitted]. The SP-method converges to a solution if the LFP is feasible and to an approximate solution in other case. Because of long steps, the SC-method converges faster than the SP-method if the LFP is feasible. Unfortunately, the SC-method 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 (PSC-method) for the LSFP in dependence on the step size and on the choice of weights. We show also that the convergence of the SC-method of Yang-Murty [see K. Yang and K. G. Murty, J. Optim. Theory Appl. 72 (1992) 163--185] and of the CQ-method of C. Byrne [Inverse Problems 18 (2002) 441--453] applied to the LSFP follows from our main result.
Keywords: Split feasibility problem, surrogate constraints, Fejér monotonicity, convergence.
MSC: 65K05, 90C06, 90C25
[ Fulltext-pdf (142 KB)] for subscribers only.