Prove that the Euclidean distance between two vectors is convex

Question

So the question in hand is : Prove that $ f(\mathbf{x}) = \Vert \mathbf{x – b} \Vert_{2}$ is convex. While I know we can use the triangle inequality to prove the convexity of the euclidean norm. Im having trouble with this function since $\mathbf{b}$ is constant. What I tried is $\Vert \lambda \mathbf{x} + (1-\lambda)\mathbf{y} – \mathbf{b}\Vert_{2} \leq \Vert \lambda\mathbf{x}\Vert_{2} +\Vert (1-\lambda)\mathbf{y} – \mathbf{b}\Vert_{2}$ but Im stuck here since I don't know how to deal with $\mathbf{b}$ here.

Thanks

Answer 1

I think that you set up your convexity equation a little wrong.

The original definition for convexity is: $f(\lambda x+(1-\lambda)y)\leq \lambda f(x) + (1-\lambda)f(y)$.

If we use that on this equation, we get that you need to show

$\lVert (\lambda x+(1-\lambda)y)-b\rVert_2 \leq \lambda\lVert x-b\rVert_2 +(1-\lambda)\lVert y-b\rVert_2$

I have put the core steps to the proof below in case you still need help after this, but I went ahead and put them in spoiler blocks so you could try it yourself without more help if you preferred that.

First you can break the $b$ up into $\lambda \dot b$ and $(1-\lambda)\dot b$

Then pair up the b's with the x and y so that you have $\lVert \lambda (x-b)+(1-\lambda)(y-b)\rVert_2$

Now apply triangle inequality and the linearity of the norm and you're done.