ИСТИНА

Spectral simplex method Vladimir Protasov Lomonosov Moscow State University The probem of finding the maximal and minimal spectral radius of a matrix over a compact set of nonnegative matrices is notoriously hard. This is natural in view of the properties of the spectral radius: it is neither concave nor convex and may loose smoothness at points of singularity. Nevertheless, for some special matrix sets this problem is efficiently solvable. We develop an iterative optimization method for 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, which can also be estimated from above. The proofs are based on spectral properties of rank-one corrections of nonnegative matrices. Some generalizations to non-polyhedral uncertainty sets, including Euclidean balls, are derived. Some applications to mathematical economics (Leontief input-output model), spectral graph theory (optimizing the spectral radius of a graph undes some conditions on each vertex), and dynamical systems (the linear switching systems) are considered. References [1] V.D.Blondel and Y.Nesterov, Polynomial-time computation of the joint spectral radius for some sets of nonnegative matrices, SIAM J. Matrix Anal. Appl. 31 (2009), no 3, 865–876. [2] Y.Nesterov and V.Yu.Protasov, Optimizing the spectral radius, SIAM J. Matrix Anal. Appl. 34 (2013), no 3, 999–1013. [3] V.Yu.Protasov, Spectral simplex