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

被引:236
作者
Pataki, G [1 ]
机构
[1] Columbia Univ, Dept Ind Engn & Operat Res, New York, NY 10027 USA
关键词
semidefinite programming; eigenvalue-optimization; nonsmooth optimization; maximum eigenvalue; sum of eigenvalues;
D O I
10.1287/moor.23.2.339
中图分类号
C93 [管理学]; O22 [运筹学];
学科分类号
070105 ; 12 ; 1201 ; 1202 ; 120202 ;
摘要
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.
引用
收藏
页码:339 / 358
页数:20
相关论文
共 26 条
[1]   INTERIOR-POINT METHODS IN SEMIDEFINITE PROGRAMMING WITH APPLICATIONS TO COMBINATORIAL OPTIMIZATION [J].
ALIZADEH, F .
SIAM JOURNAL ON OPTIMIZATION, 1995, 5 (01) :13-51
[2]   Complementarity and nondegeneracy in semidefinite programming [J].
Alizadeh, F ;
Haeberly, JPA ;
Overton, ML .
MATHEMATICAL PROGRAMMING, 1997, 77 (02) :111-128
[3]  
Aubin J.-P., 1990, Set-valued analysis, DOI 10.1007/978-0-8176-4848-0
[4]   CONES OF DIAGONALLY DOMINANT MATRICES [J].
BARKER, GP ;
CARLSON, D .
PACIFIC JOURNAL OF MATHEMATICS, 1975, 57 (01) :15-32
[5]  
Clarke F.H., 1990, OPTIMIZATION NONSMOO
[6]  
Cullum J., 1975, Math Programming Study, V3, P35
[7]   LAPLACIAN EIGENVALUES AND THE MAXIMUM CUT PROBLEM [J].
DELORME, C ;
POLJAK, S .
MATHEMATICAL PROGRAMMING, 1993, 62 (03) :557-574
[9]   SENSITIVITY ANALYSIS OF ALL EIGENVALUES OF A SYMMETRICAL MATRIX [J].
HIRIARTURRUTY, JB ;
YE, D .
NUMERISCHE MATHEMATIK, 1995, 70 (01) :45-72
[10]  
Horn R. A., 1987, MATRIX ANAL