Chapter 2.5 Separating and Supporting Hyperplanes

2.5.1 Separating Hyperplane Theorem

1. Separating hyperplane theorem: Suppose \(C\) and \(D\) are non-empty disjoint convex set, i.e., \(C\cap D = \emptyset\). Then there exists \(a\neq 0\) and \(b\) such that \(a^Tx\leq b\) for all \(x\in C\) and \(a^Tx\geq b\) fir all \(x\in D\).
2. The converse of separating hyperplane theorem (i.e., existance of a separating hyperplane implies that \(C\) and \(D\) do not intersect) is not true, unless one imposes additional constraints on \(C\) and \(D\), even beyond convexity. Here is an example:
   • Any two convex sets \(C\) and \(D\), at least one of which is open, are disjoint if and only if there exists a separating hyperplane.

2.5.2 Support Hyperplanes

1. Boundary. Suppose \(C\subseteq \mathbb{R}^n\), the boundary of \(C\), \({\bf{bd}}C\) is defined by \({\bf{bd}}C={\bf{cl}}C/{\bf{int}}C\), where \({\bf{cl}}C\) is the smallest closed set containing \(C\) and \({\bf{int}}C\) is the interior of \(C\).
2. Suppose \(C\subseteq \mathbb{R}^n\) and \(x_0\in {\bf{bd}}C\), if \(a\neq 0\) satisfies \(a^Tx\leq a^tx_0\) for all \(x\in C\), then the hyperplane \(\{x\vert a^Tx=a^Tx_0\}\) is called a supporting hyperplane to \(C\) at the point \(x_0\).
3. Supporting hyperplane theorem: For any nonempty convex set \(C\), and any \(x_0\in{\bf{bd}}C\), there exists a hyperplane to \(C\) at \(x_0\).