Assume $f: \mathbb{R}^n\rightarrow \mathbb{R}$ is a nondifferentiable convex function on $X$. Let represent a subgradient of the function at point $x \in X$ by $x^* \in \partial f(x)$, that is $$ f(y) \geq f(x) + \langle x^*, y-x \rangle $$ Is there any $\lambda$ such that we have the following? $$ \| x^* -y^* \|_* \leq \lambda \| x-y \| $$ where $\| \cdot \|_*$ is the dual norm of $\| \cdot \|$.

  • $\begingroup$ I'm confused; the notation $f'(x)$ is usually reserved for when the convex function is differentiable at $x$ and is the unique element of the Clarke subgradient. In the question, are we taking $f'(x)$ and $f'(y)$ to be (respectively) arbitrary elements of $\partial f(x)$ and $\partial f(y)$? Or is the assumption implicitly that $f$ is differentiable at these particular values? $\endgroup$ – Theo Bendit Jul 18 '18 at 0:22
  • $\begingroup$ Also, is the convex function being non-differentiable important? If you're looking for a counterexample, would a differentiable function do? $\endgroup$ – Theo Bendit Jul 18 '18 at 0:23
  • $\begingroup$ Since I did not know another symbol for representing the subgradient at different point, I used $f'(x)$ for an arbitrary subgradient at point $x$. The function is non-differentiable. $\endgroup$ – Saeed Jul 18 '18 at 0:40
  • $\begingroup$ I often see $x^*$ used to represent an element of $\partial f(x)$. You can use just about any symbols, but I would definitely avoid $f'(x)$. That's taken. :-) $\endgroup$ – Theo Bendit Jul 18 '18 at 0:42
  • $\begingroup$ Can you take a look at this page [math.stackexchange.com/questions/2855076/…. $\endgroup$ – Saeed Jul 20 '18 at 0:01

No, I don't think this is true. I'm going to show it first with a differentiable function. Take $$f : \mathbb{R} \to \mathbb{R} : x \mapsto e^{x^2}.$$ The function is convex, as $f''(x) = 2(2x^2 + 1)e^{x^2} > 0$. Moreover, we have $f'(x) = 2xe^{x^2}$: the unique element of $\partial f(x)$. Then $$\frac{\|f'(n + 1) - f'(n)\|}{\|(n + 1) - n\|} = 2(n+1)e^{(n+1)^2} - 2ne^{n^2} > e^{(n+1)^2} \to \infty$$ as $n \to \infty$. So, no such bound holds for this (differentiable) $f$.

If you insist on a non-differentiable function, take $g(x) = \max \lbrace f(x), 2 \rbrace$. The argument above still holds since $g(n) = f(n)$ for all integers $n$, and $g$ is definitely still convex as it is the supremum of two convex functions.

| cite | improve this answer | |
  • $\begingroup$ I think you are right, I need more condition on $f$ so I posted [math.stackexchange.com/questions/2855076/… $\endgroup$ – Saeed Jul 18 '18 at 1:10
  • $\begingroup$ @Saeed You need to be careful about posting problems without context or attempts to solve them. I would link your new question back to your old one, and maybe talk a bit about your motivation for solving this problem. $\endgroup$ – Theo Bendit Jul 18 '18 at 1:17
  • $\begingroup$ Sure. Thank you for letting me know. I will do that. $\endgroup$ – Saeed Jul 18 '18 at 1:18
  • $\begingroup$ Can we add an assumption on the function $f$ to have the above inequality? $\endgroup$ – Saeed Jul 18 '18 at 18:25
  • $\begingroup$ @Saeed I don't know, off the top of my head. I suspect not? $\endgroup$ – Theo Bendit Jul 18 '18 at 22:07

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.