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.
Citation
RUTCOR Research Report RRR 32-2012, Rutgers University, December 2012.