An Analytic Center Cutting Plane Method For Semidefinite Feasibility Problems

Jie Sun, Kim-Chuan Toh, and Gongyun Zhao

Semidefinite feasibility problems arise in many areas of operations research. The abstract form of these problems can be described as finding a point in a nonempty bounded convex body $\Gamma$ in the cone of symmetric positive semidefinite matrices. Assume that $\Gamma$ is defined by an oracle, which, for any given $m\times m$ symmetric matrix $\hat{Y}$, either confirms that $\hat Y \in \Gamma$ or returns a cut, i.e., a symmetric matrix $A$ such that $\Gamma$ is in the half-space $ \{ Y \mid A \bullet Y \le A \bullet \hat{Y} \}.$ We study an analytic center cutting plane algorithm for this problem. At each iteration the algorithm computes an approximate analytic center of a working set defined by the cutting-plane system generated in the previous iterations. If this approximate analytic center is a solution, then the algorithm terminates; otherwise the new cutting plane returned by the oracle is added into the system. As the number of iterations increases, the working set shrinks and the algorithm eventually finds a solution of the problem. All iterates generated by the algorithm are positive definite matrices due to log-determinant barrier terms in the potential function. The algorithm has a worst case complexity of $O^*(m^3/{\epsilon}^2)$ on the total number of cuts to be used, where $\epsilon$ is the maximum radius of a ball contained by $\Gamma$.

Research Report No 766, Department of Mathematics, National University of Singapore, January 2000