I am reading Distributed Optimization and Statistical Learning via the Alternating Direction Method of Multipliers, where Boyd claimed that

ADMM is an algorithm that is intended to blend the decomposability of dual ascent with the superior convergence properties of the method of multipliers. (Section 3.1)

I understand that the method of multipliers has superior convergence properties, but it's hard to decompose the problem due to the extra second order augmented term in the Lagrangian.

However, I don't see the difference between ADMM and the classical method of multipliers in terms of decomposability, because ADMM also uses the augmented Lagrangian with the second order term.

In section 4.4.1, Boyd mentioned that to decompose the problem in ADMM, the $A^TA$ matrix has to be block diagonal and the objective function $f(x)$ has to be block separable ($f(x) = \sum_{i=1}^N f_i(x_i)$, where $x_i$ are subvectors of $x$). I think these conditions are quite strong, and if they are met, we can also decompose the $x$-update step in the classical method of multipliers. So why do we say ADMM is more decomposable than the method of multipliers?


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.