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

  • 1
    $\begingroup$ The expression $\|x_0-y\|^T x$ does not make sense, because $\|x_0-y\|$ is a scalar. $\endgroup$ – littleO Feb 8 '17 at 3:01
  • $\begingroup$ @littleO I modified it, thanks for comment. but I'm kinda curious to know why $(x_0-y)^Tx\geq 0$. $\endgroup$ – Parisina Feb 8 '17 at 3:30
  • 1
    $\begingroup$ 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. $\endgroup$ – littleO Feb 8 '17 at 3:48
  • $\begingroup$ @littleO Yes, you're right. I changed the set and in this case, I guess it's not a ball anymore. $\endgroup$ – 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$.

Original answer:

For a given value of $y$, $\{ x: \| x-x_0\|_2 \leq \|y-x_0\|_2\}$ is a ball, hence it is convex.

Your set is an intersection of convex sets, so it is convex. No need to think about half spaces.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.