(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?


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.

  • $\begingroup$ If $f$ attains its minimum at point $x$, then $0\in \partial f(x)$. Condition $v^T (y-x) \geq 0$ holds for $v=0\in \partial f(x)$, as required. $\endgroup$
    – Yury
    May 21, 2014 at 3:39
  • $\begingroup$ @Yury That's the case for unconstrained problems, but in a constrained problem a point may be optimal without $0\in\partial f(x)$, in particular when the constraint is tight. I'm trying to avoid having to compute the subdifferential of $f(x) + \mathbf{I}_D(x)$, where $\mathbf{I}_D(x)\in\{0,\infty\}$ is the usual indicator function. $\endgroup$
    – martin
    May 21, 2014 at 7:19
  • $\begingroup$ @Yury Found proof along those lines (edited main post). $\endgroup$
    – martin
    May 21, 2014 at 7:46
  • $\begingroup$ If $f$ is defined on $D$, then $0\in\partial f(x)$. $\endgroup$
    – Yury
    May 21, 2014 at 13:11


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Browse other questions tagged or ask your own question.