Solution of constrained optimization problem (ADMM)

Question

Consider the following optimization problem which appear in ADMM page 57.

Here $\bar{a}$ is avg of $a$. I don't see how eq. 7.13 came? Lagrangian does not seem to bring that. Any help is appreciated.

Answer 1

Since $\bar{z}$ is fixed, the above problem is minimizing a quadratic function $f$ with a single affine constraint. In general, the optimality condition tells us that the gradient of $f$ at the optimal solution is orthogonal to the null space of the affine constraint (or equivalent,lies in the image of the dual of that affine map).
Now the gradient of the quadratic function is $\rho(z_1-a_1,...,z_N-a_N)$. The affine constraints is $Az=N\bar{z}$, where $A$ is a linear map, $A: \mathbb{R}^{N\times n}\to \mathbb{R}^n$ is given by $A(z)=\sum_{i=1}^{N}z_i$. Hence, the dual of $A$ is $A^*: \mathbb{R}^{n}\to\mathbb{R}^{N\times n}$, given by $A^*(y)=(y,y,...y)$, $N$ copies of $y$. Hence, the optimality condition says that there exists $y$ such that $z_i-a_i=y$ for $i=1...N$. Taking the average of $N$ equations, we have that $\bar{z}-\bar{a}=y$, and $z_i=a_i+\bar{z}-\bar{a}$ by substitution.