A convergent hierarchy of non-linear eigenproblems to compute the joint spectral radius of nonnegative matrices

Gaubert Stéphane; Stott Nikolas

doi:10.3934/mcrf.2020011

Article Contents

2020, Volume 10, Issue 3: 573-590. Doi: 10.3934/mcrf.2020011

This issue Previous Article Optimal periodic control for scalar dynamics under integral constraint on the input Next Article Optimal control of the linear wave equation by time-depending BV-controls: A semi-smooth Newton approach

A convergent hierarchy of non-linear eigenproblems to compute the joint spectral radius of nonnegative matrices

Gaubert Stéphane^1, , and
Stott Nikolas^2,

1.
INRIA and CMAP, École polytechnique, IP Paris, CNRS, CMAP, Route de Saclay, 91128 Palaiseau, France
2.
LocalSolver, 36 avenue Hoche, 75008 Paris, France

^* Corresponding author: Stéphane Gaubert
^* Corresponding author: Stéphane Gaubert

Dedicated to Fréderic Bonnans on the occasion of his 60th birthday

Received: July 31, 2018

Revised: October 31, 2019

Early access: December 2019

Published: July 2020

Stéphane Gaubert and Nikolas Stott were partially supported by the ANR projects MALTHY (ANR-13-INSE-0003) and DEMOCRITE (ANR-13-SECU-0007), by the PGMO program of EDF and Fondation Mathématique Jacques Hadamard, and by the "Investissement d'avenir", référence ANR-11-LABX-0056-LMH. S. Gaubert also gratefully acknowledges the support of the Mittag-Leffler institute

Abstract Full Text(HTML) Figure(0) / Table(2) Related Papers Cited by

Abstract

We show that the joint spectral radius of a finite collection of nonnegative matrices can be bounded by the eigenvalue of a non-linear operator. This eigenvalue coincides with the ergodic constant of a risk-sensitive control problem, or of an entropy game, in which the state space consists of all switching sequences of a given length. We show that, by increasing this length, we arrive at a convergent approximation scheme to compute the joint spectral radius. The complexity of this method is exponential in the length of the switching sequences, but it is quite insensitive to the size of the matrices, allowing us to solve very large scale instances (several matrices in dimensions of order 1000 within a minute). An idea of this method is to replace a hierarchy of optimization problems, introduced by Ahmadi, Jungers, Parrilo and Roozbehani, by a hierarchy of nonlinear eigenproblems. To solve the latter eigenproblems, we introduce a projective version of Krasnoselskii-Mann iteration. This method is of independent interest as it applies more generally to the nonlinear eigenproblem for a monotone positively homogeneous map. Here, this method allows for scalability by avoiding the recourse to linear or semidefinite programming techniques.

Keywords:

Mathematics Subject Classification: primary: 47H05; Secondary: 93C30, 49L20.

Citation:

Full Text(HTML)

Table 1. Convergence of the hierarchy on $ 5 \times 5 $ matrices

Level $ d $	CPU Time (s)	Eigenvalue $ \lambda_d $	Relative error
1	$ 0.01 $	$ 2.165 $	$ 6.8 $%
2	$ 0.01 $	$ 2.102 $	$ 3.7 $%
3	$ 0.01 $	$ 2.086 $	$ 2.9 $%
4	$ 0.01 $	$ 2.059 $	$ 1.6 $%
5	$ 0.02 $	$ 2.041 $	$ 0.7 $%
6	$ 0.05 $	$ 2.030 $	$ 0.1 $%
7	$ 0.7 $	$ 2.027 $	$ 0.0 $%
8	$ 0.32 $	$ 2.027 $	$ 0.0 $%
9	$ 1.12 $	$ 2.027 $	$ 0.0 $%

| Show Table

DownLoad: CSV

Table 2. Computation time for large matrices

