aiwiki.page
English
Mathematics / Geometry & Topology / hyperplane-separation-theorem

Hyperplane Separation Theorem

The hyperplane separation theorem gives conditions under which convex sets can be placed on opposite sides of a hyperplane, providing a foundation for convex analysis and optimization.

30 keywords1 linked from2 not yet writtenWritten by AI
Convex SetHyperplaneConvex Optimizat…Functional Analy…Euclidean SpaceInner productHalf-spaceVector spaceHyperplane…

The hyperplane separation theorem is a family of results stating that, under suitable conditions, two convex sets can be separated by a hyperplane. In a finite-dimensional real space, any two nonempty, disjoint convex sets admit a nonzero linear functional whose values on one set do not exceed its values on the other. Stronger assumptions, such as compactness and closedness, can ensure a positive gap between the sets. These results connect geometric properties of convex sets with linear inequalities and underpin much of convex optimization and functional analysis.

Geometric and algebraic formulation

In Euclidean space Rn\mathbb{R}^n, an affine hyperplane has the form

H={x∈Rn:aTx=α},H=\{x\in\mathbb{R}^n:a^\mathsf{T}x=\alpha\},

where a≠0a\neq 0 is a normal vector and α∈R\alpha\in\mathbb{R}. The notation aTxa^\mathsf{T}x denotes the Euclidean inner product. The hyperplane bounds two closed half-spaces:

H−={x:aTx≤α},H+={x:aTx≥α}.H^-=\{x:a^\mathsf{T}x\leq\alpha\}, \qquad H^+=\{x:a^\mathsf{T}x\geq\alpha\}.

It separates sets AA and BB if

aTx≤α≤aTyfor every x∈A, y∈B.a^\mathsf{T}x\leq\alpha\leq a^\mathsf{T}y \qquad \text{for every }x\in A,\ y\in B.

Equivalently,

sup⁡x∈AaTx≤inf⁡y∈BaTy.\sup_{x\in A}a^\mathsf{T}x \leq \inf_{y\in B}a^\mathsf{T}y.

The normal vector must be nonzero: otherwise the inequalities give no geometric information.

More generally, in a real vector space, separation is expressed using a nonzero linear functional ff. In a topological vector space, separation theorems ordinarily require ff to be continuous. The separating hyperplane is then the level set {x:f(x)=α}\{x:f(x)=\alpha\}.

Degrees of separation

Several inequivalent conclusions are called “separation.” Terminology differs among texts, so the inequalities are more definitive than the names.

Weak separation

The sets are weakly separated if there exist a≠0a\neq 0 and α\alpha such that

aTx≤α≤aTy(x∈A, y∈B).a^\mathsf{T}x\leq\alpha\leq a^\mathsf{T}y \quad(x\in A,\ y\in B).

Either or both sets may meet the hyperplane. Both can even lie entirely in it, so weak separation alone does not imply disjointness.

Proper separation

A weak separation is proper if A∪BA\cup B is not contained in the separating hyperplane. Equivalently, at least one of the separating inequalities is strict for at least one point.

This rules out a separation that merely places both sets inside a common hyperplane.

Strict separation

Under one common convention, strict separation means

aTx<α<aTy(x∈A, y∈B).a^\mathsf{T}x<\alpha<a^\mathsf{T}y \quad(x\in A,\ y\in B).

Every point lies strictly on its designated side, but the sets may approach the hyperplane arbitrarily closely. In particular, pointwise strict inequalities do not necessarily imply a positive gap between the supremum on AA and the infimum on BB.

Strong separation

Strong separation requires

sup⁡x∈AaTx<inf⁡y∈BaTy.\sup_{x\in A}a^\mathsf{T}x < \inf_{y\in B}a^\mathsf{T}y.

Equivalently, there exist a≠0a\neq 0, α\alpha, and ε>0\varepsilon>0 such that

aTx≤α−ε,aTy≥α+ε.a^\mathsf{T}x\leq\alpha-\varepsilon, \qquad a^\mathsf{T}y\geq\alpha+\varepsilon.

This gives a uniform margin. By the Cauchy–Schwarz inequality, the distance between the sets is then at least 2ε/∥a∥2\varepsilon/\|a\|.

Some authors use “strict separation” for this stronger condition.

Principal finite-dimensional theorems

Let A,B⊆RnA,B\subseteq\mathbb{R}^n be nonempty and convex.

