Strict convexity of the norm

89 Views Asked by At

I'm trying to prove that Strong convexity $\Rightarrow$ strict convexity. So, given $g(x) := f(x) - \alpha\|x\|^2$ I need to verify the definition:

$$g(\lambda x + (1-\lambda)y) <\lambda g(x) + (1-\lambda)g(y).$$

So this is

$$f(\lambda x + (1-\lambda)y) -\alpha\|\lambda x + (1-\lambda)y\|^2 < \lambda f(x) + (1-\lambda)f(y) -\alpha\|\lambda x + (1-\lambda)y\|^2$$

So the first part is OK because $f$ is a convex function by definition. All I need to do now is to prove that $\|x\|^2$ is a strict convex function But in general

$$\|\lambda x + (1-\lambda)y\|^2 \le ( \lambda \|x \| + (1-\lambda)\|y\|)^2$$

But the right hand side should be $< \lambda \|x\|^2 + (1-\lambda)\|y\|^2$ and this does not hold here....

1

There are 1 best solutions below

0
On BEST ANSWER

To prove strict convexity of the squared norm you need to show that $\|\lambda \mathbf{x} + (1-\lambda)\mathbf{y}\|^2 < \lambda \|\mathbf{x} \|^2 + (1-\lambda)\|\mathbf{y}\|^2$. I believe this is the part that caused your confusion.

Now, rearranging the inequality above gives: $$-(\lambda(1-\lambda)\|\mathbf{x} \|^2+\lambda(1-\lambda)\|\mathbf{y} \|^2-2\lambda(1-\lambda)\mathbf{x}^T\mathbf{y})<0.$$ Last arrangement gives us $$-\lambda(1-\lambda)\|\mathbf{x-y} \|^2<0$$

which clearly holds since $0<\lambda<1$ and $\mathbf{x}\neq\mathbf{y}$.