19
$\begingroup$

Question 2.23 out of Boyd & Vanderberghe's Convex Optimization:

Give an example of two closed convex sets that are disjoint but cannot be strictly separated.

The obvious idea is to take something like unbounded sets which are disjoint but approach each other in the limit. For example, $f(x) = \frac1x$ and $g(x) = -\frac1x$. But isn't $x=0$ a strictly separating hyperplane here?

$\endgroup$

4 Answers 4

16
$\begingroup$

Take $X = \{(x,y) \mid xy\geq 1, x,y>0\}$ and $Y = \{(x,y) \mid x\leq 0\}$.

$\endgroup$
0
9
$\begingroup$

To say that two convex sets $C$ and $D$ in $\mathbb{R}^n$ can be separated by a hyperplane $\mathcal{H}$ is to say that there is a linear functional $f$ on $\mathbb{R}^n$ such that $\mbox{sup} \{f\left(x\right)\: : \: x\in C\} \leq \mbox{inf} \{f\left(x\right)\: : \: x \in D\}$. $\mathcal{H}$ will then be the hyperplane $\{x \in \mathbb{R}^n \: : \: f\left(x\right) = c\}$, which is a coset of the kernel of $f$.

We say that $C$ and $D$ can be strictly separated if a linear functional $f$ can be chosen so that the above inequality is strict. Your intuition about what sorts of closed convex sets can be separated but not strictly separated is correct. This can happen when $C$ and $D$ are not compact and approach arbitrarily close to each other without meeting. So if you let $C$ be the points in $\mathbb{R}^2$ such that $y \geq \frac{1}{x}$ with $x > 0$ and $D$ be the points such that $y \leq -\frac{1}{x}$ with $x > 0$, then $C$ and $D$ are separated by the functional that projects onto the $y$ axis, but they are not strictly separated by this functional.

Noah's answer gives another good example. joriki's answer clears up a lot of things, and the paper he links to is a good introduction to this topic.

$\endgroup$
1
  • 3
    $\begingroup$ This answer uses a different definition of strict separation than the one in Boyd and Vanderberghe; they use the same one as H. Potter below. $\endgroup$
    – Max
    Nov 10, 2016 at 18:16
5
$\begingroup$

Some comments on the question and Albert Steppi's answer (written as an answer because they're too long for a comment):

  • You both seem to have ignored the "convex" part of the question. What you need is not the graphs of these functions but the sets they bound. Also you need to select one of the two branches of each of $1/x$ and $-1/x$ in order to get a convex set.
  • BoB, I think where your otherwise correct ideas went wrong is that you considered the inequality between the values of the functional instead of the inequality between their infimum and supremum.
  • This paper has more on the topic.
$\endgroup$
2
  • $\begingroup$ Hmm -- Albert Steppi's answer that I referred to here has been deleted. Noah Stein's answer correctly defines convex sets -- in fact his example is the same as the one in the paper I linked to. Note, however, that BoB's original idea was also correct; you don't need to have the separating line as one of the boundaries, since the inequality has to be strict between the infimum and the supremum and not just between the individual values of the functional. $\endgroup$
    – joriki
    Mar 11, 2011 at 23:23
  • $\begingroup$ I noticed that my answer was bogus pretty quick, but I guess not quick enough. From now on I'll make sure not to post when I am short on sleep. $\endgroup$ Mar 12, 2011 at 0:24
5
$\begingroup$

I'll just add that, for a slightly different definition of convex sets being "strictly separated", the example given by Albert Seppi doesn't work. (My definition is that $C$ and $D$ convex sets in $\mathbb{R}^n$ are strictly separated if there is a hyperplane $a^Tx=\beta$ such that $a^Ty<\beta$ for all $y\in C$ and $a^Ty>\beta$ for all $y\in D$)

In the latter case, $x=0$ separates strictly $\{(x,y)\mid y\geq \frac1x, x>0\}$ and $\{(x,y)\mid y\leq -\frac1x, x>0\}$.

However, it is impossible to separate the sets $\{(x,y)\mid y\geq \frac1x, x>0\}$ and $\{(x,y)\mid y\leq0\}$ because any line of slope non-zero will intersect the second set, so such a line must be of the form $(1\mbox{ } 0)^Tx=\beta$ for some $\beta$. But if $\beta\leq0$, it intersects the second set whereas $\beta >0$ implies that the line will intersect the first set.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .