# Is the $L^2$ norm of vectors convex?

Is the distance between two points $(x,y)$, $(a,b)$ convex? $f(x,y) = \sqrt{(x-a)^2 + (y-b)^2} + \sqrt{(x-c)^2 + (y-d)^2}$ Where $(a,b)$ & $(c,d)$ are fixed points and we want to pick $(x,y)$ that minimizes the total distance. Thanks!

• welcome to MSE, have you tried proving it? – Siong Thye Goh Aug 28 '18 at 0:47
• Thanks! I tried to prove it using the Hessian matrix but the formula gets messy when I took the derivatives... – Juan Aug 28 '18 at 3:46
• it is always encouraged to include your working on MSE when a question is posted. welcome to MSE. – Siong Thye Goh Aug 28 '18 at 3:49
• The $\ell_p$ norm is convex ior all $p \in [1,\infty]$ math.stackexchange.com/questions/2280341/… – dohmatob Aug 29 '18 at 0:35

Let $X=(x,y), \ A=(a,b).\ C=(c,d)$. Triangle inequality $||A-C||=||A-X+X-C||\le ||A-X||+||X-C||$. Equality (which is the minimum) when $X$ is in between $A$ and $C$ and on the straight line connecting $A$ and $C$.

Note: $||A-C||=\sqrt{(a-c)^2+(b-d)^2}$, etc.

• The first sentence is a little confusing. My answer was to minimize $f(x,y)$. – herb steinberg Aug 28 '18 at 1:26
• Sorry for the confusion and thanks for the answer! – Juan Aug 28 '18 at 3:46
• Yes, I was trying to minimize f(x,y) – Juan Aug 28 '18 at 3:47

First, prove that $g(x,y) = \sqrt{x^2+y^2}$ is convex.

Norms are convex because of triangle inequality, since $\lambda \in [0,1]$,

$$\left\|\lambda \begin{bmatrix}x_1\\y_1\end{bmatrix}+ (1-\lambda)\begin{bmatrix}x_2\\y_2 \end{bmatrix}\right\|\le \lambda\left\| \begin{bmatrix}x_1\\y_1\end{bmatrix}\right\|+ (1-\lambda)\left\| \begin{bmatrix}x_2\\y_2 \end{bmatrix}\right\|$$

and note that $g(x-a, y-b)$ is convex, it is just a translation.

Finally, we just have to use the fact that sum of convex functions are convex.

• Thank you so much for the answer! – Juan Aug 28 '18 at 4:04