Separation Plane Theorem

Separation Theorem. Given a convex and closed set $S \subset \mathbb{R}^d$ and a point $p \notin S$, there is a separation plane between $S$ and $p$.

Proof. Define $\delta = \min \{ \Vert s - p \Vert : s \in S \}$, where $\Vert \cdot \Vert$ is the $\ell_2$ norm.

Lemma. There is a point $s^\star \in S$ that achieves $\Vert s^\star - p \Vert = \delta$.

Proof:

1. Pick arbitrary point $s \in S$ and let $r = \Vert s - p \Vert$.
2. Define $S' = S \cap \{\Vert x - p \Vert \le r \}$. Observe that $S'$ is nonempty, bounded, and closed.
3. Define a function $f: S' \rightarrow R$ as $f(s) = \Vert s - p \Vert$, which is a continuous.
4. Since $S'$ is bounded and closed, there exists a point $s^\star$ that minimizes $f(s)$.
5. We claim that $f(s^\star) = \delta$. Otherwise, there is a point $s'' \in S$, s.t., $f(s^\star) > \Vert s'' - p\Vert > \delta$. But this implies $s'' \in S'$, a contradicting $s^\star = \min_{s \in S'} f(s)$.

$\square$

Lemma. $s^\star$ is unique.

Proof: The uniqueness results from the convexity of $S$. If not, let $s''$ be another optimal point. Now $\Vert q - s'\Vert = \delta$ and $\Vert q - s''\Vert = \delta$. The middle point between $s'$ and $s''$ is clearly closer to $p$ than both $s'$ and $s''$, as

The inequality is tight if $s' \neq s''$. Therefore, we use $s^\star$ to indicate the unique point.

$\square$

Lemma. $(p - s^\star)^T(x - s^\star) = 0$ is a separation plane between $S$ and $p$.

Proof.

First, observe that $(p - s^\star)^T(p - s^\star) = \delta^2 > 0$ since $p \notin S$ and $S$ is closed.

Further, for each $s \in S$, let

• $a = s^\star - p$, and
• $b = s - s^\star$.

We claim that $\left< b, a \right> \ge 0$.

For all $\lambda \in (0, 1)$, by convexity, $\lambda \cdot (s - s^\star) + s^\star \in S$. By the definition of $s^\star$,

On the other hand,

Therefore, $\lambda^2 \Vert b \Vert ^2 + 2 \lambda \left< b, a \right> \ge 0$. As $\lambda\rightarrow 0$, we obtained the desired result.

$\square$

Corollary. Given a convex and closed set $S \subset \mathbb{R}^d$ and a point $p \in \partial S$ (the boundary of $S$), there is supporting hyperplane passing through $p$ and containing $S$ in one of its half-spaces.

Proof. Since $p \in \partial S$, there is a countable, bounded sequence of points $p_k$ such that $p_k \notin S$ and $p_k \rightarrow p$.

Let $s_k$ be the projection of $p_k$ to $S$. Clearly $\Vert s_k - p_k \Vert \le \Vert p - p_k \Vert$. By triangle inequality,

It follows that $s_k \rightarrow p$.

For each $p_k$, we can find a supporting hyperplane $f_k (x) = \left< a_k, x - p_k \right>$, such that

1. $\Vert a_k \Vert \neq 0$ and,
2. $\left< a_k, s - s_k \right> \ge 0$ for all $s \in S$, where $s_k$ is the projection of $p_k$ to $S$.

Replacing $a_k$ by $a_k / \Vert a_k \Vert$, we can assume without lose of generality that $\Vert a_k \Vert = 1$.

The sequence $\{ a_k \}$ is therefore bounded. There is a converging subsequence $\{ a_\ell \}$ of $\{ a_k \}$ such that $a_\ell \rightarrow a$.
Finally,

$\blacksquare$