3

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?

Community
  • 1
Octoplus
  • 753

2 Answers2

3

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.

smcc
  • 5,694
  • Every vector norm is positive homogeneous by definition, which means every norm is a convex function (http://www.wikiwand.com/en/Convex_function) – Jae Young Lee Feb 03 '18 at 05:55
  • The first part of my answer shows this, while the second part of my answer shows that the particular function in the question is positively homogeneous. – smcc Feb 04 '18 at 09:27
  • Sounds great, as absolute homogeneity in the definition of a norm clearly indicates positive homogeneity. – Jae Young Lee Feb 05 '18 at 02:59
  • Please correct your definition of which you wrote as the first equation in your answer. It should be just $f(\alpha x+(1-\alpha )y)\leq \alpha f(x)+(1-\alpha) f(y)$ (although in this particular case both works fine but I think if we want to prove for $||\textbf{x}||^2$ then there will be problem) – Frank Moses Feb 28 '18 at 08:37
  • I used some definitions in the first part of my answer, but I do not think I provided any definitions, so I am not sure what you want me to correct. I am not sure what you are getting at, nor what you mean by "if we want to prove for $||x||^2$". (If we want to prove what? $||x||^2$ isn't a norm - it doesn't satisfy positive homogeneity). Can you please clarify? – smcc Feb 28 '18 at 15:18
0

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*}

Bernard
  • 175,478