I was trying to use Augmented Lagrangian Method to a L-infinity norm restricted problem as following (where $I$ means identity matrix):
$$\begin{array}{ccl} &\underset{x,y}{\min} &\frac12x^Tx + y^Tb\\ &\textrm{subject to} &A^Tx-Iy = 0, \|y\|_{\infty}\le\mu \end{array} $$ Augmented Lagrangian is as following (where $t$ should be a super parameter chosen by me): $$L(x,y,z) = \frac12x^Tx + y^Tb + z^T(A^Tx - Iy) + \frac{t}{2}\|A^Tx -Iy \|_2^2$$ So according to the augmented lagrangian method, the iterations should be as following: \begin{align} (x^{(k)}, y^{(k)}) &= \arg\min_{x,y} L(x,y,z^{(k-1)}) \text{,subject to}\|y\|_{\infty}\le\mu\\ z^{(k)} &= z^{(k)} + t(A^Tx^{(k)}-Iy^{(y)}) \end{align}
My problem is that how should I deal with the subroutine of $(x^{(k)}, y^{(k)})$ under Augmented Lagrangian Method? The problem doesn't seem to have a direct solution.
Augmented Lagrangian:
$L(x, y, z) = \frac{1}{2}x^Tx + b^Ty + i_{\|y\|_\infty \le \mu} + z^T(A^Tx-y) + \frac{\rho}{2}\|A^Tx-y\|_2^2$
For the $(x,y)$ update, I'd do a block-coordinate descent (BCD): update $x$ with $y$ held fixed and then update $y$. You might have to check that this actually convergens...
$x$ update: set derivative w.r.t $x$ to zero
$x^{(k+1)} = \text{argmin}_{x} L(x, y^{(k)}, z^{(k)}) = (\rho AA^T + I)^{-1}(y^{(k)}-Az^{(k)})$
$y$ update: complete-the-square in $y$
$$ \begin{split} y^{(k+1)} &= \text{argmin}_{y: \|y\|_\infty \le \mu} L(x^{(k+1)}, y, z^{(k)})\\ &=\text{argmin}_{y: \|y\|_\infty \le \mu} \frac{\rho}{2}\|y - (A^Tx^{(k+1)} + (z^{(k)}-b)/\rho)\|_2^2 \\ &= \Pi_{[-\mu,\mu]^n}(A^Tx^{(k+1)} + (z^{(k)}-b)/\rho) \end{split} $$
Appendix: projection onto hyper-cube $$\Pi_{[a_1,b_1] \times \ldots \times [a_n,b_n]}(c) = (\Pi_{[a_1,b_1]}(c_1), \ldots, \Pi_{[a_n,b_n]}(c_n)) = (\varphi(a_1, b_1, c_1),\ldots,\varphi(a_n,b_n,c_n)),$$ where $\varphi(r, s, t)$ is the projection of $t \in \mathbb R$ onto the compact interval $[r, s]$, defined by $$\varphi(r,s,t) := \begin{cases}r, &\mbox{ if}t \le r,\\t, &\mbox{ if }r < t \le s,\\s, &\mbox{otherwise.}\end{cases}$$