Uniqueness of the fixed point of nonexpansive semidifferentiable maps

Akian, Marianne; Gaubert, Stéphane; Nussbaum, Roger

doi:10.1090/S0002-9947-2015-06413-7

Uniqueness of the fixed point of nonexpansive semidifferentiable maps
HTML articles powered by AMS MathViewer

by Marianne Akian, Stéphane Gaubert and Roger Nussbaum PDF

Trans. Amer. Math. Soc. 368 (2016), 1271-1320 Request permission

Abstract:

We consider semidifferentiable (possibly nonsmooth) maps, acting on a subset of a Banach space, that are nonexpansive either in the norm of the space or in Hilbert’s or Thompson’s metric inherited from a convex cone. We show that the global uniqueness of the fixed point of the map, as well as the geometric convergence of every orbit to this fixed point, can be inferred from the semidifferential of the map at this point. In particular, we show that the geometric convergence rate of the orbits to the fixed point can be bounded in terms of Bonsall’s nonlinear spectral radius of the semidifferential. We derive similar results concerning the uniqueness of the eigenline and the geometric convergence of the orbits to it, in the case of positively homogeneous maps acting on the interior of a cone, or of additively homogeneous maps acting on an AM-space with unit. This is motivated in particular by the analysis of dynamic programming operators (Shapley operators) of zero-sum stochastic games.

References

