8
$\begingroup$

I've been reading a lot of papers on ADMM lately, and also tried to solve several problems using it, in all of which it was very effective. In contrast to other optimization methods, I can't get a good intuition as to how and why this method is so effective (of course, I've seen convergence analysis for a few cases, but nothing that gave me too much insight). Is there some intuition behind ADMM? How did the first scientists to use it come up with this idea? Some geometrical intuition would be best, but any insight anyone has will help.

$\endgroup$
  • $\begingroup$ Can you spell out what ADMM is? $\endgroup$ – Bill Barth Nov 3 '14 at 16:27
  • $\begingroup$ @BillBarth - Sure :) Alternating Direction Method of Multipliers (see e.g. stanford.edu/~boyd/admm.html) $\endgroup$ – olamundo Nov 3 '14 at 16:33
  • 1
    $\begingroup$ Can you at least say what it is about the original paper that you find so unclear? $\endgroup$ – Kirill Nov 3 '14 at 16:50
  • 3
    $\begingroup$ @Kirill Just a nit: Boyd's paper is hardly the original ADMM paper. It is a good reference, but the algorithm goes back to Douglas and Rachford (1956) and was further developed and analyzed from the 1970s to 1990s. It has seen a revival in recent years largely due to the buzz around $\ell^1$ regularization. $\endgroup$ – Jed Brown Nov 4 '14 at 1:54
  • 2
    $\begingroup$ ADMM has gotten a lot of attention because it is so effective for solving problems in $L_{1}$ regularization, but it's not a method that is generally useful for all optimization problems. A better question would be why ADMM is so effective in the context. The work of Osher and Yin on split Bregman methods (basically equivalent to ADMM) helps to explain this. See the page at caam.rice.edu/~optimization/L1/bregman $\endgroup$ – Brian Borchers Nov 4 '14 at 4:34
10
$\begingroup$

If I remember correctly, the ADMM ist often stated as an algorithm to solve $$\min_{x,y}\ F(x) + G(y),\quad\text{s.t}\quad Ax+By = c$$ for two convex, lower-semicontinuous functionals $F$ and $G$ and linear, bounded operators $A$ and $B$.

I find the following special case of $A=I$, $B=-I$ and $c=0$ illustrative. In this case the constraint says $x - y = 0$, i.e. we can substitute to get the problem $$\min_x F(x) + G(x).$$ Now solving this can be hard, while solving problems of the form $$\min_x \rho F(x) + \tfrac12\|x-z\|^2$$ can be easy. (You can make up examples for this yourself, a popular one is $F(x) = \lambda\|x\|^1$ and $G(x) = \tfrac12\|Ax-b\|^2$). In ADMM you start from the "splitted form" $$\min_{x,y}\ F(x) + G(y),\quad\text{s.t}\quad x-y=0$$ and build the "augmented Lagragian" $$L_\rho(x,y,z) = F(x) + G(y) + z^T(x-y) + \tfrac\rho2\|x-y\|^2$$ with the Lagrange multiplier $z$. Now you alternatingly minimize the augemented Lagragian in the different directions $x$ and $y$, i.e. iterate $$x^{k+1} = \mathrm{argmin}_x\ L_\rho(x,y^k,z^k)$$ $$y^{k+1} = \mathrm{argmin}_y\ L_\rho(x^{k+1},y,z)$$ and update the multiplier according to $$z^{k+1} = z^k + \rho(x^{k+1} - y^{k+1}).$$ This should explain the name alternating directions method of multipliers.

Analyzing these minimization problems for $x$ and $y$ closer, you observe that for each update only needs to solve a problem of the "simpler form", e.g. for the $x$ update $$x^{k+1} = \mathrm{argmin}_x\ F(x) + \tfrac\rho2\|x - y^k + \rho z^k\|^2$$ (neglecting terms that do not depend on $x$).

ADMM for the problem $$\min_{x,y}\ F(x) + G(y),\quad\text{s.t}\quad Ax+By = c$$ is derived similar but then the intermediate problems for the updates are still a bit difficult but may be comparably simple in comparison to the original one. Especially in the case of $F(x) = \lambda\|x\|_1$ and $G(x) = \tfrac12\|Ax-b\|^2$ (or equivalently $F(x) = \lambda\|x\|_1$, $G(y) = \tfrac12\|y\|^2$ and the constraint $Ax - y = b$) the updates are more or less straightforward to implement.

$\endgroup$
  • $\begingroup$ Nice! It is also useful to show what happens for 3 blocks (There are cases which it will work for, for example, decorrelated matrices). $\endgroup$ – Royi Dec 9 '16 at 14:50

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.