1
$\begingroup$

I am trying to come up with like three strongly convex function $f\colon\mathbb{R}\to\mathbb{R}$ where the Lipschitz constant $L$ is equal to the strong convexity parameter $u$, i.e. for every $x,y\in\mathbb{R}$ \begin{align} |\nabla f(x)-\nabla f(y)|&\leq L|x-y|, \tag{1}\\ f(\cdot)-\dfrac{u}{2}|\cdot|^2&\;\;\text{is convex, and} \tag{2}\\ L=u \tag{3} \end{align}

I am having a hard time coming up with such functions but I am suspecting that a type of least square might possess the property. Can someone help me come up with such functions where $L=u$? Thanks.

$\endgroup$
3
  • $\begingroup$ Strongly convex $\endgroup$
    – Tony....
    Aug 1, 2020 at 20:52
  • $\begingroup$ What are the domain and codomain of your function? Usually a Lipschitz operator goes from a space to itself, but strong convexity is a property of a function from a space to $\mathbb{R}$. So are you assuming this operator maps from $\mathbb{R}\to\mathbb{R}$? $\endgroup$
    – Zim
    Aug 2, 2020 at 16:27
  • $\begingroup$ Yes that is right $\endgroup$
    – Tony....
    Aug 2, 2020 at 16:29

1 Answer 1

Reset to default
0
$\begingroup$

It holds for $f(\mathbf{x})=\frac{1}{2}\|\mathbf{x}\|_2^2$, which has a strong convexity and L-smoothness parameter $1$ w.r.t the $l_2$ norm.

We derive this from the Conjugate Correspondence Theorem which states that a $\mu$-strongly convex function has a conjugate $f^*$ which is $\frac{1}{\mu}$-smooth. Since we have the "rare" occasion where $\frac{1}{2}\|\mathbf{x}\|_2^2$ is it's own conjugate, with the parameter $1=1^{-1}$, the two coincide.

$\endgroup$
4
  • $\begingroup$ Set $x=3$, $y=0$, then $|f(x)-f(y)|=4.5 > 3 = | x-y|$ so $f$ is not 1-Lipschitz. I think the constant is actually $2$, see e.g. math.stackexchange.com/questions/2617575/… $\endgroup$
    – Zim
    Aug 2, 2020 at 16:31
  • $\begingroup$ @Zim you're confusing a Lipschitz function with Lipschitz gradient. The gradient of $\frac{1}{2} x^2 = x$. Then in your example, $3\leq 1*3$. Q.E.D :) $\endgroup$
    – iarbel84
    Aug 2, 2020 at 16:43
  • $\begingroup$ I agree its gradient is $1$-Lipschitz, but it looks to me like the OP was asking for a strongly convex Lipschitz-continuous function; they did not mention $L$-smoothness at all. $\endgroup$
    – Zim
    Aug 2, 2020 at 16:47
  • $\begingroup$ @Zim you got me there. Since strong convexity and $L$-smoothness are related I might have read it wrong. But we'll need to wait and hear from him. $\endgroup$
    – iarbel84
    Aug 2, 2020 at 16:57

You must log in to answer this question.

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