4
$\begingroup$

I'm trying to bound the quantity $\langle \nabla \Psi(x),\bar{x}-x \rangle$ above, with the bound depending on $\|x-\bar{x}\|$ and perhaps also of $\|x-y\|$ for fixed (but not varying) points $y$. Where here $\Psi(x):X\mapsto \mathbb{R}$ with $X$ a finite dimensional Banach space (or $\mathbb{R}^n$, whatever) And $\Psi(x)$ is a $\mu$-strongly convex function (with $\mu$>0) that can be written as $\Psi=f+g$ with $f$ convex and differentiable with $\nabla f$ $L$-Lipschitz continuous and $g$ $\mu$-strongly convex.

I know that if $\Psi$ was differentiable and its gradient was $L$-Lipschitz continuous one could fix some point $x^*$ on the optimal set and bound as

$\langle \nabla \Psi(x), \bar{x}-x \rangle \leq \|\nabla \Psi(x)\|\|\bar{x}-x\| = \|\nabla \Psi(x)-\nabla \Psi(x^*)\|\|\bar{x}-x\| \leq L\|x-x^*\|\|\bar{x}-x\|$

And the bound is done. So my question is, is there an analogous of this property on the non-differentiable case? Like, I know that I can pick a point $x^*$ on the optimal set such that $0 \in \partial \Psi(x^*)$, but then can I say that for a $v \in \partial \Psi(x)$ it holds

$\|v\| = \|v-0\| \leq L\|x-x^*\|$ or something on that line?

Any help is appreciated

$\endgroup$
  • $\begingroup$ Oops, yes I am. Fixed I guess $\endgroup$ – karlabos Dec 2 '14 at 18:28
  • $\begingroup$ There is a concept of Lipschitz continuity for set-valued mappings as discussed in Rocafellar and Wets, Variational Analysis, Sec 9-E and, this said, some subgradients can be found to be Lipschitz continuous. $\endgroup$ – Pantelis Sopasakis Aug 3 '16 at 8:41
1
$\begingroup$

The answer is no. On the real line consider $\Phi(x)=|x| $ (and add some smooth convex function with minimum in zero if you like). Then the minimum is in zero but the subgradient at any positive point is about 1.

$\endgroup$
  • 1
    $\begingroup$ But then, for any points $x,\bar{x}$, for every $v \in \partial \Phi(x)$ we'd have $\langle \nabla \Phi(x), x-\bar{x} \rangle \leq \|\nabla \Phi(x)\|\|x-\bar{x}\| \leq 1\|x-\bar{x}\|$, so we have the bound... Am I missing something on this counterexample? $\endgroup$ – karlabos Dec 3 '14 at 0:08
  • $\begingroup$ No, but I read the question as you were asking about Lipschitz continuity of the subgradient and not the specific problem. If you want to ask that specific question, go ahead and ask it in a separate question. $\endgroup$ – Dirk Dec 3 '14 at 9:01
0
$\begingroup$

I think the property you are looking for is Lipschtiz continuity of the function $\Psi$, as this is equivalent to bounded subgradients.

$\endgroup$

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.