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.
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
References
S. Agmon,The relaxation method for linear inequalities, Cand. J. Math. 6, 382–392 (1954).
R. Aharoni, A. Berman, Y. Censor,An interior points algorithm for the convex feasibility problem, Adv. in Appl. Math. 4, 479–489 (1983).
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).
A. Auslender,Optimisation, Methodes Numériques, Mason, Paris (1976).
Y. Censor,Row-action methods for huge and sparse systems and their applications, SIAM Rev. 23, 444–446, (1981).
Y. Censor,Iterative methods for the convex feasibility problem, Annals of Discrete Math., 20, 83–91, (1984).
Y. Censor and A. Lent,Cyclic subgradient projections, Math. Programming 24, 233–235 (1982).
Y. Censor,Parallel application of block-iterative methods in medical imaging and radiation therapy, Mathematical Programming 42, 307–325 (1988).
G. Cimmino,Calcolo approsssimato per le soluzioni di sisteme di equazioni lineari, La Ricerca Scientifica XVI, 1, 326–333 (1938).
V. F. Dem'yanov and L. V. Vasil'ev,Nondifferentiable Optimization, Springer Verlag, Berlin (1985).
J. L. Goffin,The relaxation method for solving linear systems of inequalities, Math. Oper. Res. 5, 388–414 (1980).
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).
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).
A. N. Iusem and A. R. De Pierro,Convergence results for an accelerated nonlinear Cimmino algorithm, Numer. Math. 49, 367–378 (1986).
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).
S. Kaczmarz,Angenäherte Auflösung von Systemen linearer Gleichungen, Bull. Acad. Polon. Sci. Lett. A, 35, 355–357 (1937).
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).
T. S. Motzkin and I. J. Schoenberg,The relaxation method for linear inequalities, Canad. J. Math. 6, 393–404 (1954).
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).
G. Pierra,Decomposition through formalization in a product space, Mathematical Programming 28, 96–115 (1984).
A. R. De Pierro and A. N. Iusem,A simultaneous projections method for linear inequalities, Lin. Alg. Appl. 64, 243–253 (1985).
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).
N. Z. Shor,Minimization Methods for Nondifferentiable Functions, Springer-Verlag, Berlin (1983).
J. E. Spingarn,A primal-dual projection method for solving systems of linear inequalities, Lin. Alg. Applic. 65, 45–62 (1985).
Author information
Authors and Affiliations
Additional information
The research of the first author was partially supported by Ruhrgas under a NAVF grant.
Rights 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
Received:
Revised:
Issue Date:
DOI: https://doi.org/10.1007/BF02017349