Convex Geometry - Applications

TheoremSeparating Hyperplane Theorem

Let $A$ and $B$ be disjoint non-empty convex sets in $\mathbb{R}^n$ . Then there exists a hyperplane separating them: there exist $\mathbf{a} \in \mathbb{R}^n$ and $c \in \mathbb{R}$ such that:

\langle \mathbf{a}, x \rangle \leq c \quad \text{for all } x \in A

\langle \mathbf{a}, y \rangle \geq c \quad \text{for all } y \in B

If one set is compact and the other closed, strict separation exists (strict inequalities with different constants).

This theorem is fundamental to convex analysis, optimization, and economics. It formalizes the intuition that disjoint convex sets can be separated by a flat surface (hyperplane).

ExampleSupport Vector Machines

In machine learning, SVMs find the maximum-margin separating hyperplane between two classes. Given labeled data points, the SVM optimization problem:

\min_{\mathbf{w}, b} \|\mathbf{w}\|^2 \quad \text{subject to } y_i(\mathbf{w} \cdot \mathbf{x}_i + b) \geq 1

finds the separating hyperplane with maximum distance to nearest points (support vectors). The separating hyperplane theorem guarantees existence for linearly separable data.

Duality in optimization leverages separation. The strong duality theorem (primal and dual optima coincide for convex problems) follows from geometric separation arguments. This enables efficient algorithms and provides economic interpretations (shadow prices).

DefinitionNormal Cone

The normal cone to convex set $C$ at point $x \in C$ is:

N_C(x) = \{\mathbf{v} : \langle \mathbf{v}, y - x \rangle \leq 0 \text{ for all } y \in C\}

Normal cones generalize gradients and are fundamental in variational analysis and subdifferential calculus.

Remark

Applications span diverse fields:

Economics: Welfare theorems use separating hyperplanes to prove existence of competitive equilibria
Control theory: Reachable sets (convex) are analyzed via supporting hyperplanes
Statistics: Classification problems reduce to finding separating hyperplanes
Robotics: Configuration space obstacles (convex) are avoided using separation

The theorem extends to infinite dimensions (Hahn-Banach theorem), providing foundational results in functional analysis. Geometric intuition (separating convex sets) translates to analytic conclusions (extending linear functionals).