Remote Access Transactions of the American Mathematical Society
Green Open Access

Transactions of the American Mathematical Society

ISSN 1088-6850(online) ISSN 0002-9947(print)

 
 

 

Uniqueness of the fixed point of nonexpansive semidifferentiable maps


Authors: Marianne Akian, Stéphane Gaubert and Roger Nussbaum
Journal: Trans. Amer. Math. Soc. 368 (2016), 1271-1320
MSC (2010): Primary 47H07, 47H09, 47H10, 47J10; Secondary 91A20
DOI: https://doi.org/10.1090/S0002-9947-2015-06413-7
Published electronically: February 19, 2015
MathSciNet review: 3430364
Full-text PDF

Abstract | References | Similar Articles | Additional Information

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 [Enhancements On Off] (What's this?)

  • [AB99] Charalambos D. Aliprantis and Kim C. Border, Infinite-dimensional analysis: A hitchhiker's guide, 2nd ed., Springer-Verlag, Berlin, 1999. MR 1717083 (2000k:46001)
  • [AG03] 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 (2003i:93085), https://doi.org/10.1016/S0362-546X(02)00170-0
  • [AGG12] 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, https://doi.org/10.1142/S0218196711006674
  • [AGLN06] 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 (2008g:37018), https://doi.org/10.1017/S0305004105008832
  • [AGN11] 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.
  • [AS08] 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 (2008k:92019), https://doi.org/10.1016/j.nonrwa.2006.09.006
  • [Bir57] Garrett Birkhoff, Extensions of Jentzsch's theorem, Trans. Amer. Math. Soc. 85 (1957), 219-227. MR 0087058 (19,296a)
  • [Bir62] Garrett Birkhoff, Uniformly semi-primitive multiplicative processes, Trans. Amer. Math. Soc. 104 (1962), 37-51. MR 0146100 (26 #3626)
  • [BK66] Garrett Birkhoff and Leon Kotin, Integro-differential delay equations of positive type, J. Differential Equations 2 (1966), 320-327. MR 0198169 (33 #6328)
  • [BLN94] 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 (96b:47067), https://doi.org/10.1006/jfan.1994.1089
  • [Blu53] Leonard M. Blumenthal, Theory and applications of distance geometry, Oxford, at the Clarendon Press, 1953. MR 0054981 (14,1009a)
  • [Bon58] F. F. Bonsall, Linear operators in complete positive cones, Proc. London Math. Soc. (3) 8 (1958), 53-75. MR 0092938 (19,1183c)
  • [Bou95] 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 (96b:93085), https://doi.org/10.1137/S0363012992229069
  • [Bus73] P. J. Bushell, Hilbert's metric and positive contraction mappings in a Banach space, Arch. Rational Mech. Anal. 52 (1973), 330-338. MR 0336473 (49 #1247)
  • [Bus86] 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 (88d:47071), https://doi.org/10.1016/0024-3795(86)90319-8
  • [CT80] 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 (81a:47054), https://doi.org/10.2307/2042330
  • [Fur63] Harry Furstenberg, Noncommuting random products, Trans. Amer. Math. Soc. 108 (1963), 377-428. MR 0163345 (29 #648)
  • [FV97] Jerzy Filar and Koos Vrieze, Competitive Markov decision processes, Springer-Verlag, New York, 1997. MR 1418636 (97g:90003)
  • [GG04] Stéphane Gaubert and Jeremy Gunawardena, The Perron-Frobenius theorem for homogeneous, monotone functions, Trans. Amer. Math. Soc. 356 (2004), no. 12, 4931-4950 (electronic). MR 2084406 (2006d:15038), https://doi.org/10.1090/S0002-9947-04-03470-1
  • [GV12] 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, https://doi.org/10.1017/S0305004111000673
  • [HJ10a] 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 (2011f:34088), https://doi.org/10.1016/j.nonrwa.2009.11.015
  • [HJ10b] 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 (2011k:34096), https://doi.org/10.1090/S0002-9939-2010-10389-1
  • [Hop63] Eberhard Hopf, An inequality for positive linear integral operators, J. Math. Mech. 12 (1963), 683-692. MR 0165325 (29 #2614)
  • [Hör94] 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 (95h:35255)
  • [Kat95] Tosio Kato, Perturbation theory for linear operators, Classics in Mathematics, Springer-Verlag, Berlin, 1995. Reprint of the 1980 edition. MR 1335452 (96a:47025)
  • [Kol92] V. N. Kolokoltsov, 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 (93k:47065)
  • [KR48] 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 (10,256c)
  • [Kra64] M. A. Krasnoselskiĭ, Positive solutions of operator equations, Translated from the Russian by Richard E. Flaherty; edited by Leo F. Boron, P. Noordhoff Ltd., Groningen, 1964. MR 0181881 (31 #6107)
  • [Kra01] 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 (2004f:39038), https://doi.org/10.1016/S0362-546X(01)00281-4
  • [LLP$^+$99] 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 (2001f:91023), https://doi.org/10.1006/game.1998.0676
  • [LN12] B. Lemmens and R. D. Nussbaum.
    Non-linear Perron-Frobenius theory, volume 189 of Cambridge Tracts in Mathematics.
    Cambridge University Press, 2012.
  • [Met05] Volker Metz, The short-cut test, J. Funct. Anal. 220 (2005), no. 1, 118-156. MR 2114701 (2005k:31026), https://doi.org/10.1016/j.jfa.2004.06.008
  • [MN91] Peter Meyer-Nieberg, Banach lattices, Universitext, Springer-Verlag, Berlin, 1991. MR 1128093 (93f:46025)
  • [Mor64] Michio Morishima, Equilibrium, stability, and growth: A multi-sectoral analysis, Clarendon Press, Oxford, 1964. MR 0183526 (32 #1006)
  • [MPN02] 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 (2003c:47088), https://doi.org/10.3934/dcds.2002.8.519
  • [MPN10] 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 (2011j:47148), https://doi.org/10.1007/s11784-010-0010-3
  • [MPN11a] John Mallet-Paret and Roger D. Nussbaum, Inequivalent measures of noncompactness, Ann. Mat. Pura Appl. (4) 190 (2011), no. 3, 453-488. MR 2825257, https://doi.org/10.1007/s10231-010-0158-x
  • [MPN11b] 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 (2011m:47010), https://doi.org/10.1090/S0002-9939-2010-10511-7
  • [MS69] M. V. Menon and Hans Schneider, The spectrum of a nonlinear operator associated with a matrix, Linear Algebra and Appl. 2 (1969), 321-334. MR 0246893 (40 #162)
  • [MS96] 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 (99c:60091)
  • [Ney03] 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 (2004m:91027), https://doi.org/10.1007/978-94-010-0189-2_26
  • [NS03] 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 (2004h:91004)
  • [Nus71] Roger D. Nussbaum, The fixed point index for local condensing maps, Ann. Mat. Pura Appl. (4) 89 (1971), 217-258. MR 0312341 (47 #903)
  • [Nus72] Roger D. Nussbaum, Degree theory for local condensing maps, J. Math. Anal. Appl. 37 (1972), 741-766. MR 0306986 (46 #6107)
  • [Nus85] 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 (87a:47085)
  • [Nus88] Roger D. Nussbaum, Hilbert's projective metric and iterated nonlinear maps, Mem. Amer. Math. Soc. 75 (1988), no. 391, iv+137. MR 961211 (89m:47046), https://doi.org/10.1090/memo/0391
  • [Nus89] Roger D. Nussbaum, Iterated nonlinear maps and Hilbert's projective metric. II, Mem. Amer. Math. Soc. 79 (1989), no. 401, iv+118. MR 963567 (90c:47109), https://doi.org/10.1090/memo/0401
  • [Nus94] 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 (95b:58010)
  • [Nus01] Roger Nussbaum, Periodic points of positive linear operators and Perron-Frobenius operators, Integral Equations Operator Theory 39 (2001), no. 1, 41-97. MR 1806843 (2001m:47083), https://doi.org/10.1007/BF01192149
  • [NVL99] Roger 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 (99i:58125), https://doi.org/10.1090/memo/0659
  • [Obe05] 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 (electronic). MR 2137000 (2006h:65165), https://doi.org/10.1090/S0025-5718-04-01688-6
  • [Pen82] Jean-Paul Penot, On regularity conditions in mathematical programming: Optimality and stability in mathematical programming, Math. Programming Stud. 19 (1982), 167-199. MR 669731 (84d:90095)
  • [Per07] Benoît Perthame, Transport equations in biology, Frontiers in Mathematics, Birkhäuser Verlag, Basel, 2007. MR 2270822 (2007j:35004)
  • [Pot77] 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 0442768 (56 #1147)
  • [PSSW09] 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 (2009h:91004), https://doi.org/10.1090/S0894-0347-08-00606-1
  • [Roc70] R. Tyrrell Rockafellar, Convex analysis, Princeton Mathematical Series, No. 28, Princeton University Press, Princeton, N.J., 1970. MR 0274683 (43 #445)
  • [RS01] Dinah Rosenberg and Sylvain Sorin, An operator approach to zero-sum repeated games, Israel J. Math. 121 (2001), 221-246. MR 1818389 (2002k:91031), https://doi.org/10.1007/BF02802505
  • [RW98] 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 (98m:49001)
  • [Sab97] 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 (98h:60118), https://doi.org/10.1016/S0012-9593(97)89934-X
  • [Sch74] H. H. Schaefer, Banach lattices and positive operators, Springer-Verlag, New York-Heidelberg, 1974. Die Grundlehren der mathematischen Wissenschaften, Band 215. MR 0423039 (54 #11023)
  • [SW99] 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 (2000j:46001)
  • [Tho63] A. C. Thompson, On certain contraction mappings in a partially ordered vector space, Proc. Amer. Math. Soc. 14 (1963), 438-443. MR 0149237 (26 #6727)
  • [ZKP71] P. P. Zabreĭko, M. A. Krasnoselskiĭ, 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 (45 #928)

Similar Articles

Retrieve articles in Transactions of the American Mathematical Society with MSC (2010): 47H07, 47H09, 47H10, 47J10, 91A20

Retrieve articles in all journals with MSC (2010): 47H07, 47H09, 47H10, 47J10, 91A20


Additional Information

Marianne Akian
Affiliation: INRIA and CMAP, École Polytechnique, 91128 Palaiseau Cedex, France
Email: marianne.akian@inria.fr

Stéphane Gaubert
Affiliation: INRIA and CMAP, École Polytechnique, 91128 Palaiseau Cedex, France
Email: stephane.gaubert@inria.fr

Roger Nussbaum
Affiliation: Mathematics Department, Hill Center, Rutgers University, 110 Frelinghuysen Road, Piscataway, New Jersey 08854-8019
Email: nussbaum@math.rutgers.edu

DOI: https://doi.org/10.1090/S0002-9947-2015-06413-7
Keywords: Nonlinear eigenvector, Hilbert's metric, Thompson's metric, nonexpansive maps, AM-space with unit, semidifferentiability, nonlinear spectral radius, geometric convergence, zero-sum stochastic games, value iteration
Received by editor(s): February 15, 2012
Received by editor(s) in revised form: February 19, 2014
Published electronically: February 19, 2015
Additional Notes: The first and second authors were partially supported by the Arpege programme of the French National Agency of Research (ANR), project “ASOPT”, number ANR-08-SEGI-005
The third author was partially supported by NSFDMS 0701171 and by NSFDMS 1201328.
Article copyright: © Copyright 2015 American Mathematical Society

American Mathematical Society