4
$\begingroup$

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.

  • 0
    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?2012-10-02
  • 0
    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.2012-10-02
  • 0
    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.2012-10-02
  • 0
    The domain of $f$ is just linear space. No Hilbert space structure assumed.2012-10-03

5 Answers 5

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.

1

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

  • 0
    So is there a counterexample?2012-11-10
  • 0
    For a counterexample, any convex function on the standard simplex $\Delta_n$ satisfies $(2)$ w.r.t. the $l_1$ norm, since $\|x\|_1=1\forall x\in \Delta_n$.2015-03-24
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.

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.

1

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