Spectral simplex method

• 成果类型: Article
• 署名作者: Protasov, Vladimir Yu.
• 署名单位: Lomonosov Moscow State University
• 刊物名称: MATHEMATICAL PROGRAMMING
• ISSN/ISSBN: 0025-5610
• DOI: 10.1007/s10107-015-0905-2
• 发表日期: 2016
• 页码: 485-511
• 关键词: radius; STABILITY; matrices; systems; sets

摘要

We develop an iterative optimization method for finding the maximal and minimal spectral radius of a matrix over a compact set of nonnegative matrices. We consider 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. The proofs are based on spectral properties of rank-one corrections of nonnegative matrices. The practical efficiency is demonstrated in numerical examples and statistics in dimensions up to 500. Some generalizations to non-polyhedral uncertainty sets, including Euclidean balls, are derived. Finally, we consider applications to spectral graph theory, mathematical economics, dynamical systems, and difference equations.