Interior-Point Algorithms for Semidefinite Programming
Based on A Nonlinear Programming Formulation
Samuel Burer, Renato D.C. Monteiro, Yin Zhang
Recently, the authors of this paper introduced a nonlinear
transformation to convert the positive definiteness constraint
on an $n \times n$ matrix function of a certain form into the
positivity constraint on $n$ scalar variables while keeping the
number of variables unchanged. Based on this transformation,
they proposed interior point algorithms for solving a special
class of linear semidefinite programs. In this paper, we extend
this approach and apply the transformation to general linear
semidefinite programs, producing nonlinear programs that have not
only the $n$ positivity constraints, but also $n$ additional
nonlinear inequality constraints. Despite this complication, the
transformed problems still retain most of the desirable properties.
We propose interior-point algorithms for this type of nonlinear
program and establish their global convergence.
Technical Report TR99-27,
Department of Computational
and Applied Mathematics,
Houston, Texas 77005.