On the rank of extreme matrices in semidefinite programs and the multiplicity of optimal eigenvalues

• 成果类型: Article
• 署名作者: Pataki, G
• 署名单位: Columbia University
• 刊物名称: MATHEMATICS OF OPERATIONS RESEARCH
• ISSN/ISSBN: 0364-765X
• DOI: 10.1287/moor.23.2.339
• 发表日期: 1998
• 页码: 339-358
• 关键词: symmetrical matrix; optimization

摘要

We derive some basic results on the geometry of semidefinite programming (SDP) and eigenvalue-optimization, i.e., the minimization of the sum of the k largest eigenvalues of a smooth matrix-valued function. We provide upper bounds on the rank of extreme matrices in SDPs, and the first theoretically solid explanation of a phenomenon of intrinsic interest in eigenvalue-optimization. In the spectrum of an optimal matrix, the kth and (k + 1)st largest eigenvalues tend to be equal and frequently have multiplicity greater than two. This clustering is intuitively plausible and has been observed as early as 1975. When the matrix-valued function is affine, we prove that clustering must occur at extreme points of the set of optimal solutions, if the number of variables is sufficiently large. We also give a lower bound on the multiplicity of the critical eigenvalue. These results generalize to the case of a general matrix-valued function under appropriate conditions.