Spectral theorem for convex monotone homogeneous maps, and ergodic control. (English) Zbl 1030.47048

Akian, Marianne; Gaubert, Stéphane

Nonlinear Anal., Theory Methods Appl., Ser. A, Theory Methods 52, No. 2, 637-679 (2003).

In this paper, the authors consider a convex map \(f:\mathbb R^n\to\mathbb R^n\) which is monotone and nonexpansive for the sup-norm and show that the fixed point set of \(f\), when it is nonempty, is isomorphic to a convex inf-subsemilattice of \(\mathbb R^n\), whose dimension is at most equal to the number of strongly connected components of a critical graph defined from the tangent affine maps of \(f\). This yields in particular a uniqueness result for the bias vector of ergodic control problems, which generalizes results obtained previously by Lanery, Romanovsky, and Schweitzer and Federgruen.

Reviewer: Sotiris K. Ntouyas (Ioannina)

MSC:

47J10	Nonlinear spectral theory, nonlinear eigenvalue problems
93E20	Optimal stochastic control
47H09	Contraction-type mappings, nonexpansive mappings, \(A\)-proper mappings, etc.
15A80	Max-plus and related algebras
15B48	Positive matrices and their generalizations; cones of matrices

Keywords:

Nonexpansive maps; periodic orbits; eigenspace; spectral theorem

References:

