##
Solving Semidefinite Programs via
Nonlinear Programming. Part I:
Transformations and Derivatives

###
Sam Burer, Renato Monteiro, Yin Zhang

In this paper, we introduce transformations that convert a large class
of linear and/or nonlinear semidefinite programming (SDP) problems
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. For example, in the case of the SDP
relaxation of a MAXCUT problem, $N$ is zero and $n$, the number of
variables of the resulting nonlinear optimization problem, is the
number of vertices in the underlying graph. The class of transformable
problems includes most, if not all, instances of SDP relaxations of
combinatorial optimization problems with binary variables, as well as
other important SDP problems. We also derive formulas for the first
and second derivatives of the objective function of the resulting
nonlinear optimization problem, hence enabling the effective
application of existing nonlinear optimization techniques to the
solution of large-scale SDP problems.
Technical Report TR99-17
Department of Computational and Applied Mathematics,
Rice University, Houston, Texas 77005, USA

Contact: zhang@caam.rice.edu