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.
Contact: [email protected]