TITLE: Why is every $p$-norm convex?
QUESTION [29 upvotes]: I know that $p$-norm of $x\in\Bbb{R}^n$ is defined as, for all $p\ge1$,$$\Vert{x}\Vert_p=\left(\sum_{i=1}^{n} \vert{x_i}\vert^p\right)^{1/p}.$$
The textbook refers to "Every norm is convex" for an example of convex functions.
I failed to prove $f(x)=\Vert{x}\Vert_p$ for all $p\ge1$, then tried to find the proof on the internet but I cannot find it.
Can someone let me understand why $p$-norm is convex for all $p\ge1$.

REPLY [54 votes]: The Definition of a norm is:
Be V a Vectorspace, $\|\cdot\|: V \rightarrow \mathbb{R} $ is a norm $:\iff $

$\forall v \in V: \|v\|\ge0$ and $\|v\| =0 \iff v=0$ (positive/definite)
$\forall v\in V, \lambda\in \mathbb{R}: |\lambda|\|v\| =\|\lambda v\|$ (absolutely scaleable)
$\forall v,w\in V : \|v+w\| \le \|v\|+\|w\|$ (Triangle inequality)

The Definition of convex is:
$f:V\rightarrow\mathbb{R}$ is convex $:\iff$
$\forall  v,w \in V, \lambda \in [0,1]: f(\lambda v+(1-\lambda )w)\le \lambda f(v) +(1-\lambda)f(w)$
So using the Triangle inequality and the fact that the norm is absolutely scalable, you can see that every Norm is convex:
$$\|\lambda v+(1-\lambda )w\|\le\|\lambda v\|+\|(1-\lambda)w\| = \lambda\|v\|+(1- \lambda)\|w\|$$
So by definition every norm is convex. What is left to show is, that the p-norm is in fact a norm. The first two requirements are pretty easy to show, the third is hard. That is why it has its own name: the Minkowski Inequality which is a result of the Hölder inequality and shows that the triangle inequality holds for every p-norm (if p>1) and thus that it is a norm.

EDIT: Since this seems to be somewhat popular, I thought I would add a sketch of the proof of the Minkowski inequality.

You show Young's Inequality: $xy\le \frac{x^p}{p}+\frac{y^q}{q}\quad \forall q,p>1 \text{ with } \frac{1}{p}+\frac{1}{q}=1,\ \forall x,y\ge 0$.

You can do that by looking at the function $f(x)=\frac{x^p}{p}+\frac{y^q}{q}-xy$ find the critical point, show it is a minimum and is greater zero (derivatives).

You show the Hölder Inequality: $\|fg\|_1 \le \|f\|_p\|g\|_q \quad \forall q,p>1 \text{ with } \frac{1}{p}+\frac{1}{q}=1$

You can do that by setting $x=\frac{|f|}{||f||_p}$ and $y=\frac{|g|}{||g||_q}$ and plug them into young's inequality.
You get
\begin{align}
&&\frac{|fg|}{\|f\|_p\|g\|_q}&\le \frac{|f|^p}{p\|f\|_p^p} + \frac{|g|^q}{q\|g\|_q^q}
\\
\Rightarrow &&\int \frac{|fg|}{\|f\|_p\|g\|_q} d\mu &\le \int \frac{|f|^p}{p\|f\|_p^p}d\mu + \int \frac{|g|^q}{q\|g\|_q^q}d\mu
\\
\Rightarrow &&\frac{\|fg\|_1}{\|f\|_p\|g\|_q}&\le \frac{1}{p}+\frac{1}{q}=1
\end{align}
It works just the same for sequences or $\mathbb{R}^n$, you just use young's inequality for every index and then sum over it instead of using the integral.

And last the Minkowski Inequality: $\|x+y\|_p\le\|x\|_p+\|y\|_p \quad \forall p>1$

Set $q=\frac{p}{p-1}$ thus $q(p-1)=p$ and $\frac{1}{p}+\frac{1}{q}=1$. Then:
\begin{align}
\|x+y\|_p^p&=\int |x+y|^pd\mu\le\int |x+y|^{p-1}|x|d\mu+ \int |x+y|^{p-1}|y|d\mu
\\
&\le \left(\int|x+y|^{q(p-1)}d\mu\right)^{1/q}\left(\int|x|^pd\mu\right)^{1/p} + \left(\int|x+y|^{q(p-1)}d\mu\right)^{1/q}\left(\int|y|^pd\mu\right)^{1/p}
\\
&=\left(\int|x+y|^{p}d\mu\right)^{\frac{1}{p}\frac{p}{q}}(\|x\|_p+\|y\|_p)
=\|x+y\|_p^{p/q}(\|x\|_p+\|y\|_p)
\end{align}
If you realize that $p-\frac{p}{q}=p(1-\frac{1}{q})=1$ you are done.
{"set_name": "stack_exchange", "score": 29, "question_id": 2280341}