4

There are several equivalent definitions for strongly convex.

For example, some literature said:

A function $f$ is strongly convex with modulus $c$ if either of the following holds

  1. $$f(\alpha x+(1-\alpha)x')\leq\alpha f(x)+(1-\alpha)f(x')-\frac{1}{2}c\alpha(1-\alpha)\|x-x'\|^2$$

  2. $f-\frac{c}{2}\|\cdot\|^2$ is convex.

I do not know how to prove the equivalence of the above statements. The difficulty here is that the norm is an arbitrary norm, not necessarily the $\ell_2$ norm.

Rodrigo de Azevedo
  • 1
mining
  • 1,075
  • I presume the fraction in the second definition is $\frac{c}{2}$ rather than $\frac{1}{2}$. Also, is the norm induces by an inner-product or not? – S.B. Oct 02 '12 at 20:37
  • Yes, you are right. The fraction is $\frac{c}{2}$. As I said in the post, the norm is an arbitrary norm, not necessarily $\ell_2$. So the norm is not necessarily induced by the inner product. – mining Oct 02 '12 at 21:31
  • Using each of the definitions you can write a lower bound for $\alpha f\left(x\right)+\left(1-\alpha\right)f\left(x'\right)-f\left(\alpha x+\left(1-\alpha\right)x'\right)$. To have the equivalence, I think these lower bounds must be identical. If you set $\alpha=\frac{1}{2}$ in the mentioned equation you get the parallelogram law, which implies that your space is equipped with an inner-product. Check if there's something assumed about the domain of $f$ like being a Hilbert space or an inner-product space. – S.B. Oct 02 '12 at 23:45
  • The domain of $f$ is just linear space. No Hilbert space structure assumed. – mining Oct 03 '12 at 02:55

5 Answers5

3

I think you need to say that the space is an inner product space, in which case the equivalence can fairly easily be obtained. You can find the proof here.

Glorfindel
  • 3,955
Alvaro Maggiar
  • 1,028
1

The proof of the equivalence can be found on Page 565, Book "Variational Analysis" by Rocafellar & Wets.

user286430
  • 11
  • 1
1

It seems (1) and (2) are equivalent if the norm is $\ell_2$ norm. Otherwise, they are not guaranteed to be the same.

mining
  • 1,075
1

It is known that the equivalence (1)$\iff$ (2) characterizes inner product spaces. Namely, a parallelogram law holds iff a norm is strongly convex with modulus 1.

szw1710
  • 8,102
1

It is easy to prove if you write out (2) based on the definition of convex function. Then what you need to know is that f(.) is convex and the norm is convex. Here any norm is ok, because of any norm is convex. Then the problem is proved.

E.J.
  • 939