How to use ADMM for the problem given below?
\begin{alignat}{2}
\tag{P1}
&\underset{x \in \mathbb{R}^{n \times 1}}{\text{minimize}}&\quad \frac{1}{2}\left\|Ax – r \right\|_2^2\\
&\text{subject to }&\quad \|x\|_{1} \leq b,
\end{alignat}
where $r \in \mathbb{R}^{m \times 1}$, $A \in \mathbb{R}^{m \times n}$, and $b \in \mathbb{R}_{\geq0}$.
To use ADMM (http://stanford.edu/~boyd/admm.html), I can rewrite P1 as following.
\begin{alignat}{2}
&\underset{x \in \mathbb{R}^{n \times 1}, \ z \in \mathbb{R}^{m \times 1}}{\text{minimize}}&\quad \frac{1}{2}\left\|z – r \right\|_2^2 + f(x) \\
&\text{subject to } & z = Ax ,
\end{alignat}
where $f(x)$ is an indicator function to the $\ell_1$ norm ball, i.e., $f(x) = 0$ if $x \in C$ otherwise $+\infty$ and $C = \left\{ x : \|x\|_{1} \leq b \right \}$.
And, ADMM steps are
\begin{align}
{x}^{k+1}
&= \arg\min_{x} L_\rho\left( x, z^{k}, y^{k} \right) \\
{z}^{k+1}
&= \arg\min_{z} L_\rho\left( x^{k+1}, z, y^{k} \right) \\
{y}^{k+1}
&= {y}^{k} + \rho \left( A {x}^{k+1} – {z}^{k+1} \right),
\end{align}
where the augmented Lagrangian is
\begin{align}
L_\rho\left( x, z, y \right) = \frac{1}{2}\left\|z – r \right\|_2^2 + f(x) + y^T\left( Ax – z \right) + \frac{\rho }{2}\left\| Ax – z \right\|_2^2.
\end{align}
For the step 1 of ADMM iteration, I need to solve the following
\begin{align}
0 \in \partial f(x) + A^Ty + \rho A^T \left( Ax – z \right).
\end{align}
Now, I am stuck and do not know how to solve for $x$. Can anyone help me?
For the step 2 of ADMM iteration, it is simple. But step 1 is unclear.
Best Answer
The way that the optimization problem (P1) has been reformulated here, the $x$-update is indeed not easy. An iterative algorithm would be required just to solve that subproblem. So what we should do is reformulate the problem differently so that both updates are easy.
In this case, you can just express the optimization problem (P1) as $$ \tag{1} \text{minimize} \quad f(x) + \underbrace{\frac12 \| Ax - r \|_2^2}_{g(x)} $$ and minimize $f+g$ using the Douglas-Rachford method (which is a special case of ADMM). (Here the optimization variable is $x$, and $f$ is the indicator function of the $\ell_1$-norm ball of radius $b$.) Evaluating the proximal operator of $g$ reduces to solving a linear system of equations involving the matrix $A$. Evaluating the proximal operator of $f$ is equivalent to projecting a point onto the $\ell_1$-norm ball of radius $b$. (One way to do that is explained on slide 6-15 in Vandenberghe's UCLA 236c notes.)
By the way, because $g$ is differentiable, you can also solve problem (1) using the proximal gradient method or an accelerated proximal gradient method such as FISTA. I'd bet FISTA would be faster than ADMM, and also these methods have two other advantages: 1) There is no need to solve a large linear system of equations at each iteration; 2) Line search procedures are available (so there's no need to laboriously tune your step size, as is often necessary with ADMM).