Charalambos D. Aliprantis and Kim C. Border, Infinite-dimensional analysis, 2nd ed., Springer-Verlag, Berlin, 1999. A hitchhiker’s guide. MR 1717083, DOI 10.1007/978-3-662-03961-8
Marianne Akian and Stéphane Gaubert, Spectral theorem for convex monotone homogeneous maps, and ergodic control, Nonlinear Anal. 52 (2003), no. 2, 637–679. MR 1938367, DOI 10.1016/S0362-546X(02)00170-0
Marianne Akian, Stéphane Gaubert, and Alexander Guterman, Tropical polyhedra are equivalent to mean payoff games, Internat. J. Algebra Comput. 22 (2012), no. 1, 1250001, 43. MR 2900854, DOI 10.1142/S0218196711006674
Marianne Akian, Stéphane Gaubert, Bas Lemmens, and Roger Nussbaum, Iteration of order preserving subhomogeneous maps on a cone, Math. Proc. Cambridge Philos. Soc. 140 (2006), no. 1, 157–176. MR 2197581, DOI 10.1017/S0305004105008832
Marianne Akian, Stéphane Gaubert, and Roger Nussbaum, A Collatz-Wielandt characterization of the spectral radius of order-preserving homogeneous maps on cones, arXiv:1112.5968, 2011.
David Angeli and Eduardo D. Sontag, Translation-invariant monotone systems, and a global convergence result for enzymatic futile cycles, Nonlinear Anal. Real World Appl. 9 (2008), no. 1, 128–140. MR 2370168, DOI 10.1016/j.nonrwa.2006.09.006
Garrett Birkhoff, Extensions of Jentzsch’s theorem, Trans. Amer. Math. Soc. 85 (1957), 219–227. MR 87058, DOI 10.1090/S0002-9947-1957-0087058-6
Garrett Birkhoff, Uniformly semi-primitive multiplicative processes, Trans. Amer. Math. Soc. 104 (1962), 37–51. MR 146100, DOI 10.1090/S0002-9947-1962-0146100-6
Garrett Birkhoff and Leon Kotin, Integro-differential delay equations of positive type, J. Differential Equations 2 (1966), 320–327. MR 198169, DOI 10.1016/0022-0396(66)90072-6
J. M. Borwein, A. S. Lewis, and R. D. Nussbaum, Entropy minimization, $DAD$ problems, and doubly stochastic kernels, J. Funct. Anal. 123 (1994), no. 2, 264–307. MR 1283029, DOI 10.1006/jfan.1994.1089
Leonard M. Blumenthal, Theory and applications of distance geometry, Oxford, at the Clarendon Press, 1953. MR 0054981
F. F. Bonsall, Linear operators in complete positive cones, Proc. London Math. Soc. (3) 8 (1958), 53–75. MR 92938, DOI 10.1112/plms/s3-8.1.53
Philippe Bougerol, Almost sure stabilizability and Riccati’s equation of linear systems with random parameters, SIAM J. Control Optim. 33 (1995), no. 3, 702–717. MR 1327234, DOI 10.1137/S0363012992229069
P. J. Bushell, Hilbert’s metric and positive contraction mappings in a Banach space, Arch. Rational Mech. Anal. 52 (1973), 330–338. MR 336473, DOI 10.1007/BF00247467
P. J. Bushell, The Cayley-Hilbert metric and positive operators, Proceedings of the symposium on operator theory (Athens, 1985), 1986, pp. 271–280. MR 872288, DOI 10.1016/0024-3795(86)90319-8
Michael G. Crandall and Luc Tartar, Some relations between nonexpansive and order preserving mappings, Proc. Amer. Math. Soc. 78 (1980), no. 3, 385–390. MR 553381, DOI 10.1090/S0002-9939-1980-0553381-X
Harry Furstenberg, Noncommuting random products, Trans. Amer. Math. Soc. 108 (1963), 377–428. MR 163345, DOI 10.1090/S0002-9947-1963-0163345-0
Jerzy Filar and Koos Vrieze, Competitive Markov decision processes, Springer-Verlag, New York, 1997. MR 1418636
Stéphane Gaubert and Jeremy Gunawardena, The Perron-Frobenius theorem for homogeneous, monotone functions, Trans. Amer. Math. Soc. 356 (2004), no. 12, 4931–4950. MR 2084406, DOI 10.1090/S0002-9947-04-03470-1
Stéphane Gaubert and Guillaume Vigeral, A maximin characterisation of the escape rate of non-expansive mappings in metrically convex spaces, Math. Proc. Cambridge Philos. Soc. 152 (2012), no. 2, 341–363. MR 2887878, DOI 10.1017/S0305004111000673
Hongxiao Hu and Jifa Jiang, Translation-invariant monotone systems, I: autonomous/periodic case, Nonlinear Anal. Real World Appl. 11 (2010), no. 4, 3211–3217. MR 2661981, DOI 10.1016/j.nonrwa.2009.11.015
Hongxiao Hu and Jifa Jiang, Translation-invariant monotone systems II: Almost periodic/automorphic case, Proc. Amer. Math. Soc. 138 (2010), no. 11, 3997–4007. MR 2679621, DOI 10.1090/S0002-9939-2010-10389-1
Eberhard Hopf, An inequality for positive linear integral operators, J. Math. Mech. 12 (1963), 683–692. MR 0165325
Lars Hörmander, The analysis of linear partial differential operators. III, Grundlehren der mathematischen Wissenschaften [Fundamental Principles of Mathematical Sciences], vol. 274, Springer-Verlag, Berlin, 1994. Pseudo-differential operators; Corrected reprint of the 1985 original. MR 1313500
Tosio Kato, Perturbation theory for linear operators, Classics in Mathematics, Springer-Verlag, Berlin, 1995. Reprint of the 1980 edition. MR 1335452, DOI 10.1007/978-3-642-66282-9
V. N. Kolokol′tsov, On linear, additive, and homogeneous operators in idempotent analysis, Idempotent analysis, Adv. Soviet Math., vol. 13, Amer. Math. Soc., Providence, RI, 1992, pp. 87–101. MR 1203786
M. G. Kreĭn and M. A. Rutman, Linear operators leaving invariant a cone in a Banach space, Uspehi Matem. Nauk (N. S.) 3 (1948), no. 1(23), 3–95 (Russian). MR 0027128
M. A. Krasnosel′skiĭ, Positive solutions of operator equations, P. Noordhoff Ltd., Groningen, 1964. Translated from the Russian by Richard E. Flaherty; edited by Leo F. Boron. MR 0181881
Ulrich Krause, Concave Perron-Frobenius theory and applications, Proceedings of the Third World Congress of Nonlinear Analysts, Part 3 (Catania, 2000), 2001, pp. 1457–1466. MR 1977031, DOI 10.1016/S0362-546X(01)00281-4
Andrew J. Lazarus, Daniel E. Loeb, James G. Propp, Walter R. Stromquist, and Daniel H. Ullman, Combinatorial games under auction play, Games Econom. Behav. 27 (1999), no. 2, 229–264. MR 1685133, DOI 10.1006/game.1998.0676
B. Lemmens and R. D. Nussbaum. Non-linear Perron-Frobenius theory, volume 189 of Cambridge Tracts in Mathematics. Cambridge University Press, 2012.
Volker Metz, The short-cut test, J. Funct. Anal. 220 (2005), no. 1, 118–156. MR 2114701, DOI 10.1016/j.jfa.2004.06.008
Peter Meyer-Nieberg, Banach lattices, Universitext, Springer-Verlag, Berlin, 1991. MR 1128093, DOI 10.1007/978-3-642-76724-1
Michio Morishima, Equilibrium, stability, and growth: A multi-sectoral analysis, Clarendon Press, Oxford, 1964. MR 0183526
John Mallet-Paret and Roger D. Nussbaum, Eigenvalues for a class of homogeneous cone maps arising from max-plus operators, Discrete Contin. Dyn. Syst. 8 (2002), no. 3, 519–562. MR 1897866, DOI 10.3934/dcds.2002.8.519
John Mallet-Paret and Roger D. Nussbaum, Generalizing the Krein-Rutman theorem, measures of noncompactness and the fixed point index, J. Fixed Point Theory Appl. 7 (2010), no. 1, 103–143. MR 2652513, DOI 10.1007/s11784-010-0010-3
John Mallet-Paret and Roger D. Nussbaum, Inequivalent measures of noncompactness, Ann. Mat. Pura Appl. (4) 190 (2011), no. 3, 453–488. MR 2825257, DOI 10.1007/s10231-010-0158-x
John Mallet-Paret and Roger D. Nussbaum, Inequivalent measures of noncompactness and the radius of the essential spectrum, Proc. Amer. Math. Soc. 139 (2011), no. 3, 917–930. MR 2745644, DOI 10.1090/S0002-9939-2010-10511-7
M. V. Menon and Hans Schneider, The spectrum of a nonlinear operator associated with a matrix, Linear Algebra Appl. 2 (1969), 321–334. MR 246893, DOI 10.1016/0024-3795(69)90034-2
Ashok P. Maitra and William D. Sudderth, Discrete gambling and stochastic games, Applications of Mathematics (New York), vol. 32, Springer-Verlag, New York, 1996. MR 1382657, DOI 10.1007/978-1-4612-4002-0
Abraham Neyman, Stochastic games and nonexpansive maps, Stochastic games and applications (Stony Brook, NY, 1999) NATO Sci. Ser. C Math. Phys. Sci., vol. 570, Kluwer Acad. Publ., Dordrecht, 2003, pp. 397–415. MR 2035569, DOI 10.1007/978-94-010-0189-2_{2}6
Abraham Neyman and Sylvain Sorin (eds.), Stochastic games and applications, NATO Science Series C: Mathematical and Physical Sciences, vol. 570, Kluwer Academic Publishers, Dordrecht, 2003. MR 2032421, DOI 10.1007/978-94-010-0189-2
Roger D. Nussbaum, The fixed point index for local condensing maps, Ann. Mat. Pura Appl. (4) 89 (1971), 217–258. MR 312341, DOI 10.1007/BF02414948
Roger D. Nussbaum, Degree theory for local condensing maps, J. Math. Anal. Appl. 37 (1972), 741–766. MR 306986, DOI 10.1016/0022-247X(72)90253-3
Roger D. Nussbaum, The fixed point index and some applications, Séminaire de Mathématiques Supérieures [Seminar on Higher Mathematics], vol. 94, Presses de l’Université de Montréal, Montreal, QC, 1985. MR 791918
Roger D. Nussbaum, Hilbert’s projective metric and iterated nonlinear maps, Mem. Amer. Math. Soc. 75 (1988), no. 391, iv+137. MR 961211, DOI 10.1090/memo/0391
Roger D. Nussbaum, Iterated nonlinear maps and Hilbert’s projective metric. II, Mem. Amer. Math. Soc. 79 (1989), no. 401, iv+118. MR 963567, DOI 10.1090/memo/0401
Roger D. Nussbaum, Finsler structures for the part metric and Hilbert’s projective metric and applications to ordinary differential equations, Differential Integral Equations 7 (1994), no. 5-6, 1649–1707. MR 1269677
Roger Nussbaum, Periodic points of positive linear operators and Perron-Frobenius operators, Integral Equations Operator Theory 39 (2001), no. 1, 41–97. MR 1806843, DOI 10.1007/BF01192149
R. D. Nussbaum and S. M. Verduyn Lunel, Generalizations of the Perron-Frobenius theorem for nonlinear maps, Mem. Amer. Math. Soc. 138 (1999), no. 659, viii+98. MR 1470912, DOI 10.1090/memo/0659
Adam M. Oberman, A convergent difference scheme for the infinity Laplacian: construction of absolutely minimizing Lipschitz extensions, Math. Comp. 74 (2005), no. 251, 1217–1230. MR 2137000, DOI 10.1090/S0025-5718-04-01688-6
Jean-Paul Penot, On regularity conditions in mathematical programming, Math. Programming Stud. 19 (1982), 167–199. Optimality and stability in mathematical programming. MR 669731, DOI 10.1007/bfb0120988
Benoît Perthame, Transport equations in biology, Frontiers in Mathematics, Birkhäuser Verlag, Basel, 2007. MR 2270822, DOI 10.1007/978-3-7643-7842-4
A. J. B. Potter, Applications of Hilbert’s projective metric to certain classes of non-homogeneous operators, Quart. J. Math. Oxford Ser. (2) 28 (1977), no. 109, 93–99. MR 442768, DOI 10.1093/qmath/28.1.93
Yuval Peres, Oded Schramm, Scott Sheffield, and David B. Wilson, Tug-of-war and the infinity Laplacian, J. Amer. Math. Soc. 22 (2009), no. 1, 167–210. MR 2449057, DOI 10.1090/S0894-0347-08-00606-1
R. Tyrrell Rockafellar, Convex analysis, Princeton Mathematical Series, No. 28, Princeton University Press, Princeton, N.J., 1970. MR 0274683, DOI 10.1515/9781400873173
Dinah Rosenberg and Sylvain Sorin, An operator approach to zero-sum repeated games, Israel J. Math. 121 (2001), 221–246. MR 1818389, DOI 10.1007/BF02802505
R. Tyrrell Rockafellar and Roger J.-B. Wets, Variational analysis, Grundlehren der mathematischen Wissenschaften [Fundamental Principles of Mathematical Sciences], vol. 317, Springer-Verlag, Berlin, 1998. MR 1491362, DOI 10.1007/978-3-642-02431-3
C. Sabot, Existence and uniqueness of diffusions on finitely ramified self-similar fractals, Ann. Sci. École Norm. Sup. (4) 30 (1997), no. 5, 605–673 (English, with English and French summaries). MR 1474807, DOI 10.1016/S0012-9593(97)89934-X
Helmut H. Schaefer, Banach lattices and positive operators, Die Grundlehren der mathematischen Wissenschaften, Band 215, Springer-Verlag, New York-Heidelberg, 1974. MR 0423039, DOI 10.1007/978-3-642-65970-6
H. H. Schaefer and M. P. Wolff, Topological vector spaces, 2nd ed., Graduate Texts in Mathematics, vol. 3, Springer-Verlag, New York, 1999. MR 1741419, DOI 10.1007/978-1-4612-1468-7
A. C. Thompson, On certain contraction mappings in a partially ordered vector space. , Proc. Amer. Math. soc. 14 (1963), 438–443. MR 0149237, DOI 10.1090/S0002-9939-1963-0149237-7
P. P. Zabreĭko, M. A. Krasnosel′skiĭ, and Ju. V. Pokornyĭ, A certain class of positive linear operators, Funkcional. Anal. i Priložen. 5 (1971), no. 4, 9–17 (Russian). MR 0291838