## Self Equivalence of the Alternating Direction Method of MultipliersMing Yan and Wotao Yin Published in Splitting Methods in Communication, Imaging, Science and Engineering (Eds. R. Glowinski, S. Osher, and W. Yin): Technical report (Updated: March 5, 2015)
## OverviewThe alternating direction method of multipliers (ADM or ADMM) breaks a complex optimization problem into much simpler subproblems. The ADM algorithms are typically short and easy to implement yet exhibit (nearly) state-of-the-art performance for large-scale optimization problems. To apply ADM, we first formulate a given problem into the ‘‘ADM-ready“ form,
so the final algorithm depends on the formulation. A problem like
has six different ‘‘ADM-ready” formulations.
They can be in the primal or dual forms, and they differ by how dummy variables are
introduced. To each ‘‘ADM-ready" formulation, ADM can be applied in two
different orders how the primal variables are updated. Finally, In this paper, we show many of the different ways of applying ADM are equivalent. Specifically, we show that ADM applied to a primal formulation is equivalent to ADM applied to its Lagrange dual; ADM is equivalent to a primal-dual algorithm applied to the saddle-point formulation of the same problem. These results are surprising since the primal and dual variables in ADM are seemingly treated very differently, and some previous work exhibits preferences in one over the other on specific problems. In addition, when one of the two objective functions is quadratic, possibly subject to an affine constraint. we show that swapping the update order of the two primal variables in ADM gives the same algorithm. These results identify the few truly different ADM algorithms for a problem, which generally have different forms of subproblems from which it is easy to pick one with the most computationally friendly subproblems. ## Citation
« Back |