# Method of Multipliers: Why is the next iterate always dual feasible?

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$$.

• In Eqn (1), shouldn't it be $x^{k+1}$ ? May 19 at 16:20
• I am using a different subscript compared to the paper. In the algorithm, they define $x^{k+1} = \arg \min_x L(x, \lambda^k)$, while I am defining $x^k = \arg \min_x L(x, \lambda^k)$. I chose this because $\arg \min_x L(x, \lambda^k)$ is used to find the gradient of the dual at $\lambda^k$, so it makes more sense to me to call it $x^k$. May 19 at 16:37

By dual feasibility, all that the authors mean is that $$(x^{k+1}, \lambda^{k+1})$$ in Equation (1) satisfies the stationarity equation in the KKT optimality conditions for the problem shown at the top of your question. Recall that the stationarity equation for the problem is to find $$x, \lambda$$ such that
$$\nabla f(x) + A^{\top} \lambda = 0$$
• Thanks for your answer. Do you think that by some trickery, $(x^{k+1}, \lambda^{k+1})$ satisfying the KKT system could imply that $d(\lambda^{k+1}) > -\infty$? May 19 at 16:41
• I dont see why the inf cannot be $-\infty$. For finite $\lambda$, suppose $f(x) = c^\top x$ such that $c$ is in the null space of $A$, then the inf is indeed $-\infty$ since we can set $x = r (-c)$ where $r$ is $+\infty$. May 19 at 16:53