Polynomial-time computation of the joint spectral radius for some sets of nonnegative matrices
AbstractWe propose two simple upper bounds for the joint spectral radius of sets of nonnegative matrices. These bounds, the joint column radius and the joint row radius, can be computed in polynomial time as solutions of convex optimization problems. We show that for general matrices these bounds are within a factor 1/n of the exact value, where n is the size of the matrices. Moreover, for sets of matrices with independent column uncertainties of with independent row uncertainties, the corresponding bounds coincide with the joint spectral radius. In these cases, the joint spectral radius is also given by the largest spectral radius of the matrices in the set. As a byproduct of these results, we propose a polynomial-time technique for solving Boolean optimization problems related to the spectral radius. We also consider economics and engineering applications of our results which were never considered practice due to their intrinsic computational complexity.
Download InfoIf you experience problems downloading a file, check if you have the proper application to view it first. In case of further problems read the IDEAS help page. Note that these files are not on the IDEAS site. Please be patient as the files may be large.
Bibliographic InfoPaper provided by Université catholique de Louvain, Center for Operations Research and Econometrics (CORE) in its series CORE Discussion Papers with number 2008034.
Date of creation: 01 May 2008
Date of revision:
Contact details of provider:
Postal: Voie du Roman Pays 34, 1348 Louvain-la-Neuve (Belgium)
Fax: +32 10474304
Web page: http://www.uclouvain.be/core
More information through EDIRC
joint spectral radius; joint column radius; joint row radius; nonnegative matrices; asynchronous systems; convex optimization; Leontief model.;
This paper has been announced in the following NEP Reports:
- NEP-ALL-2008-11-25 (All new papers)
You can help add them by filling out this form.
CitEc Project, subscribe to its RSS feed for this item.
- Protasov, Vladimir Y., 2010. "Joint Spectral Characteristics of Matrices: a Conic Programming Approach. SIAM J. Matrix Anal. Appl," Open Access publications from UniversitÃ© catholique de Louvain info:hdl:2078.1/33719, Université catholique de Louvain.
For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: (Alain GILLIS).
If references are entirely missing, you can add them using this form.