0
$\begingroup$

I am reading this manuscript and in section 2.1 (Dual Ascent) Boyd describes the following:

Minimize $f(x)$ subject to $Ax=b$

This gives a lagrangian:

$$ L(x,y) = f(x) + \langle y, Ax-b\rangle$$

which leads to the dual function:

$$ g(y) = \inf\limits_{x} L(x,y) = -f^*(-A^* y) - \langle y,b\rangle$$

where $f^*$ is the convex conjugate of $f$.


I understand how the above is derived. What I don't understand is the following claim from Boyd:

Assuming that $g(y)$ is differentiable we can find the gradient $\nabla g(y)$ in the following way, first find $x^+ = \arg\min\limits_{x}L(x,y)$ and then we will have $\nabla g(y) = Ax^+-b$.


When I try to find $\nabla g(y)$ myself I get the following:

$$\nabla g(y) = \nabla \left(-f^*(-A^* y)-\langle y,b\rangle\right),\\ =-\nabla \left(f^*(-A^* y)\right)-\nabla\left(\langle y,b\rangle\right),\\ =-\arg\max\limits_{x}\left(\langle -A^*y, x\rangle - f(x)\right)-b\\ =-\arg\max\limits_{x}\left(-\langle y, Ax\rangle - f(x)\right)-b\\ =-\left(\arg\min\limits_{x}L(x,y)\right)-b\\ =-x^+-b$$

Can someone explain what I am doing wrong?

$\endgroup$
  • $\begingroup$ How did you go from $\nabla f^*(-A^*y)$ to the $\mathop{\textrm{argmax}}_x$ on the next line? Isn't that assuming the very fact you're trying to prove? $\endgroup$ – Michael Grant Feb 12 '18 at 20:43
  • $\begingroup$ Incidentally, it goes further than what Boyd is saying there: the subdifferential of $g$ at $y$ is $$\partial g(y) = \left\{ Ax^+-b \,\middle|\, x^+\in\mathop{\textrm{argmin}}_x L(x,y)\right\}$$If this set is a singleton, then $g$ is differentiable at $y$, but this holds even if it is not. $\endgroup$ – Michael Grant Feb 12 '18 at 21:04
  • $\begingroup$ Re: "How did go you from..." I can't find it now but I had some lecture slides and they wrote that if the argmax is unique then it is the gradient of the convex conjugate. I don't believe it's circular at all, I am trying to show the gradient of the dual function and I use the gradient of the convex conjugate to do so. How do you derive the subdifferential ∂g(y)? That is essentially what I am trying to show (I am assuming it is a singleton in this simplified version, of course). I know that ∂g(y)=Ax+−b, I am not doubting what Boyd wrote, I want to show it. $\endgroup$ – TSF Feb 13 '18 at 10:02
  • $\begingroup$ The problem is that you are misapplying it. The presence of $A$ inside that term means a straight substitution like that fails. $\endgroup$ – Michael Grant Feb 13 '18 at 12:40
  • $\begingroup$ Okay, that explains why I am getting the wrong result and I appreciate that. Do you happen to know how to derive the expression $\nabla g(y) = Ax^+ - b$? $\endgroup$ – TSF Feb 13 '18 at 14:18
1
$\begingroup$

Let's start from the definition of a subgradient: $$v\in\partial g(y) \quad\Longleftrightarrow\quad g(z) \leq g(y) + \langle v, z - y \rangle \quad \forall z$$ Pulling from the definition, we have $$g(z) = \inf_x f(x) + \langle A x - b, z \rangle = \inf_x f(x) + \langle A x - b, y \rangle + \langle A x - b, z - y \rangle$$ Let $x^+\in\mathop{\textrm{argmin}} L(x,y)$. Then $$\begin{aligned} \inf_x f(x) + \langle A x - b, y \rangle + \langle A x - b, z - y \rangle &\leq f(x^+)+\langle Ax^+-b,y\rangle + \langle Ax^+-b, z-y\rangle \\ &= g(y) + \langle Ax^+-b, z-y\rangle \end{aligned}$$ Therefore, $$g(z) \leq g(y) + \langle Ax^+-b, z-y\rangle$$ Therefore, $Ax^+-b\in\partial g(y)$. If $x^+$ is a unique minimizer, or if the value of $Ax-b$ is identical for all minimizers, then $g$ is differentiable at $y$ and its gradient is $\nabla g(y)=Ax^+-b$.

EDIT: actually, the logic here actually isn't complete. What we haven't proven is a reverse implication: that if $v$ is a subgradient, it must be equal to $Ax^+-b$ (or some other minimizer). Without this, we can't say that $Ax^+-b$ is the gradient, because we can't guarantee it is a unique subgradient.

$\endgroup$
  • $\begingroup$ Thanks so much for this Michael! For the reverse implication I think if we assume that $g$ is differentiable then the subgradient is unique, as it's then a singleton, and we have Boyd's claim (He does assume $g$ is differentiable for this). $\endgroup$ – TSF Feb 14 '18 at 9:48
  • $\begingroup$ If you want to assume $g$ is differentiable that is fine! $\endgroup$ – Michael Grant Feb 14 '18 at 12:31
  • $\begingroup$ I decided to go through this one more time on my own and I noticed something. The subgradient is defined by $v\in\partial g(y)\iff \forall z: g(z)\geq g(y) + \langle v, z-y\rangle$ right? And we can rearrange this to get $\forall z: g(z)+\langle v,y-z\rangle \geq g(y)$. But you have something different in the first line? $\endgroup$ – TSF Feb 14 '18 at 12:49
  • $\begingroup$ I think you are right, let me see if this can be salvaged $\endgroup$ – Michael Grant Feb 15 '18 at 3:05

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.