11
$\begingroup$

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?

$\endgroup$

4 Answers 4

15
$\begingroup$

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.

$\endgroup$
0
9
$\begingroup$

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]$.

$\endgroup$
6
  • $\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$
    – user95864
    Commented 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$
    – daulomb
    Commented Oct 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$
    – user95864
    Commented 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$
    – daulomb
    Commented Nov 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$
    – clarkson
    Commented Dec 25, 2015 at 6:29
3
$\begingroup$

The Hessian of the squared Euclidean norm is everywhere (edit: twice) the identity matrix, which is positive definite.

$\endgroup$
0
2
$\begingroup$

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\|$.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .