# Dual ascent and gradient of convex conjugate

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?

• 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? – Michael Grant Feb 12 '18 at 20:43
• 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. – Michael Grant Feb 12 '18 at 21:04
• 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. – TSF Feb 13 '18 at 10:02
• The problem is that you are misapplying it. The presence of $A$ inside that term means a straight substitution like that fails. – Michael Grant Feb 13 '18 at 12:40
• 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$? – TSF Feb 13 '18 at 14:18

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.
• 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). – TSF Feb 14 '18 at 9:48
• If you want to assume $g$ is differentiable that is fine! – Michael Grant Feb 14 '18 at 12:31
• 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? – TSF Feb 14 '18 at 12:49