Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
    
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 2 '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 2 '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 2 '12 at 23:45
    
The domain of $f$ is just linear space. No Hilbert space structure assumed. –  mining Oct 3 '12 at 2:55
add comment

4 Answers 4

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

share|improve this answer
    
So is there a counterexample? –  AndreasS Nov 10 '12 at 19:55
add comment

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.

share|improve this answer
add comment

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.

share|improve this answer
add comment

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.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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