(Proximal) subgradient inclusion property proof

Question

I'm having a bit of trouble proving what seems to be two fairly straightforward statements for a nonlinear optimisation class I'm taking. We're studying properties of the proximal subgradient, $\partial_p(f) = \{ v\ |\ \exists \rho, \delta: f(y) \geq f(x) + \langle v, y-x \rangle - \frac{\rho}{2}||y-x||^2\ \forall y \in B_\delta(x)\}$

The two properties I'm attempting to prove are as follows:

• If $f \in C^1(\mathbb{R}^n)$, then $\partial_p(f) \subseteq \{\nabla f\}$
• If $f \in C^2(\mathbb{R}^n)$, then $\partial_p(f) = \{\nabla f\}$

I've managed to make a good start, I think, for the $C^1$ case -- replace $f(y)$ with $f(x) + \langle \nabla f(x), y-x\rangle + o(||y-x||^2)$, divide through by $||y-x||$ and take $lim_{y \rightarrow x}$. This takes me to $\langle \nabla f(x) - v, \hat{h}\rangle \geq 0$ (where $\hat{h}$ is some unit-length vector), which gives me that $\nabla f(x) = v$ -- however, this gives me equality, not inclusion!

Would someone be able to tell me what I'm doing wrong, or what piece I'm missing? At this point I'm mildly confused, which is preventing me from making a start on the $C^2$ case!

Answer 1

(from comment) For $C^1$, you can only get $f(y) = f(x) + O(\|x-y\|_2)$, whereas for $C^2$ you have what you used, which is $f(y) = f(x) + \nabla f^T (y-x) + O(\|x-y\|_2^2)$. Reference at wikipedia entry for Taylor's Theorem

So it leaves the $C^1$ case just for you (Did you get it?)

---

I think you may want to use the remainder (in this case it's a type of Fundamental Theorem):

$f(y) - f(x) = \int_0^1 \nabla f(x+t(y-x))^T (y-x) dt$

Suppose there is a $v$ in the subgradient. We have

$\int \left\langle \nabla f(x+t(y-x)), y-x \right\rangle dt = f(y)-f(x) \geq \langle v,y-x \rangle - \rho/2 \|y-x\|^2$

From here you can do a few things to show that $v = \nabla f$. By the way, what this shows is that assuming something is even in the subgradient, it has to be $\nabla f(x)$. This actually shows inclusion. (PS I had slightly more work in a previous edit if you wanted to see how, but I feel you might not need it.)

So it seems that in the $C^2$, you have one more thing to prove: You have to show that $\nabla f(x)$ is in the subgradient. This means finding a $\rho$ and a $\delta$ such that the conditions of the subgradient holds, but it seems that the work is already there, you just need to be careful when you write the details of proof.

For instance, in your original post, you seem to assume the subgradient condition for some $v$, and then do a replacement and manipulation, and conclude that $v = \nabla f$, so this actually was showing inclusion.