2

In Exercise 2.12 (e) on Stephen Boyd & Lieven Vandenberghe's Convex Optimization:

The set of points closer to one set than another, i.e., $$\big\{x \mid \text{dist}(x, S)\leqslant\text{dist}(x,T)\big\}$$ where $\,S,T\subseteq\mathbb R^n$, and $\text{ dist}(x, S) = \text{inf}\big\{\lVert x-z\rVert\;|\;z\in S\big\}$

Why is the set not convex? Since I can turn the set into a halfspace.

Although I know, there is an example that the authors provided, in the solution manual to show it's not a convex set. However, they used the exact same method to turn the set into a half space in Exercise 2.12 (d) and the set is instead convex.

Rodrigo de Azevedo
  • 1
big_djas
  • 21
  • You seem to think that all half-spaces are convex sets. That’s not true. – bubba Oct 23 '22 at 10:57
  • I don't have the book at hand, but it seems to me that, depending on the sets $S,T$, the set of the points "closer" to $S$ than to $T$ may or may not be convex. If $S,R$ are both single-element sets, it is convex (half-plane). If $S$ is a line and $T$ is a point, it is not convex (the "exterior" of a parabola). Maybe the author wants to show that it is undecided one way or another without additional conditions? Maybe they want to introduce additional conditions which will imply convexity or non-convexity? –  Oct 23 '22 at 11:01
  • @StinkingBishop Okay. So, is actually quite dependent on the forms of S and T (like a unit circle, PSD cone, a line, a point, ....) – big_djas Oct 23 '22 at 11:05
  • @bubba do you have an example? like two halfspaces but give x < -1 or x > 1? – big_djas Oct 23 '22 at 11:13
  • Found the book at https://web.stanford.edu/~boyd/cvxbook/, although still don't know where to find the answer key. Anyways, for (d) the answer is "yes, it is convex" as it is an intersection of half-spaces. For (e) the answer is "it depends" (on S and T), and to prove it depends you need to show at least one example where it's convex and at least one where it isn't. –  Oct 23 '22 at 11:17
  • Indeed @bubba in $\mathbb R^n$ all half-spaces are convex, unless you assume some unusual definition of a "half-space". If the latter, can you please be clearer in what you assume? –  Oct 23 '22 at 11:22
  • Let us continue this discussion in chat. – big_djas Oct 23 '22 at 11:29
  • Listed – Rodrigo de Azevedo Oct 23 '22 at 11:30
  • My definition of half-space is a set of the form ${x \in \mathbb R^n : f(x) \le 0}$, where $f: \mathbb R^n \to \mathbb R$ is some function. What’s yours? – bubba Oct 24 '22 at 13:15

1 Answers1

1

As a counter-example, consider S as points on the unit circle and T as the origin. The set of points closer to the circle has a hole around the origin.

mikado
  • 141
  • That's a good example. But how do you, in general, prove whether a set is a convex set? I know there are 1) definition of convexity, 2) intersection to any line, and 3) operation preserving convexity. But sometimes, to me, the approach is not obvious. – big_djas Oct 23 '22 at 11:01