Consider the problem $$ \min f(x) \; \text{s.t.} \; x\in D $$ where $f(x)$ is convex but not differentiable, and $D$ is convex.

For differentiable $f$, we know that $x$ is optimal if and only if $\forall y\in D, \; \nabla f(x)^T(y-x)\geq0$ (4.2.3 in Boyd, for instance).

I'm trying to show something similar for non-differentiable $f$. Namely, I believe it should be true that $x$ is optimal if and only if $\exists v\in \partial f(x)$ such that $\forall y\in D,\; v^T(y-x)\geq0$ (where $\partial f(x)$ is the subdifferential).

One direction is easy -- assume $\exists v\in \partial f(x)$ such that $\forall y\in D,\; v^T(y-x)\geq0$. Then, by definition of the subdifferential, $\forall y\in D$ we have $f(y)\geq f(x) + v^T(y-x) \geq f(x)$.

For the other direction, it seems easiest to begin by assuming that we have found some $y\in D$ such that $\forall v\in\partial f(x),\; v^T(y-x)<0$, and going from there. At this point Boyd uses differentiability to argue that for some $t\in(0,1)$ sufficiently small, one must have $f(x+t(y-x))<f(x)$. For the same approach to work here, one needs to argue that for some element of the subdifferential, the subdifferential inequality is "tight" in the direction from $x$ to $y$, and I don't immediately see how to do that.

This seems like a fairly elementary statement though. Surely there has to be a similar proof somewhere?

Thanks.