I'm trying to understand conciliation of the proximal formulation of ADMM with its Augmented Lagrangian (method of multipliers) interpretation. In particular, I'm struggling with page 156 here (https://web.stanford.edu/~boyd/papers/pdf/prox_algs.pdf) where it says "pull the linear terms into the quadratic ones". To be more specific:
$\mathbf y^{T}\mathbf x + (\rho/2) ||\mathbf x- \mathbf z||_2^2$
should become
$(\rho/2) ||\mathbf x- \mathbf z + (1/\rho)\mathbf y||_2^2$
I cannot make sense of that passage. Can someone detail how the equivalence is achieved? Am I missing something obvious?
The two expressions, i.e. scaled and unscaled forms, are equivalent.
We have
$$\begin{align*} \textbf{y}^T(\textbf{x-z}) + \frac{\rho}{2}\|\textbf{x-z}\|_2^2 &= \frac{\rho}{2}\|\textbf{x-z} + \frac{\textbf{y}}{\rho}\|_2^2 - (\frac{1}{2\rho})\|\textbf{y}\|_2^2 \\ &=\frac{\rho}{2}(\textbf{x-z} + \frac{\textbf{y}}{\rho})^T(\textbf{x-z} + \frac{\textbf{y}}{\rho})- (\frac{1}{2\rho})\|\textbf{y}\|_2^2 \\ &=\frac{\rho}{2}((\textbf{x-z})^T(\textbf{x-z}) + (\textbf{x-z})^T(\frac{1}{\rho})\textbf{y} + (\frac{1}{\rho})\textbf{y}^T(\textbf{x-z}) + (\frac{1}{\rho})\textbf{y}^T(\frac{1}{\rho})\textbf{y}) - (\frac{1}{2\rho})\|\textbf{y}\|_2^2 \\ &=\frac{\rho}{2}(\|\textbf{x-z}\|^2_2 + (\frac{2}{\rho})\textbf{y}^T(\textbf{x-z}) + (\frac{1}{\rho^2})\|\textbf{y}\|^2_2) - (\frac{1}{2\rho})\|\textbf{y}\|_2^2 \\ &=\frac{\rho}{2}\|\textbf{x-z}\|^2_2 + \textbf{y}^T(\textbf{x-z}) + (\frac{1}{2\rho})\|\textbf{y}\|_2^2 - (\frac{1}{2\rho})\|\textbf{y}\|_2^2 \\ &=\frac{\rho}{2}\|\textbf{x-z}\|^2_2 + \textbf{y}^T(\textbf{x-z}) \end{align*}$$
$\textbf{Note}$ that the term $-(\frac{1}{2\rho})\|\textbf{y}\|_2^2$ is generally dropped out from the ADMM iterations because it doesn't depend nither on $\textbf{x}$ nor $\textbf{z}$.