The Separating Hyperplane Theorem

Theorem 1

Suppose that \(E_1\) and \(E_2\) are closed, disjoint, nonempty convex sets in a real Hilbert space \(H\). If one of \(E_1\) or \(E_2\) is compact, then there exists a vector \(z \in H\) and a constant \(c\) such that \(\left<z,x\right> > c\) for all \(x \in E_1\) and \(\left<z,y\right> < c\) for all \(y \in E_2\).

1. Proof Part I

Recall from the notes on orthogonal projection that given a closed convex set \(K\) in a Hilbert space \(H\) and a vector \(y \not \in K\), there is a unique \(y' \in K\) which minimizes \(||y -y'||\) over all of \(K\).

By continuity of \(y \mapsto \inf_{y' \in E_2} ||y-y'||\) and compactness of \(E_1\), there exists \(x' \in E_1\) such that

\[ \inf_{y \in E_2} ||x' - y|| = \inf_{x \in E_1} \inf_{y \in E_2} ||x-y||. \]

Here we have used the Extreme Value Theorem on compact metric spaces.

2. Proof Part II

Now suppose for the \(x' \in E_1\) identified above that \(y' \in E_2\) attains the infimum \(\inf_{y \in E_2} ||x' - y||\). This implies that

\[ ||x' - y'|| \leq ||x-y|| \]

for all \(x \in E_1, y \in E_2\). Because \(E_1 \cap E_2\) is empty, \(x' - y' \neq 0\).

If \(y\) is any element of \(E_2\) and \(t \in [0,1]\), then

\[{}|| x' - (t y + (1-t)y')||^2{}\]

\[{}= ||x'-y'||^2{}\]

\[{}+ 2 t\left<x'-y',y'-y\right>{}\]

\[{}+ t^2 ||y-y'||^2. {}\]

By convexity, \(t y + (1-t)y' \in E_2\) and consequently the left-hand side is at least \(||x'-y'||^2\) for all \(t \in [0,1]\). Taking the derivative in \(t\) at \(t = 0\) implies that

\[ \left<x'-y',y'-y\right> \geq 0. \]

Setting \(z := x' -y'\) gives that \(\left<z,y\right> \leq \left<z,y'\right>\) for each \(y \in E_2\).

By an entirely symmetric argument,

\[ \left<y' - x',x'-x\right> \geq 0 \]

for all \(x \in E_1\), i.e., \(\left<z,x'\right> \leq \left<z,x\right>\) for all \(x \in E_1\). To finish, observe that

\[ \left<z,y\right> \leq \left<z,y'\right> < \left<z,y'\right> + |z|^2 = \left<z,x'\right> \leq \left<z,x\right>.\]

The constant \(c\) can be chosen strictly between \(\left<z,y'\right>\) and \(\left<z,x'\right>\) to achieve the theorem.

3. Example Application

Exercise

Show that every proper closed convex subset of \({\mathbb R}^d\) can be written as an intersection of closed half spaces.

Theorem 2

Every point on the boundary of a closed convex set \(K \subset {\mathbb R}^d\) is contained in a hyperplane \(P\) having the property that all points of \(K\) either belong to \(P\) or to the same side of \({\mathbb R}^d \setminus P\).

Proof

Meta (Main Idea)

Let \(\{y_n\}_{n=1}^\infty\) be a sequence in \(K^c\) converging to \(k\), and for each \(n\), apply the Separating Hyperplane Theorem to the pair \(E_1 = \{y_n\}\), \(E_2 := K\). This yields a sequence of vectors \(z_n\) such that \(\left<x,z_n\right> \geq \left<y_n,z_n\right>\) for each \(x \in K\) and each \(n\). The theorem guarantees that \(z_n \neq 0\), so we may divide \(z_n\) by \(||z_n||\) without loss of generality to assume that \(||z_n|| \leq 1\) for each \(n\). Let \(e_1,\ldots,e_d\) be an orthonormal basis of \({\mathbb R}^d\). By the Bolzano-Weierstrass theorem, there is a subsequence of \(\{e_1,z_n\}\) such that the limit \(\left<e_1,z_{n_k}\right>\) exists (because \(|\left<e_i,z_n\right>| \leq ||e_i|| ||z_n|| \leq 1\), i.e., it's a bounded sequence). Taking a subsequence of the subsequence, etc., gives a subsequence \(z_{m_j}\) such that \(\left<e_i,z_{m_j}\right>\) converges as \(j \rightarrow \infty\) for each \(i = 1,\ldots,d\). Since \(z_{m_j} = \left<z_{m_j},e_1\right> e_1 + \cdots + \left<z_{m_j},e_d\right> e_d\), this implies that \(z_{m_j}\) itself converges to some \(z\) as \(j \rightarrow \infty\).

But now for any \(x \in K\), \(\left<x,z_{m_j}\right> \geq \left<y_{m_j},z_{m_j}\right>\) for each \(j\). Taking limits as \(j \rightarrow \infty\) gives that \(\left<x,z\right> \geq \left<k,z\right>\); the hyperplane \(P\) promised by the theorem is given by \(P := \{ y \in H \ : \ \left<y, z\right> = \left<k,z\right> \}\). It clearly contains \(k\) and all points of \(K\) lie in the half space \(\{y \in H \ : \ \left<y,z\right> \geq \left<k,z\right>\}\).