×

Projection and proximal point methods: Convergence results and counterexamples. (English) Zbl 1059.47060

The paper under review is a valuable and deep contribution to the convergence theory of certain sequences in Hilbert space. These sequences base on projection and proximal point methods. Herewith, this paper from functional analysis with its clear structure and thorough proofs is meaningful also for applied mathematics, especially, optimization theory in abstract spaces. This relation is reflected by the extension of projector classes and by the references.
After preparations in terms of projector and mapping classes, as well as the classical J. von Neumann’s and L. M. Bregman’s results, two main lines of work on which the paper bases itself and which it continues, are as follows:
(i) In the workshop “Inherently Parallel Algorithms in Feasibility and Optimization and Their Applications”, Haifa, 2000, H. Hundal presented a hyperplane \(H\), a cone \(K\) and an initial point \(y_0\) in \(\ell_2\) such that the sequence of iterates of stepwise alternating projections on firstly \(H\) and secondly \(K\), weakly converges but not norm converges to a point in the intersection of \(H\) with \(K\). The authors extend this result to a counterexample on norm convergence of iterates given by averaged projections.
(ii) Herewith, a question posed by S. Reich becomes answered. In the paper, further counterexamples are presented in the line of research done by
(iii) A. Genel and J. Lindenstrauss: firmly nonexpansive maps,
(iv) O. Güler: proximal point algorithms, and
(v) Y. Censor et al.: string-averaging projection methods. Finally, extensions to the Hilbert ball and Banach spaces are discussed, too.
This paper with its rich and wide results may in the future serve for a deeper understanding of the numerical treatment of various problems from optimization, calculus of variations and optimal control.

MSC:

