A Nonlinear Programming Algorithm for Solving Semidefinite
Programs via Low-rank Factorization
Samuel Burer, Renato D.C. Monteiro
In this paper, we present a nonlinear programming algorithm for
solving semidefinite programs (SDPs) in standard form. The algorithm's
distinguishing feature is a change of variables that replaces the
symmetric, positive semidefinite variable X of the SDP with a
rectangular variable R according to the factorization X = RR^T. The
rank of the factorization, i.e., the number of columns of R, is chosen
minimally so as to enhance computational speed while maintaining
equivalence with the SDP. Fundamental results concerning the
convergence of the algorithm are derived, and encouraging
computational results on some large-scale test problems are also
presented.
School of ISyE
Georgia Tech
Atlanta, GA 30332
March, 2001
Contact: [email protected]