ADMM formalization

Question

I found lots of examples of ADMM formalization of equality constraint problems (all with single constraint). I am wondering how to generalize it for multiple constraints with mix of equality and inequality constraints.

I have a problem

Minimize $||A_x||_1 + \lambda ||A_y||_2 $, such that: $$A_x X = A_x$$ $$\mathrm{diag}(A_x) = 0$$ $$A_x \ge 0$$ $$A_y \le 0$$

How can I write this in ADMM form ?.

Answer 1

One way to formulate the problem using ADMM is to let the ADMM-variable $X$ contain $A_x$ and $A_y$, i.e. $X = [A_x; A_y]$ (semi-colon denotes stacking, as in Matlab etc.), and let $Z=[Z_1; Z_2; Z_3; Z_4]$ contain four blocks corresponding to $A_x$, $A_x$, $A_x$ and $A_y$ respectively. (I will write $Q$ for $X-I$, where $X$ is your variable $X$! Thus $A_x Q=0$ should hold.)

$X$ and $Z$ would then be linked by $$ \left[\begin{array}{cc} I & 0 \\ I & 0 \\ I & 0 \\ 0 & I \end{array}\right] \left[ \begin{array}{c} A_x \\ A_y \end{array}\right] = \left[\begin{array}{c} Z_1 \\ Z_2 \\ Z_3 \\ Z_4 \end{array}\right] $$ where $I$ and $0$ are identity matrices and zero matrices of suitable sizes (this defines the matrices $A$ and $B$ of ADMM).

Now updating $A_x$ amounts to computing the proximal operator for the 1-norm (is the norm $\|\cdot\|_1$ the entry-wise sum of absolute values of elements, or the operator norm induced by the 1-vector norm?). Updating $A_y$ amount to evaluating the proximal operator of the 2-norm.

The function $g(Z)$ should be $g(Z) = g_1(Z_1) + \ldots + g_4(Z_4)$, where the $g_i$ encode the four constraints $Q A_x=0$, $diag(A_x)=0$, $A_x\geq 0$, $A_y\leq 0$. More precisely, they are indicator functions for the respective sets, so the proximal operators become projections. The norm for these projections is the Frobenius norm (the "vector 2-norm for matrices").

Thus you need to compute the projections on the respective sets, which should be manageable.

Does this make sense?

/Tobias

Answer 2

The "constraint" $Ax+Bz=c$ is there to introduce variable splitting. The actual (problem) constraints are introduced through indicator functions (e.g. $g(z) = \mathbf{1}_{\|\cdot\| \leq \varepsilon} (z)$). To allow for multiple constraints, you can reformulate your problem such that $f$ or $g$ represents a sum of penalty functions (approach known as SDMM, check this paper).