The greedy strategy for optimizing the Perron eigenvalue
- PDF / 468,787 Bytes
- 31 Pages / 439.37 x 666.142 pts Page_size
- 53 Downloads / 183 Views
Series A
The greedy strategy for optimizing the Perron eigenvalue Aleksandar Cvetkovi´c1 · Vladimir Yu. Protasov2,3 Received: 22 April 2018 / Accepted: 15 October 2020 © The Author(s) 2020
Abstract We address the problems of minimizing and of maximizing the spectral radius over a compact family of non-negative matrices. Those problems being hard in general can be efficiently solved for some special families. We consider the so-called product families, where each matrix is composed of rows chosen independently from given sets. A recently introduced greedy method works very fast. However, it is applicable mostly for strictly positive matrices. For sparse matrices, it often diverges and gives a wrong answer. We present the “selective greedy method” that works equally well for all non-negative product families, including sparse ones. For this method, we prove a quadratic rate of convergence and demonstrate its efficiency in numerical examples. The numerical examples are realised for two cases: finite uncertainty sets and polyhedral uncertainty sets given by systems of linear inequalities. In dimensions up to 2000, the matrices with minimal/maximal spectral radii in product families are found within a few iterations. Applications to dynamical systems and to the graph theory are considered. Keywords Iterative optimization method · Non-negative matrix · Spectral radius · Relaxation algorithm · Cycling · Spectrum of a graph · Quadratic convergence · Dynamical system · Stability Mathematics Subject Classification 15B48 · 90C26 · 15A42
The second author was supported by Russian Foundation for Basic Research projects 19-04-01227 and 20-01-00469.
B
Vladimir Yu. Protasov [email protected]
1
GSSI, L’Aquila, Italy
2
DISIM of University of L’Aquila, L’Aquila, Italy
3
Moscow State University, Moscow, Russia
123
A. Cvetkovi´c, V. Yu. Protasov
1 Introduction The problem of minimizing or maximizing the spectral radius of a non-negative matrix over a general constrained set can be very hard. There are no efficient algorithms even for solving this problem over a compact convex (say, polyhedral) set of positive matrices. This is because the objective function is neither convex nor concave in matrix coefficients and, in general, non-Lipschitz. There may be many points of local extrema, which are, moreover, hard to compute. Nevertheless, for some special sets of matrices efficient methods do exist. In this paper we consider the so-called product families. Their spectral properties were discovered and analysed by Blondel and Nesterov in [6]; the first methods of optimizing the spectral radius over such families originated in [29]. One of them, the spectral simplex method, was further developed in [34]. This method is quite simple in realization and has a fast convergence to the global minimum/maximum. Similar methods for optimising the spectral radius appeared in the literature in various contexts: in stochastic and entropy games (see [1] and references therein), PageRanking [10,14]. The relation to the Markov Decision Pr
Data Loading...
