×

zbMATH — the first resource for mathematics

Spectral theorem for convex monotone homogeneous maps, and ergodic control. (English) Zbl 1030.47048
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.

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
PDF BibTeX XML Cite
Full Text: DOI arXiv
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. · 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. · 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 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 New York
[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 New York/Paris
[9] Berman, A.; Plemmons, R.J., Nonnegative matrices in the mathematical sciences, classics in applied mathematics, (1994), SIAM Philadelphia, PA
[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.
[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. · 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.
[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.
[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 Berlin
[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 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. · 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. · 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.
[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.
[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.
[27] 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.
[29] Hernández-Lerma, O.; Lasserre, J.-B., Discrete-time Markov control processes, (1996), 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. · 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. · Zbl 0925.47016
[33] Kolokoltsov, V.N.; Maslov, V.P., Idempotent analysis and applications, (1997), 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.
[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.
[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.
[40] Maslov, V.P.; Samborskiı̆, S.N., Idempotent analysis, Advances in soviet mathematics, Vol. 13, (1992), American Mathematical Society Providence, RI
[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. · 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.
[44] Morishima, M., Equilibrium, stability, and growth: A multi-sectoral analysis, (1964), 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 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, NJ · Zbl 0229.90020
[58] Rockafellar, R.T.; Wets, R.J.-B., Variational analysis, (1998), 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)
[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). · 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 l1-spaces, European J. combin., 9, 1, 73-81, (1988) · Zbl 0639.47046
[64] Scheutzow, M., Erratum: periods of nonexpansive operators on finite l1-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)
[69] 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. · Zbl 0664.47036
[71] 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. · Zbl 0856.49003
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. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.