Eigenvalue multiplicity estimate in semidefinite programming

• Published in: Journal of optimization theory and applications 1997-07, Vol.94 (1), p.55-72
• Main Authors: FAN, M. K. H, GONG, Y
• Format: Article
• Language: English
• Subjects: Applied sciences; Eigenvalues; Exact sciences and technology; Operational research and scientific management; Operational research. Management science; Optimization. Search problems; Semidefinite programming
• ISSN: 0022-3239; 1573-2878
• DOI: 10.1023/A:1022603518289

A semidefinite programming problem is a mathematical program in which the objective function is linear in the unknowns and the constraint set is defined by a linear matrix inequality. This problem is nonlinear, nondifferentiable, but convex. It covers several standard problems (such as linear and quadratic programming) and has many applications in engineering. Typically, the optimal eigenvalue multiplicity associated with a linear matrix inequality is larger than one. Algorithms based on prior knowledge of the optimal eigenvalue multiplicity for solving the underlying problem have been shown to be efficient. In this paper, we propose a scheme to estimate the optimal eigenvalue multiplicity from points close to the solution. With some mild assumptions, it is shown that there exists an open neighborhood around the minimizer so that our scheme applied to any point in the neighborhood will always give the correct optimal eigenvalue multiplicity. We then show how to incorporate this result into a generalization of an existing local method for solving the semidefinite programming problem. Finally, a numerical example is included to illustrate the results.