3.2 Separation theorems for convex sets

Separating hyperplanes divide space into half-spaces containing convex sets. This powerful concept allows us to prove the existence of optimal solutions in various fields, from machine learning to financial mathematics.

The theorem states that for disjoint convex sets, there's always a hyperplane separating them. This idea forms the foundation for many problem-solving techniques in geometric optimization and classification tasks.

Separation Theorems for Convex Sets

Separating hyperplane theorem

Top images from around the web for Separating hyperplane theorem

• 

  computational geometry - The (Sigma) Algebra of Convex Sets - MathOverflow View original

  Is this image relevant?

• 

  enter image description here View original

  Is this image relevant?

• 

  Convex optimization using quantum oracles – Quantum View original

  Is this image relevant?

• 

  computational geometry - The (Sigma) Algebra of Convex Sets - MathOverflow View original

  Is this image relevant?

• 

  enter image description here View original

  Is this image relevant?

1 of 3

Top images from around the web for Separating hyperplane theorem

• 

  computational geometry - The (Sigma) Algebra of Convex Sets - MathOverflow View original

  Is this image relevant?

• 

  enter image description here View original

  Is this image relevant?

• 

  Convex optimization using quantum oracles – Quantum View original

  Is this image relevant?

• 

  computational geometry - The (Sigma) Algebra of Convex Sets - MathOverflow View original

  Is this image relevant?

• 

  enter image description here View original

  Is this image relevant?

1 of 3

• Separating hyperplane divides space into two half-spaces containing convex sets (upper and lower half-planes)
• Theorem states for disjoint convex sets A and B in $\mathbb{R}^n$, non-zero vector $v$ and scalar $c$ exist where $\langle v, x \rangle \leq c$ for A and $\langle v, x \rangle \geq c$ for B
• Geometrically, hyperplane $\{x : \langle v, x \rangle = c\}$ separates A and B (horizontal line in 2D, plane in 3D)

Proof of separating hyperplane existence

• Consider difference set $D = A - B$ (set of all pairwise differences)
• Show 0 not in interior of D using contradiction and definition of interior points
• Apply supporting hyperplane theorem to D at 0 (tangent plane at boundary point)
• Proof steps:
  1. Assume 0 in interior of D
  2. Derive contradiction using interior point definition
  3. Conclude 0 on boundary or outside D
  4. Use supporting hyperplane theorem at 0 for D
  5. Translate separating hyperplane back to A and B

Applications in geometric problem-solving

• Optimization proves optimal solution existence and characterizes optimality conditions (linear programming)
• Machine learning uses support vector machines to find optimal separating hyperplane between classes (binary classification)
• Financial mathematics applies no-arbitrage conditions in asset pricing (risk-neutral pricing)
• Game theory separates payoff vectors in cooperative games (core solution concept)
• Convex analysis proves subgradient existence for convex functions (generalized derivatives)

Strict vs non-strict convex set separation

• Non-strict separation allows points from both sets on separating hyperplane ($\langle v, x \rangle \leq c$ for A, $\langle v, x \rangle \geq c$ for B)
• Strict separation requires positive distance between sets ($\langle v, x \rangle < c$ for A, $\langle v, x \rangle > c$ for B)
• Strict separation conditions: one set compact (closed and bounded) and disjoint closures
• Geometrically, non-strict allows sets to touch hyperplane, strict keeps sets on opposite sides
• Applications: strict separation provides stronger classification guarantees, non-strict often sufficient for theoretical results (convex optimization)