We present a row-by-row (RBR) method for solving semidefinite programming (SDP) problem based on solving a sequence of problems obtained by restricting the n-dimensional positive semidefinite constraint on the matrix X. By fixing any (n-1)-dimensional principal submatrix of X and using its (generalized) Schur complement, the positive semidefinite constraint is reduced to a simple second-order cone constraint. When the RBR method is applied to solve the maxcut SDP relaxation, the optimal solution of the RBR subproblem only involves a single matrix-vector product which leads to a simple and very efficient method. To handle linear constraints in generic SDP problems, we use an augmented Lagrangian approach. Specialized versions are presented for the maxcut SDP relaxation and the minimum nuclear norm matrix completion problem since closed-form solutions for the RBR subproblems are available. Finally, numerical results on the maxcut SDP relaxation and matrix completion problems are presented to demonstrate the robustness and efficiency of our algorithm.
Citation
@TECHREPORT{RBR-WenGoldfarbMaScheinberg-2009, author = {Wen, Zaiwen and Goldfarb, Donald and Ma, Shiqian and Scheinberg, Katya}, title = {Row by row methods for semidefinite programming}, institution = {Dept of IEOR, Columbia University}, year = {2009} }