Strong separating hyperplane - check proof

130 Views Asked by At

Let $S,T \subset \mathbb R^n$ be non empty convex sets.

We say that the hyperplane $H: a^Tx = b$ strongly separates $S,T$ if $\exists \epsilon$ such that $S + \epsilon B_0(1) \subset \{x \in \mathbb R^n: a^Tx > b\}$ and $T+\epsilon B_0(1) \subset \{x \in \mathbb R^n :a^Tx < b\}$

Where $B_0(1) = \{x \in \mathbb R^n: |x| \leq 1\}$ is the unit ball centered at zero.

We are asked to show that if $T,S$ can be strongly separated, then $0 \notin \text{cl}(S-T)$, or in other words, $\text{inf}_{t \in T, s \in S}\|t-s\| > 0$

Here's what I tried.

Suppose that $\text{inf}_{t \in T, s \in S}\|t-s\| = 0$ and that there's a strong separation. Then there are two sequences $\{t_k\} \subset T, \{s_k\} \subset S$ that converge to the same limit, $t_k \to v, s_k \to v$.

Let $\epsilon$ be the epsilon from the strong separation. Then there's a number $N$ such that $\|t_k - v\| < \frac{\epsilon}{4}, \| s_k - v\| < \frac{\epsilon}{4}$ for all $k > N$. Let $t_l, s_l$ be such vectors.

It follows that $\epsilon B_{t_l}(1) \bigcap \epsilon B_{s_l}(1) \neq \emptyset$, and so $T + \epsilon B_{0}(1) \bigcap S + \epsilon B_{0}(1) \neq \emptyset$

It's impossible for an element $x$ in the intersection to be both $a^Tx > b$ and $a^Tx < b$, hence we arrive at a contradiction.

Is this solution correct?

1

There are 1 best solutions below

2
On BEST ANSWER

There's a flaw in your assumption that the sequences $\ \left\{t_k\right\}\ $ and $\ \left\{s_k\right\}\ $ converge. It's possible that $\ 0\in\text{cl}(S-T)\ $, without any such convergent sequences existing. Let $\ S=\left\{(x,y)\in\mathbb{R}^2\left|y\ge e^x\right.\right\}\ $, $\ T=\left\{(x,y)\in\mathbb{R}^2\left|y\le -e^x\right.\right\}\ $, for instance. Then $\ S-T= $$\left\{(x,y)\in\mathbb{R}^2\left|y>0\right.\right\}\ $, and $\ (0,0)\in\text{cl}(S-T)\ $, but the only sequences $\ \left\{t_k\right\}\subset T\ $, $\ \left\{s_k\right\}\subset S\ $ for which $\ \lim_\limits{k\rightarrow\infty}\left\|s_k-t_k\right\|=0\ $ have $x$-coordinates that diverge to $\ -\infty\ $. While such unbounded pairs of convex sets like this aren't strongly separated, your proof fails to account for them.

Nevertheless, I think you can easily modify your proof to avoid the assumption that $\ \left\{t_k\right\}\ $ and $\ \left\{s_k\right\}\ $ converge. All you really need to use is that $\ s_k-t_k \rightarrow0\ $.