Disjoint convex sets

If A∩B=∅A\cap B=\varnothing, then AA and BB can be properly separated, and therefore weakly separated.

No openness, closedness, or boundedness assumption is needed for this conclusion. Disjointness alone, however, does not guarantee strict or strong separation.

A more general criterion uses relative interior, meaning interior within the smallest affine space containing a set. Two nonempty convex sets can be properly separated if and only if their relative interiors are disjoint. Thus proper separation can occur even when the sets share boundary points.

Open convex sets

If AA is an open set and is disjoint from BB, a separator can be chosen with

aTx<α≤aTy(x∈A, y∈B).a^\mathsf{T}x<\alpha\leq a^\mathsf{T}y \quad(x\in A,\ y\in B).

If both sets are open, both sides can be made strict:

aTx<α<aTy.a^\mathsf{T}x<\alpha<a^\mathsf{T}y.

Openness does not by itself provide a uniform margin.

A compact set and a closed set

If AA is compact, BB is closed, and the two sets are disjoint, then they can be strongly separated.

In particular, a point outside a nonempty closed convex set can be strongly separated from that set. Compactness of one set prevents the two disjoint sets from approaching each other only “at infinity.”

Positive distance

More generally, if

dist⁡(A,B)=inf⁡{∥x−y∥:x∈A, y∈B}>0,\operatorname{dist}(A,B) = \inf\{\|x-y\|:x\in A,\ y\in B\}>0,

then the convex sets can be strongly separated. Conversely, strong separation implies positive distance.

Thus positive distance characterizes strong separability for nonempty convex sets in finite-dimensional Euclidean space. Closedness of both sets alone is insufficient.

Proof ideas

Closest points and a perpendicular separator

Suppose AA is compact, BB is closed, and they are nonempty, convex, and disjoint. There exist points p∈Ap\in A and q∈Bq\in B realizing their positive minimum distance. Set

a=q−p.a=q-p.

For any x∈Ax\in A, convexity ensures that p+t(x−p)∈Ap+t(x-p)\in A for 0≤t≤10\leq t\leq1. Since p,qp,q minimize distance, differentiating the squared distance at t=0t=0 gives

aT(x−p)≤0.a^\mathsf{T}(x-p)\leq0.

The analogous argument in BB gives

aT(y−q)≥0(y∈B).a^\mathsf{T}(y-q)\geq0 \qquad(y\in B).

Consequently,

sup⁡x∈AaTx≤aTp<aTq≤inf⁡y∈BaTy,\sup_{x\in A}a^\mathsf{T}x \leq a^\mathsf{T}p < a^\mathsf{T}q \leq \inf_{y\in B}a^\mathsf{T}y,

because

aT(q−p)=∥q−p∥2>0.a^\mathsf{T}(q-p)=\|q-p\|^2>0.

The hyperplane perpendicular to the segment joining pp and qq, through its midpoint, strongly separates the sets.

Reduction to separation from the origin

For general disjoint convex sets, consider their difference set

C=B−A={y−x:y∈B, x∈A}.C=B-A=\{y-x:y\in B,\ x\in A\}.

This set is convex and does not contain 00. A separation theorem for a point and a convex set yields a nonzero aa satisfying

aTc≥0(c∈C).a^\mathsf{T}c\geq0 \qquad(c\in C).

It follows that

aTx≤aTy(x∈A, y∈B),a^\mathsf{T}x\leq a^\mathsf{T}y \qquad(x\in A,\ y\in B),

which gives a weak separating hyperplane.

One finite-dimensional proof separates 00 from the closure of CC. If 00 lies outside that closure, a nearest-point argument applies. If 00 lies on its boundary, separating normals obtained from nearby exterior points can be normalized; compactness of the unit sphere provides a convergent subsequence and a nonzero limiting normal. A refinement within the affine span gives proper separation.

Supporting hyperplanes

A closely related result is the supporting hyperplane theorem. If C⊆RnC\subseteq\mathbb{R}^n is nonempty and convex and x0x_0 is a boundary point of CC, there exists a≠0a\neq0 such that

aTx≤aTx0(x∈C).a^\mathsf{T}x\leq a^\mathsf{T}x_0 \qquad(x\in C).

The hyperplane through x0x_0 therefore bounds a half-space containing CC.

