Hilbertian convex feasibility problem: Convergence of projection methods. (English) Zbl 0872.90069
Summary: 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 this broad framework, which provides a unified view of projection methods for solving Hilbertian convex feasibility problems.
MSC:
| 90C25 | Convex programming |
| 52A41 | Convex functions and convex programs in convex geometry |
| 65J05 | General theory of numerical analysis in abstract spaces |
| 40A05 | Convergence and divergence of series and sequences |
| 90C48 | Programming in abstract spaces |
Keywords:
alternating projections; boundedly regular sets; chaotic iterations; convex feasibility problem; weak and strong convergence results; intersection of countably many closed and convex sets; Hilbert space; convex combinations of approximate projectionsReferences:
| [1] | Agmon S (1954) The relaxation method for linear inequalities. Canad J Math 6:382–392 · Zbl 0055.35001 · doi:10.4153/CJM-1954-037-2 |
| [2] | Aharoni R, Berman A, Censor Y (1983) An interior points algorithm for the convex feasibility problem. Adv in Appl Math 4:479–489 · Zbl 0489.52005 · doi:10.1016/0196-8858(83)90019-2 |
| [3] | Aharoni R, Censor Y (1989) Block-iterative methods for parallel computation of solutions to convex feasibility problems. Linear Algebra Appl 120:165–175 · Zbl 0679.65046 · doi:10.1016/0024-3795(89)90375-3 |
| [4] | 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 · Zbl 0886.90179 · doi:10.1023/A:1022631928592 |
| [5] | Amemiya I, Ando T (1965) Convergence of random products of contractions in Hilbert space. Acta Sci Math (Szeged) 26:239–244 · Zbl 0143.16202 |
| [6] | Auslender A (1969) Méthodes Numériques pour la Résolution des Problèmes d’Optimisation avec Contraintes. Thèse, Faculté des Sciences, Grenoble |
| [7] | Bauschke HH (1995) A norm convergence result on random products of relaxed projections in Hilbert space. Trans Amer Math Soc 347:1365–1373 · Zbl 0832.47055 · doi:10.1090/S0002-9947-1995-1257097-1 |
| [8] | Bauschke HH, Borwein JM (1996) On projection algorithms for solving convex feasibility problems. SIAM Rev 38:367–426 · Zbl 0865.47039 · doi:10.1137/S0036144593251710 |
| [9] | 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 |
| [10] | Brègman LM (1965) The method of successive projection for finding a common point of convex sets. Soviet Math Dokl 6:688–692 · Zbl 0142.16804 |
| [11] | Brézis H (1983) Analyse Fonctionnelle. Masson, Paris · Zbl 0511.46001 |
| [12] | 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 · Zbl 0108.10003 |
| [13] | Browder FE (1967) Convergence theorems for sequences of nonlinear operators in Banach spaces. Math Z 100:201–225 · Zbl 0149.36301 · doi:10.1007/BF01109805 |
| [14] | Bruck RE (1982) Random products of contractions in metric and Banach spaces. J Math Anal Appl 88:319–332 · Zbl 0512.47042 · doi:10.1016/0022-247X(82)90195-0 |
| [15] | Butnariu D, Flåm SD (1995) Strong convergence of expected-projection methods in Hilbert spaces. Numer Funct Anal Optim 16:601–636 · Zbl 0834.65041 · doi:10.1080/01630569508816635 |
| [16] | Censor Y (1981) Row-action methods for huge and sparse systems and their applications. SIAM Rev 23:444–466 · Zbl 0469.65037 · doi:10.1137/1023097 |
| [17] | Censor Y, Lent A (1982) Cyclic subgradient projections. Math Programming 24:233–235 · Zbl 0491.90077 · doi:10.1007/BF01585107 |
| [18] | Cheney W, Goldstein AA (1959) Proximity maps for convex sets. Proc Amer Math Soc 10:448–450 · Zbl 0092.11403 · doi:10.1090/S0002-9939-1959-0105008-8 |
| [19] | Cimmino G (1938) Calcolo approssimato per le soluzioni dei sistemi di equazioni lineari. Ricerca Sci (Roma) 1:326–333 · JFM 64.1244.02 |
| [20] | Combettes PL (1993) The foundations of set theoretic estimation. Proc IEEE 81:182–208 · doi:10.1109/5.214546 |
| [21] | 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 · Zbl 0830.65047 |
| [22] | 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 |
| [23] | Combettes PL, Puh H (1993) Extrapolated projection method for the euclidean convex feasibility problem. Research report, City University of New York |
| [24] | Combettes PL, Puh H (1994) Iterations of parallel convex projections in Hilbert spaces. Numer Funct Anal Optim 15:225–243 · Zbl 0814.46064 · doi:10.1080/01630569408816563 |
| [25] | 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 · Zbl 0696.90052 · doi:10.1007/BF00939646 |
| [26] | Crombez G (1991) Image recovery by convex combinations of projections. J Math Anal Appl 155:413–419 · Zbl 0752.65045 · doi:10.1016/0022-247X(91)90010-W |
| [27] | 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 |
| [28] | De Pierro AR, Iusem AN (1988) A finitely convergent ”row-action” method for the convex feasibility problem. Appl Math Optim 17:225–235 · Zbl 0655.65085 · doi:10.1007/BF01448368 |
| [29] | 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 · Zbl 0751.41031 |
| [30] | Dye JM, Reich S (1992) Unrestricted iterations of nonexpansive mappings in Hilbert space. Nonlinear Anal 18:199–207 · Zbl 0753.47024 · doi:10.1016/0362-546X(92)90094-U |
| [31] | Eremin II (1965) Generalization of the relaxation method of Motzkin-Agmon. Uspekhi Mat Nauk 20:183–187 · Zbl 0254.65049 |
| [32] | Flåm SD, Zowe J (1990) Relaxed outer projections, weighted averages, and convex feasibility. BIT 30:289–300 · Zbl 0715.65038 · doi:10.1007/BF02017349 |
| [33] | 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 |
| [34] | Halperin I (1962) The product of projection operators. Acta Sci Math (Szeged) 23:96–99 · Zbl 0143.16102 |
| [35] | Iusem AN, De Pierro AR (1986) Convergence results for an accelerated nonlinear Cimmino algorithm. Numer Math 49:367–378 · Zbl 0571.65051 · doi:10.1007/BF01389537 |
| [36] | Iusem AN, Moledo L (1986) A finitely convergent method of simultaneous subgradient projections for the convex feasibility problem. Mat Apl Comput 5:169–184 · Zbl 0625.90079 |
| [37] | Kaczmarz S (1937) Angenäherte Auflösung von Systemen linearer Gleichungen. Bull Acad Sci Pologne A35:355–357. · Zbl 0017.31703 |
| [38] | Kiwiel KC (1995) Block-iterative surrogate projection methods for convex feasibility problems. Linear Algebra Appl 215:225–259 · Zbl 0821.65037 · doi:10.1016/0024-3795(93)00089-I |
| [39] | Levitin ES, Polyak BT (1966) Convergence of minimizing sequences in conditional extremum problems. Soviet Math Dokl 7:764–767 · Zbl 0161.07002 |
| [40] | Merzlyakov YI (1963) On a relaxation method of solving systems of linear inequalities. USSR Comput Math and Math Phys 2:504–510 · Zbl 0123.11204 · doi:10.1016/0041-5553(63)90463-4 |
| [41] | Motzkin TS, Schoenberg IJ (1954) The relaxation method for linear inequalities. Canad J Math 6:393–404 · Zbl 0055.35002 · doi:10.4153/CJM-1954-038-x |
| [42] | 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 · Zbl 0544.65090 |
| [43] | Ottavy N (1988) Strong convergence of projection-like methods in Hilbert spaces. J Optim Theory Appl 56:433–461 · Zbl 0621.49019 · doi:10.1007/BF00939552 |
| [44] | Pierra G (1975) Méthodes de projections parallèles extrapolées relatives à une intersection de convexes. Rapport de Recherche, INPG, Grenoble |
| [45] | Pierra G (1984) Decomposition through formalization in a product space. Math Programming 28:96–115 · Zbl 0523.49022 · doi:10.1007/BF02612715 |
| [46] | Pierra G, Ottavy N (1988) New parallel projection methods for linear varieties and applications. Presented at the XIIth International Symposium on Mathematical Programming, Tokyo |
| [47] | Poincaré H (1890) Sur les équations aux dérivées partielles de la physique mathématique. Amer J Math 12:211–294 · JFM 22.0977.03 · doi:10.2307/2369620 |
| [48] | Polyak BT (1969) Minimization of unsmooth functionals. USSR Comput Math and Math Phys 9:14–29 · Zbl 0229.65056 · doi:10.1016/0041-5553(69)90061-5 |
| [49] | Práger M (1960) On a principle of convergence in Hilbert space. Czechoslovak Math J 10:271–282 |
| [50] | Reich S (1983) A limit theorem for projections. Linear and Multilinear Algebra 13:281–290 · Zbl 0523.47040 · doi:10.1080/03081088308817526 |
| [51] | Stiles WJ (1965) Closest point maps and their product II. Nieuw Arch Wisk 13:212–225 · Zbl 0132.10403 |
| [52] | Tseng P (1992) On the convergence of products of firmly nonexpansive mappings. SIAM J Optim 2:425–434 · Zbl 0763.49011 · doi:10.1137/0802021 |
| [53] | Tsent P, Bertsekas DP (1987) Relaxation methods for problems with strictly convex separable costs and linear constraints. Math Programming 38:303–321 · Zbl 0636.90072 · doi:10.1007/BF02592017 |
| [54] | 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) · Zbl 0034.06102 · doi:10.2307/1969463 |
| [55] | 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 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
