I have a question from Boyd book -
The set of points closer to one set than another, i.e., $\{x|\text{dist}(x,S) ≤ \text{dist}(x,T)\}$, where $S,T⊆R^n$, and $\text{dist(x,S)} = \inf\{|x−z|_2|z\in S\}$.
In the solution manual of the convex optimization book, we have the solution for problem 2.12 -e.
The solution is:
In general, this set is not convex, as the following example in R shows. With $S =\{-1,1\}, T=\{0\}$.
$\{x|\text{dist}(x,S) ≤ \text{dist}(x,T)\} = \{x|x \le -0.5,x\ge 0.5\}$
which clearly is not convex.
Can someone explain the solution?
$S$ consists two points on the real line, $-1$ and $1$. $T$ is formed by just one point, $0$. If you consider point $x=3$, what is its distance to $S$? The distance between $x=3$ and $1$ is $2=|x-1|$ and the distance between $3$ and $-1$ is $4=|3-(-1)|$. You are suposed to take the smallest, so $dist(3,S)=2=\inf\{|x-1|,|x-(-1)|\}$.
If you think of $x=0.5$, you see that it is halfway between $0$ and $1$. Any $x>0.5$ will, therefore, be closer to $1$ than to $0$ and, hence, closer to $S$ than to $T$. Likewise for $x<-0.5$. The limiting cases $x=\pm 0.5$ need to be included as well, because the set must contain all points such that the distance to $T$ is at least as large as the distance to $S$.
The resulting set is not convex, because it has a gap. In order for a set to be convex you need to be able to choose any two points of it, say $x_1$ and $x_2$, and all points that lie on the straight line segment that connect them need to be elements of the set as well. Let $A=\{x|x \le -0.5,x\ge 0.5\}$. If we choose $x_1=-1$ and $x_2=1$ we see that $y=\alpha x_1+(1-\alpha)x_2$ only is an element of $A$ for some $\alpha\in\left[0,1\right]$. For instance, $y=\frac{1}{2} x_1+\left(1-\frac{1}{2}\right)x_2=0\not\in A$.