4

Show $f(x)=\|x\|^2 = x^Tx$ is strictly convex by proving:

For distinct $x,y \in \mathbb{R}$ and $0<\lambda <1$, $f(\lambda x+(1-\lambda) y) < \lambda f(x)+(1-\lambda)f(y)$

I have tried to expand and simplify both sides (taking up a full page each try) but I am having trouble exactly relating the two. It would be too much to show all my work here but I will show the point that I have gotten to.

\begin{align} \text{LHS:} \quad & \lambda^2\sum_{i=1}^n x_i^2+(1-\lambda)^2\sum_{i=1}^n y_i^2 +2\lambda(1-\lambda)\sum_{i=1}^n x_iy_i \\[10pt] \text{RHS:} \quad & \lambda\sum_{i=1}^n x_i^2+(1-\lambda)\sum_{i=1}^n y_i^2 \end{align}

I think I have to use the fact that $\lambda^2<\lambda$ so I have that $$\lambda^2\sum_{i=1}^n x_i^2+(1-\lambda)^2\sum_{i=1}^n y_i^2 < \lambda\sum_{i=1}^n x_i^2+(1-\lambda)\sum_{i=1}^n y_i^2$$

But how can I show that the difference between the two sides of the inequality is greater than $2\lambda(1-\lambda)\sum_{i=1}^n x_iy_i$

Rodrigo de Azevedo
  • 1
mhlzzz
  • 343
  • 1
    $\frac{d^2(x^Tx)}{dx^Tdx}=2I>0$ – MAN-MADE Jul 22 '17 at 18:55
  • 1
    Along any line, $|x|^2$ is just a quadratic of the parameter (here $\lambda$) – Hagen von Eitzen Jul 22 '17 at 19:46
  • If the typographical difference between $||u||$ and $|u|$ is not conspicuous enough to you, look at the difference between $||u|| ||v||,$ coded as ||u|| ||v||, and $|u||v|,$ coded as |u||v|. The second form is the one intended by the creators of this software. I edited accordingly. So far all three who have posted answers have made the same mistake. – Michael Hardy Jul 22 '17 at 20:58
  • To make "MANMAID" 's comment a bit more legible: $\displaystyle \frac{\partial^2 (x^T x)}{\partial x^T,\partial x} = 2I>0. \qquad$ – Michael Hardy Jul 22 '17 at 21:00

3 Answers3

4

Suppose $\|x\|\neq \|y\|$

$$\lambda (1-\lambda)(\|x\|-\|y\|)^2>0\\\Rightarrow \lambda (1-\lambda)\|x\|^2+\lambda (1-\lambda)\|y\|^2-2\lambda (1-\lambda)\|x\|\|y\|>0\\\Rightarrow [\lambda-\lambda^2]\|x\|^2+[(1-\lambda)-(1-\lambda)^2]\|y\|^2-2\lambda (1-\lambda)\|x\|\|y\|>0\\\Rightarrow \lambda^2\|x\|^2+(1-\lambda)^2\|y\|^2+2\lambda (1-\lambda)\|x\|\|y\|<\lambda\|x\|^2+(1-\lambda)\|y\|^2\\\Rightarrow [\lambda\|x\|+(1-\lambda)\|y\|]^2<\lambda\|x\|^2+(1-\lambda)\|y\|^2$$

By Triangle inequality $$\|\lambda x+(1-\lambda) y\|\leq\lambda\|x\|+(1-\lambda)\|y\|$$

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

Then $\|x\|^2$ is strictly convex. $\blacksquare$

MAN-MADE
  • 5,381
  • 2
    Why may we assume that $|x|\neq |y|$ when it is only given that $x\neq y$? Would the condition $x\neq y$ not imply convexity instead of strict convexity? – Student W Sep 15 '20 at 13:43
  • The origin of the first inequality (with the given scalar multiplication $\lambda (1 - \lambda)$) is somewhat not intuitive. The solution in https://math.stackexchange.com/questions/1902967/strict-convexity-of-squared-euclidean-norm essentially works in the reverse order and with the Cauchy-Schwartz inequality one can find the origin that is written here. – sunspots Mar 01 '24 at 20:45
2

You can use your working to show that \begin{align} & \lambda f(x) + (1-\lambda) f(y) - f(\lambda x + (1-\lambda)y) \\[10pt] = {} & (\lambda-\lambda^2) x^Tx + ((1-\lambda)-(1-\lambda)^2) y^T y - 2\lambda(1-\lambda) x^T y \\[10pt] = {} & \lambda(1-\lambda) (x-y)^T(x-y) = \lambda(1-\lambda) f(x-y) > 0 \end{align} if $x \neq y$ and $0<\lambda<1$. (This identity actually holds for any quadratic form.)

Johannes
  • 3
Chappers
  • 67,606
  • The case ||y|| = ||x|| should imply y = tx, for some t >0 Also, is this result valid for the squared norm of a function, i.e. ||f(x||^2 is strictly convex ? – Hass Saidane Aug 07 '21 at 17:56
1

$f(x) =\|x\|^2$ then $f''(x)=2I$ which is positive definite.

If you want use definition , you first compute

$$\text{RHS} - \text{LHS}$$

And don't use that fact you mentioned.

Michael Hardy
  • 1
Red shoes
  • 6,948