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