Dimension $ n $	Level $ d $	Eigenvalue $ \lambda_d $	CPU Time
$ 10 $	$ 2 $	$ 4.287 $	$ 0.01 $ s
	$ 3 $	$ 4.286 $	$ 0.03 $ s
$ 20 $	$ 2 $	$ 8.582 $	$ 0.01 $ s
	$ 3 $	$ 8.576 $	$ 0.03 $ s
$ 50 $	$ 2 $	$ 22.34 $	$ 0.04 $ s
	$ 3 $	$ 22.33 $	$ 0.16 $ s
$ 100 $	$ 2 $	$ 44.45 $	$ 0.17 $ s
	$ 3 $	$ 44.45 $	$ 0.53 $ s
$ 200 $	$ 2 $	$ 89.77 $	$ 0.71 $ s
	$ 3 $	$ 89.76 $	$ 2.46 $ s
$ 500 $	$ 2 $	$ 224.88 $	$ 5.45 $ s
	$ 3 $	$ 224.88 $	$ 19.7 $ s
$ 1000 $	$ 2 $	$ 449.87 $	$ 44.0 $ s
	$ 3 $	$ 449.87 $	$ 2.7 $ min
$ 2000 $	$ 2 $	$ 889.96 $	$ 4.6 $ min
	$ 3 $	$ 889.96 $	$ 19.2 $ min
$ 5000 $	$ 2 $	$ 2249.69 $	$ 51.9 $ min
	$ 3 $	$ 2249.57 $	$ 3.3 $ h

| Show Table

DownLoad: CSV

Related Papers

Cited by

References

