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, Rice University, Houston, Texas 77005.