Solving Semidefinite Programs via Nonlinear Programming Part II: Interior Point Methods for a Subclass of SDPs

Sam Burer, Renato D.C. Monteiro and Yin Zhang

In Part I of this series of papers, we have introduced transformations which convert a large class of linear and nonlinear semidefinite programs (SDPs) into nonlinear optimization problems over ``orthants'' of the form $\Re^n_{++} \times \Re^N$, where $n$ is the size of the matrices involved in the problem and $N$ is a nonnegative integer dependent upon the specific problem. In doing so, we have effectively reduced the number of variables and constraints. In this paper, we develop interior point methods for solving a subclass of the transformable linear SDP problems where the diagonal of a matrix variable is given. These new interior point methods have the advantage of working entirely within the space of the transformed problem while still maintaining close ties with the original SDP. Under very mild and reasonable assumptions, global convergence of these methods is proved.

Technical Report TR99-23, Department of Computational and Applied Mathematics, Rice University, Houston, Texas 77005.