I am reading this expository paper on ADMM by Boyd, et. al.
Consider the problem \begin{align*} &\min f(x)\\ & \ \text{s.t.} \ \ \ Ax = b \end{align*}
with Lagrangian $L(x, \lambda) = f(x) + \lambda^T (Ax - b)$. The Dual Ascent algorithm is
Choose $\lambda_0$
For $k = 0, 1, 2, ...$
$\ \ \ \ \ \ \ x^k = \arg \min_x L(x, \lambda^k)$
$ \ \ \ \ \ \ \ \lambda^{k+1} = \lambda^k + \alpha_k (Ax^k - b)$
With some assumptions and correct choice of the step size $\alpha_k$, $x^k$ converges to primal optimal solution and $\lambda^k$ converges to dual optimal solution.
In the Method of Multipliers, all we do is apply the Dual Ascent algorithm to the equivalent problem
\begin{align*} &\min f(x) + \frac p2 ||Ax - b||^2\\ & \ \text{s.t.} \ \ \ Ax = b \end{align*} and choose the stepsize as the constant $p$. Thus, the Method of Multipliers is:
Choose $\lambda_0$
For $k = 0, 1, 2, ...$
$\ \ \ \ \ \ \ x^k = \arg \min_x L_p(x, \lambda^k)$
$ \ \ \ \ \ \ \ \lambda^{k+1} = \lambda^k + p (Ax^k - b)$
where $L_p(x, \lambda) = f(x) + \lambda^T(Ax - b) + \frac p2 ||Ax - b||^2$.
Now, in the case where $f$ is differentiable, the authors give the following as a justification of why the step size should be $p$ (pages 11-12): since $x^k$ minimizes $L_p(x, \lambda^k)$, we must have
\begin{align*}
0 &= \nabla_x L_p(x^k, \lambda^k)\\
&= \nabla f(x^k) + A^T \lambda ^k + pA^T(Ax^k - b)\\
&= \nabla f(x^k) + A^T(\lambda ^k + p(Ax - b))\\
&= \nabla f(x^k) + A^T \lambda^{k+1} \tag{1}\label{Eq:1}
\end{align*}
The authors claim if we chose $p$ for the stepsize, the above calculation implies $\lambda^{k+1}$ is dual feasible. However, I don't see why. Using what was just proved, we have
\begin{align*}
d(\lambda^{k+1}) &= \inf_x [f(x) + \lambda^{k+1} \cdot(Ax-b) + \frac p2 ||Ax - b||^2]\\
&= \inf_x [f(x) - \nabla f(x^k)^Tx + \frac p2 ||Ax - b||^2] - \lambda^{k+1} \cdot b \tag{2} \label{Eq:2}
\end{align*}
But it's not clear at all to me why this $\inf$ cannot be $-\infty$.
