Alternating direction method of multipliers

Introducing ADMM!

Let’s say we want to solve:

minimize $f(x) + g(z)$
subject to $Ax + Bz = c$


ADMM does:

This is a quite general problem. Actually this is a special case:

minimize $F(x, z)$
subject to $G(x, z) = 0$

where $F : (x, z)$ is biconvex, which means convex in $x$ (for each $z$) and in $z$ (for each $x$).

ADMM would become:

Please note that when $G = 0$, ADMM becomes alternate minimization.

It can also be applied to nonnegative matrix factorization. In this case with $G = 0$ one can recover ALS.

Some GitHub repos: