A Computational Study of a Gradient-Based Log-Barrier Algorithm
for a Class of Large-Scale SDPs
S. Burer, R. D. C. Monteiro, and Y. Zhang
The authors of this paper recently introduced a transformation
\cite{BuMoZh99-1} that converts a class of semidefinite programs
(SDPs) into nonlinear optimization problems free of matrix-valued
constraints and variables. This transformation enables the application
of nonlinear optimization techniques to the solution of certain SDPs
that are too large for conventional interior-point methods to handle
efficiently. Based on the transformation, they proposed a globally
convergent, first-order (i.e., gradient-based) log-barrier algorithm
for solving a class of linear SDPs. In this paper, we discuss an
efficient implementation of the proposed algorithm and report
computational results on semidefinite relaxations of three types of
combinatorial optimization problems. Our results demonstrate that the
proposed algorithm is indeed capable of solving large-scale SDPs and
is particularly effective for problems with a large number of
constraints.
Working paper, School of ISyE, Georgia Tech, Atlanta, GA, USA, June 2001.
Contact: [email protected]