Intuição por trás do método de direção alternada dos multiplicadores

Ultimamente, tenho lido muitos artigos sobre o ADMM e também tentei resolver vários problemas usando-o, nos quais foi muito eficaz. Ao contrário de outros métodos de otimização, não consigo ter uma boa intuição de como e por que esse método é tão eficaz (é claro, já vi análises de convergência em alguns casos, mas nada que me desse muita informação). Existe alguma intuição por trás do ADMM? Como os primeiros cientistas a usá-lo tiveram essa ideia? Alguma intuição geométrica seria melhor, mas qualquer insight que alguém tenha ajudará.

$$\min_{x,y}\ F(x) + G(y),\quad\text{s.t}\quad Ax+By = c$$ $F$$G$$A$$B$

Eu encontrar o seguinte caso especial de , e ilustrativos. Nesse caso, a restrição diz , ou seja, podemos substituir para obter o problema Agora, resolver isso pode ser difícil, enquanto a solução de problemas da forma pode ser fácil. (Você mesmo pode criar exemplos disso, um popular é e ). No ADMM, você começa a partir da "forma " e cria o Lagragian aumentado " $A=I$$B=-I$$c=0$$x - y = 0$

$$\min_x F(x) + G(x).$$ $$\min_x \rho F(x) + \tfrac12\|x-z\|^2$$ $F(x) = \lambda\|x\|^1$$G(x) = \tfrac12\|Ax-b\|^2$ $$\min_{x,y}\ F(x) + G(y),\quad\text{s.t}\quad x-y=0$$ $$L_\rho(x,y,z) = F(x) + G(y) + z^T(x-y) + \tfrac\rho2\|x-y\|^2$$ com o multiplicador de Lagrange . Agora você minimiza alternadamente o Lagragian aumentado nas diferentes direções e , ou seja, itera e atualize o multiplicador de acordo com Isso deve explicar o nome do método de direções alternadas dos multiplicadores .$z$ $x$$y$ $$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)$$ $$z^{k+1} = z^k + \rho(x^{k+1} - y^{k+1}).$$

Analisando estes problemas de minimização para e mais perto, você observar que para cada atualização só precisa resolver um problema da "forma mais simples", por exemplo, para o atualização (negligenciando termos que não dependem de ).$x$$y$$x$

$$x^{k+1} = \mathrm{argmin}_x\ F(x) + \tfrac\rho2\|x - y^k + \rho z^k\|^2$$ $x$

O ADMM para o problema é derivado de maneira semelhante, mas os problemas intermediários das atualizações ainda são um um pouco difícil, mas pode ser comparativamente simples em comparação com o original. Especialmente no caso de e (ou equivalente , e a restrição ) as atualizações são mais ou menos simples de implementar.

$$\min_{x,y}\ F(x) + G(y),\quad\text{s.t}\quad Ax+By = c$$ $F(x) = \lambda\|x\|_1$$G(x) = \tfrac12\|Ax-b\|^2$$F(x) = \lambda\|x\|_1$$G(y) = \tfrac12\|y\|^2$$Ax - y = b$