1

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?

stoic-santiago
  • 13,705
XYZ
  • 35
  • Have you tried to apply the definition of distance and of the set to that particular case? – Patricio Mar 23 '21 at 13:38
  • I don't understand how to apply the distance. – XYZ Mar 23 '21 at 13:39
  • You are taking the distance to the set to be the smallest of the distances between the point and each of the elements of the set. The distance to $S$ is smaller than the distance to $T$ for any point such that $x\leq-\frac{1}{2}$ or $x\geq\frac{1}{2}$. Make a small graphic representation and it will be apparent to you. – Patricio Mar 23 '21 at 13:45
  • Thank you but the solution is still not clear to me. I don't understand how to apply the distance function. – XYZ Mar 23 '21 at 13:54

1 Answers1

1

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

Patricio
  • 1,604