The goal is to write a program that solves for x in
$$\textbf{min}\quad \|A\textbf{x}-\textbf{b}\|_1+\sigma \|\bf x \|_1$$ for $A\in \mathbb{R}^{m\times n}$. We assume that ${m}<{n}$ and ${\sigma}>{0}$. This optimization problem can also be reformulated as an LP.
The program must be an ADMM (alternating direction method of multipliers) on the variables $$ {\bf u}={A}{\bf x}-{\bf b},\quad \quad {\bf v}=\sigma{\bf x} $$
Which leads to $$ \bf min \quad \|{\bf u}\|_{1}+\|v\|_{1} \\ s.t.\quad \binom{\textit{A}}{\sigma I}x-\binom{u}{v}=\binom{b}{0} $$ So I set up me wee little Augmented Lagrangian $$ \mathcal{L}_{\rho}({\bf x,u,v,\nu}) = {\bf \|u\|_{1}+\|v\|_{1} } +\Lambda^\top \left(\binom{\textit{A}}{\sigma I}{\bf x-\binom{u}{v}-\binom{b}{0} }\right) + \frac{\rho}{2}\left\|\binom{\textit{A}}{\sigma I}{\bf x-\binom{u}{v}-\binom{b}{0} }\right\|_{2}^{2} $$
Question 1 & 2
I know how to do $\displaystyle\frac{\partial \mathcal{L}}{\partial \bf x}$, but what is $\displaystyle\frac{\partial \mathcal{L}}{\partial \bf u}$ and $\displaystyle\frac{\partial \mathcal{L}}{\partial \bf v}$?
Question 3
These equations were given $${\bf x}^{({k}+{1})} = \left( {A}^\top {A}+{\tau}^{2 }{I} \right)^{-1} \begin{pmatrix} {A}\\{\tau}{I} \end{pmatrix}^\top \left( \begin{pmatrix} {\bf u}\\{\bf v} \end{pmatrix} ^{({k})} +\begin{pmatrix} {\bf b}\\{\bf 0} \end{pmatrix} -\frac{1}{\rho}{\Lambda}^{({k})} \right)$$
what is $\Lambda^{(0)}$?
Question 4 $${\Lambda}^{({k}+{1})} = {\Lambda}^{({k})} + \frac{1}{\rho} \left( \begin{pmatrix}{A}\\{\tau}{I}\end{pmatrix} {\bf x}^{({k}+{1})}-\begin{pmatrix}{\bf u}\\{\bf v} \end{pmatrix}^{({k}+{1})}-\begin{pmatrix}{\bf b}\\{\bf 0} \end{pmatrix} \right)$$ where did this equation come from?
Question 5
How do you find $\displaystyle\binom{\bf u}{\bf v}^{k+1}$? The instructions are to use a skrinkage operator on $\displaystyle\binom{\bf u}{\bf v}$. What is that?!!!!
I have been reading the textbook for days. Epically stumped on this
Thanks,
Jason
Undergraduate Math
University of California, Berkeley