Skip to main content
SpringerLink
Log in

Relaxed outer projections, weighted averages and convex feasibility

  • Part II Numerical Mathematics
  • Published:
BIT Aims and scope Submit manuscript

Abstract

A new algorithmic scheme is proposed for finding a common point of finitely many closed convex sets. The scheme uses weighted averages (convex combinations) of relaxed projections onto approximating halfspaces. By varying the weights we generalize Cimmino's and Auslender's methods as well as more recent versions developed by Iusem & De Pierro and Aharoni & Censor. Our approach offers great computational flexibility and encompasses a wide variety of known algorithms as special instances. Also, since it is “block-iterative”, it lends itself to parallel processing.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Similar content being viewed by others

References

  1. S. Agmon,The relaxation method for linear inequalities, Cand. J. Math. 6, 382–392 (1954).

    MATH  MathSciNet  Google Scholar 

  2. R. Aharoni, A. Berman, Y. Censor,An interior points algorithm for the convex feasibility problem, Adv. in Appl. Math. 4, 479–489 (1983).

    Article  MATH  MathSciNet  Google Scholar 

  3. R. Aharoni and Y. Censor,Block-iterative projection methods for parallel computation of solutions to convex feasibility problems, to appear in Linear Algebra and its Applications (1989).

  4. A. Auslender,Optimisation, Methodes Numériques, Mason, Paris (1976).

    MATH  Google Scholar 

  5. Y. Censor,Row-action methods for huge and sparse systems and their applications, SIAM Rev. 23, 444–446, (1981).

    Article  MATH  MathSciNet  Google Scholar 

  6. Y. Censor,Iterative methods for the convex feasibility problem, Annals of Discrete Math., 20, 83–91, (1984).

    MathSciNet  Google Scholar 

  7. Y. Censor and A. Lent,Cyclic subgradient projections, Math. Programming 24, 233–235 (1982).

    Article  MATH  MathSciNet  Google Scholar 

  8. Y. Censor,Parallel application of block-iterative methods in medical imaging and radiation therapy, Mathematical Programming 42, 307–325 (1988).

    Article  MATH  MathSciNet  Google Scholar 

  9. G. Cimmino,Calcolo approsssimato per le soluzioni di sisteme di equazioni lineari, La Ricerca Scientifica XVI, 1, 326–333 (1938).

    Google Scholar 

  10. V. F. Dem'yanov and L. V. Vasil'ev,Nondifferentiable Optimization, Springer Verlag, Berlin (1985).

    Google Scholar 

  11. J. L. Goffin,The relaxation method for solving linear systems of inequalities, Math. Oper. Res. 5, 388–414 (1980).

    Article  MATH  MathSciNet  Google Scholar 

  12. J. L. Goffin,Acceleration in the relaxation method for linear inequalities and subgradient optimization, in Progress in Nondifferentiable Optimization, IIASA Proceeding Series, Pergamon, Oxford (1978).

  13. L. G. Gubin, B. T. Polyak and E. V. Raik,The method of projections for finding the common point of convex sets, USSR Comp. Math. and Math. Phys. 7, 1–24 (1967).

    Article  Google Scholar 

  14. A. N. Iusem and A. R. De Pierro,Convergence results for an accelerated nonlinear Cimmino algorithm, Numer. Math. 49, 367–378 (1986).

    Article  MATH  MathSciNet  Google Scholar 

  15. A. N. Iusem and A. R. De Pierro,A simultaneous iterative method for computing projections on ployhedra, SIAM J. Control and Optimization, 25, 231–243 (1987).

    Article  MATH  MathSciNet  Google Scholar 

  16. S. Kaczmarz,Angenäherte Auflösung von Systemen linearer Gleichungen, Bull. Acad. Polon. Sci. Lett. A, 35, 355–357 (1937).

    Google Scholar 

  17. J. M. Martinez and R. J. B. De Sampaio,Parallel and sequential Kaczmarz methods for solving underdetermined nonlinear equations, J. Comput. Appl. Math. 5, 311–321 (1986).

    Article  Google Scholar 

  18. T. S. Motzkin and I. J. Schoenberg,The relaxation method for linear inequalities, Canad. J. Math. 6, 393–404 (1954).

    MATH  MathSciNet  Google Scholar 

  19. W. Oettli,Symmetric duality and convergent subgradient methods for discrete, linear, constrained approximation problems with arbitrary norms appearing in the objective function and in the constraints, J. Approx. Theory, 14, 43–50 (1975).

    Article  MATH  MathSciNet  Google Scholar 

  20. G. Pierra,Decomposition through formalization in a product space, Mathematical Programming 28, 96–115 (1984).

    Article  MATH  MathSciNet  Google Scholar 

  21. A. R. De Pierro and A. N. Iusem,A simultaneous projections method for linear inequalities, Lin. Alg. Appl. 64, 243–253 (1985).

    Article  MATH  Google Scholar 

  22. A. R. De Pierro and A. N. Iusem,A finitely convergent rowaction method for the convex feasibility problem, Appl. Math. Optim. 17, 225–235 (1988).

    Article  MATH  MathSciNet  Google Scholar 

  23. N. Z. Shor,Minimization Methods for Nondifferentiable Functions, Springer-Verlag, Berlin (1983).

    Google Scholar 

  24. J. E. Spingarn,A primal-dual projection method for solving systems of linear inequalities, Lin. Alg. Applic. 65, 45–62 (1985).

    Article  MATH  MathSciNet  Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Dep. of Economics, Univ. of Bergen, N-5008, Bergen, Norway

    Sjur D. Flåm & Jochem Zowe

  2. Dep. of Mathematics, Univ. of Bayreuth, D-8580, BRD

    Sjur D. Flåm & Jochem Zowe

Authors
  1. Sjur D. Flåm
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Jochem Zowe
    View author publications

    You can also search for this author in PubMed Google Scholar

Additional information

The research of the first author was partially supported by Ruhrgas under a NAVF grant.

Rights and permissions

Reprints and permissions

About this article

Cite this article

Flåm, S.D., Zowe, J. Relaxed outer projections, weighted averages and convex feasibility. BIT 30, 289–300 (1990). https://doi.org/10.1007/BF02017349

Download citation

  • Received:

  • Revised:

  • Issue Date:

  • DOI: https://doi.org/10.1007/BF02017349

CR categories

Key words

Search

Navigation