# Prove convexity of set with triangular inequality

This question is about proving the convexity of a set using triangular inequality. However, I'm missing something as I can't wrap it up. The task is to prove that the set below is convex where $$\|\cdot\|_2$$ denotes the two-norm

$$M = \{x | \quad \|x-x_0\|_2 \leq \|x-y\|_2 \quad\forall y \in S \}$$

What I've done is start with two points $$x_1$$, $$x_2$$ $$\in M$$. Using the triangle inequality, I tried to prove that all points between these arbitrary points are contained within the set as shown below

\begin{align} \|\theta x_1 + (1- \theta)x_2-x_0\|_2 &= \|\theta ( x_1 - x_0) + (1- \theta)(x_2-x_0)\|_2 \\ &\leq \theta \|x_1-x_0\|_2 + (1- \theta) \|x_2 -x_0\|_2 \\ &\leq \theta \|x_1 -y\|_2 + (1-\theta) \|x_2 -y\|_2 \quad \forall y \in S \end{align}

However, the problem is I don't think that I'm allowed to use the triangle inequality on the equation at the far right-hand side, because I cannot guarantee that it's necessarily true as the right-hand side might not be bigger than the left-hand side anymore (as can be seen below)

$$\|\theta x_1 + (1- \theta)x_2-x_0\|_2 \leq \|\theta x_1 + (1-\theta) x_2 -y\|_2 \quad \forall y \in S$$

However, the solution makes sense in the manner that any point on the line between $$x_1$$ and $$x_2$$ (call it $$x_i$$) is upper bounded by itself as shown in the equation below. Which is exactly what I want to prove but I'm afraid I've jumped to an invalid conclusion.

$$M = \{x| \quad \|x_i-x_0\|_2 \leq \|x_i-y\|_2 \quad \forall y \in S \}$$

Can anyone give me a peak?

EDIT below to clarify: The question is in short:

I've proven that the below statement holds. But that doesn't prove the set is convex as far as i know since the upper bound is not equal to $$\|x-y\|_2$$ \begin{align} \|\theta x_1 + (1- \theta)x_2-x_0\|_2 \leq \theta \|x_1 -y\|_2 + (1-\theta) \|x_2 -y\|_2 \quad \forall y \in S \end{align}

However, if I simplify the equations right-hand side with triangular inequality I get the equation below which makes sense but I'm not sure that it's correct. Because triangle inequality states that $$\|A+B\| \leq \|A\| + \|B\|$$. Which means that I'm not sure if I can guarantee that the below statement holds. So my question is in short: Can I use triangular inequality on the right-hand side of the equation above to gain the equation below and still be sure that the equality holds?

$$\|\theta x_1 + (1- \theta)x_2-x_0\|_2\; (\leq)? \; \|\theta x_1 + (1-\theta) x_2 -y\|_2 \quad \forall y \in S$$

• I've made some edits and done some typesetting for readability. I hope this is OK. Also, I'm not sure what/where the issue is? Are you asking whether $$x_{1}, x_{2} \in M \implies \theta \| x_{1}-x_{0}\|_{2} + (1-\theta)\|x_{2}-x_{0}\|_{2} \le \theta \| x_{1}-y\|_{2} + (1-\theta)\|x_{2}-y\|_{2}$$ ? – Mattos Feb 22 at 14:00
• The equation you have written i'm quite confident that it's true. However i'm not sure if the further simplifications are valid. I updated the question with a short summary at the end to clarify what i'm asking – Pontus S Feb 22 at 14:17
• @PontusS the further step that you are talking about is not valid, you have to prove this in a different way. – TenaliRaman Feb 22 at 14:18
• I suspected this although i've no clue as to what method i should use. The equation that @Mattos stated above doesn't seem to prove that the points between $x_1$ and $x_2$ are contained within the set. I might be wrong though as my skills are quite bad in this subject – Pontus S Feb 22 at 14:21
• @SujitBhattacharyya seems reasonable, but i'm not sure as to what mathematical simplifications i can make in order to prove this. $x_{1}, x_{2} \in M \implies \theta \| x_{1}-x_{0}\|_{2} + (1-\theta)\|x_{2}-x_{0}\|_{2} \le \theta \| x_{1}-y\|_{2} + (1-\theta)\|x_{2}-y\|_{2}$ $\forall y \in S$, $S \subseteq \mathbb{R}^n$ Does this equation alone prove that it's singleton? – Pontus S Feb 22 at 14:41

$$M = \cap_{y \in S} M_y$$ where, $$M_y = \{x|\quad \|x - x_0\|_2 \leq \|x - y\|_2 \quad\}$$

We can try to show that $$M_y$$ is convex. Now, $$\|x - x_0\|_2 \leq \|x - y\|_2 \\ \Rightarrow \|x - x_0\|_2^2 \leq \|x - y\|_2^2 \\ \Rightarrow \|x\|_2^2 + \|x_0\|_2^2 - 2x_0^{\top}x \leq \|x\|_2^2 + \|y\|_2^2 - 2y^{\top}x \\ \Rightarrow (y - x_0)^{\top}x \leq \frac{1}{2} \left( \|y\|_2^2 - \|x_0\|_2^2 \right)$$

So, $$M_y$$ is a Half Space, which is a convex set (which is fairly easy to show as well).

Finally, $$M$$ is the intersection of convex sets which is also convex.

Isn't $$M$$ simply the set of points closer to $$x_0$$ than any other point, thus $$M=\{x_0\}$$. Specifically if you pick $$y=x$$, then the inequality is satisfied only for $$x=x_0$$.

Needless to say the singleton set is convex.

• The question seems to be $M$ is the set of points closer to the point $x_0$ than aa given set $S$. (I see i wrote wrong in the question now it's $y \in S$ and not $y \in \mathbb{R}^n$. Nedless of the intuitive explanation i'm looking for a mathematical way to prove that fact by using triangle inequality. – Pontus S Feb 22 at 14:28
• @PontusS Is $S$ arbitrary? I think that if it is not convex this is not true. – lightxbulb Feb 22 at 14:28
• yes $S \subseteq \mathbb{R}^n$ – Pontus S Feb 22 at 14:30
• Makes perfect sense, although it would be satisfying to know what could be done with the mentioned equations in order to prove this. But i'm happy with this explanation. Thanks! – Pontus S Feb 22 at 14:48
• @PontusS It is correct. I got to the part where I need to prove that if $z$ is a convex linear combination of $x_1, x_2$ then the ball with center $z$ and radius $d(z-x_0)$ is a subset of the union of the balls with centers $x_1, x_2$ and radii $d(x_1 - x_0), d(x_2-x_0)$. I can't say whether this statement is correct right off the bat. But if you can prove this, then the proof for convexity of $M$ is straightforward. The proof in the accepted answer is a lot more elegant though. – lightxbulb Feb 22 at 15:45