# Strong Separation Theorem

## Theorem

Let $C \subset \R^\ell$ be closed and convex.

Let $D = \set {\mathbf v} \subset C^c$.

Then $C$ and $D$ can be strongly separated.

## Proof

### Lemma 1

For any $\mathbf y \ne 0$ and any $\mathbf z \in \map {H_{\mathbf y}^<} r$, $r = \mathbf y \mathbf y$, the line segment joining $\mathbf y$ and $\mathbf z$ contains points with lengths strictly less than $\mathbf y$.

### Proof of Lemma 1

Since $\mathbf z \in \map {H_\mathbf y} r^<$:

$\mathbf z = \mathbf x - s \mathbf y$

for some $\mathbf x \perp \mathbf y$ and $s > 0$.

Let:

$\map f \gamma = \norm {\gamma \mathbf y + \paren {1 - \gamma} \mathbf z}^2$

for $\gamma \in \closedint 0 1$.

We show that:

$\map f \gamma < \norm {\mathbf y}^2$

as $\gamma \to 1$.

Expand $\map f \gamma$:

 $\ds \map f \gamma$ $=$ $\ds \norm {\gamma \, \mathbf y + \paren {1 - \gamma} \mathbf z}^2$ Definition of $\map f \gamma$ $\ds$ $=$ $\ds \paren {\gamma \, \mathbf y + \paren {1 - \gamma} \mathbf z} \cdot \paren {\gamma \mathbf y + \paren {1 - \gamma} \mathbf z}$ Definition of norm on vector space $\R^\ell$ $\ds$ $=$ $\ds \paren {\gamma \, \mathbf y + \paren {1 - \gamma} \paren {\mathbf x - s \, \mathbf y} } \cdot \paren {\gamma \, \mathbf y + \paren {1 - \gamma} \paren {\mathbf x - s \, \mathbf y} }$ as $\mathbf z = \mathbf x - s \, \mathbf y$ $\ds$ $=$ $\ds \gamma^2 \mathbf y \mathbf y + 2 \gamma \paren {1 - \gamma} \mathbf y \paren {\mathbf x - s \mathbf y} + \paren {1 - \gamma}^2 \paren {\mathbf x - s \, \mathbf y} \paren {\mathbf x - s \, \mathbf y}$ Distributive property of dot product $\ds$ $=$ $\ds \gamma^2 \mathbf y \mathbf y - 2 \gamma \paren {1 - \gamma} s \, \mathbf y \mathbf y + \paren {1 - \gamma}^2 s^2 \mathbf y \mathbf y$ Distributive property of dot product $\ds$  $\, \ds + \,$ $\ds 2 \gamma \paren {1 - \gamma} \mathbf x \mathbf y - 2 \paren {1 - \gamma}^2 s \, \mathbf x \mathbf y + \paren {1 - \gamma}^2 \mathbf x \mathbf x$ $\ds$ $=$ $\ds \mathbf y \mathbf y \paren {\gamma^2 - 2 \gamma \paren {1 - \gamma} s + \paren {1 - \gamma}^2 s^2} + \paren {1 - \gamma}^2 \mathbf x \mathbf x$ Definition of orthogonal vectors $\ds$ $=$ $\ds \mathbf y \mathbf y \paren {\gamma - s \paren {1 - \gamma} }^2 + \paren {1 - \gamma}^2 \mathbf x \mathbf x$ Binomial Theorem

Since $\map {f'} 1 = 2 \paren {1 + s} > 0$:

$\map f \gamma < \map f 1$

as $\gamma \to 1$.

Since $\map f 1 = \mathbf y \mathbf y = \norm {\mathbf y}^2$:

$\map f \gamma < \norm {\mathbf y}^2$

as $\gamma \to 1$.

$\Box$

### Proof of Theorem

Translating $C$ and $D = \set {\mathbf v}$ by $-\mathbf v$:

We show that the theorem holds for $\mathbf v = 0$.

Pick $n > 0$ such that:

$K = \map \cl {\map {B_n} {\mathbf v} } \cap C \ne \O$

Since $C$ is closed, $K$ is closed.

Since $\map {B_n} {\mathbf v}$ is bounded, $K$ is bounded.

Since $K$ is closed and bounded, $K$ is compact.

Let $\map f {\mathbf x} = \norm {\mathbf x}$.

Since $\norm {\mathbf x}^2$ and $\sqrt x: \R_+ \to \R_+$ are both continuous, $\map f {\mathbf x}$ is continuous.

Since $K$ is compact and $\map f {\mathbf x}$ is continuous, $\map f {\mathbf x}$ achieves its minimum at $\mathbf y \in C$ by the Weierstrass Theorem.

Let $\map L {\mathbf x} = \mathbf y \mathbf x$ and $r = \mathbf y \mathbf y$.

We show that:

$C \subset \map {L^{-1} } {\hointr r \to}$

Suppose $C$ is not a subset of $\map {L^{-1} } {\hointr r \to}$.

There exists $\mathbf z \in C \cap \map {L^{-1} } {\closedint {-\infty} r}$

So:

$\mathbf z \in \map {H_\mathbf y} r$

As $\gamma \to 1$, there exists a $0 < \gamma < 1$ such that:

$\norm {\mathbf y \, \gamma \, \mathbf z} < \norm {\mathbf y}$

by Lemma 1.

Since $C$ is convex, $\mathbf y \in C$ and $\mathbf z \in C$, convex combination $\mathbf y \, \gamma \, \mathbf z \in C$.

Since $\mathbf y$ is a minimmizer of $\norm {\mathbf x}$:

$\norm {\mathbf y} \le \norm {\mathbf y \, \gamma \, \mathbf z}$

For strong separation, let $\epsilon < r / 2$.

We have:

$C \subset \map {L^{-1} } {\hointr r \to} \subset \map {L^{-1} } {\hointr {r/2 + \epsilon} \infty}$

Since:

$\map L {\mathbf 0} = \mathbf y \mathbf 0 = 0$

and:

$r/2 - \epsilon > 0$

it follows that:

$\mathbf v = \mathbf 0 \subset \map {L^{-1} } {\hointl {-\infty} {r/2 - \epsilon} }$

$\blacksquare$