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