Computing the joint spectral radius for some of nonnegative matrices

DATE: April 3, 2009

TIME: 11:00 AM – 12:00 PM

LOCATION: Executive classroom

FEES: none

EVENT CONTACT:

Anita Race, H. Milton Stewart School of Industrial and Systems Engineering
Contact Anita Race

TITLE: Computing the joint spectral radius for some sets of nonnegative matrices

SPEAKER: Dr. Yuri Nesterov

ABSTRACT:

We propose two simple upper bounds for the Joint Spectral Radius (JSR) of arbitrary sets of nonnegative matrices. These bounds, the Joint Column Radius, and the Joint Row Radius, can be computed in polynomial time as solutions to some convex optimization problems. We show that for general matrices they are within a factor ${1 over n}$ of the exact value, where $n$ is the size of the matrices. However, for the set of matrices with independent column (or row) uncertainties, the corresponding bounds coincide with JSR. As a byproduct of this result, we get a possibility to solve in polynomial time some boolean optimization problems related to spectral radius. We present also other economical and engineering applications of our results, which were never considered in computational practice in view of their intrinsic complexity.