EIGENVALUE MULTIPLICITY ESTIMATE IN SEMIDEFINITE PROGRAMMING

A semidefinite programming problem is a mathematical program in which the objective function is linear in the unknowns and the constraint se t is defined by a linear matrix inequality. This problem is nonlinear, nondifferentiable, but convex. It covers several standard problems (s uch 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 f rom points close to the solution. With some mild assumptions, it is sh own that there exists an open neighborhood around the minimizer so tha t our scheme applied to any point in the neighborhood will always give the correct optimal eigenvalue multiplicity. We then show how to inco rporate 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.