3
$\begingroup$

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)$?

enter image description here

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?

$\endgroup$

1 Answer 1

3
$\begingroup$

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. enter image description here

$\endgroup$
7
  • $\begingroup$ 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? $\endgroup$
    – MasterJ
    Oct 11, 2021 at 9:08
  • 1
    $\begingroup$ I improved my post, so it should be correct now. Please tell me if there is still anything incorrect. $\endgroup$
    – mag
    Oct 11, 2021 at 9:34
  • 1
    $\begingroup$ Now it seems correct. You "simply" tried to find $h$ with a steeper descent in some interval. Thanks! $\endgroup$
    – MasterJ
    Oct 11, 2021 at 10:47
  • 1
    $\begingroup$ 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. $\endgroup$
    – mag
    Oct 12, 2021 at 9:14
  • 1
    $\begingroup$ 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. $\endgroup$
    – MasterJ
    Oct 12, 2021 at 9:59

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .