Why is every $p$-norm convex?

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

• en.wikipedia.org/wiki/Minkowski_inequality or did you want an intuition? Anyway using the triangle inequality: $||\lambda a+(1-\lambda) b|| \le ||\lambda a|| +||(1-\lambda) b||=\lambda ||a|| +(1-\lambda)||b||$ – Felix B. May 14 '17 at 10:41
• @FelixB. Triangular inequality?? Hmm... I will try it again. Thank you. – Danny_Kim May 15 '17 at 14:43

The Definition of a norm is:

Be V a Vectorspace, $$\|\cdot\|: V \rightarrow \mathbb{R}$$ is a norm $$:\Leftrightarrow$$

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

The Definition of convex is:

$$f:V\rightarrow\mathbb{R}$$ is convex $$:\Leftrightarrow$$ $$\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 scaleable, 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.

1. 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 extremum, show it is a minimum and is greater zero (derivatives).

1. 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.

1. 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.

• This is the perfect explanation among what I have seen so far. Thank you. – Danny_Kim May 17 '17 at 4:25
• Is it correct that the : means the relation: "What is left of the : does/means what is right of the :? I derived that meaning from the function arrow description on en.wikipedia.org/wiki/List_of_mathematical_symbols, but I could not find a direct reference. – a.t. Feb 23 at 12:57
• @a.t. Yes, in $:\Leftrightarrow$ and $:=$, the colons indicate that it is a definition. The colon by itself between two statements is simply a separator and should be read as "such that". For example $\forall x\in X : f(x)=y$ "For all x in X such that f(x)=y" – Felix B. Feb 23 at 17:00