Abstract
The classical problem of finding a point in the intersection of countably many closed and convex sets in a Hilbert space is considered. Extrapolated iterations of convex combinations of approximate projections onto subfamilies of sets are investigated to solve this problem. General hypotheses are made on the regularity of the sets and various strategies are considered to control the order in which the sets are selected. Weak and strong convergence results are established within thisbroad framework, which provides a unified view of projection methods for solving hilbertian convex feasibility problems.
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
References
Agmon S (1954) The relaxation method for linear inequalities. Canad J Math 6:382–392
Aharoni R, Berman A, Censor Y (1983) An interior points algorithm for the convex feasibility problem. Adv in Appl Math 4:479–489
Aharoni R, Censor Y (1989) Block-iterative methods for parallel computation of solutions to convex feasibility problems. Linear Algebra Appl 120:165–175
Alber Y, Butnariu D (1997) Convergence of Brègman-projection methods for solving consistent convex feasibility problems in reflexive Banach spaces. J Optim Theory Appl 92:33–61
Amemiya I, Ando T (1965) Convergence of random products of contractions in Hilbert space. Acta Sci Math (Szeged) 26:239–244
Auslender A (1969) Méthodes Numériques pour la Résolution des Problèmes d’Optimisation avec Contraintes. Thèse, Faculté des Sciences, Grenoble
Bauschke HH (1995) A norm convergence result on random products of relaxed projections in Hilbert space. Trans Amer Math Soc 347:1365–1373
Bauschke HH, Borwein JM (1996) On projection algorithms for solving convex feasibility problems. SIAM Rev 38:367–426
Bauschke HH, Borwein JM, Lewis AS (1996) On the method of cyclic projections for closed convex sets in Hilbert space. To appear in Contemporary Mathematics: Optimization and Nonlinear Analysis (Censor Y, Reich S, editors). American Mathematical Society, Providence, RI
Brègman LM (1965) The method of successive projection for finding a common point of convex sets. Soviet Math Dokl 6:688–692
Brézis H (1983) Analyse Fonctionnelle. Masson, Paris
Browder FE (1958) On some approximation methods for solutions of the Dirichlet problem for linear elliptic equations of arbitrary order. J Math Mech 7:69–80
Browder FE (1967) Convergence theorems for sequences of nonlinear operators in Banach spaces. Math Z 100:201–225
Bruck RE (1982) Random products of contractions in metric and Banach spaces. J Math Anal Appl 88:319–332
Butnariu D, Flåm SD (1995) Strong convergence of expected-projection methods in Hilbert spaces. Numer Funct Anal Optim 16:601–636
Censor Y (1981) Row-action methods for huge and sparse systems and their applications. SIAM Rev 23:444–466
Censor Y, Lent A (1982) Cyclic subgradient projections. Math Programming 24:233–235
Cheney W, Goldstein AA (1959) Proximity maps for convex sets. Proc Amer Math Soc 10:448–450
Cimmino G (1938) Calcolo approssimato per le soluzioni dei sistemi di equazioni lineari. Ricerca Sci (Roma) 1:326–333
Combettes PL (1993) The foundations of set theoretic estimation. Proc IEEE 81:182–208
Combettes PL (1995) Construction d’un point fixe commun à une famille de contractions fermes. C R Acad Sci Paris Sér I Math 320:1385–1390
Combettes PL (1996) The convex feasibility problem in image recovery. Advances in Imaging and Electron Physics (Hawkes P, editor), vol 95, pp 155–270. Academic Press, New York
Combettes PL, Puh H (1993) Extrapolated projection method for the euclidean convex feasibility problem. Research report, City University of New York
Combettes PL, Puh H (1994) Iterations of parallel convex projections in Hilbert spaces. Numer Funct Anal Optim 15:225–243
Combettes PL, Trussell HJ (1990) Method of successive projections for finding a common point of sets in metric spaces. J Optim Theory Appl 67:487–507
Crombez G (1991) Image recovery by convex combinations of projections. J Math Anal Appl 155:413–419
De Pierro AR, Iusem AN (1985) A parallel projection method for finding a common point of a family of convex sets. Pesqui Oper 5:1–20
De Pierro AR, Iusem AN (1988) A finitely convergent “row-action” method for the convex feasibility problem. Appl Math Optim 17:225–235
Deutsch F (1992) The method of alternating orthogonal projections. In Approximation Theory, Spline Functions and Application (Singh SP, editor), pp 105–121. Kluwer, The Netherlands
Dye JM, Reich S (1992) Unrestricted iterations of nonexpansive mappings in Hilbert space. Nonlinear Anal 18:199–207
Eremin II (1965) Generalization of the relaxation method of Motzkin-Agmon. Uspekhi Mat Nauk 20:183–187
Flåm SD, Zowe J (1990) Relaxed outer projections, weighted averages, and convex feasibility. BIT 30:289–300
Gurin (Gubin) LG, Polyak BT, Raik EV (1967) The method of projections for finding the common point of convex sets. USSR Comput Math and Math Phys 7:1–24
Halperin I (1962) The product of projection operators. Acta Sci Math (Szeged) 23:96–99
Iusem AN, De Pierro AR (1986) Convergence results for an accelerated nonlinear Cimmino algorithm. Numer Math 49:367–378
Iusem AN, Moledo L (1986) A finitely convergent method of simultaneous subgradient projections for the convex feasibility problem. Mat Apl Comput 5:169–184
Kaczmarz S (1937) Angenäherte Auflösung von Systemen linearer Gleichungen. Bull Acad Sci Pologne A35:355–357.
Kiwiel KC (1995) Block-iterative surrogate projection methods for convex feasibility problems. Linear Algebra Appl 215:225–259
Levitin ES, Polyak BT (1966) Convergence of minimizing sequences in conditional extremum problems. Soviet Math Dokl 7:764–767
Merzlyakov YI (1963) On a relaxation method of solving systems of linear inequalities. USSR Comput Math and Math Phys 2:504–510
Motzkin TS, Schoenberg IJ (1954) The relaxation method for linear inequalities. Canad J Math 6:393–404
Nashed MZ (1981) Continuous and semicontinuous analogues of iterative methods of Cimmino and Kaczmarz with applications to the inverse Radon transform. Lectures Notes in Medical Informatics (Herman GT, Natterer F, editors), vol 8, pp 160–178. Springer-Verlag, New York
Ottavy N (1988) Strong convergence of projection-like methods in Hilbert spaces. J Optim Theory Appl 56:433–461
Pierra G (1975) Méthodes de projections parallèles extrapolées relatives à une intersection de convexes. Rapport de Recherche, INPG, Grenoble
Pierra G (1984) Decomposition through formalization in a product space. Math Programming 28:96–115
Pierra G, Ottavy N (1988) New parallel projection methods for linear varieties and applications. Presented at the XIIth International Symposium on Mathematical Programming, Tokyo
Poincaré H (1890) Sur les équations aux dérivées partielles de la physique mathématique. Amer J Math 12:211–294
Polyak BT (1969) Minimization of unsmooth functionals. USSR Comput Math and Math Phys 9:14–29
Práger M (1960) On a principle of convergence in Hilbert space. Czechoslovak Math J 10:271–282
Reich S (1983) A limit theorem for projections. Linear and Multilinear Algebra 13:281–290
Stiles WJ (1965) Closest point maps and their product II. Nieuw Arch Wisk 13:212–225
Tseng P (1992) On the convergence of products of firmly nonexpansive mappings. SIAM J Optim 2:425–434
Tsent P, Bertsekas DP (1987) Relaxation methods for problems with strictly convex separable costs and linear constraints. Math Programming 38:303–321
Von Neumann J (1949) On rings of operators. Reduction theory. Ann of Math 50:401–485 (th result of interest first appeared in 1933 in lecture notes)
Zarantonello EH (1971) Projections on convex sets in Hilbert space and spectral theory. In Contributions to Nonlinear Functional Analysis (Zarantonello EH editor), pp 237–424. Academic Press, New York
Author information
Authors and Affiliations
Additional information
This work was supported by the National Science Foundation under Grant MIP-9308609.
Rights and permissions
About this article
Cite this article
Combettes, P.L. Hilbertian convex feasibility problem: Convergence of projection methods. Appl Math Optim 35, 311–330 (1997). https://doi.org/10.1007/BF02683333
Accepted:
Issue Date:
DOI: https://doi.org/10.1007/BF02683333
Key Words
- Alternating projections
- Boundedly regular sets
- Chaotic iterations
- Convergence
- Convex feasibility problem
- Convex sets
- Extrapolated projections
- Fejér-monotone sequences
- Hilbert spaces
- Parallel projections
- Relaxations
- Successive projections