# Upper bound for the dual norm of a subgradient of a convex function?

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 \|$.

• 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? – Theo Bendit Jul 18 '18 at 0:22
• Also, is the convex function being non-differentiable important? If you're looking for a counterexample, would a differentiable function do? – Theo Bendit Jul 18 '18 at 0:23
• 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. – Saeed Jul 18 '18 at 0:40
• 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. :-) – Theo Bendit Jul 18 '18 at 0:42
• Can you take a look at this page [math.stackexchange.com/questions/2855076/…. – 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.
• I think you are right, I need more condition on $f$ so I posted [math.stackexchange.com/questions/2855076/… – Saeed Jul 18 '18 at 1:10
• Can we add an assumption on the function $f$ to have the above inequality? – Saeed Jul 18 '18 at 18:25