3
$\begingroup$

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

$\endgroup$
2
  • $\begingroup$ In Eqn (1), shouldn't it be $x^{k+1}$ ? $\endgroup$
    – batwing
    May 19 at 16:20
  • $\begingroup$ 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$. $\endgroup$
    – user56202
    May 19 at 16:37
3
$\begingroup$

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

$\endgroup$
2
  • $\begingroup$ 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$? $\endgroup$
    – user56202
    May 19 at 16:41
  • $\begingroup$ 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$. $\endgroup$
    – batwing
    May 19 at 16:53

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.