ON THE RANK OF EXTREME MATRICES IN SEMIDEFINITE PROGRAMS AND THE MULTIPLICITY OF OPTIMAL EIGENVALUES

We derive some basic results on the geometry of semidefinite programmi ng (SDP) and eigenvalue-optimization, i.e., the minimization of the su m 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 int erest in eigenvalue-optimization. In the spectrum of an optimal matrix , the kth and (k + 1)st largest eigenvalues tend to be equal and frequ ently have multiplicity greater than two. This clustering is intuitive ly plausible and has been observed as early as 1975. When the matrix-v alued function is affine, we prove that clustering must occur at extre me 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.