The greedy strategy for optimizing the Perron eigenvalue

DOI10.1007/S10107-020-01585-ZzbMATH Open1498.65053arXiv1807.05099OpenAlexW3096190278MaRDI QIDQ2133407

Vladimir Yu. Protasov, Aleksandar S. Cvetković

Publication date: 29 April 2022

Published in: Mathematical Programming. Series A. Series B (Search for Journal in Brave)

Abstract: We address the problems of minimizing and of maximizing the spectral radius overa compact family of non-negative matrices. Those problems being hard in generalcan be efficiently solved for some special families. We consider the so-called prod-uct families, where each matrix is composed of rows chosen independently from givensets. A recently introduced greedy method works very fast. However, it is applicablemostly for strictly positive matrices. For sparse matrices, it often diverges and gives awrong answer. We present the "selective greedy method" thatworks equally well forall non-negative product families, including sparse ones.For this method, we provea quadratic rate of convergence and demonstrate its efficiency in numerical examples.The numerical examples are realised for two cases: finite uncertainty sets and poly-hedral uncertainty sets given by systems of linear inequalities. In dimensions up to 2000, the matrices with minimal/maximal spectral radii in product families are foundwithin a few iterations. Applications to dynamical systemsand to the graph theoryare considered

Full work available at URL: https://arxiv.org/abs/1807.05099

zbMATH Keywords

stabilityspectral radiusdynamical systemcyclingiterative optimization methodspectrum of a graphquadratic convergencerelaxation algorithmnon-negative matrix

Mathematics Subject Classification ID

Inequalities involving eigenvalues and eigenvectors (15A42) Numerical computation of eigenvalues and eigenvectors of matrices (65F15) Nonconvex programming, global optimization (90C26)

Cites Work

• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Efficient algorithms for deciding the type of growth of products of integer matrices
• A Maximum Principle for the Stability Analysis of Positive Bilinear Control Systems with Applications to Positive Linear Switched Systems
• Depth-First Search and Linear Graph Algorithms
• On the spectral radius of (0,1)-matrices
• The maximal eigenvalue of 0-1 matrices with prescribed number of ones
• Maximal graphs and graphs with maximal spectral radius
• On sets of eigenvalues of matrices with prescribed row sums and prescribed graph
• Spectral simplex method
• Optimizing the spectral radius
• Polynomial-Time Computation of the Joint Spectral Radius for Some Sets of Nonnegative Matrices
• Optimal Investment Selection with a Multitude of Projects
• Stability and Stabilizability of Switched Linear Systems: A Survey of Recent Results
• On an upper bound of the spectral radius of graphs
• Finding the stationary states of Markov chains by iterative methods
• The simplex and policy-iteration methods are strongly polynomial for the Markov decision problem with a fixed discount rate
• The Simplex Method is Strongly Polynomial for Deterministic Markov Decision Processes
• On Nonterminating Stochastic Games
• Ergodic Control and Polyhedral Approaches to PageRank Optimization
• Multiplicative Markov Decision Chains
• Strategy Iteration Is Strongly Polynomial for 2-Player Turn-Based Stochastic Games with a Constant Discount Factor
• The operator approach to entropy games
• Entropy Games and Matrix Multiplication Games
• Computing Closest Stable Nonnegative Matrix
• Hourglass alternative and the finiteness conjecture for the spectral characteristics of sets of non-negative matrices
• On the Closest Stable/Unstable Nonnegative Matrix and Related Stability Radii
• How to make the Perron eigenvector simple
• PageRank optimization by edge selection

Cited In (4)

• Bounding the row sum arithmetic mean by Perron roots of row-permuted matrices
• The cycle time vector of D-A-D functions
• How to make the Perron eigenvector simple
• Stabilizing the Metzler matrices with applications to dynamical systems

This page was built for publication: The greedy strategy for optimizing the Perron eigenvalue

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2133407)