《《2016 Interior-Point Algorithms for Semidefinite Programming Based on a Nonlinear Formulation》.pdf

Computational Optimization and Applications, 22, 49–79, 2002 c 2002 Kluwer Academic Publishers. Manufactured in The Netherlands. Interior-Point Algorithms for Semidefinite Programming Based on a Nonlinear Formulation∗ SAMUEL BURER† samuel-burer@uiowa.edu Department of Management Sciences, University of Iowa, Iowa City, IA 52242, USA RENATO D.C. MONTEIRO∗∗ monteiro@isye.gatech.edu School of ISyE, Georgia Tech., Atlanta, Georgia 30332, USA YIN ZHANG‡ zhang@caam.rice.edu Department of Computational and Applied Mathematics, Rice University, Houston, Texas 77005, USA Received December 1999; Revised May 2001 Abstract. Recently in Burer et al. (Mathematical Programming A, submitted), the authors of this paper introduced a nonlinear transformation to convert the positive definiteness constraint on an n ×n matrix-valued 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 a first-order interior-point algorithm 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 first-order and second-order interior-point algorithms for this type of nonlinear program and establish their global convergence. Computational results demonstrating the effectivene