Why is the Euclidian norm convex, if the square root function is concave?

Question

I have some trouble figuring out if the Euclidean norm is convex.

$\left\|{\boldsymbol {x}}\right\|:={\sqrt {{\boldsymbol {x}}\cdot {\boldsymbol {x}}}}$

On one side I read that all norms are convex (page 5) and that by definition a vector norm is convex.

On the other side, I read that the square root function is concave.

Is $\sqrt{x}$ concave?

How is it possible?

Answer 1

A vector norm (in $\mathbb{R}^n$) is just a function $f:\mathbb{R}^n\to\mathbb{R}$ satisfying certain properties. If you put the positive homogeneity property together with the triangle inequality you get convexity of $f$:

Let $\alpha\in[0,1]$, and $x,y\in\mathbb{R}^n$. Then

$$f(\alpha x+(1-\alpha)y)\leq f(\alpha x)+f((1-\alpha)y)=\alpha f(x)+(1-\alpha)f(y)$$ where the inequality is from the triangle inequality, and the equality is from positive homogeneity.

---

For the case where $f(x)=\sqrt{x\cdot x}$ positive homogeneity holds because for any $\alpha\geq 0$ and $x\in\mathbb{R}^n$:

$$f(\alpha x)=\sqrt{(\alpha x)\cdot(\alpha x)}=\sqrt{\alpha^2(x\cdot x)}=\alpha\sqrt{x\cdot x}=\alpha f(x)$$

The square root "cancels" the square on the scalar $\alpha$ that was produced when taking the dot product.

Answer 2

This is because of Cauchy-Schwarz'inequality.

Indeed, you have to prove, for any $0\le\lambda, \mu\le1 $, $\lambda+\mu=1$, that
$$\lVert\lambda a +\mu b\rVert\le \lambda\lVert a\rVert + \mu\lVert b\rVert $$ which is equivalent to \begin{align*} \lVert\lambda a +\mu b\rVert^2=\lambda^2\lVert a\rVert^2+\mu^2\lVert b\rVert^2 +2\lambda\mu\langle a,b\rangle &\le\lambda^2\lVert a\rVert^2+\mu^2\lVert b\rVert^2 +2\lambda\mu\lVert a\rVert\lVert b\rVert\\[1ex] \iff\langle a,b\rangle & \le\lVert a\rVert\lVert b\rVert. \end{align*}