Separating & Supporting Hyperplanes

Two disjoint convex sets can always be cut apart by a single flat blade.

The idea

Theorem (Separating hyperplane theorem).

Let $C$ and $D$ be nonempty convex sets with no point in common. Then there exist $a \neq 0$ and $b$ with $a^{T}x \le b$ for every $x \in C$ and $a^{T}x \ge b$ for every $x \in D$.

The set $\{x : a^{T}x = b\}$ is a hyperplane — a line in the plane, an ordinary plane in three dimensions — and it divides space into the two halfspaces $a^{T}x \le b$ and $a^{T}x \ge b$. The theorem says one halfspace contains $C$ and the other contains $D$.

Convexity is essential: two disjoint nonconvex sets can interlock like linked horseshoes, and then no hyperplane has one set on each side. Convex sets cannot interlock.

The theorem converts the claim that $C$ and $D$ never meet, a statement about infinitely many points, into a certificate: a single pair $(a, b)$ whose two inequalities we can verify directly. The duality theory of convex optimization is built from such certificates.

Ways to work on it

• Walkthrough. Separate two explicit discs, then support one at a boundary point.
• Proof. The minimum-distance construction, and why nothing can cross it.
• Practice. Strictly separate a random point from a disc.
• Hardest. A hyperbola region and a halfplane — decide which kinds of separation are possible.

Not sure where to start? Take the ten-question placement test.