Row by row methods for semidefinite programming

Zaiwen Wen(zw2109columbia.edu)
Donald Goldfarb(goldfarbcolumbia.edu)
Shiqian Ma(sm2756columbia.edu)
Katya Scheinberg(ks79columbia.edu)

Abstract: 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.

Keywords: semidefinite programming, row by row method, (block) coordinate descent method, nonlinear Gauss-Seidel method, alternating direction method, matrix completion, maximum cut

Category 1: Linear, Cone and Semidefinite Programming

Category 2: Convex and Nonsmooth Optimization

Category 3: Nonlinear Optimization

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} }

Download: [PDF]

Entry Submitted: 04/28/2009
Entry Accepted: 04/29/2009
Entry Last Modified: 04/28/2009

Modify/Update this entry