Combinatorics Seminar 2015

Speaker: Vladimir Yuryevich Protasov (Протасов Владимир Юрьевич), Moscow State University

Date: Mon, Nov 23, 2015

Time: 16:00 - 17:00

Venue: Middle Meeting Room

Title: Spectral simplex method


The problem of maximizing and minimizing of the Perron-Frobenius eigenvalue over a compact set of nonnegative matrices arises naturally in combinatorics, dynamical systems, etc. This problem is notoriously hard, because of the properties of the spectral radius: it is neither concave nor convex and may lose smoothness at points of singularity. Nevertheless, for some special matrix sets it is efficiently solvable. We present 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 applications to mathematical economics (Leontief input-output model), spectral graph theory (optimizing the spectral radius of a graph), and dynamical systems (the linear switching systems) are considered.

Slides: View slides