The greedy strategy for optimizing the Perron eigenvalue
From MaRDI portal
Publication:2133407
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
Recommendations
Cites work
- scientific article; zbMATH DE number 3717357 (Why is no real title available?)
- scientific article; zbMATH DE number 3760340 (Why is no real title available?)
- scientific article; zbMATH DE number 45971 (Why is no real title available?)
- scientific article; zbMATH DE number 47363 (Why is no real title available?)
- scientific article; zbMATH DE number 2152830 (Why is no real title available?)
- A maximum principle for the stability analysis of positive bilinear control systems with applications to positive linear switched systems
- Computing Closest Stable Nonnegative Matrix
- Depth-First Search and Linear Graph Algorithms
- Efficient algorithms for deciding the type of growth of products of integer matrices
- Entropy Games and Matrix Multiplication Games
- Ergodic Control and Polyhedral Approaches to PageRank Optimization
- Finding the stationary states of Markov chains by iterative methods
- Hourglass alternative and the finiteness conjecture for the spectral characteristics of sets of non-negative matrices
- How to make the Perron eigenvector simple
- Maximal graphs and graphs with maximal spectral radius
- Multiplicative Markov Decision Chains
- On Nonterminating Stochastic Games
- On an upper bound of the spectral radius of graphs
- On sets of eigenvalues of matrices with prescribed row sums and prescribed graph
- On the closest stable/unstable nonnegative matrix and related stability radii
- On the spectral radius of (0,1)-matrices
- Optimal Investment Selection with a Multitude of Projects
- Optimizing the spectral radius
- PageRank optimization by edge selection
- Polynomial-Time Computation of the Joint Spectral Radius for Some Sets of Nonnegative Matrices
- Spectral simplex method
- Stability and Stabilizability of Switched Linear Systems: A Survey of Recent Results
- Strategy iteration is strongly polynomial for 2-player turn-based stochastic games with a constant discount factor
- The maximal eigenvalue of 0-1 matrices with prescribed number of ones
- The operator approach to entropy games
- 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
Cited in
(5)
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)
