I need to prove that the square of the Euclidean norm is convex, so:
$||\theta x+(1-\theta)y||^2\leq\theta||x||^2+(1-\theta)||y||^2$.
Can I use the triangular inequality (if yes, how?) or should I use something else?
$\begingroup$
$\endgroup$
Add a comment
|
4 Answers
$\begingroup$
$\endgroup$
0
First we show that any norm $|| \cdot ||: \mathbb{R}^n \to \mathbb{R_+}$ is a convex function:
It's clear the domain $\mathbb{R}^n$ is a convex set. Then by properties of the norm, $|| k x || =|k| || x ||$ and $||x+y|| \leq ||x|| + ||y|| $, for any $x,y \in \mathbb{R}^n$ and $0 \leq \theta \leq 1$,
$$|| \theta x + (1-\theta)y || \leq ||\theta x || + ||(1-\theta)y || = \theta || x || + (1-\theta)||y || $$
Now that $f(x)=x^2$ and $g(x)=||x||_2$ are both convex, and $f(x)=x^2$ is non-decreasing on $[0, \infty)$, the range of $g$ , therefore the composition $ f \circ g=||\cdot ||_2^2$ is convex.
$\begingroup$
$\endgroup$
6
Notice that $f(x)=x^2$ is convex ($2=f''(x)>0$.) Thus it is convex, which means that it satisfies $f\big(\theta\|x\|+(1-\theta)\|y\|\big)\leq \theta f(\|x\|)+(1-\theta)f(\|y\|)$ for $\theta\in [0, 1]$.
-
$\begingroup$ Thanks for your answer. Taking the norm $||x||^2$ is not just squaring, but $||x||^2=x_1^2+x_2^2+...$. I'm not sure if you can just simplify it like you propose. Or is it allowed if you use $\nabla$? $\endgroup$ Oct 31, 2013 at 17:51
-
$\begingroup$ Just put $a=\|x\|, b=\|y\|$ in the definition of a convex function $f(\theta a+(1-\theta)b)\leq \theta f(a)+(1-\theta)f(b)$. What do you mean by $\nabla$? $\endgroup$– daulombOct 31, 2013 at 18:34
-
$\begingroup$ With $\nabla$ I mean the partial derivative, since $x$ is a vector, you can take the derivative with respect to $n$ different variables ($x_1,...,x_n$). Then $\nabla^2$ would be the second derivative, which gives indeed 2. $\endgroup$ Nov 1, 2013 at 8:40
-
$\begingroup$ You mean what happens if the norm contains partal derivatives! The above is true for any norm. $\endgroup$– daulombNov 1, 2013 at 9:08
-
6$\begingroup$ @daulomb I don't understand this proof. so since $x^2$ is convex, $(\theta x+(1-\theta )y)^2<=\theta x^2+(1-\theta) y^2$ where $x,y\in R^2$. So can I say since ||x|| and ||y|| $\in R^2$, $(\theta ||x||+(1-\theta )||y||)^2<=\theta ||x||^2+(1-\theta) ||y||^2$. But what we have to show in order to show that $||x||^2$ is convex is, $||\theta x+(1-\theta y)||^2<=\theta ||x||^2+(1-\theta) ||y||^2$ right?. $\endgroup$– clarksonDec 25, 2015 at 6:29
$\begingroup$
$\endgroup$
0
The Hessian of the squared Euclidean norm is everywhere (edit: twice) the identity matrix, which is positive definite.
$\begingroup$
$\endgroup$
For $\theta \in (0,1)$,
\begin{align*} \theta \| x\|^2 + (1-\theta)\|y\|^2 - \|\theta x + (1-\theta) y \|^2 &= \theta \| x\|^2 + (1-\theta)\|y\|^2 - \theta^2\|x\|-(1-\theta)^2\|y\|^2 \\ & \quad -2\theta (1-\theta) \langle x | y \rangle \\ &\geq \theta(1-\theta)\|x\|^2 + \theta(1-\theta)\|y\|^2-2\theta (1-\theta)\|x\|\|y\|\\ &= \theta (1-\theta) (\|x\|^2+\|y\|^2-2\|x\|\|y\|)\\ &= \theta (1-\theta) (\|x\| - \|y\|)^2 \geq 0 \end{align*} with equality iff $x = y$ because the first equality requires $x = \alpha y$ for $\alpha \geq 0$ and the second equality requires $\|x\| = \|y\|$.
