(EDIT: see proof at the end) 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.
EDIT: Oh ok. We know that $x$ is optimal iff $0\in\partial (f(x)+\mathbf{I}_D(x))$, where $\mathbf{I}_D(x)\in\{0,\infty\}$ is the indicator of $D$. Now, $0\in\partial (f(x)+\mathbf{I}_D(x))$ iff $\exists v\in\partial f(x)$ such that $-v\in\partial \mathbf{I}_D(x)$. The condition $-v\in\partial \mathbf{I}_D(x)$ is identical to $\mathbf{I}_D(y)\geq\mathbf{I}_D(x) - v^T(y-x) \; \forall y$. The latter, in turn, is trivial for $y\notin D$, and for $y\in D$ is equivalent to $v^T(y-x)\geq 0$, with the obvious extra addendum that $x\in D$. Almost trivial, as I suspected.