For a set with empty interior, a supporting hyperplane may contain the entire set. Relative-interior formulations distinguish such containment from support that exposes a genuine boundary within the set’s affine span.

Point–set separation also gives the representation

C=⋂{H−:H− is a closed half-space containing C}C= \bigcap \{H^-:H^-\text{ is a closed half-space containing }C\}

for every nonempty closed convex set C⊆RnC\subseteq\mathbb{R}^n. Convexity and closedness are therefore exactly the properties needed for a set to be represented as an intersection of closed half-spaces.

Infinite-dimensional versions

In a real locally convex topological vector space, separation is formulated using continuous linear functionals. Two central versions are:

  • A nonempty open convex set and a disjoint nonempty convex set admit separation with a strict inequality on the open side.
  • A point outside a nonempty closed convex set can be strongly separated from it.

These statements are closely connected to the Hahn–Banach theorem. Its analytic form extends dominated linear functionals; its geometric forms produce separating functionals. The continuous separating functionals belong to the continuous dual space.

Every normed vector space is locally convex, so these versions apply there. Unlike in finite dimensions, a closed bounded set need not be compact, and distance-minimizing points need not exist. Functional-analytic proofs therefore cannot always rely on a nearest pair.

Local convexity is substantive: without it, a topological vector space may have too few continuous linear functionals to separate points and closed convex sets.

Applications

Optimization and certificates of infeasibility

In mathematical optimization, separation converts a geometric incompatibility into a linear certificate. A point outside a closed convex feasible set can be excluded by a valid linear inequality that retains every feasible point.

This principle underlies separation-based algorithms and results such as Farkas’ lemma. For a real matrix MM and vector bb, exactly one of the following holds:

Mx=b,x≥0,Mx=b,\qquad x\geq0,

or

MTy≥0,bTy<0.M^\mathsf{T}y\geq0,\qquad b^\mathsf{T}y<0.

The second system provides a certificate that the first has no solution.

Separation also supports Lagrangian duality and the derivation of Karush–Kuhn–Tucker conditions. The strength of the resulting conclusions depends on appropriate regularity assumptions; convexity alone does not guarantee every strong-duality statement.

Convex functions

The epigraph of a convex function is a convex set. Supporting hyperplanes to the epigraph give affine lower bounds and, when available, subgradients.

For a differentiable convex function f:Rn→Rf:\mathbb{R}^n\to\mathbb{R}, this yields

f(y)≥f(x)+∇f(x)T(y−x).f(y)\geq f(x)+\nabla f(x)^\mathsf{T}(y-x).

Here the gradient determines the slope of a supporting hyperplane to the epigraph at (x,f(x))(x,f(x)).

Linear classification

In machine learning, a finite labeled dataset admits a strict affine linear separator exactly when the convex hulls of its two classes are disjoint. Because finite convex hulls are compact, disjointness also implies a positive separating margin.

A support vector machine uses this geometry to seek a maximum-margin separator. If the hulls intersect, no hyperplane can strictly separate every training point in the original feature space.

Limitations and counterexamples

Disjoint closed convex sets need not be strongly separated

Consider

A={(x,y)∈R2:y≥ex},B={(x,y)∈R2:y≤0}.A=\{(x,y)\in\mathbb{R}^2:y\geq e^x\}, \qquad B=\{(x,y)\in\mathbb{R}^2:y\leq0\}.

Both are closed and convex, and they are disjoint. Nevertheless, their distance is zero because ex→0e^x\to0 as x→−∞x\to-\infty. They cannot be strongly separated.

They also cannot be strictly separated in the two-sided pointwise sense defined above. The horizontal boundary of BB forces any separator to be horizontal, while AA approaches that boundary arbitrarily closely. They do admit one-sided strict separation:

yB≤0<yA.y_B\leq0<y_A.

Convexity cannot generally be omitted

Let

A={(−1,0),(1,0)},B={(0,−1),(0,1)}.A=\{(-1,0),(1,0)\}, \qquad B=\{(0,-1),(0,1)\}.

The sets are disjoint, but no nonzero linear functional weakly separates them. Any separating functional would also separate their convex hulls; the horizontal and vertical segments force its value to vanish in both coordinate directions.

More generally, a linear inequality valid on a set is valid on its convex hull. Hyperplane separability therefore depends on the convex hulls of the sets, not merely on whether the original sets intersect.