Abstract

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.

Author information

Contact details are reproduced from the original publication and may be historical.

Andrzej Cegielski

Faculty of Mathematics, Computer Science and Econometrics, University of Zielona Góra, Zielona Góra, Poland

a.cegielski@wmie.uz.zgora.pl

Keywords

  • Split feasibility problem
  • surrogate constraints
  • Fejér monotonicity
  • convergence

Mathematics Subject Classification

65K05, 90C06, 90C25

References

  1. R. Aharoni, Y. Censor: Block-iterative projection methods for parallel computation of solutions to convex feasibility problems, Linear Algebra Appl. 120 (1989) 165–175.https://doi.org/10.1016/0024-3795(89)90375-3Google Scholar
  2. A. Auslender: Optimisation, Méthodes Numériques, Masson, Paris (1983).Google Scholar
  3. H. H. Bauschke, J. M. Borwein: On projection algorithms for solving convex feasibility problems, SIAM Rev. 38 (1996) 367–426.https://doi.org/10.1137/S0036144593251710Google Scholar
  4. D. Butnariu, Y. Censor: On the behavior of a block-iterative projection method for solving convex feasibility problems, Int. J. Comp. Math. 34 (1990) 79–94.https://doi.org/10.1080/00207169008803865Google Scholar
  5. C. Byrne: Iterative oblique projection onto convex sets and the split feasibility problem, Inverse Probl. 18 (2002) 441–453.https://doi.org/10.1088/0266-5611/18/2/310Google Scholar
  6. C. Byrne: A unified treatment of some iterative algorithms in signal processing and image reconstruction, Inverse Probl. 20 (2004) 103–120.https://doi.org/10.1088/0266-5611/20/1/006Google Scholar
  7. A. Cegielski: Projection methods for the linear split feasibility problems, Optimization (2007), to appear.https://doi.org/10.1080/02331930601124971Google Scholar
  8. A. Cegielski, R. Dylewski: Selection strategies in projection methods for convex minimization problems, Discuss. Math., Differ. Incl. Control Optim. 22 (2002) 97–123.https://doi.org/10.7151/dmdico.1034Google Scholar
  9. A. Cegielski, R. Dylewski: Residual selection in a projection method for convex minimization problems, Optimization 52 (2003) 211–220.https://doi.org/10.1080/0233193031000079883Google Scholar
  10. Y. Censor, T. Elfving: A multiprojection algorithm using Bregman projections in a product space, Numer. Algorithms 8 (1994) 221–239.https://doi.org/10.1007/BF02142692Google Scholar
  11. Y. Censor, D. Gordon, R. Gordon: Component averaging: An efficient iterative parallel algorithm for large and sparse unstructured problems, Parallel Comput. 27 (2001) 777–808.https://doi.org/10.1016/S0167-8191(00)00100-9Google Scholar
  12. K. Goebel, W. A. Kirk: Topics in Metric Fixed Point Theory, Cambrigde University Press, Cambridge (1990).https://doi.org/10.1017/CBO9780511526152Google Scholar
  13. H. W. Hamacher, K.-H. Küfer: Inverse radiation therapy planning – a multiple objective optimization approach, Discrete Appl. Math. 118 (2002) 145–161.https://doi.org/10.1016/S0166-218X(01)00261-XGoogle Scholar
  14. J.-B. Hiriart-Urruty, C. Lemaréchal: Convex Analysis and Minimization Algorithms. Part 1: Fundamentals, Springer, Berlin (1993).https://doi.org/10.1007/978-3-662-02796-7_1Google Scholar
  15. A. R. De Pierro, A. N. Iusem: A simultaneous projections method for linear inequalities, Linear Algebra Appl. 64 (1985) 243–253.https://doi.org/10.1016/0024-3795(85)90280-0Google Scholar
  16. Y. Xiao, D. Michalski, Y. Censor, J. M. Galvin: Inherent smoothness of intensity patterns for intensity modulated radiation therapy generated by simultaneous projection algorithm, Phys. Med. Biol. 49 (2004) 3227–3245.https://doi.org/10.1088/0031-9155/49/14/015Google Scholar
  17. K. Yang, K. G. Murty: New iterative methods for linear inequalities, J. Optimization Theory Appl. 72 (1992) 163–185.https://doi.org/10.1007/BF00939954Google Scholar

Suggested citation

A. Cegielski. “Convergence of the Projected Surrogate Constraints Method for the Linear Split Feasibility Problems.” Journal of Convex Analysis 14 (2007), No. 1, 169–183. https://doi.org/10.68381/jca14013

Download BibTeXPublished by Heldermann Verlag.

Published by Heldermann Verlag, 2007. Rights now held by Banach Press LLC.