# Lower bound of a strongly convex function

Let $$f,h\colon\mathbb R^n\to\mathbb R$$ be two strongly convex functions such that $$f\ge h$$ and $$f\left( x^*\right)=h\left( x^*\right)$$, where $$x^*$$ is a joint unique minimizer for both. Assume that $$f$$ is non-differntiable and $$h$$ is continuously differentiable.

Take any $$x,y\in\mathbb R^n$$ such that $$f\left( x\right)\ge f\left( y\right)$$. Can we say that $$f\left( x\right)- f\left( y\right)\ge h\left( x\right)- h\left( y\right)$$?

I encountered this problem while analyzing an optimization algorithm. I tried to use the the multi-variable mean value theorem (although $$f$$ is non-differentiable in infinitely many points). Any ideas on even if this statement is true?

The statement is not true. Think about this counterexample for $$n=1$$: Let's denote by $$z_0\approx 4.89$$ the bigger one of the two roots of $$g(x)=3x^{4/3}-1-x^2$$. Then the counterexample is given by $$h(x)=x^2$$ and $$f(x)=\begin{cases}2x^2,\qquad x<1\\ 3x^{4/3}-1,\ x\in[1,z_0]\\ x^2,\quad x>z_0 \end{cases}$$ at the points $$x=z_0$$ and $$y=1$$. Both functions have the same value at point $$x$$, but as $$h(y)=1$$ and $$f(y)=2$$, so the function $$f$$ is growing less in this interval.
• Thank you for your answer! To my understating of the concept of strong convexity, it seems that the function $f$ is not strongly convex, since it is linear in the segment $1\le x\le 2+\sqrt 2$. Is that correct? Oct 11, 2021 at 9:08
• Now it seems correct. You "simply" tried to find $h$ with a steeper descent in some interval. Thanks! Oct 11, 2021 at 10:47
• In $\mathbb R$ this is correct. But I don't think that it is still correct in higher dimensions. The counterexample which comes into my mind is $h(x,y)=x^2+y^2$ and $f(x,y)=x^2+y^2+|x|$. Then take two points on a equipotential line of $f$. Clearly $f$ is constant, but $h$ canges its values. I haven't checked this into detail whether all conditions are satisfied. Maybe you can do this and help others in the future who got stuck at the same problem.
• I intend to that, since for any strongly convex and non-differentiable function $f$, I want to construct a strongly convex and continuously differentiable function $h$, such that $f\left(x\right)-f\left(y\right)\ge h\left(x\right)-h\left(y\right)$. I'm pretty sure that it is possible to find such $h$, but I'm straggling how to construct it. Hopefully I will establish some results in the coming days. Oct 12, 2021 at 9:59