• Previous Article
    Optimal control of the linear wave equation by time-depending BV-controls: A semi-smooth Newton approach
  • MCRF Home
  • This Issue
  • Next Article
    Optimal periodic control for scalar dynamics under integral constraint on the input
September  2020, 10(3): 573-590. doi: 10.3934/mcrf.2020011

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

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

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

Received  August 2018 Revised  November 2019 Published  September 2020 Early access  December 2019

Fund Project: 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

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.

Citation: Stéphane Gaubert, Nikolas Stott. A convergent hierarchy of non-linear eigenproblems to compute the joint spectral radius of nonnegative matrices. Mathematical Control and Related Fields, 2020, 10 (3) : 573-590. doi: 10.3934/mcrf.2020011
References:
[1]

A. A. AhmadiR. M. JungersP. 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. AkianS. 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. AkianS. GaubertJ. 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. AkianS. 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. AkianS. 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. CarliniM. 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. CominettiJ. 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. FriedlandS. 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. PhilippeR. EssickG. 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.

show all references

References:
[1]

A. A. AhmadiR. M. JungersP. 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. AkianS. 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. AkianS. GaubertJ. 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. AkianS. 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. AkianS. 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. CarliniM. 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. CominettiJ. 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. FriedlandS. 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. PhilippeR. EssickG. 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.

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 $%
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 $%
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
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
[1]

Marianne Akian, Stéphane Gaubert, Antoine Hochart. A game theory approach to the existence and uniqueness of nonlinear Perron-Frobenius eigenvectors. Discrete and Continuous Dynamical Systems, 2020, 40 (1) : 207-231. doi: 10.3934/dcds.2020009

[2]

Jiu Ding, Noah H. Rhee. A unified maximum entropy method via spline functions for Frobenius-Perron operators. Numerical Algebra, Control and Optimization, 2013, 3 (2) : 235-245. doi: 10.3934/naco.2013.3.235

[3]

Stefan Klus, Péter Koltai, Christof Schütte. On the numerical approximation of the Perron-Frobenius and Koopman operator. Journal of Computational Dynamics, 2016, 3 (1) : 51-79. doi: 10.3934/jcd.2016003

[4]

Victor Kozyakin. Iterative building of Barabanov norms and computation of the joint spectral radius for matrix sets. Discrete and Continuous Dynamical Systems - B, 2010, 14 (1) : 143-158. doi: 10.3934/dcdsb.2010.14.143

[5]

Martin Lustig, Caglar Uyanik. Perron-Frobenius theory and frequency convergence for reducible substitutions. Discrete and Continuous Dynamical Systems, 2017, 37 (1) : 355-385. doi: 10.3934/dcds.2017015

[6]

Gary Froyland, Ognjen Stancevic. Escape rates and Perron-Frobenius operators: Open and closed dynamical systems. Discrete and Continuous Dynamical Systems - B, 2010, 14 (2) : 457-472. doi: 10.3934/dcdsb.2010.14.457

[7]

Chaoqian Li, Yaqiang Wang, Jieyi Yi, Yaotang Li. Bounds for the spectral radius of nonnegative tensors. Journal of Industrial and Management Optimization, 2016, 12 (3) : 975-990. doi: 10.3934/jimo.2016.12.975

[8]

Jacob Ashiwere Abuchu, Godwin Chidi Ugwunnadi, Ojen Kumar Narain. Inertial Mann-Type iterative method for solving split monotone variational inclusion problem with applications. Journal of Industrial and Management Optimization, 2022  doi: 10.3934/jimo.2022075

[9]

Xiongping Dai, Yu Huang, Mingqing Xiao. Realization of joint spectral radius via Ergodic theory. Electronic Research Announcements, 2011, 18: 22-30. doi: 10.3934/era.2011.18.22

[10]

Victor Kozyakin. Minimax joint spectral radius and stabilizability of discrete-time linear switching control systems. Discrete and Continuous Dynamical Systems - B, 2019, 24 (8) : 3537-3556. doi: 10.3934/dcdsb.2018277

[11]

Mehdi Bastani, Davod Khojasteh Salkuyeh. On the GSOR iteration method for image restoration. Numerical Algebra, Control and Optimization, 2021, 11 (1) : 27-43. doi: 10.3934/naco.2020013

[12]

Yu-Feng Sun, Zheng Zeng, Jie Song. Quasilinear iterative method for the boundary value problem of nonlinear fractional differential equation. Numerical Algebra, Control and Optimization, 2020, 10 (2) : 157-164. doi: 10.3934/naco.2019045

[13]

Qun Lin, Ryan Loxton, Kok Lay Teo. The control parameterization method for nonlinear optimal control: A survey. Journal of Industrial and Management Optimization, 2014, 10 (1) : 275-309. doi: 10.3934/jimo.2014.10.275

[14]

Guimin Liu, Hongbin Lv. Bounds for spectral radius of nonnegative tensors using matrix-digragh-based approach. Journal of Industrial and Management Optimization, 2021  doi: 10.3934/jimo.2021176

[15]

Hongxia Yin. An iterative method for general variational inequalities. Journal of Industrial and Management Optimization, 2005, 1 (2) : 201-209. doi: 10.3934/jimo.2005.1.201

[16]

Gaohang Yu, Shanzhou Niu, Jianhua Ma. Multivariate spectral gradient projection method for nonlinear monotone equations with convex constraints. Journal of Industrial and Management Optimization, 2013, 9 (1) : 117-129. doi: 10.3934/jimo.2013.9.117

[17]

Chandan Pal, Somnath Pradhan. Zero-sum games for pure jump processes with risk-sensitive discounted cost criteria. Journal of Dynamics and Games, 2022, 9 (1) : 13-25. doi: 10.3934/jdg.2021020

[18]

Pierre Lissy. Construction of gevrey functions with compact support using the bray-mandelbrojt iterative process and applications to the moment method in control theory. Mathematical Control and Related Fields, 2017, 7 (1) : 21-40. doi: 10.3934/mcrf.2017002

[19]

Miao Yu, Haoyang Lu, Weipeng Shang. A new iterative identification method for damping control of power system in multi-interference. Discrete and Continuous Dynamical Systems - S, 2020, 13 (6) : 1773-1790. doi: 10.3934/dcdss.2020104

[20]

Zhen-Zhen Tao, Bing Sun. Galerkin spectral method for elliptic optimal control problem with $L^2$-norm control constraint. Discrete and Continuous Dynamical Systems - B, 2022, 27 (8) : 4121-4141. doi: 10.3934/dcdsb.2021220

2021 Impact Factor: 1.141

Metrics

  • PDF downloads (266)
  • HTML views (447)
  • Cited by (0)

Other articles
by authors

[Back to Top]