3
$\begingroup$

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

$\endgroup$
  • $\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 '14 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 '14 at 7:19
  • $\begingroup$ @Yury Found proof along those lines (edited main post). $\endgroup$ – martin May 21 '14 at 7:46
  • $\begingroup$ If $f$ is defined on $D$, then $0\in\partial f(x)$. $\endgroup$ – Yury May 21 '14 at 13:11

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.