Convergence of proximal splitting algorithms in $\operatorname{CAT}(\kappa)$ spaces and beyond

Florian Lauster1, D. Lüke1
1Institute for Numerical and Applied Mathematics, University of Goettingen, Goettingen, Germany

Tóm tắt

AbstractIn the setting of$\operatorname{CAT}(\kappa)$CAT(κ)spaces, common fixed point iterations built from prox mappings (e.g. prox-prox, Krasnoselsky–Mann relaxations, nonlinear projected-gradients) converge locally linearly under the assumption of linear metric subregularity. Linear metric subregularity is in any case necessary for linearly convergent fixed point sequences, so the result is tight. To show this, we develop a theory of fixed point mappings that violate the usual assumptions of nonexpansiveness and firm nonexpansiveness inp-uniformly convex spaces.

Từ khóa


Tài liệu tham khảo

Ariza-Ruiz, D., López-Acedo, G., Nicolae, A.: The asymptotic behavior of the composition of firmly nonexpansive mappings. J. Optim. Theory Appl. 167, 409–429 (2015)

Aspelmeier, T., Charitha, C., Luke, D.R.: Local linear convergence of the ADMM/Douglas–Rachford algorithms without strong convexity and application to statistical imaging. SIAM J. Imaging Sci. 9(2), 842–868 (2016)

Bërdëllima, A.: Investigations in Hadamard Spaces. PhD thesis, Georg-August Universität Göttingen, Göttingen (2020)

Bërdëllima, A., Lauster, F., Luke, D.R.: α-firmly nonexpansive operators on metric spaces. arXiv:2104.11302 (2021)

Bolte, J., Daniilidis, A., Lewis, A.: The Lojasiewicz inequality for nonsmooth subanalytic functions with applications to subgradient dynamical systems. SIAM J. Optim. 17, 1205–1223 (2006)

Bolte, J., Daniilidis, A., Ley, O., Mazet, L.: Characterizations of Lojasiewicz inequalities: subgradient flows, talweg, convexity. Trans. Am. Math. Soc. 362(6), 3319–3363 (2010)

Dontchev, A.L., Rockafellar, R.T.: Implicit Functions and Solution Mappings, 2nd edn. Springer, Dordrecht (2014)

Izuchukwu, C., Ugwunnadi, G.C., Mewomo, O.T., Khan, A.R., Abbas, M.: Proximal-type algorithms for split minimization problem in P-uniformly convex metric spaces. Numer. Algorithms 82(3), 909–935 (2019)

Kuwae, K.: Jensen’s inequality on convex spaces. Calc. Var. Partial Differ. Equ. 49(3–4), 1359–1378 (2014)

Luke, D.R., Teboulle, M., Thao, N.H.: Necessary conditions for linear convergence of iterated expansive, set-valued mappings. Math. Program. 180, 1–31 (2018)

Luke, D.R., Thao, N.H., Tam, M.K.: Quantitative convergence analysis of iterated expansive, set-valued mappings. Math. Oper. Res. 43(4), 1143–1176 (2018)

Naor, A., Silberman, L.: Poincaré inequalities, embeddings, and wild groups. Compos. Math. 147(5), 1546–1572 (2011)

Ohta, S.: Convexities of metric spaces. Geom. Dedic. 125, 225–250 (2007)