ADMM structure of mathematical model

Question

If I have the following mathematical model:

$Min f(x)$

s.t.

$Ax = b$

$Bx \leq c$

How do I convert this model to ADMM format if $f(x)$ is affine?

Thanks

Answer 1

I'll assume $f(x) = a^T x$. One approach is to reformulate your problem as minimizing $$ \underbrace{a^T x + I_{\{b \}}(u) + I_{\leq c}(v)}_{g(x,u,v)} + I(x,u,v), $$ where the indicator function $I_{\{b \}}(u)$ enforces the constraint $u = b$, the indicator function $I_{\leq c}(v)$ enforces the constraint $v \leq c$, and the indicator function $I(x,u,v)$ enforces the constraint $$ \begin{bmatrix} A \\ B \end{bmatrix} x = \begin{bmatrix} u \\ v \end{bmatrix}. $$ The optimization variables in the reformulated problem are $x, u$, and $v$. The prox-operator of $g$ can be evaluated easily because it is a separable sum of functions with easy prox-operators. The prox-operator of $I$ projects onto the graph of $\begin{bmatrix} A \\ B \end{bmatrix}$, which is just a linear algebra problem. So $g(x,u,v) + I(x,u,v)$ can be minimized using the Douglas-Rachford algorithm, which is a special case of ADMM.

---

You could also reformulate the problem as minimizing $f(x) + G(u,v)$ subject to $$ \begin{bmatrix} A \\ B \end{bmatrix} x - \begin{bmatrix} u \\ v \end{bmatrix} = 0 $$ where $G(u,v) = I_{\{b \}}(u) + I_{\leq c}(v)$. This fits the standard ADMM problem form.