zbMATH — the first resource for mathematics

Examples
Geometry Search for the term Geometry in any field. Queries are case-independent.
Funct* Wildcard queries are specified by * (e.g. functions, functorial, etc.). Otherwise the search is exact.
"Topological group" Phrases (multi-words) should be set in "straight quotation marks".
au: Bourbaki & ti: Algebra Search for author and title. The and-operator & is default and can be omitted.
Chebyshev | Tschebyscheff The or-operator | allows to search for Chebyshev or Tschebyscheff.
"Quasi* map*" py: 1989 The resulting documents have publication year 1989.
so: Eur* J* Mat* Soc* cc: 14 Search for publications in a particular source with a Mathematics Subject Classification code (cc) in 14.
"Partial diff* eq*" ! elliptic The not-operator ! eliminates all results containing the word elliptic.
dt: b & au: Hilbert The document type is set to books; alternatively: j for journal articles, a for book articles.
py: 2000-2015 cc: (94A | 11T) Number ranges are accepted. Terms can be grouped within (parentheses).
la: chinese Find documents in a given language. ISO 639-1 language codes can also be used.

Operators
a & b logic and
a | b logic or
!ab logic not
abc* right wildcard
"ab c" phrase
(ab c) parentheses
Fields
any anywhere an internal document identifier
au author, editor ai internal author identifier
ti title la language
so source ab review, abstract
py publication year rv reviewer
cc MSC code ut uncontrolled term
dt document type (j: journal article; b: book; a: book article)
Extrapolation algorithm for affine-convex feasibility problems. (English) Zbl 1098.65060

The problem is to find a common point of a countable family of closed affine subspaces and convex sets in a Hilbert space. A general algorithmic framework is proposed, which unifies the existing convergence results for a wide range of projection, subgradient projection, proximal, and fixed-point methods. A new extrapolation algorithm based on the general framework is presented, its convergence is established, and connections with existing results are shown.

In the concluding section of the paper, the proposed algorithm is specialized to the case of finding a common point of two sets only, namely of a closed affine subspace and a closed convex subset of a Hilbert space. Numerical simulation results confirming the expected acceleration in this special case are presented.

