First-order methods for semidefinite programming

2009 2009

Other formats: Order a copy

Abstract (summary)

Semidefinite programming (SDP) problems are concerned with minimizing a linear function of a symmetric positive definite matrix subject to linear equality constraints. These convex problems are solvable in polynomial time by interior point methods. However, if the number of constraints m in an SDP is of order O(n 2) when the unknown positive semidefinite matrix is n × n, interior point methods become impractical both in terms of the time (O(n6)) and the amount of memory (O(m2)) required at each iteration to form the m × m positive definite Schur complement matrix M and compute the search direction by finding the Cholesky factorization of M. This significantly limits the application of interior-point methods. In comparison, the computational cost of each iteration of first-order optimization approaches is much cheaper, particularly, if any sparsity in the SDP constraints or other special structure is exploited. This dissertation is devoted to the development, analysis and evaluation of two first-order approaches that are able to solve large SDP problems which have been challenging for interior point methods.

In chapter 2, we present a row-by-row (RBR) method 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. Numerical results on the maxcut SDP relaxation and matrix completion problems are presented to demonstrate the robustness and efficiency of our algorithm.

In chapter 3, we present an alternating direction method based on the augmented Lagrangian framework for solving SDP problems in standard form. At each iteration, the algorithm, also known as a two-splitting scheme, minimizes the dual augmented Lagrangian function sequentially with respect to the Lagrange multipliers corresponding to the linear constraints, then the dual slack variables and finally the primal variables, while in each minimization keeping the other variables fixed. Convergence is proved by using a fixed-point argument. A multiple-splitting algorithm is then proposed to handle SDPs with inequality constraints and positivity constraints directly without transforming them to the equality constraints in standard form. Numerical results on frequency assignment, maximum stable set and binary integer quadratic programming problems, show that our algorithm is very promising.

Indexing (details)

Applied Mathematics;
Operations research
0364: Applied Mathematics
0796: Operations research
Identifier / keyword
Applied sciences; Alternating direction method; Semidefinite programming
First-order methods for semidefinite programming
Wen, Zaiwen
Number of pages
Publication year
Degree date
School code
DAI-B 71/02, Dissertation Abstracts International
Place of publication
Ann Arbor
Country of publication
United States
Goldfarb, Donald
Columbia University
University location
United States -- New York
Source type
Dissertations & Theses
Document type
Dissertation/thesis number
ProQuest document ID
Database copyright ProQuest LLC; ProQuest does not claim copyright in the individual underlying works.
Document URL
Access the complete full text

You can get the full text of this document if it is part of your institution's ProQuest subscription.

Try one of the following:

  • Connect to ProQuest through your library network and search for the document from there.
  • Request the document from your library.
  • Go to the ProQuest login page and enter a ProQuest or My Research username / password.