A Multiple-Cut Analytic Center Cutting Plane Method for Semidefinite Feasibility Problems

We consider the problem of finding a point in a nonempty bounded convex body $\Gamma$ in the cone of symmetric positive semidefinite matrices ${\cal S}^m_+$. Assume that $\Gamma$ is defined by a separating oracle, which, for any given $m\ti m$ symmetric matrix $\hat{Y}$, either confirms that $\hat Y \in \Gamma$ or returns several selected cuts, i.e., a number of symmetric matrices Ai, i=1,. . .,p, p\le p_{\max}$, such that $\Gamma$ is in the polyhedron $ \{ Y \in {\cal S}^m_+ \mid A_i \bullet Y \le A_i \bullet \hat{Y}, i=1,\ldots,p \}.$ We present a multiple-cut analytic center cutting plane algorithm. Starting from a trivial initial point, the algorithm generates a sequence of positive definite matrices which are approximate analytic centers of a shrinking polytope in ${\cal S}^m_+$. The algorithm terminates with a point in $\Gamma$ within $O(m^3p_{\max}/\epsilon^2)$ Newton steps (to leading order), where $\epsilon$ is the maximum radius of a ball contained in $\Gamma$.