Optimization Online


Augmented Lagrangian and Alternating Direction Methods for Convex Optimization: A Tutorial and Some Illustrative Computational Results

Jonathan Eckstein (jeckstei***at***rci.rutgers.edu)

Abstract: The alternating direction of multipliers (ADMM) is a form of augmented Lagrangian algorithm that has experienced a renaissance in recent years due to its applicability to optimization problems arising from ``big data'' and image processing applications, and the relative ease with which it may be implemented in parallel and distributed computational environments. This paper aims to provide an accessible introduction to the analytical underpinnings of the method, which are often obscured in treatments that do not assume knowledge of convex and set-valued analysis. In particular, it is tempting to view the method as an approximate version of the classical augmented Lagrangian algorithm, using one pass of block coordinate minimization to approximately minimize the augmented Lagrangian at each iteration. This paper, assuming as little prior knowledge of convex analysis as possible, shows that the actual convergence mechanism of the algorithm is quite different, and then underscores this observations with some new computational results in which we compare the ADMM to algorithms that do indeed work by approximately minimizing the augmented Lagrangian.

Keywords: Convex programming, augmented lagrangian, alternating direction method of multipliers

Category 1: Convex and Nonsmooth Optimization (Convex Optimization )

Citation: RUTCOR Research Report RRR 32-2012, Rutgers University, December 2012.

Download: [PDF]

Entry Submitted: 12/08/2012
Entry Accepted: 12/08/2012
Entry Last Modified: 12/27/2012

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 Optimization Society