[1]	Akcoglu, M. A.; Krengel, U., Nonlinear models of diffusion on a finite space, Probab. Theory Related Fields, 76, 4, 411-420 (1987) · Zbl 0611.60070
[2]	M. Akian, S. Gaubert, A spectral theorem for convex monotone homogeneous maps, in: Proceedings of the Satellite Workshop on Max-Plus Algebras, IFAC SSSC’01, Praha, Elsevier, Amsterdam, 2001.; M. Akian, S. Gaubert, A spectral theorem for convex monotone homogeneous maps, in: Proceedings of the Satellite Workshop on Max-Plus Algebras, IFAC SSSC’01, Praha, Elsevier, Amsterdam, 2001. · Zbl 1030.47048
[3]	M. Akian, J.-P. Quadrat, M. Viot, Duality between probability and optimization, in: J. Gunawardena (Ed.), Idempotency, Publications of the Isaac Newton Institute, Cambridge University Press, Cambridge, 1998.; M. Akian, J.-P. Quadrat, M. Viot, Duality between probability and optimization, in: J. Gunawardena (Ed.), Idempotency, Publications of the Isaac Newton Institute, Cambridge University Press, Cambridge, 1998. · Zbl 0906.60031
[4]	Akian, M.; Sulem, A.; Taksar, M., Dynamic optimisation of long term growth rate for a portfolio with transaction costs and logarithmic utility, Math. Finance, 11, 2, 153-188 (2001) · Zbl 1055.91016
[5]	Aliprantis, C. D.; Border, K. C., Infinite Dimensional Analysis, A Hitchiker’s Guide (1999), Springer: Springer Berlin · Zbl 0938.46001
[6]	Baccelli, F.; Cohen, G.; Olsder, G. J.; Quadrat, J.-P., Synchronization and Linearity: An Algebra for Discrete Events Systems (1992), Wiley: Wiley New York · Zbl 0824.93003
[7]	Bapat, R. B., A max version of the Perron-Frobenius theorem, Linear Algebra Appl., 275/276, 3-18 (1998) · Zbl 0941.15020
[8]	Bensoussan, A., Perturbation Methods in Optimal Control (1988), Wiley/Gauthier-Villars: Wiley/Gauthier-Villars New York/Paris · Zbl 0648.49001
[9]	Berman, A.; Plemmons, R. J., Nonnegative matrices in the mathematical sciences, Classics in Applied Mathematics (1994), SIAM: SIAM Philadelphia, PA · Zbl 0815.15016
[10]	Bewley, T.; Kohlberg, E., The asymptotic solution of a recursion equation occurring in stochastic games, Math. Oper. Res., 1, 4, 321-336 (1976) · Zbl 0364.93032
[11]	Bougerol, P., Almost sure stabilizability and Riccati’s equation of linear systems with random parameters, SIAM J. Control Optim., 33, 3, 702-717 (1995) · Zbl 0827.93066
[12]	Bruck, R. E., Properties of fixed-point sets of nonexpansive mappings in Banach spaces, Trans. Amer. Math. Soc., 179, 251-262 (1973) · Zbl 0265.47043
[13]	G. Cohen, D. Dubois, J.-P. Quadrat, M. Viot, Analyse du comportement périodique des systèmes de production par la théorie des dioı̈des, Rapport de recherche 191, INRIA, Le Chesnay, France, 1983.; G. Cohen, D. Dubois, J.-P. Quadrat, M. Viot, Analyse du comportement périodique des systèmes de production par la théorie des dioı̈des, Rapport de recherche 191, INRIA, Le Chesnay, France, 1983.
[14]	G. Cohen, S. Gaubert, J.-P. Quadrat, Algebraic system analysis of timed Petri nets, in: J. Gunawardena (Ed.), Idempotency, Publications of the Isaac Newton Institute, Cambridge University Press, Cambridge, 1998.; G. Cohen, S. Gaubert, J.-P. Quadrat, Algebraic system analysis of timed Petri nets, in: J. Gunawardena (Ed.), Idempotency, Publications of the Isaac Newton Institute, Cambridge University Press, Cambridge, 1998. · Zbl 0897.68069
[15]	G. Cohen, S. Gaubert, J.-P. Quadrat, Asymptotic throughput of continuous timed petri nets, in: Proceedings of the 34th Conference on Decision and Control, New Orleans, December, IEEE Press, New York, 1995.; G. Cohen, S. Gaubert, J.-P. Quadrat, Asymptotic throughput of continuous timed petri nets, in: Proceedings of the 34th Conference on Decision and Control, New Orleans, December, IEEE Press, New York, 1995.
[16]	G. Cohen, S. Gaubert, J.-P. Quadrat, Linear projectors in the max-plus algebra, in: Proceedings of the IEEE Mediterranean Conference, Cyprus, IEEE Press, New York, 1997.; G. Cohen, S. Gaubert, J.-P. Quadrat, Linear projectors in the max-plus algebra, in: Proceedings of the IEEE Mediterranean Conference, Cyprus, IEEE Press, New York, 1997.
[17]	Crandall, M. G.; Tartar, L., Some relations between nonexpansive and order preserving maps, Proc. AMS, 78, 3, 385-390 (1980) · Zbl 0449.47059
[18]	Cuninghame-Green, R., Minimax Algebra (1979), Springer: Springer Berlin · Zbl 0399.90052
[19]	Dellacherie, C., Théorie générale du potentiel, I, Astérisque, 236, 109-124 (1996) · Zbl 0869.31015
[20]	Filar, J. A.; Vrieze, K., Competitive Markov Decision Processes (1997), Springer: Springer Berlin · Zbl 0934.91002
[21]	S. Gaubert, J. Gunawardena, A non-linear hierarchy for discrete event dynamical systems, in: Proceedings of the Fourth Workshop on Discrete Event Systems (WODES98), Cagliari, Italy, IEE Press, London, 1998.; S. Gaubert, J. Gunawardena, A non-linear hierarchy for discrete event dynamical systems, in: Proceedings of the Fourth Workshop on Discrete Event Systems (WODES98), Cagliari, Italy, IEE Press, London, 1998. · Zbl 0933.49017
[22]	S. Gaubert, J. Gunawardena, The Perron-Frobenius theorem for homogeneous, monotone functions, Hewlett-Packard Technical Report 2001-12, HPL-BRIMS, 2001, arXiv:math.FA/0105091.; S. Gaubert, J. Gunawardena, The Perron-Frobenius theorem for homogeneous, monotone functions, Hewlett-Packard Technical Report 2001-12, HPL-BRIMS, 2001, arXiv:math.FA/0105091. · Zbl 1067.47064
[23]	S. Gaubert, M. Plus, Methods and applications of (max,+) linear algebra, in: Proceedings of STACS’97, Rapport de recherche, INRIA 3088, 1997.; S. Gaubert, M. Plus, Methods and applications of (max,+) linear algebra, in: Proceedings of STACS’97, Rapport de recherche, INRIA 3088, 1997.
[24]	M. Gondran, M. Minoux, Valeurs propres et vecteurs propres dans les dioı̈des et leur interprétation en théorie des graphes, Bull. Direction Études Recherches Sér. C Math. Informat. 2 (1977) i, 25-41.; M. Gondran, M. Minoux, Valeurs propres et vecteurs propres dans les dioı̈des et leur interprétation en théorie des graphes, Bull. Direction Études Recherches Sér. C Math. Informat. 2 (1977) i, 25-41.
[25]	Gunawardena, J., Min-max functions, Discrete Event Dyn. Systems, 4, 377-406 (1994) · Zbl 0841.93029
[26]	J. Gunawardena (Ed.), Idempotency, Publications of the Isaac Newton Institute, Cambridge University Press, Cambridge, 1998.; J. Gunawardena (Ed.), Idempotency, Publications of the Isaac Newton Institute, Cambridge University Press, Cambridge, 1998.
[27]	J. Gunawardena, From max-plus algebra to nonexpansive maps: a nonlinear theory for discrete event systems, Theoret. Comput. Sci., 2001, to appear.; J. Gunawardena, From max-plus algebra to nonexpansive maps: a nonlinear theory for discrete event systems, Theoret. Comput. Sci., 2001, to appear. · Zbl 1036.93045
[28]	J. Gunawardena, M. Keane, On the existence of cycle times for some nonexpansive maps, BRIMS Technical Report HPL-BRIMS-95-003, Hewlett-Packard Labs, 1995.; J. Gunawardena, M. Keane, On the existence of cycle times for some nonexpansive maps, BRIMS Technical Report HPL-BRIMS-95-003, Hewlett-Packard Labs, 1995.
[29]	Hernández-Lerma, O.; Lasserre, J.-B., Discrete-Time Markov Control Processes (1996), Springer: Springer Berlin · Zbl 0724.93087
[30]	J.G. Kemeny, J.L. Snell, A.W. Knapp, Denumerable Markov Chains, The University Series in Higher Mathematics, Van Nostrand, Princeton, NJ, 1966.; J.G. Kemeny, J.L. Snell, A.W. Knapp, Denumerable Markov Chains, The University Series in Higher Mathematics, Van Nostrand, Princeton, NJ, 1966. · Zbl 0149.13301
[31]	Kohlberg, E., Invariant half-lines of nonexpansive piecewise-linear transformations, Math. Oper. Res., 5, 3, 366-372 (1980) · Zbl 0442.90102
[32]	V.N. Kolokoltsov, On linear, additive and homogeneous operators in idempotent analysis, in: V.P. Maslov, S.N. Samborski (Eds), Idempotent Analysis, Advances in Soviet Mathematics, Vol. 13, American Mathematical Society, Providence, RI, 1992.; V.N. Kolokoltsov, On linear, additive and homogeneous operators in idempotent analysis, in: V.P. Maslov, S.N. Samborski (Eds), Idempotent Analysis, Advances in Soviet Mathematics, Vol. 13, American Mathematical Society, Providence, RI, 1992. · Zbl 0925.47016
[33]	Kolokoltsov, V. N.; Maslov, V. P., Idempotent Analysis and Applications (1997), Kluwer Academic Publishers: Kluwer Academic Publishers Dordrecht · Zbl 0941.93001
[34]	Kreı̆n, M. G.; Rutman, M. A., Linear operators leaving invariant a cone in a Banach space, Amer. Math. Soc. (Transl.), 1950, 26, 128 (1950) · Zbl 0030.12902
[35]	Lanery, E., Étude asymptotique des systèmes markoviens à commande, Rev. Française Informat. Recherche Opérationnelle, 1, 5, 3-56 (1967) · Zbl 0159.48804
[36]	B. Lemmens, Iteration of nonexpansive maps under the 1-norm, Ph.D. Thesis, Vrije Universiteit, Amsterdam, 2001.; B. Lemmens, Iteration of nonexpansive maps under the 1-norm, Ph.D. Thesis, Vrije Universiteit, Amsterdam, 2001.
[37]	G.L. Litvinov, V.P. Maslov, G.B. Shpiz, Idempotent functional analysis: an algebraical approach, 2000, E-print arxiv:math.FA/0009128, http://arXiv.org; G.L. Litvinov, V.P. Maslov, G.B. Shpiz, Idempotent functional analysis: an algebraical approach, 2000, E-print arxiv:math.FA/0009128, http://arXiv.org
[38]	Liverani, C.; Wojtkowski, M., Generalization of the Hilbert metric to the space of positive definite matrices, Pacific. J. Math., 2, 339-355 (1994) · Zbl 0824.53019
[39]	V.P. Maslov, Méthodes Operatorielles, Mir, Moscou, 1973, trad. fr. 1987.; V.P. Maslov, Méthodes Operatorielles, Mir, Moscou, 1973, trad. fr. 1987.
[40]	Maslov, V. P.; Samborskiı̆, S. N., Idempotent Analysis, Advances in Soviet Mathematics, Vol. 13 (1992), American Mathematical Society: American Mathematical Society Providence, RI · Zbl 0772.00015
[41]	Menon, M.; Schneider, H., The spectrum of an operator associated with a matrix, Linear Algebra Appl., 2, 321-334 (1969) · Zbl 0183.30902
[42]	P.De Moral, Maslov optimization theory: topological aspects, in: J. Gunawardena (Ed.), Idempotency, Publications of the Isaac Newton Institute, Cambridge University Press, Cambridge, 1998.; P.De Moral, Maslov optimization theory: topological aspects, in: J. Gunawardena (Ed.), Idempotency, Publications of the Isaac Newton Institute, Cambridge University Press, Cambridge, 1998. · Zbl 0905.60036
[43]	P.De Moral, T. Thuillet, G. Rigal, G. Salut, Optimal versus random processes: the nonlinear case, Rapport de recherche, LAAS, 1990.; P.De Moral, T. Thuillet, G. Rigal, G. Salut, Optimal versus random processes: the nonlinear case, Rapport de recherche, LAAS, 1990.
[44]	Morishima, M., Equilibrium, Stability, and Growth: A Multi-Sectoral Analysis (1964), Clarendon Press: Clarendon Press Oxford · Zbl 0117.15406
[45]	Nussbaum, R. D., Convexity and log-convexity for the spectral radius, Linear Algebra Appl., 73, 59-122 (1986) · Zbl 0588.15016
[46]	Nussbaum, R. D., Hilbert’s projective metric and iterated nonlinear maps, Mem. Ames. Math. Soc., 75, 391, iv, 137 (1988) · Zbl 0666.47028
[47]	Nussbaum, R. D., Iterated nonlinear maps and Hilbert’s projective metric, II, Mem. Ames. Math. Soc., 79, 401, iv, 118 (1989) · Zbl 0669.47031
[48]	Nussbaum, R. D., Omega limit sets of nonexpansive maps: finiteness and cardinality estimates, Differential Integral Equations, 3, 3, 523-540 (1990) · Zbl 0735.47033
[49]	Nussbaum, R. D., Convergence of iterates of a nonlinear operator arising in statistical mechanics, Nonlinearity, 4, 4, 1223-1240 (1991) · Zbl 0753.47026
[50]	Nussbaum, R. D., Estimates of the periods of periodic points for nonexpansive operators, Israel J. Math., 76, 3, 345-380 (1991) · Zbl 0774.47027
[51]	Nussbaum, R. D.; Scheutzow, M.; Verduyn Lunel, S. M., Periodic points of nonexpansive maps and nonlinear generalizations of the Perron-Frobenius theory, Selecta Math. (N.S.), 4, 1, 141-181 (1998) · Zbl 0923.47031
[52]	Nussbaum, R. D.; Verduyn Lunel, S. M., Generalizations of the Perron-Frobenius theorem for nonlinear maps, Mem. Amer. Math. Soc., 138, 659, viii+98 (1999) · Zbl 0933.47036
[53]	Oshime, Y., Nonlinear Perron-Frobenius problem for weakly contractive transformations, Math. Japonica, 29, 5, 681-704 (1984) · Zbl 0599.47092
[54]	Puhalskiı̆, A., Large Deviations and Idempotent Probability, Monographs and Surveys in Pure and Applied Mathematics, Vol. 119 (2001), Chapman & Hall: Chapman & Hall London · Zbl 0983.60003
[55]	Quadrat, J.-P., Théorèmes asymptotiques en programmation dynamique, C.R.A.S., 311, 745-748 (1990) · Zbl 0711.90082
[56]	Quadrat, J.-P.; Plus, M., Min-plus linearity and statistical mechanics, Markov Process. Related Fields, 3, 4, 565-587 (1997) · Zbl 0905.90174
[57]	Rockafellar, R. T., Convex Analysis (1970), Princeton University Press: Princeton University Press Princeton, NJ · Zbl 0229.90020
[58]	Rockafellar, R. T.; Wets, R. J.-B., Variational Analysis (1998), Springer: Springer Berlin · Zbl 0888.49001
[59]	Romanovskiı̆, I. V., Optimization of stationary control of discrete deterministic process in dynamic programming, Kibernetika, 3, 2, 66-78 (1967) · Zbl 0178.10301
[60]	I.V. Romanovsky, On the solvability of Bellman’s functional equation for a Markovian decision process, J. Math. Anal. Appl. 42 (1973) 485-498 (Collection of articles dedicated to Salomon Bochner).; I.V. Romanovsky, On the solvability of Bellman’s functional equation for a Markovian decision process, J. Math. Anal. Appl. 42 (1973) 485-498 (Collection of articles dedicated to Salomon Bochner). · Zbl 0263.90041
[61]	Rosenberg, D.; Sorin, S., An operator approach to zero-sum repeated games, Israel J. Math., 121, 221-246 (2001) · Zbl 1054.91014
[62]	Sabot, C., Existence and uniqueness of diffusions on finitely ramified self-similar fractals, Ann. Sci. École Norm. Sup. (4), 30, 5, 605-673 (1997) · Zbl 0924.60064
[63]	Scheutzow, M., Periods of nonexpansive operators on finite \(l_1\)-spaces, European J. Combin., 9, 1, 73-81 (1988) · Zbl 0639.47046
[64]	Scheutzow, M., Erratum: Periods of nonexpansive operators on finite \(l_1\)-spaces, European J. Combin., 12, 2, 183 (1991) · Zbl 0722.47043
[65]	Schweitzer, P. J.; Federgruen, A., The asymptotic behavior of undiscounted value iteration in Markov decision problems, Math. Oper. Res., 2, 4, 360-381 (1978) · Zbl 0402.90098
[66]	Schweitzer, P. J.; Federgruen, A., The functional equations of undiscounted Markov renewal programming, Math. Oper. Res., 3, 4, 308-321 (1978) · Zbl 0388.90083
[67]	Sine, R., A nonlinear Perron-Frobenius theorem, Proc. Amer. Math. Soc., 109, 2, 331-336 (1990) · Zbl 0698.47040
[68]	Vincent, J.-M., Some ergodic results on stochastic iterative discrete event systems, Discrete Event Dyn. Systems, 7, 209-233 (1997) · Zbl 0880.93057
[69]	N.N. Vorobyev, Extremal algebra of positive matrices, Elektron. Informationsverarbeitung und Kybernetik 3 (1967) 39-71 (in Russian).; N.N. Vorobyev, Extremal algebra of positive matrices, Elektron. Informationsverarbeitung und Kybernetik 3 (1967) 39-71 (in Russian).
[70]	D. Weller, Hilbert’s metric, part metric and self mappings of a cone, Ph.D. Thesis, Universität Bremen, Germany, December 1987.; D. Weller, Hilbert’s metric, part metric and self mappings of a cone, Ph.D. Thesis, Universität Bremen, Germany, December 1987. · Zbl 0664.47036
[71]	P. Whittle, Optimization Over Time, Vol. II, Wiley, New York, 1986.; P. Whittle, Optimization Over Time, Vol. II, Wiley, New York, 1986.
[72]	Wojtkowski, M., Invariant families of cones and Lyapunov exponents, Ergodic Theory Dyn. Systems, 5, 145-161 (1985) · Zbl 0578.58033
[73]	S.Y. Yakovenko, L.A. Kontorer, Nonlinear semigroups and infinite horizon optimization, in: V.P. Maslov, S.N. Samborski (Eds), Idempotent Analysis, Advances in Soviet Mathematics, Vol. 13, American Mathematical Society, Providence, RI, 1992.; S.Y. Yakovenko, L.A. Kontorer, Nonlinear semigroups and infinite horizon optimization, in: V.P. Maslov, S.N. Samborski (Eds), Idempotent Analysis, Advances in Soviet Mathematics, Vol. 13, American Mathematical Society, Providence, RI, 1992. · Zbl 0856.49003