Convergence of the Projected Surrogate Constraints Method for the Linear Split Feasibility Problems

A. Cegielski

Journal of convex analysis, Tome 14 (2007) no. 1, pp. 169-183

Résumé

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.