TITLE: ADMM formalization
QUESTION [1 upvotes]: 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 ?.

REPLY [2 votes]: 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
{"set_name": "stack_exchange", "score": 1, "question_id": 1261819}