Speaker: Dr. Zaiwen Wen (Institute for Pure and Applied Mathematics, UCLA and Rice University )

Inviter: Prof. Ya-Xiang Yuan

Time: 9:00 - 10:30, April 1st (Thursday), 2010 

Venue: Room 311

Subject: First-order Methods for Semidefinite Programming

Abstract:

Semidefinite programming (SDP) is concerned with minimizing a linear function of a symmetric positive semidefinite matrix  subject to linear constraints. These convex optimization problems are solvable in polynomial time by  interior point methods to any prescribed accuracy. However, if the number of constraints m in an SDP is of order O(n^2) when the size of the unknown matrix X is n, interior point  methods become impractical both in terms of the time and the amount of memory required at each iteration. On the contrary, although the computational complexity of the first-order optimization methods  is not polynomial, each iteration of these methods can be executed much more cheaply than in an interior point algorithm.  This enables them to solve very large SDPs efficiently.  In this talk, we first present a row-by-row method. By fixing any (n-1)-dimensional principal submatrix of X and using its Schur complement, the positive semidefinite constraint is reduced to a simple second-order cone constraint and then a sequence of second-order cone programming problems constructed from the primal augmented Lagrangian function are minimized.  Then, we introduce an alternating direction augmented Lagrangian method. At each iteration, this algorithm minimizes the dual augmented Lagrangian function with respect to each block of dual variables separately while other blocks are fixed and then updates the primal variables. Our methods can be extremely efficient on many problems including a few SDP relaxations of combinatorial optimization problems by exploiting their underlying structures.