×

Discrete-time gradient flows and law of large numbers in Alexandrov spaces. (English) Zbl 1335.51014

Let \(\left( M,\rho\right) \) be an Alexandrov space \(\left( M,\rho\right) \) of curvature \(\leq K\) (in which minimal geodesics depend continuously on their endpoints, i.e, \(\left( M,\rho\right) \) is an Alexandrov \(\operatorname{Re}_{K}\) domain also known as \(\text{CAT}\left( K\right) \) space) or an Alexandrov space of curvature \(\geq K^{\prime}\).
The authors study discrete-time gradient flows for finding a point of minimum of a convex function \(f:M\rightarrow(-\infty,+\infty]\). The discrete-time gradient flow is constructed by means of the (metric) resolvent \(J_{\lambda }^{f}:M\rightarrow M\) by setting \(x_{k+1}=J_{\lambda}^{f}\left( x_{k}\right) \), \(k\in \mathbb{N}\) where \(\lambda>0\). In the case of curvature bounded above, the familiar Moreau-Yosida resolvent is used: \(J_{\lambda}^{f}\left( x\right) =\text{argmin}_{y\in M}\left\{ f\left( y\right) +\frac{1}{2\lambda }d^{2}\left( x,y\right) \right\} \); for \(K=0\), see [J. Jost, Comment. Math. Helv. 70, No. 4, 659–673 (1995; Zbl 0852.58022)]. In the case of the lower curvature bound, \(J_{\lambda}^{f}\left( x\right) =\text{gexp}\left( \lambda\nabla\left( -f\right) \left( x\right) \right) \) where \(\text{gexp}\) is the gradient exponential map (Section 4).
In Section 5, the authors generalize the result from [M. Bačák, Isr. J. Math. 194, Part B, 689–701 (2013; Zbl 1278.49039)] by proving the following theorem for complete \(\operatorname{Re}_{K}\) domains: If \(f:M\rightarrow(-\infty,+\infty]\) is a convex, lower semi-continuous function, \(G\subseteq M\) is a closed, geodesically convex set containing a sublevel set of \(f\) satisfying \(\text{diam}\left( G\right) <\pi/2\sqrt{K}\) for positive \(K\), \(\left( \lambda_{k}\right) _{k=1}^{\infty}\) is a sequence of positive numbers such that \(\sum _{k=1}^{\infty}\lambda_{k}=+\infty\), \(x_{0}\in G\) and \(x_{k}=J_{\lambda_{k} }^{f}\left( x_{k-1}\right) \), \(k\in\mathbb{N}\), then \(\lim_{k\rightarrow\infty}f\left( x_{k}\right) =\inf_{y\in G}f\left( y\right) \). The authors also consider the case when \(f=\sum _{k=0}^{n}f_{k}\) where \(f_{k}\) are convex and Lipschitz in a locally compact Alexandrov space of curvature either \(\leq K\) or \(\geq K^{\prime}\) and prove that the proximal point algorithm produces the sequence converging to a point of minima of \(f\) when it exists (Theorem 5.5).
In Section 6, the authors present results related to stochastic discrete-time gradient flow for a convex infinite (integral form) combination of convex functions and generalize Sturm’s law of large numbers to Alexandrov spaces of curvature either \(\leq K\) or \(\geq K^{\prime}\) for arbitrary \(K\) and \(K^{\prime}\in\mathbb{R}\).

MSC:

51K05 General theory of distance geometry
53C20 Global Riemannian geometry, including pinching
58C05 Real-valued functions on manifolds
49L20 Dynamic programming in optimal control and differential games
49M37 Numerical methods based on nonlinear programming
52A01 Axiomatic and generalized convexity
53C21 Methods of global Riemannian geometry, including PDE methods; curvature restrictions
53C45 Global surface theory (convex surfaces à la A. D. Aleksandrov)
PDFBibTeX XMLCite
Full Text: DOI arXiv

References:

