# Showing a set is convex

I'm stuck on showing that the following set is convex.

$$\{x:\|x-x_0\|_2\leq \|x-y\|_2 \text{ for all } y\in S\},$$ where $S\subset \mathbb{R}^n$.

$\|x-x_0\|_2\leq \|x-y\|_2$ implies $(x_0-y)^Tx\geq 0$, which a half-space. Therefore, this set is equivalent to the intersection of half-spaces: $$\bigcap_{y\in S}\{x:(x_0-y)^Tx\geq 0\}.$$

It's not clear to me why $\|x-x_0\|_2\leq \|x-y\|_2$ implies $(x_0-y)^Tx\geq 0$.

As $\|x-x_0\|_2\leq \|x-y\|_2$, we get $(x-x_0)^T(x-x_0)\leq (x-y)^T(x-y)$. Hence, $$x^Tx-x^Tx_0-x_0^Tx+x_0^Tx_0\leq x^Tx-x^Ty-y^Tx+y^Ty$$ I guess I'm allowed to say that $x^Tx_0=x_0^Tx$. Therefore, $$x^T_0x_0\leq 2x^T(x_0-y)+y^Ty$$

But I don't know how I can prove $(x_0-y)^Tx\geq 0$.

• The expression $\|x_0-y\|^T x$ does not make sense, because $\|x_0-y\|$ is a scalar. – littleO Feb 8 '17 at 3:01
• @littleO I modified it, thanks for comment. but I'm kinda curious to know why $(x_0-y)^Tx\geq 0$. – Parisina Feb 8 '17 at 3:30
• How is the inequality $\|x-x_0\|_2 \leq \|x-y\|_2$ relevant to the set that you introduced? This is not the inequality that appears in the definition of your set. – littleO Feb 8 '17 at 3:48
• @littleO Yes, you're right. I changed the set and in this case, I guess it's not a ball anymore. – Parisina Feb 8 '17 at 16:34

Edit: Now that the question has been revised to ask about a different set, I'll give a different answer. Note that for a given vector $y$, \begin{align} & \| x - x_0 \|_2 \leq \| x - y \|_2 \\ \iff & \| x - x_0 \|_2^2 \leq \| x - y \|_2^2 \\ \iff & \| x \|_2^2 - 2 \langle x, x_0 \rangle + \| x_0 \|_2^2 \leq \| x \|_2^2 - 2 \langle x, y \rangle + \| y \|_2^2 \\ \iff & \langle x, 2(y - x_0) \rangle \leq \| y \|_2^2 - \|x_0 \|_2^2. \end{align} This shows that your set is an intersection of half spaces, so it's convex.
This agrees with the work you showed, which is correct. The only incorrect thing is the statement that $\| x - x_0 \|_2 \leq \| x - y \|_2$ implies $\langle x_0 - y, x \rangle \geq 0$.
For a given value of $y$, $\{ x: \| x-x_0\|_2 \leq \|y-x_0\|_2\}$ is a ball, hence it is convex.