Let $f:\mathbb{R}^N\to\mathbb{R}$ be strongly convex and its gradient is Lipschitz continuous, i.e., for some $l>0$ and $L>0$ we have $$f(y)\geq f(x)+\nabla f(x)^T(y-x)+\frac{l}{2}||y-x||^2,$$ and $$||\nabla f(y)-\nabla f(x)||\leq L||y-x||$$ for any $x,y\in\mathbb{R}^N$.

For such a function, the only example I can come up with is the quadratic function $$f(x)=x^T A x +B x + C$$ where $A$ is positive definite. I wonder if there is any other example? Thanks.

Note: the strong convexity and Lipschitz continuity hold for the whole $\mathbb{R}^N$; otherwise $e^x$ ($x\in\mathbb{R}$) is good enough in $[0,1]$.

-- New Remark: I ask this question because these two assumptions are often seen in optimization papers. Functions that satisfy one of the two are easy to think of; to satisfy these two assumptions at the same time, I really doubt how many functions exist.

-- Finally came up with an example by myself: $$f(x)=\log(x+\sqrt{1+x^2})+x^2,x\in\mathbb{R}.$$

Strong convexity: $$\nabla f(x) = \frac{1}{\sqrt{1+x^2}}+2x,$$ $$\nabla^2 f(x) = -\frac{x}{(1+x^2)^{3/2}}+2.$$ Since $$\left|\frac{x}{(1+x^2)^{3/2}}\right|=\left|\frac{x}{\sqrt{1+x^2}}\right|\frac{1}{1+x^2}<1,$$ strong convexity follows from $$3 > \nabla^2 f(x)>1.$$

Lipschitz continuous gradient: \begin{align} \left|\nabla f(x+h)-\nabla f(x)\right|&\stackrel{(a)}{=}\left|\nabla f(x)+\nabla^2 f(y)h-\nabla f(x)\right|\\ &=\left|\nabla^2 f(y)h\right|\\ &\leq 3|h| \end{align} where $(a)$ is from the mean value theorem and $y$ is some number in $[x,x+h]$ for $h\geq 0$ or $[x+h,x]$ for $h<0$.

  • $\begingroup$ Yes, have corrected it. $\endgroup$ – ZhuShY Jan 16 '15 at 2:15
  • $\begingroup$ Now it's clear. So this question reduces to find another convex function that has Lipschitz gradient on the whole $\mathbb{R}^N$ space. Hopefully I can find one :) $\endgroup$ – ZhuShY Jan 16 '15 at 2:47
  • $\begingroup$ Yes. Sorry for the earlier confusion! $\endgroup$ – Michael Grant Jan 16 '15 at 2:48
  • $\begingroup$ I think to avoid confusion for others I shall delete my incorrect comment. You may wish to delete/restate followups. $\endgroup$ – Michael Grant Jan 16 '15 at 4:22
  • 1
    $\begingroup$ @MichaelGrant Just let you know I finally came up with an example. $\endgroup$ – ZhuShY Feb 25 '15 at 17:28

Here's an example on $\mathbb R: f(x) = x^2-\cos x.$

A way to make lots of examples: Let $f$ be any positive bounded continuous function on $[0,\infty).$ For $x\ge 0,$ set

$$g(x) =\int_0^x \int_0^t f(s)\, ds\,dt.$$

Extend $g$ to an even function on all of $\mathbb R.$ Then $g$ satisfies the requirements.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.