Proof verification: Duality between cone of descent and subdifferential

162 Views Asked by At

Let $f$ be some convex function and $x$ some point in it's domain. Define the cone of descent at $x$ as the conic hull of the set of directions in which $f$ is decreased:

$$\mathcal{D}(f,x) = \bigcup_{t>0}\{h \, |\, f(x + th) \leq f(x)\}$$

The polar of a cone is given by the set of directions that are negatively correlated with every point in the set:

$$C^\circ = \{y \, | \, \langle y, x\rangle \leq 0 \, \forall \, x \in C\}$$

The subdifferential of $f$ at a point $x$ is the set of normals of hyperplanes that lowerbound $f$:

$$\partial f(x) = \{w \, | f(y) \leq f(x) + \langle w, y-x\rangle \, \forall y \in \mathbb{R}^d\}$$

Show that the polar of the cone of descent at $x$ is equal to the conic hull of the subdifferential at $x$:

$$\mathcal{D}(f, x)^\circ = \text{cone }\partial f(x) = \bigcup_{\tau \geq 0} \partial f(x)$$

What I've tried

We show the inclusion in both directions:

First to show: $\text{cone }\partial f(x) \subseteq \mathcal{D}(f, x)^\circ$

Consider some $u \in \partial f(x), t \geq 0 \implies f(x + h) - f(x) \geq \langle u, h \rangle$ for all $h \in \mathbb{R}^d$. But if $h$ is in the cone of descent at $x$, then the LHS is less than $0$ and so $\langle tu, h \rangle \leq 0$ for nonnegative $t$. This shows the first inclusion.

For the second inclusion, consider $u \in \mathcal{D}(f,x)^\circ$. $u$ is in the conic hull of the subdifferential at $x$ if: $f(x + h) - f(x) \geq \langle tu, h \rangle \, \forall h$ for some nonnegative $t$. Since we have the flexibility of scaling from the $t$ (since we are looking at the conic hull), we only need to check the signs of the two sides.

There are two cases: $f(x + h) - f(x) < 0 \implies h \in \mathcal{D}(f,x) \implies \langle tu, h \rangle \leq 0$. And in the second case $f(x + h) - f(x) \geq 0$, we have $\langle u, h \rangle \geq 0$ since $t$ can be made arbitrarily small, and equal to $0$.

I could use some feedback on my proof and reasoning.