[1] Afsari, B.: Riemannian \[L^p\] Lp center of mass: existence, uniqueness, and convexity. Proc. Am. Math. Soc. 139, 655-673 (2011) · Zbl 1220.53040 · doi:10.1090/S0002-9939-2010-10541-5
[2] Ambrosio, L., Gigli, N., Savaré, G.: Gradient Flows in Metric Spaces and in the Space of Probability Measures, 2nd edn. Birkhäuser Verlag, Basel (2008) · Zbl 1145.35001
[3] Arnaudon, M., Li, X.M.: Barycenters of measures transported by stochastic flows. Ann. Probab. 33, 1509-1543 (2005) · Zbl 1077.60039 · doi:10.1214/009117905000000071
[4] Arnaudon, M., Dombry, C., Phan, A., Yang, L.: Stochastic algorithms for computing means of probability measures. Stoch. Process. Appl. 122, 1437-1455 (2012) · Zbl 1262.60073 · doi:10.1016/j.spa.2011.12.011
[5] Bačák, M.: The proximal point algorithm in metric spaces. Israel J. Math. 194, 689-701 (2013) · Zbl 1278.49039 · doi:10.1007/s11856-012-0091-3
[6] Bačák, M.: Computing means and medians in Hadamard spaces. SIAM J. Optim. (2014), to appear. arXiv:1210.2145 · Zbl 1306.49046
[7] Bento, G.C., Cruz, J.X.: Neto, finite termination of the proximal point method for convex functions on Hadamard manifolds. Optimization (2012). doi:10.1080/02331934.2012.730050 · Zbl 1293.49111
[8] Bertsekas, D.P.: Incremental proximal methods for large scale convex optimization. Math. Program. Ser. B 129, 163-195 (2011) · Zbl 1229.90121 · doi:10.1007/s10107-011-0472-0
[9] Bertsekas, D.P., Tsitsiklis, J.N.: Neuro-dynamic Programming. Athena Scientific, Belmont (1996) · Zbl 0924.68163
[10] Bhatia, R.: Positive definite matrices. In: Princeton Series in Applied Mathematics. Princeton University Press, Princeton (2007) · Zbl 1125.15300
[11] Bhatia, R., Holbrook, J.: Riemannian geometry and matrix geometric means. Linear Algebra Appl. 413, 594-618 (2006) · Zbl 1088.15022 · doi:10.1016/j.laa.2005.08.025
[12] Brézis, H., Lions, P.-L.: Produits infinis de rèsolvantes. Israel J. Math. 29, 329-345 (1978) · Zbl 0387.47038 · doi:10.1007/BF02761171
[13] Burago, D., Burago, Yu., Ivanov, S.: A Course in Metric Geometry. American Mathematical Society, Providence (2001) · Zbl 0981.51016 · doi:10.1090/gsm/033
[14] Espínola, R., Fernández-León, A.: CAT \[(k)\](k)-spaces, weak convergence and fixed points. J. Math. Anal. Appl. 353, 410-427 (2009) · Zbl 1182.47043 · doi:10.1016/j.jmaa.2008.12.015
[15] Ferreira, O.P., Oliveira, P.R.: Proximal point algorithm on Riemannian manifolds. Optimization 51, 257-270 (2002) · Zbl 1013.49024 · doi:10.1080/02331930290019413
[16] Holbrook, J.: No dice: a deterministic approach to the Cartan centroid. J. Ramanujan Math. Soc. 27, 509-521 (2012) · Zbl 1325.47039
[17] Jost, J.: Equilibrium maps between metric spaces. Calc. Var. Partial Differ. Equ. 2, 173-204 (1994) · Zbl 0798.58021 · doi:10.1007/BF01191341
[18] Jost, J.: Convex functionals and generalized harmonic maps into spaces of nonpositive curvature. Comment. Math. Helv. 70, 659-673 (1995) · Zbl 0852.58022 · doi:10.1007/BF02566027
[19] Jost, J.: Nonpositive Curvature: Geometric and Analytic Aspects. Birkhäuser Verlag, Basel (1997) · Zbl 0896.53002 · doi:10.1007/978-3-0348-8918-6
[20] Jost, J.: Nonlinear dirichlet forms, new directions in Dirichlet forms 1-47. In: AMS/IP Stud. Adv. Math., vol. 8. American Mathematical Society, Providence (1998) · Zbl 1229.15024
[21] Karcher, H.: Riemannian center of mass and mollifier smoothing. Commun. Pure Appl. Math. 30, 509-541 (1977) · Zbl 0354.57005 · doi:10.1002/cpa.3160300502
[22] Kendall, W.S.: Probability, convexity, and harmonic maps with small image I: uniqueness and fine existence. Proc. Lond. Math. Soc. (3) 61, 371-406 (1990) · Zbl 0675.58042 · doi:10.1112/plms/s3-61.2.371
[23] Kendall, W.S.: Convexity and the hemisphere. J. Lond. Math. Soc. (2) 43, 567-576 (1991) · Zbl 0688.58001 · doi:10.1112/jlms/s2-43.3.567
[24] Korf, L.A., Wets, R.J.-B.: Random lsc functions: an ergodic theorem. Math. Oper. Res. (26) 2, 421-445 (2001) · Zbl 1082.90552 · doi:10.1287/moor.26.2.421.10548
[25] Kuwae, K.: Jensen’s inequality over CAT \[(\kappa )\](κ)-space with small diameter. In: Potential Theory and Stochastics in Albac. Theta Ser. Adv. Math., vol. 11, pp. 173-182. Theta, Bucharest (2009) · Zbl 1199.53096
[26] Lawson, J., Lim, Y.: Monotonic properties of the least squares mean. Math. Ann. 351, 267-279 (2011) · Zbl 1229.15024 · doi:10.1007/s00208-010-0603-6
[27] Li, C., López, G., Martín-Márquez, V.: Monotone vector fields and the proximal point algorithm on Hadamard manifolds. J. Lond. Math. Soc. (2) 79, 663-683 (2009) · Zbl 1171.58001 · doi:10.1112/jlms/jdn087
[28] Lim, Y., Pálfia, M.: Weighted deterministic walks for the least squares mean on Hadamard spaces. Bull. Lond. Math. Soc. 46, 561-570 (2014) · Zbl 1291.53050
[29] Lytchak, A.: Open map theorem for metric spaces. St. Petersb. Math. J. 17, 477-491 (2006) · Zbl 1152.53033 · doi:10.1090/S1061-0022-06-00916-2
[30] Mayer, U.F.: Gradient flows on nonpositively curved metric spaces and harmonic maps. Commun. Anal. Geom. 6, 199-253 (1998) · Zbl 0914.58008
[31] Moakher, M.: Means and averaging in the group of rotations. SIAM J. Matrix Anal. Appl. 24, 1-16 (2002) · Zbl 1028.47014 · doi:10.1137/S0895479801383877
[32] Nedic, A., Bertsekas, D.P.: Convergence rate of incremental subgradient algorithms. In: Stochastic Optimization: Algorithms and Applications (Gainesville, FL, 2000). Appl. Optim., vol. 54, pp. 223-264. Kluwer, Dordrecht (2001) · Zbl 0984.90033
[33] Nedic, A., Bertsekas, D.P.: Incremental subgradient methods for nondifferentiable optimization. SIAM J. Optim. 12, 109-138 (2001) · Zbl 0991.90099 · doi:10.1137/S1052623499362111
[34] Ohta, S.: Convexities of metric spaces. Geom. Dedic. 125, 225-250 (2007) · Zbl 1140.52001 · doi:10.1007/s10711-007-9159-3
[35] Ohta, S.: Gradient flows on Wasserstein spaces over compact Alexandrov spaces. Am. J. Math. 131, 475-516 (2009) · Zbl 1169.53053 · doi:10.1353/ajm.0.0048
[36] Ohta, S.: Barycenters in Alexandrov spaces of curvature bounded below. Adv. Geom. 12, 571-587 (2012) · Zbl 1276.53073
[37] Perel’man, G., Petrunin, A.: Quasigeodesics and gradient curves in Alexandrov spaces. Unpublished preprint. http://www.math.psu.edu/petrunin/ (1995). Accessed 12 Feb 2015 · Zbl 0387.47038
[38] Petrunin, A.: Semiconcave functions in Alexandrov’s geometry. In: Surveys in Differential Geometry, vol. XI, pp. 137-201. Int. Press, Somerville (2007) · Zbl 1166.53001
[39] Rockafellar, R.T.: Convex Analysis. Princeton University Press, Princeton (1997) · Zbl 0932.90001
[40] Rockafellar, R.T., Wets, R.J.-B.: Variational Analysis. Springer, Berlin (1998) · Zbl 0888.49001 · doi:10.1007/978-3-642-02431-3
[41] Sturm, K.-T.: Nonlinear Markov operators associated with symmetric Markov kernels and energy minimizing maps between singular spaces. Calc. Var. Partial Differ. Equ. 12, 317-357 (2001) · Zbl 0987.31006 · doi:10.1007/PL00009916
[42] Sturm, K.-T.: Nonlinear Markov operators, discrete heat flow, and harmonic maps between singular spaces. Potential Anal. 16, 305-340 (2002) · Zbl 1049.31010 · doi:10.1023/A:1014888715237
[43] Sturm, K.-T.: Nonlinear martingale theory for processes with values in metric spaces of nonpositive curvature. Ann. Probab. 30, 1195-1222 (2002) · Zbl 1017.60050 · doi:10.1214/aop/1029867125
[44] Sturm, K.-T.: Probability measures on metric spaces of nonpositive curvature. In: Heat Kernels and Analysis on Manifolds, Graphs, and Metric Spaces (Paris, 2002). Contemp. Math., vol. 338, pp. 357-90. Am. Math. Soc., Providence (2003) · Zbl 1169.53053
[45] Sturm, K.-T.: A semigroup approach to harmonic maps. Potential Anal. 23, 225-277 (2005) · Zbl 1078.58010 · doi:10.1007/s11118-004-7740-z
[46] Sturm, K.-T.: On the geometry of metric measure spaces. Acta Math. 196, 65-131 (2006) · Zbl 1105.53035 · doi:10.1007/s11511-006-0002-8
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.