Can a Lipschitz continuous function be strongly convex?

Question

Let $\varphi:\mathbb R^n\to\mathbb R$, and suppose for all $x,y\in\mathbb R^n$, $$\|\varphi(x)-\varphi(y)\|\leq L\|x-y\|$$ for Lipschitz constant $L$. Is it possible for such a function to satisfy strong convexity? i.e., $$ \varphi(x) - \varphi(y) \geq \nabla \varphi(y)^T(x-y) + \frac{\lambda}{2}\|x-y\|^2 $$ I can't think of such an example, so I'm curious if there is a proof to show this.

Answer 1

It's possible for a strongly convex function to have a Lipschitz continuous gradient, but no, it is not possible for a strongly convex function to have a Lipschitz continuous value. To see why, note that $$\varphi(x)-\varphi(y)\geq \nabla\varphi(y)^T(x-y)+\frac{\lambda}{2}\|x-y\|^2 \geq \left(\frac{\lambda}{2}\|x-y\|-\|\nabla\varphi(y)\|_*\right)\|x-y\|$$ where $\|\cdot\|_*$ is the norm dual to $\|\cdot\|$. This follows from the Cauchy-Schwarz inequality $$-\|u\|_*\|v\|\leq u^Tv\leq\|u\|_*\|v\|.$$ Therefore, for $x\neq y$, we have $$\frac{\varphi(x)-\varphi(y)}{\|x-y\|} \geq -\|\nabla\varphi(y)\|_*+\frac{\lambda}{2}\|x-y\|$$ The right-hand side is unbounded as $\|x-y\|\rightarrow+\infty$, so no fixed value of $L$ can be found.