×

Implicit error bounds for Picard iterations on Hilbert spaces. (English) Zbl 1391.49025

Summary: We investigate the role of error bounds, or metric subregularity, in the convergence of Picard iterations of nonexpansive maps in Hilbert spaces. Our main results show, on one hand, that the existence of an error bound is sufficient for strong convergence and, on the other hand, that an error bound exists on bounded sets for nonexpansive mappings possessing a fixed point whenever the space is finite dimensional. In the Hilbert space setting, we show that a monotonicity property of the distances of the Picard iterations is all that is needed to guarantee the existence of an error bound. The same monotonicity assumption turns out also to guarantee that the distance of Picard iterates to the fixed point set converges to zero. Our results provide a quantitative characterization of strong convergence as well as new criteria for when strong, as opposed to just weak, convergence holds.

MSC:

49J53 Set-valued and variational analysis
65K10 Numerical optimization and variational techniques
49M05 Numerical methods based on necessary conditions
49M27 Decomposition methods
65K05 Numerical mathematical programming methods
90C30 Nonlinear programming
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Baillon, JB; Bruck, RE; Reich, S, On the asymptotic behavior of nonexpansive mappings and semigroups in Banach spaces, Houst. J. Math., 4, 1-9, (1978) · Zbl 0396.47033
[2] Bauschke, HH; Borwein, JM, On the convergence of von neumann’s alternating projection algorithm for two sets, Set-Valued Anal., 1, 185-212, (1993) · Zbl 0801.47042 · doi:10.1007/BF01027691
[3] Bauschke, H.H., Combettes, P.L.: Convex Analysis and Monotone Operator Theory in Hilbert Spaces. CMS Books Math./Ouvrages Math. SMC. Springer, New York (2011) · Zbl 1218.47001
[4] Bauschke, HH; Deutsch, F; Hundal, H, Characterizing arbitrarily slow convergence in the method of alternating projections, Int. Trans. Oper. Res., 16, 413-425, (2009) · Zbl 1208.47079 · doi:10.1111/j.1475-3995.2008.00682.x
[5] Bauschke, HH; 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 · doi:10.1090/S0002-9947-03-03136-2
[6] Bauschke, HH; Noll, D; Phan, HM, Linear and strong convergence of algorithms involving averaged nonexpansive operators, J. Math. Anal. Appl., 421, 1-20, (2015) · Zbl 1297.65060 · doi:10.1016/j.jmaa.2014.06.075
[7] Bolte, J; Nguyen, TP; Peypouquet, J; Suter, BW, From error bounds to the complexity of first-order descent methods for convex functions, Math. Program., 165, 471-507, (2017) · Zbl 1373.90076 · doi:10.1007/s10107-016-1091-6
[8] Borwein, JM; Li, G; Tam, MK, Convergence rate analysis for averaged fixed point iterations in common fixed point problems, SIAM J. Optim., 27, 1-33, (2017) · Zbl 1361.90045 · doi:10.1137/15M1045223
[9] Borwein, JM; Li, G; Yao, L, Analysis of the convergence rate for the cyclic projection algorithm applied to basic semialgebraic convex sets, SIAM J. Optim., 24, 498-527, (2014) · Zbl 1296.41011 · doi:10.1137/130919052
[10] Boţ, RI; Csetnek, ER, A dynamical system associated with the fixed points set of a nonexpansive operator, J. Dyn. Differ. Equ., 29, 155-168, (2017) · Zbl 1387.34091 · doi:10.1007/s10884-015-9438-x
[11] Drusvyatskiy, D; Ioffe, AD; Lewis, A, Transversality and alternating projections for nonconvex sets, Found. Comput. Math., 15, 1637-1651, (2015) · Zbl 1338.49057 · doi:10.1007/s10208-015-9279-3
[12] Friedrichs, K, On certain inequalities and characteristic value problems for analytic functions and for functions of two variables, Trans. Am. Math. Soc., 41, 321-364, (1937) · JFM 63.0364.01 · doi:10.1090/S0002-9947-1937-1501907-0
[13] Genel, A; Lindenstrauss, J, An example concerning fixed points, Isr. J. Math., 22, 81-86, (1975) · Zbl 0314.47031 · doi:10.1007/BF02757276
[14] 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 · doi:10.1137/0329022
[15] Hundal, H, An alternating projection that does not converge in norm, Nonlinear Anal., 57, 35-61, (2004) · Zbl 1070.46013 · doi:10.1016/j.na.2003.11.004
[16] Ioffe, AD, Nonlinear regularity models, Math. Program. Ser. B, 139, 223-242, (2013) · Zbl 1275.47106 · doi:10.1007/s10107-013-0670-z
[17] Ishikawa, S, Fixed points and iteration of a nonexpansive mapping in a Banach space, Proc. Am. Math. Soc., 59, 65-71, (1976) · Zbl 0352.47024 · doi:10.1090/S0002-9939-1976-0412909-X
[18] Jordan, C, Essai sur la géométrie á n dimensions, Bull. Soc. Math. Fr., 3, 103-174, (1875) · JFM 07.0457.01 · doi:10.24033/bsmf.90
[19] Kayalar, S; Weinert, H, Error bounds for the method of alternating projections, Math. Control Signals Syst., 1, 43-59, (1988) · Zbl 0673.65036 · doi:10.1007/BF02551235
[20] Leventhal, D, Metric subregularity and the proximal point method, J. Math. Anal. Appl., 360, 681-688, (2009) · Zbl 1175.49028 · doi:10.1016/j.jmaa.2009.07.012
[21] Li, G., Nghia, T.T.A., Mordukhovich, B.S., Phạm, T.S.: Error bounds for parametric polynomial systems with applications to higher-order stability analysis and convergence rates. Math Program. https://doi.org/10.1007/s10107-016-1014-6 (2016) · Zbl 1400.90251
[22] Luke, D.R., Thao, N.H., Tam, M.K.: Quantitative convergence analysis of iterated expansive, set-valued mappings. Math. Oper. Res. (to appear) · Zbl 1033.41019
[23] Luke, D.R., Thao, N.H., Teboulle, M.: Necessary conditions for linear convergence of Picard iterations and application to alternating projections. arXiv:1704.08926 (2017) · Zbl 0314.47031
[24] Noll, D; Rondepierre, A, On local convergence of the method of alternating projections, Found. Comput. Math., 16, 425-455, (2016) · Zbl 1339.65079 · doi:10.1007/s10208-015-9253-0
[25] Opial, Z, Weak convergence of the sequence of successive approximations for nonexpansive mappings, Bull. Am. Math. Soc., 73, 591-597, (1967) · Zbl 0179.19902 · doi:10.1090/S0002-9904-1967-11761-0
[26] von Neumann, J.: Functional Operators, Vol. II. The Geometry of Orthogonal Spaces Annals of Mathematical Studies, vol. 22. Princeton University Press, Princeton (1950) · Zbl 0039.28401
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.