MSC:
65K05Mathematical programming (numerical methods)
90C25Convex programming
47J25Iterative procedures (nonlinear operator equations)
47N10Applications of operator theory in optimization, convex analysis, programming, economics
90C48Programming in abstract spaces
References:
[1]A. Auslender, Méthodes Numériques pour la Résolution des Problèmes d’Optimisation avec Contraintes, Thèse, Faculté des Sciences, Grenoble, France (1969).
[2]H.H. Bauschke, Projection algorithms and monotone operators, PhD Thesis, Department of Mathematics, Simon Fraser University, Burnaby, British Columbia, Canada (August 1996). Available at http://www.cecm.sfu.ca/preprints/1996pp.html .
[3]H.H. Bauschke and J.M. Borwein, On projection algorithms for solving convex feasibility problems, SIAM Rev. 38 (1996) 367–426. · Zbl 0865.47039 · doi:10.1137/S0036144593251710
[4]H.H. Bauschke and P.L. Combettes, A weak-to-strong convergence principle for Fejér-monotone methods in Hilbert spaces, Math. Oper. Res. 26 (2001) 248–264. · Zbl 1082.65058 · doi:10.1287/moor.26.2.248.10558
[5]H.H. Bauschke, F. Deutsch, H. Hundal and S.-H. Park, Fejér monotonicity and weak convergence of an accelerated method of projections, in: Constructive, Experimental, and Nonlinear Analysis, ed. M. Théra (CMS Conference Proceedings 27, 2000) pp. 1–6.
[6]H.H. Bauschke, F. Deutsch, H. Hundal, and S.-H. Park, Accelerating the convergence of the method of alternating projections, Trans. Am. Math. Soc. 355 (2003) 3433–3461. · Zbl 1033.41019 · doi:10.1090/S0002-9947-03-03136-2
[7]H.H. Bauschke and S.G. Kruk, Reflection-projection method for convex feasibility problems with an obtuse cone, J. Optim. Theory Appl. 120 (2004) 503–531. · Zbl 1136.90432 · doi:10.1023/B:JOTA.0000025708.31430.22
[8]E. Blum and W. Oettli, From optimization and variational inequalities to equilibrium problems, Math. Stud. 63 (1994) 123–145.
[9]L.M. Bregman, The method of successive projection for finding a common point of convex sets, Sov. Math., Dokl. 6 (1965) 688–692.
[10]F.E. Browder, Convergence theorems for sequences of nonlinear operators in Banach spaces, Math. Z. 100 (1967) 201–225. · Zbl 0149.36301 · doi:10.1007/BF01109805
[11]D. Butnariu and Y. Censor, On the behavior of a block-iterative projection method for solving convex feasibility problems, Int. J. Comput. Math. 34 (1990) 79–94. · Zbl 0708.90064 · doi:10.1080/00207169008803865
[12]D. Butnariu, Y. Censor and S. Reich, eds., Inherently Parallel Algorithms in Feasibility and Optimization and Their Applications (Elsevier, New York, 2001).
[13]A. Cauchy, Méthode générale pour la résolution des systèmes d’équations simultanées, C. R. Acad. Sci. Paris 25 (1847) 536–538.
[14]Y. Censor, Iterative methods for the convex feasibility problem, Ann. Discrete Math. 20 (1984) 83–91.
[15]Y. Censor and A. Lent, Cyclic subgradient projections, Math. Program. 24 (1982) 233–235. · Zbl 0491.90077 · doi:10.1007/BF01585107
[16]Y. Censor and S.A. Zenios, Parallel Optimization: Theory, Algorithms, and Applications (Oxford University Press, New York, 1997).
[17]G. Cimmino, Calcolo approssimato per le soluzioni dei sistemi di equazioni lineari, La Ricerca Scientifica (Roma) 1 (1938) 326–333.
[18]P.L. Combettes, The foundations of set theoretic estimation, Proc. IEEE 81 (1993) 182–208. · doi:10.1109/5.214546
[19]P.L. Combettes, Construction d’un point fixe commun à une famille de contractions fermes, C. R. Acad. Sci. Paris Sér. I Math. 320 (1995) 1385–1390.
[20]P.L. Combettes, The convex feasibility problem in image recovery, in: Advances in Imaging and Electron Physics, ed. P. Hawkes, Vol. 95, (Academic, New York, 1996) pp. 155–270.
[21]P.L. Combettes, Convex set theoretic image recovery by extrapolated iterations of parallel subgradient projections, IEEE Trans. Image Process. 6 (1997) 493–506. · doi:10.1109/83.563316
[22]P.L. Combettes, Hilbertian convex feasibility problem: Convergence of projection methods, Appl. Math. Optim. 35 (1997) 311–330.
[23]P.L. Combettes, Quasi-Fejérian analysis of some optimization algorithms, in: Inherently Parallel Algorithms in Feasibility and Optimization and Their Applications, eds. D. Butnariu, Y. Censor and S. Reich (Elsevier, New York, 2001) pp. 115–152.
[24]P.L. Combettes, Solving monotone inclusions via compositions of nonexpansive averaged operators, Optimization 53 (2004) 475–504. · Zbl 1153.47305 · doi:10.1080/02331930412331327157
[25]P.L. Combettes and S.A. Hirstoaga, Equilibrium programming in Hilbert spaces, J. Nonlinear Convex Anal. 6 (2005) 117–136.
[26]G. Crombez, Image recovery by convex combinations of projections, J. Math. Anal. Appl. 155 (1991) 413–419. · Zbl 0752.65045 · doi:10.1016/0022-247X(91)90010-W
[27]G. Crombez, Viewing parallel projection methods as sequential ones in convex feasibility problems, Trans. Am. Math. Soc. 347 (1995) 2575–2583. · Zbl 0846.46010 · doi:10.2307/2154839
[28]A.R. De Pierro and A.N. Iusem, A parallel projection method for finding a common point of a family of convex sets, Pesqui. Oper. 5 (1985) 1–20.
[29]F. Deutsch, The method of alternating orthogonal projections, in: Approximation Theory, Spline Functions and Applications, ed. S.P. Singh (Kluwer, The Netherlands, 1992) pp. 105–121.
[30]F. Deutsch, Best Approximation in Inner Product Spaces (Springer, Berlin Heidelberg New York, 2001).
[31]L.T. Dos Santos, A parallel subgradient projections method for the convex feasibility problem, J. Comput. Appl. Math. 18 (1987) 307–320. · Zbl 0623.90076 · doi:10.1016/0377-0427(87)90004-5
[32]I.I. Eremin, Generalization of the relaxation method of Motzkin–Agmon, Uspekhi Mat. Nauk 20 (1965) 183–187.
[33]S.D. Flåm and J. Zowe, Relaxed outer projections, weighted averages, and convex feasibility, BIT 30 (1990) 289–300. · Zbl 0715.65038 · doi:10.1007/BF02017349
[34]U. García-Palomares, Parallel-projected aggregation methods for solving the convex feasibility problem, SIAM J. Optim. 3 (1993) 882–900. · Zbl 0791.90042 · doi:10.1137/0803046
[35]U.M. García-Palomares and F.J. González-Castaño, Incomplete projection algorithms for solving the convex feasibility problem, Numer. Algorithms 18 (1998) 177–193. · Zbl 0913.65146 · doi:10.1023/A:1019165330848
[36]K. Goebel, and S. Reich, Uniform Convexity, Hyperbolic Geometry, and Nonexpansive Mappings (Marcel Dekker, New York, 1984).
[37]K. Goebel, and W.A. Kirk, Topics in Metric Fixed Point Theory (Cambridge University Press, Cambridge, 1990).
[38]F.J. González-Castaño, U.M. García-Palomares, J.L. Alba-Castro and J.M. Pousada-Carballo, Fast image recovery using dynamic load balancing in parallel architectures, by means of incomplete projections, IEEE Trans. Image Process. 10 (2001) 493–499. · Zbl 1036.68612 · doi:10.1109/83.913584
[39]A. Göpfert, H. Riahi, C. Tammer and C. Zaălinescu, Variational Methods in Partially Ordered Spaces (Springer, Berlin Heidelberg New York, 2003).
[40]L.G. Gubin, B.T. Polyak and E.V. Raik, The method of projections for finding the common point of convex sets, USSR Comput. Math. Math. Phys. 7 (1967) 1–24. · Zbl 0199.51002 · doi:10.1016/0041-5553(67)90113-9
[41]S. Kaczmarz, Angenäherte Auflösung von Systemen linearer Gleichungen, Bull. Acad. Sci. Pologne A35 (1937) 355–357.
[42]K.C. Kiwiel, Block-iterative surrogate projection methods for convex feasibility problems, Linear Algebra Appl. 215 (1995) 225–259. · Zbl 0821.65037 · doi:10.1016/0024-3795(93)00089-I
[43]K.C. Kiwiel and B. opuch, Surrogate projection methods for finding fixed points of firmly nonexpansive mappings, SIAM J. Optim. 7 (1997) 1084–1102. · Zbl 0905.47044 · doi:10.1137/S1052623495279569
[44]N. Lehdili and B. Lemaire, The barycentric proximal method, Comm. Appl. Nonlinear Anal. 6 (1999) 29–47.
[45]Y.I. Merzlyakov, On a relaxation method of solving systems of linear inequalities, USSR Comput. Math. Math. Phys. 2 (1963) 504–510. · Zbl 0123.11204 · doi:10.1016/0041-5553(63)90463-4
[46]W. Oettli, A remark on vector-valued equilibria and generalized monotonicity, Acta Math. Vietnam. 22 (1997) 215–221.
[47]N. Ottavy, Strong convergence of projection-like methods in Hilbert spaces, J. Optim. Theory Appl. 56 (1988) 433–461. · Zbl 0621.49019 · doi:10.1007/BF00939552
[48]G. Pierra, Éclatement de contraintes en parallèle pour la minimisation d’une forme quadratique, in: Lecture Notes in Computer Science, Vol. 41, (Springer, Berlin Heidelberg New York, 1976) pp. 200–218.
[49]G. Pierra, Decomposition through formalization in a product space, Math. Programming 28 (1984) 96–115. · Zbl 0523.49022 · doi:10.1007/BF02612715
[50]B.T. Polyak, Minimization of unsmooth functionals, USSR Comput. Math. Math. Phys. 9 (1969) 14–29. · Zbl 0229.65056 · doi:10.1016/0041-5553(69)90061-5
[51]S. Reich, A limit theorem for projections, Linear Multilinear Algebra 13 (1983) 281–290. · Zbl 0523.47040 · doi:10.1080/03081088308817526
[52]R.T. Rockafellar, Monotone operators and the proximal point algorithm, SIAM J. Control Optim. 14 (1976) 877–898. · Zbl 0358.90053 · doi:10.1137/0314056
[53]P. Tseng, On the convergence of products of firmly nonexpansive mappings, SIAM J. Optim. 2 (1992) 425–434. · Zbl 0763.49011 · doi:10.1137/0802021
[54]I. Yamada, K. Slavakis and K. Yamada, An efficient robust adaptive filtering algorithm based on parallel subgradient projection techniques, IEEE Trans. Signal Process. 50 (2002) 1091–1101. · doi:10.1109/78.995065
[55]I. Yamada and N. Ogura, Adaptive projected subgradient method for asymptotic minimization of sequence of nonnegative convex functions, Numer. Funct. Anal. Optim. 25 (2004) 593–617. · Zbl 1156.90428 · doi:10.1081/NFA-200045806
[56]E. Zeidler, Nonlinear Functional Analysis and Its Applications II/B – Nonlinear Monotone Operators (Springer, Berlin Heidelberg New York, 1990).