47H09 Contraction-type mappings, nonexpansive mappings, \(A\)-proper mappings, etc.
47J25 Iterative procedures involving nonlinear operators
90C25 Convex programming
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] H. Attouch, H. Brézis, Duality for the sum of convex functions in general Banach spaces, in: J.A. Barroso (Ed.), Aspects of Mathematics and its Applications, North-Holland Math. Library, Vol. 34, North-Holland, Amsterdam, The Netherlands, 1986, pp. 125-133.; H. Attouch, H. Brézis, Duality for the sum of convex functions in general Banach spaces, in: J.A. Barroso (Ed.), Aspects of Mathematics and its Applications, North-Holland Math. Library, Vol. 34, North-Holland, Amsterdam, The Netherlands, 1986, pp. 125-133.
[2] A. Auslender, Méthodes Numériques pour la Résolution des Problèmes d’Optimisation avec Constraintes, Thèse, Faculté des Sciences, Grenoble, 1969.; A. Auslender, Méthodes Numériques pour la Résolution des Problèmes d’Optimisation avec Constraintes, Thèse, Faculté des Sciences, Grenoble, 1969.
[3] Baillon, J.-B.; Bruck, R. E.; Reich, S., On the asymptotic behavior of nonexpansive mappings and semigroups in Banach spaces, Houston J. Math., 4, 1-9 (1978) · Zbl 0431.47034
[4] H.H. Bauschke, Projection Algorithms and Monotone Operators, Ph.D. Thesis, Simon Fraser University, 1996. Available as Preprint 96:080 at .; H.H. Bauschke, Projection Algorithms and Monotone Operators, Ph.D. Thesis, Simon Fraser University, 1996. Available as Preprint 96:080 at .
[5] Bauschke, H. H., Projection algorithms: results and open problems, (Butnariu, D.; Censor, Y.; Reich, S., Inherently Parallel Algorithms in Feasibility and Optimization and Their Applications, Haifa, 2000 (2001), Elsevier: Elsevier Amsterdam, The Netherlands), 11-22 · Zbl 0991.65050
[6] Bauschke, H. H.; Borwein, J. M., On the convergence of von Neumann’s alternating projection algorithm for two sets, Set-Valued Analysis, 1, 185-212 (1993) · Zbl 0801.47042
[7] Bauschke, H. H.; Borwein, J. M., Dykstra’s alternating projection algorithm for two sets, J. Approx. Theory, 79, 418-443 (1994) · Zbl 0833.46011
[8] Bauschke, H. H.; Borwein, J. M., On projection algorithms for solving convex feasibility problems, SIAM Rev., 38, 367-426 (1996) · Zbl 0865.47039
[9] Bauschke, H. H.; Borwein, J. M.; Lewis, A. S., The method of cyclic projections for closed convex sets in Hilbert space, (Censor, Y.; Reich, S., Recent Developments in Optimization Theory and Nonlinear Analysis, Jerusalem, 1995. Recent Developments in Optimization Theory and Nonlinear Analysis, Jerusalem, 1995, Contemporary Mathematics, Vol. 204 (1997), American Mathematical Society: American Mathematical Society Providence, RI), 1-38 · Zbl 0874.47029
[10] H.H. Bauschke, J.V. Burke, F.R. Deutsch, H.S. Hundal, J.D. Vanderwerff, A new proximal point iteration that converges weakly but not in norm, Proc. Amer. Math. Soc., available at as Preprint 02:191.; H.H. Bauschke, J.V. Burke, F.R. Deutsch, H.S. Hundal, J.D. Vanderwerff, A new proximal point iteration that converges weakly but not in norm, Proc. Amer. Math. Soc., available at as Preprint 02:191. · Zbl 1071.65082
[11] Bauschke, H. H.; Combettes, P. L., A weak-to-strong convergence principle for Fejér-monotone methods in Hilbert spaces, Math. Oper. Res., 26, 248-264 (2001) · Zbl 1082.65058
[12] Bauschke, H. H.; Deutsch, F.; Hundal, H.; Park, S.-H., Fejér monotonicity and weak convergence of an accelerated method of projections, (Théra, M., Constructive, Experimental, and Nonlinear Analysis, Limoges, 1999 (2000), American Mathematical Society: American Mathematical Society Providence, RI), 1-6 · Zbl 1016.65032
[13] Bauschke, H. H.; Deutsch, F.; Hundal, H.; Park, S.-H., Accelerating the convergence of the method of alternating projections, Trans. Am. Math. Soc., 355, 3433-3461 (2003) · Zbl 1033.41019
[14] Y. Benyamini, J. Lindenstrauss, Geometric Nonlinear Functional Analysis, Vol. 1, American Mathematical Society, Providence, RI, 2000.; Y. Benyamini, J. Lindenstrauss, Geometric Nonlinear Functional Analysis, Vol. 1, American Mathematical Society, Providence, RI, 2000. · Zbl 0946.46002
[15] Bregman, L. M., The method of successive projection for finding a common point of convex sets, Sov. Math. Dokl., 6, 688-692 (1965) · Zbl 0142.16804
[16] Brézis, H., Opérateurs Maximaux Monotones et Semi-Groupes de Contractions dans les Espaces de Hilbert (1973), North-Holland: North-Holland Amsterdam · Zbl 0252.47055
[17] Brézis, H.; Lions, P.-L., Produits infinis de résolvantes, Isr. J. Math., 29, 329-345 (1978) · Zbl 0387.47038
[18] Bruck, R. E.; Reich, S., Nonexpansive projections and resolvents of accretive operators in Banach spaces, Houston J. Math., 3, 459-470 (1977) · Zbl 0383.47035
[19] D. Butnariu, Y. Censor, S. Reich (Eds.), Inherently Parallel Algorithms in Feasibility and Optimization and Their Applications, Elsevier, Amsterdam, The Netherlands, 2001.; D. Butnariu, Y. Censor, S. Reich (Eds.), Inherently Parallel Algorithms in Feasibility and Optimization and Their Applications, Elsevier, Amsterdam, The Netherlands, 2001.
[20] Censor, Y., On sequential and parallel projection algorithms for feasibility and optimization, (Censor, Y.; Ding, M., Visualization and Optimization Techniques. Visualization and Optimization Techniques, Proceedings of SPIE, Vol. 4553 (2001), SPIE—The International Society for Optical Engineering: SPIE—The International Society for Optical Engineering Bellingham, WA), 1-9
[21] Censor, Y.; Elfving, T.; Herman, G. T., Averaging strings of sequential iterations for convex feasibility problems, (Butnariu, D.; Censor, Y.; Reich, S., Inherently Parallel Algorithms in Feasibility and Optimization and Their Applications, Haifa, 2000 (2001), Elsevier: Elsevier Amsterdam, The Netherlands), 101-114 · Zbl 1160.65320
[22] Censor, Y.; Tom, E., Convergence of string-averaging projection schemes for inconsistent convex feasibility problems, Optim. Methods Software, 18, 543-554 (2003) · Zbl 1065.65074
[23] Censor, Y.; Zenios, S. A., Parallel Optimization (1997), Oxford University Press: Oxford University Press New York, NY
[24] G. Cimmino, Calcolo approssimato per le soluzioni dei sistemi di equazioni lineari, La Ricerca Scientifica ed il Progresso Tecnico nell’Economia Nazionale, Roma, Vol. 1, 1938, pp. 326-333.; G. Cimmino, Calcolo approssimato per le soluzioni dei sistemi di equazioni lineari, La Ricerca Scientifica ed il Progresso Tecnico nell’Economia Nazionale, Roma, Vol. 1, 1938, pp. 326-333.
[25] Combettes, P. L., Hilbertian convex feasibility problemconvergence of projection methods, Appl. Math. Optim., 35, 311-330 (1997) · Zbl 0872.90069
[26] Crombez, G., Finding common fixed points of strict paracontractions by averaging strings of sequential iterations, J. Nonlinear and Convex Anal., 3, 345-351 (2002) · Zbl 1039.47044
[27] Deutsch, F., Best Approximation in Inner Product Spaces (2001), Springer: Springer New York, NY · Zbl 0980.41025
[28] Dye, J. M.; Reich, S., On the unrestricted iteration of projections in Hilbert space, J. Math. Anal. Appl., 156, 101-119 (1991) · Zbl 0731.65041
[29] Genel, A.; Lindenstrauss, J., An example concerning fixed points, Isr. J. Math., 22, 81-86 (1975) · Zbl 0314.47031
[30] Goebel, K.; Kirk, W. A., Topics in Metric Fixed Point Theory (1990), Cambridge University Press: Cambridge University Press Cambridge, UK · Zbl 0708.47031
[31] Goebel, K.; Reich, S., Uniform Convexity, Hyperbolic Geometry, and Nonexpansive Mappings (1984), Marcel Dekker: Marcel Dekker New York, NY · Zbl 0537.46001
[32] Güler, O., On the convergence of the proximal point algorithm for convex minimization, SIAM J. Control Optim., 29, 403-419 (1991) · Zbl 0737.90047
[33] Hiriart-Urruty, J.-B., A general formula on the conjugate of the difference of functions, Can. Math. Bull., 29, 482-485 (1986) · Zbl 0608.90087
[34] H. Hundal, An alternating projection that does not converge in norm, Nonlinear Anal., available at as Preprint 02:189.; H. Hundal, An alternating projection that does not converge in norm, Nonlinear Anal., available at as Preprint 02:189.
[35] Kirszbraun, M. D., Über die zusammenziehenden und Lipschitzschen Transformationen, Fund Math., 22, 77-108 (1934) · Zbl 0009.03904
[36] Kuczumow, T.; Reich, S.; Shoikhet, D., Fixed points of holomorphic mappings: a metric approach, (Kirk, W. A.; Sims, B., Handbook of Metric Fixed Point Theory (2001), Kluwer: Kluwer Dordrecht, The Netherlands), 437-515 · Zbl 1019.47041
[37] Kuzcumow, T.; Stachura, A., Extensions of nonexpansive mappings in the Hilbert ball with the hyperbolic metric II, Commentat. Math. Univ. Carolin., 29, 403-410 (1988) · Zbl 0672.47036
[38] Martinet, B., Régularisation d’inéquations variationnelles par approximations successives, Rev. Fr. d’Informatique Recherche Opér., 4, 154-158 (1970) · Zbl 0215.21103
[39] Merzlyakov, Y. I., On a relaxation method of solving systems of linear inequalities, USSR Comput. Math. Math. Phys., 2, 504-510 (1963) · Zbl 0123.11204
[40] Minty, G. J., Monotone (nonlinear) operators in Hilbert space, Duke Math. J., 29, 341-346 (1962) · Zbl 0111.31202
[41] Moreau, J.-J., Proximité et dualité dans un espace hilbertien, Bull. Soc. Math. France, 93, 273-299 (1965) · Zbl 0136.12101
[42] Reich, S., Product formulas, nonlinear semigroups, and accretive operators, J. Funct. Anal., 36, 147-168 (1980) · Zbl 0437.47048
[43] Reich, S., On the asymptotic behavior of nonlinear semigroups and the range of accretive operators, J. Math. Anal. Appl., 79, 113-126 (1981) · Zbl 0457.47053
[44] Reich, S., On the asymptotic behavior of nonlinear semigroups and the range of accretive operators II, J. Math. Anal. Appl., 87, 134-146 (1982) · Zbl 0493.47034
[45] Reich, S., A limit theorem for projections, Linear and Multilinear Algebra, 13, 281-290 (1983) · Zbl 0523.47040
[46] Reich, S., Averaged mappings in the Hilbert ball, J. Math. Anal. Appl., 109, 199-206 (1985) · Zbl 0588.47061
[47] Reich, S., The alternating algorithm of von Neumann in the Hilbert ball, Dynamic Systems Appl., 2, 21-25 (1993) · Zbl 0768.41032
[48] Rockafellar, R. T., On the maximal monotonicity of subdifferential mappings, Pacific J. Math., 33, 209-216 (1970) · Zbl 0199.47101
[49] Rockafellar, R. T., Monotone operators and the proximal point algorithm, SIAM J. Control Optim., 14, 877-898 (1976) · Zbl 0358.90053
[50] von Neumann, J., On rings of operators. Reduction theory, Ann. Math., 50, 401-485 (1949) · Zbl 0034.06102
[51] von Neumann, J., Functional Operators II: The Geometry of Orthogonal Spaces (1950), Princeton University Press: Princeton University Press Princeton, NJ, (This is a reprint of mimeographed lecture notes first distributed in 1933.) · Zbl 0039.11701
[52] Wiener, N., On the factorization of matrices, Comment. Math. Helv., 29, 97-111 (1955) · Zbl 0064.06301
[53] Yamada, I., The hybrid steepest descent method for the variational inequality problem over the intersection of fixed points sets of nonexpansive mappings, (Butnariu, D.; Censor, Y.; Reich, S., Inherently Parallel Algorithms in Feasibility and Optimization and Their Applications, Haifa, 2000 (2001), Elsevier: Elsevier Amsterdam, The Netherlands), 473-504 · Zbl 1013.49005
[54] Zălinescu, C., Convex Analysis in General Vector Spaces (2002), World Scientific: World Scientific River Edge, NJ · Zbl 1023.46003
[55] Zarantonello, E. H., Projections on convex sets in Hilbert space and spectral theory, (Zarantonello, E. H., Contributions to Nonlinear Functional Analysis (1971), Academic Press: Academic Press New York, NY), 237-424
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.