1
$\begingroup$

I am trying to understand intuition of ADMM (alternating direction methods of multipliers). It combines dual ascent and method of multipliers. Downside of method of multiplier is the loss of decomposability. Why does method of multipliers lose decomposability?

$\endgroup$
6
$\begingroup$

The question is missing some important context about the form of the objective function and constraints. I believe that the OP is referring to minimizing a function

$ f(x)=f_{1}(x_{1})+\cdots + f_{N}(x_{N}) $

subject to constraints

$Ax=b$.

Here the vector $x$ is decomposed into $N$ blocks (that can be vectors of various sizes)

$x=\left[ \begin{array}{c} x_{1} \\ x_{2} \\ \vdots \\ x_{N} \end{array} \right]$.

We can write $Ax=b$ as

$Ax=A_{1}x_{1}+ \cdots A_{N}x_{N}=b$.

The Lagrangian can be written as

$L(x,\lambda)=f_{1}(x_{1})+ \cdots + f_{N}(x)+ \lambda^{T}(A_{1}x_{1}+ \cdots +A_{N}x_{N}-b)$

In the dual decomposition method, we can minimize the Lagrangian with respect to $x$ by minimizing with respect to the components $x_{1}$, $x_{2}$, $\ldots$, $x_{N}$ in sequence. This works because $f(x)$ is decomposable and the $\lambda^{T}(Ax-b)$ term is also decomposable.

In the method of multipliers, the Lagrangian is augmented with a term

$\ldots + (\rho/2) \| Ax -b \|_{2}^{2}$.

This extra term is not decomposable in terms of functions of $x_{1}$, $x_{2}$, $\ldots$, $x_{N}$ because it is quadratic and involves cross-terms of $x_{i}$ and $x_{j}$.

Thus the augmented Lagrangian cannot be minimized by components in the same way as the unaugmented Lagrangian.

$\endgroup$

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.