Spectral simplex method

详细信息    查看全文

• 作者：Vladimir Yu. Protasov
• 关键词：Iterative optimization method ; Nonnegative matrix ; Spectral radius ; Cycling ; Spectrum of a graph ; Leontief model ; Positive linear switching system ; 15B48 ; 90C26 ; 15A42
• 刊名：Mathematical Programming
• 出版年：2016
• 出版时间：March 2016
• 年：2016
• 卷：156
• 期：1-2
• 页码：485-511
• 全文大小：576 KB
• 参考文献：1.Blondel, V.D., Nesterov, Y.: Polynomial-time computation of the joint spectral radius for some sets of nonnegative matrices. SIAM J. Matrix Anal. Appl. 31(3), 865–876 (2009)CrossRef MathSciNet
  2.Berman, A., Plemmons, R.J.: Nonnegative Matrices in the Mathematical Sciences. Acedemic Press, New York (1979)MATH
  3.Brualdi, R.A., Hoffman, A.J.: On the spectral radius of (0, 1)-matrices. Linear Algebra Appl. 65, 133–146 (1985)CrossRef MathSciNet MATH
  4.Cantor, D.G., Lippman, S.A.: Optimal investment selection with a multiple of projects. Econometrica 63, 1231–1240 (1995)CrossRef MATH
  5.Cvetković, D., Doob, M., Sachs, H.: Spectra of Graphs. Theory and Application. Academic Press, New York (1980)
  6.Engel, G.M., Schneider, H., Sergeev, S.: On sets of eigenvalues of matrices with prescribed row sums and prescribed graph. Linear Algebra Appl. 455, 187–209 (2014)CrossRef MathSciNet MATH
  7.Fainshil, L., Margaliot, M.: A maximum principle for the stability analysis of positive bilinear control systems with applications to positive linear switched systems. SIAM J. Control Optim. 50(4), 2193–2215 (2012)CrossRef MathSciNet MATH
  8.Friedland, S.: The maximal eigenvalue of 0–1 matrices with prescribed number of ones. Linear Algebra Appl. 69, 33–69 (1985)CrossRef MathSciNet MATH
  9.Jungers, R., Protasov, V.Yu., Blondel, V.: Efficient algorithms for deciding the type of growth of products of integer matrices. Linear Algebra Appl. 428(10), 2296–2312 (2008)
  10.Horn, R.A., Johnson, C.R.: Matrix Analysis. Cambridge University Press, Cambridge (1990)MATH
  11.Kozyakin, V.S.: A short introduction to asynchronous systems. In: Aulbach, B., Elaydi, S., Ladas, G. (eds.) Proceedings of the Sixth International Conference on Difference Equations (Augsburg, Germany 2001): New Progress in Difference Equations, pp. 153–166. CRC Press, Boca Raton (2004)CrossRef
  12.Leontief, W.: Input–Output Economics, 2nd edn. Oxford University Press, New York (1986)
  13.Liberzon, D.: Switching in Systems and Control. Birkhauser, Boston (2003)CrossRef MATH
  14.Lin, H., Antsaklis, P.J.: Stability and stabilizability of switched linear systems: a survey of recent results. IEEE Trans. Autom. Control 54(2), 308–322 (2009)CrossRef MathSciNet
  15.Liu, B.: On an upper bound of the spectral radius of graphs. Discrete Math. 308(2), 5317–5324 (2008)CrossRef MathSciNet MATH
  16.Logofet, D.O.: Matrices and Graphs: Stability Problems in Mathematical Ecology. CRC Press, Boca Raton (1993)
  17.Meyer, C.D., Stewart, G.W.: Derivatives and perturbations of eigenvectors. SIAM J. Numer. Anal. 25(3), 679–691 (1988)CrossRef MathSciNet MATH
  18.Miller, K.S.: Linear Difference Equations. Elsevier, Amsterdam (2000)
  19.Nesterov, Y., Protasov, V.Yu.: Optimizing the spectral radius. SIAM J. Matrix Anal. Appl. 34(3), 999–1013 (2013)
  20.Olesky, D.D., Roy, A., van den Driessche, P.: Maximal graphs and graphs with maximal spectral radius. Linear Algebra Appl. 346, 109–130 (2002)CrossRef MathSciNet MATH
  21.Pachpatte, B.G.: Integral and Finite Difference Inequalities and Applications. W. A. Benjamin Inc., New York-Amsterdam (1968)
  22.Schvatal, V.: Linear Programming. W. H. Freeman, New York (1983)
  23.Stewart, G.W., Sun, J.G.: Matrix Perturbation Theory. Academic Press, New York (1990)MATH
  24.Vladimirov, A.G., Grechishkina, N., Kozyakin, V., Kuznetsov, N., Pokrovskii, A., Rachinskii, D.: Asynchronous systems: theory and practice. Inform. Process. 11, 1–45 (2011)
  
• 作者单位：Vladimir Yu. Protasov (1)
  
  1. Deparment of Mechanics and Mathematics, Moscow State University, Vorobyovy Gory, 119992, Moscow, Russia
  
• 刊物类别：Mathematics and Statistics
• 刊物主题：Mathematics
  Calculus of Variations and Optimal Control
  Mathematics of Computing
  Numerical Analysis
  Combinatorics
  Mathematical and Computational Physics
  Mathematical Methods in Physics
  
• 出版者：Springer Berlin / Heidelberg
• ISSN：1436-4646

文摘

We develop an iterative optimization method for finding the maximal and minimal spectral radius of a matrix over a compact set of nonnegative matrices. We consider matrix sets with product structure, i.e., all rows are chosen independently from given compact sets (row uncertainty sets). If all the uncertainty sets are finite or polyhedral, the algorithm finds the matrix with maximal/minimal spectral radius within a few iterations. It is proved that the algorithm avoids cycling and terminates within finite time. The proofs are based on spectral properties of rank-one corrections of nonnegative matrices. The practical efficiency is demonstrated in numerical examples and statistics in dimensions up to 500. Some generalizations to non-polyhedral uncertainty sets, including Euclidean balls, are derived. Finally, we consider applications to spectral graph theory, mathematical economics, dynamical systems, and difference equations. Keywords Iterative optimization method Nonnegative matrix Spectral radius Cycling Spectrum of a graph Leontief model Positive linear switching system