The greedy strategy for optimizing the Perron eigenvalue

• 成果类型: Article
• 署名作者: Cvetkovic, Aleksandar; Protasov, Vladimir Yu
• 署名单位: Gran Sasso Science Institute (GSSI); Lomonosov Moscow State University
• 刊物名称: MATHEMATICAL PROGRAMMING
• ISSN/ISSBN: 0025-5610
• DOI: 10.1007/s10107-020-01585-z
• 发表日期: 2022
• 页码: 1-31
• 关键词: spectral-radius; STABILITY; simplex; sets; matrices; systems

摘要

We address the problems of minimizing and of maximizing the spectral radius over a compact family of non-negative matrices. Those problems being hard in general can be efficiently solved for some special families. We consider the so-called product families, where each matrix is composed of rows chosen independently from given sets. A recently introduced greedy method works very fast. However, it is applicable mostly for strictly positive matrices. For sparse matrices, it often diverges and gives a wrong answer. We present the selective greedy method that works equally well for all non-negative product families, including sparse ones. For this method, we prove a quadratic rate of convergence and demonstrate its efficiency in numerical examples. The numerical examples are realised for two cases: finite uncertainty sets and polyhedral uncertainty sets given by systems of linear inequalities. In dimensions up to 2000, the matrices with minimal/maximal spectral radii in product families are found within a few iterations. Applications to dynamical systems and to the graph theory are considered.