[1]	A. A. Ahmadi, R. M. Jungers, P. A. Parrilo and M. Roozbehani, Joint spectral radius and path-complete graph Lyapunov functions, SIAM J. Control and Optimization, 52 (2014), 687-717. doi: 10.1137/110855272.
[2]	M. Akian, S. Gaubert and A. Guterman, Tropical polyhedra are equivalent to mean payoff games, International Journal of Algebra and Computation, 22 (2012), 125001, 43 pp. doi: 10.1142/S0218196711006674.
[3]	M. Akian, S. Gaubert, J. Grand-Clément and J. Guillaud, The operator approach to entropy games, Theor. Comp. Sys., 63 (2019), 1089-1130. doi: 10.1007/s00224-019-09925-z.
[4]	M. Akian, S. Gaubert and A. Hochart, Generic uniqueness of the bias vector of finite stochastic games with perfect information, Journal of Mathematical Analysis and Applications, 457 (2018), 1038-1064. doi: 10.1016/j.jmaa.2017.07.017.
[5]	M. Akian, S. Gaubert and R. Nussbaum, A Collatz-Wielandt characterization of the spectral radius of order-preserving homogeneous maps on cones, (2011), arXiv: 1112.5968.
[6]	M. Akian, S. Gaubert and R. Nussbaum, Uniqueness of the fixed point of nonexpansive semidifferentiable maps, Trans. Amer. Math. Soc., 368 (2016), 1271-1320. doi: 10.1090/S0002-9947-2015-06413-7.
[7]	V. Anantharam and V. S. Borkar, A variational formula for risk-sensitive reward, arXiv: 1501.00676.
[8]	E. Asarin, J. Cervelle, A. Degorre, C. Dima, F. Horn and V. Kozyakin, Entropy games and matrix multiplication games, 33rd Symposium on Theoretical Aspects of Computer Science, LIPIcs. Leibniz Int. Proc. Inform., Schloss Dagstuhl, Leibniz-Zent. Inform., Wadern, (2016), Art. No. 11, 14 pp.
[9]	J.-B. Baillon and R. E. Bruck, Optimal rates of asymptotic regularity for averaged nonexpansive mappings, Fixed Point Theory and Applications (Halifax, NS, 1991), World Sci. Publ., River Edge, NJ, (1992), 27–66.
[10]	N. E. Barabanov, Lyapunov indicator for discrete inclusions. I, Autom. Remote Control, 49 (1988), 152-157.
[11]	V. D. Blondel and Y. Nesterov, Polynomial-time computation of the joint spectral radius for some sets of nonnegative matrices, SIAM J. Matrix Anal., 31 (2009), 865-876. doi: 10.1137/080723764.
[12]	O. Bokanowski and H. Zidani, Anti-dissipative schemes for advection and application to Hamilton-Jacobi-Bellman equations, J. Sci. Compt., 30 (2007), 1-33. doi: 10.1007/s10915-005-9017-0.
[13]	P. J. Bushell, Hilbert's metric and positive contraction mappings in a banach space, Archive for Rational Mechanics and Analysis, 52 (1973), 330-338. doi: 10.1007/BF00247467.
[14]	I. Capuzzo Dolcetta, On a discrete approximation of the Hamilton-Jacobi equation of dynamic programming, Appl. Math. Optim., 10 (1983), 367-377. doi: 10.1007/BF01448394.
[15]	E. Carlini, M. Falcone and R. Ferretti, An efficient algorithm for Hamilton-Jacobi equations in high dimension, Comput. Vis. Sci., 7 (2004), 15-29. doi: 10.1007/s00791-004-0124-5.
[16]	R. Cominetti, J. A. Soto and J. Vaisman, On the rate of convergence of Krasnosel'skii-Mann iterations and their connection with sums of Bernoullis, Israel Journal of Mathematics, 199 (2014), 757-772. doi: 10.1007/s11856-013-0045-4.
[17]	M. G. Crandall and P.-L. Lions, Two approximations of solutions of Hamilton-Jacobi equations, Math. Comp., 43 (1894), 1-19. doi: 10.1090/S0025-5718-1984-0744921-8.
[18]	M. Edelstein and R. C. O'Brien, Nonexpansive mappings, asymptotic regularity and successive approximations, J. London Math. Soc., 17 (1978), 547-554. doi: 10.1112/jlms/s2-17.3.547.
[19]	M. Falcone and R. Ferretti, Discrete time high-order schemes for viscosity solutions of Hamilton-Jacobi-Bellman equations, Numer. Math., 67 (1994), 315-344. doi: 10.1007/s002110050031.
[20]	S. Friedland, S. Gaubert and L. Han, Perron-Frobenius theorem for nonnegative multilinear forms and extensions, Linear Algebra and its Applications, 438 (2013), 738-749. doi: 10.1016/j.laa.2011.02.042.
[21]	S. Gaubert and J. Gunawardena, The Perron-Frobenius theorem for homogeneous, monotone functions, Trans. Amer. Math. Soc., 356 (2004), 4931-4950. doi: 10.1090/S0002-9947-04-03470-1.
[22]	S. Gaubert, W. McEneaney and Z. Qu, Curse of dimensionality reduction in max-plus based approximation methods: Theoretical estimates and improved pruning algorithms, Decision and Control and European Control Conference (CDC-ECC), 2011 50th IEEE Conference on, (2011), 1054–1061. doi: 10.1109/CDC.2011.6161386.
[23]	S. Gaubert and N. Stott, Tropical Kraus maps for optimal control of switched systems, 56th IEEE Conference on Decision and Control, CC 2017, Melbourne, Australia, (2017). doi: 10.1109/CDC.2017.8263839.
[24]	S. Gaubert and G. Vigeral, A maximin characterization of the escape rate of nonexpansive mappings in metrically convex spaces, Math. Proc. of Cambridge Phil. Soc., 152 (2012), 341-363. doi: 10.1017/S0305004111000673.
[25]	N. Guglielmi and V. Protasov, Exact computation of joint spectral characteristics of linear operators, Foundations of Computational Mathematics, 13 (2013), 37-97. doi: 10.1007/s10208-012-9121-0.
[26]	N. Guglielmi and M. Zennaro, Stability of linear problems: Joint spectral radius of sets of matrices, Current Challenges in Stability Issues for Numerical Differential Equations, Lecture Notes in Math., Fond. CIME/CIME Found. Subser., Springer, Cham, 2082 (2014), 265-313. doi: 10.1007/978-3-319-01300-8_5.
[27]	S. Ishikawa, Fixed points and iteration of a nonexpansive mapping in a Banach space, Proceedings of the American Mathematical Society, 59 (1976), 65-71. doi: 10.1090/S0002-9939-1976-0412909-X.
[28]	R. Jungers, Classical results and problems, Springer Berlin Heidelberg, Berlin, Heidelberg, (2009), 23–46.
[29]	R. Jungers, The Joint Spectral Radius. Theory and Applications, Lecture Notes in Control and Information Sciences, 385. Springer-Verlag, Berlin, 2009. doi: 10.1007/978-3-540-95980-9.
[30]	V. Kozyakin, Iterative building of barabanov norms and computation of the joint spectral radius for matrix sets, Discrete and Continuous Dynamical Systems Series-B, 14 (2010), 143-158. doi: 10.3934/dcdsb.2010.14.143.
[31]	M. A. Krasnosel'ski$\mathop {\rm{i}}\limits^ \vee $, Two remarks on the method of successive approximations, Uspekhi Matematicheskikh Nauk, 10 (1955), 123-127.
[32]	B. Lemmens and R. Nussbaum, Nonlinear Perron-Frobenius Theory, Cambridge Tracts in Mathematics, 189. Cambridge University Press, Cambridge, 2012. doi: 10.1017/CBO9781139026079.
[33]	J. Mallet-Paret and R. D. Nussbaum, Eigenvalues for a class of homogeneous cone maps arising from max-plus operators, Discrete and Continuous Dynamical Systems, 8 (2002), 519-562. doi: 10.3934/dcds.2002.8.519.
[34]	W. R. Mann, Mean value methods in iteration, Proceedings of the American Mathematical Society, 4 (1953), 506-510. doi: 10.1090/S0002-9939-1953-0054846-3.
[35]	W. M. McEneaney, A curse-of-dimensionality-free numerical method for solution of certain HJB PDEs, SIAM Journal on Control and Optimization, 46 (2007), 1239-1276. doi: 10.1137/040610830.
[36]	W. M. McEneaney and L. J. Kluberg, Convergence rate for a curse-of-dimensionality-free method for a class of HJB PDEs, SIAM J. Control Optim., 48 (2009/10), 3052-3079. doi: 10.1137/070681934.
[37]	R. D. Nussbaum, Convexity and log convexity for the spectral radius, Linear Algebra Appl., 73 (1986), 59-122. doi: 10.1016/0024-3795(86)90233-8.
[38]	R. D. Nussbaum, Hilbert's projective metric and iterated nonlinear maps, Mem. Amer. Math. Soc., 75 (1988). doi: 10.1090/memo/0391.
[39]	A. Papadopoulos and M. Troyanov, Weak Finsler structures and the Funk weak metric, Math. Proc. Cambridge Philos. Soc., 147 (2009), 419-437. doi: 10.1017/S0305004109002461.
[40]	M. Philippe, R. Essick, G. E. Dullerud and R. M. Jungers, Stability of discrete-time switching systems with constrained switching sequences, Automatica J. IFAC, 72 (2016), 242-250. doi: 10.1016/j.automatica.2016.05.015.
[41]	V. Y. Protasov, Spectral simplex method, Mathematical Programming, 156 (2016), 485-511. doi: 10.1007/s10107-015-0905-2.
[42]	Z. Qu, Contraction of Riccati flows applied to the convergence analysis of a max-plus curse-of-dimensionality-free method, SIAM Journal on Control and Optimization, 52 (2014), 2677-2706. doi: 10.1137/130906702.
[43]	N. Stott, Minimal Upper Bounds in the Löwner Order and Application to Invariant Computation for Switched Systems, Phd thesis, Université Paris-Saclay, École polytechnique, 2017.