Optimization Online


Alternating Direction Augmented Lagrangian Methods for semidefinite programming

Zaiwen Wen (zw2109***at***columbia.edu)
Donald Goldfarb (goldfarb***at***columbia.edu)
Wotao Yin (wotao.yin***at***rice.edu)

Abstract: We present an alternating direction method based on an augmented Lagrangian framework for solving semidefinite programming (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. Finally, numerical results for frequency assignment, maximum stable set and binary integer quadratic programming problems are presented to demonstrate the robustness and efficiency of our algorithm.

Keywords: semidefinite programming, alternating direction method, augmented Lagrangian method

Category 1: Linear, Cone and Semidefinite Programming (Semi-definite Programming )

Category 2: Convex and Nonsmooth Optimization (Convex Optimization )

Citation: @TECHREPORT{AltSDP-WenGoldfarbYin-2009, author = {Wen, Zaiwen and Goldfarb, Donald and Yin, Wotao}, title = {Alternating Direction Augmented Lagrangian Methods for semidefinite programming}, institution = {Dept of IEOR, Columbia University}, year = {2009} }

Download: [PDF]

Entry Submitted: 08/10/2009
Entry Accepted: 08/10/2009
Entry Last Modified: 08/29/2009

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Programming Society