## Method of centers for minimizing generalized eigenvaluesS. Boyd and L. El Ghaoui
We consider the problem of minimizing the largest generalized eigenvalue of a
pair of symmetric matrices, each of which depends affinely on the decision
variables. Although this problem may appear specialized, it is in fact quite
general, and includes for example all linear, quadratic, and linear fractional
programs. Many problems arising in control theory can be cast in this form. The
problem is nondifferentiable but quasiconvex, so methods such as Kelley's
cutting-plane algorithm or the ellipsoid algorithm of Shor, Nemirovksy, and
Yudin are guaranteed to minimize it. In this paper we describe relevant
background material and a simple interior point method that solves such
problems more efficiently. The algorithm is a variation on Huard's method of
centers, using a self-concordant barrier for matrix inequalities developed by
Nesterov and Nemirovsky. (Nesterov and Nemirovsky have also extended their
potential reduction methods to handle the same problem.) Since the problem is
quasiconvex but not convex, devising a non-heuristic stopping criterion
( |