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 , an affine hyperplane has the form
where is a normal vector and . The notation denotes the Euclidean inner product. The hyperplane bounds two closed half-spaces:
It separates sets and if
Equivalently,
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 . In a topological vector space, separation theorems ordinarily require to be continuous. The separating hyperplane is then the level set .
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 and such that
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 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
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 and the infimum on .
Strong separation
Strong separation requires
Equivalently, there exist , , and such that
This gives a uniform margin. By the Cauchy–Schwarz inequality, the distance between the sets is then at least .
Some authors use “strict separation” for this stronger condition.
Principal finite-dimensional theorems
Let be nonempty and convex.
Disjoint convex sets
If , then and 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 is an open set and is disjoint from , a separator can be chosen with
If both sets are open, both sides can be made strict:
Openness does not by itself provide a uniform margin.
A compact set and a closed set
If is compact, 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
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 is compact, is closed, and they are nonempty, convex, and disjoint. There exist points and realizing their positive minimum distance. Set
For any , convexity ensures that for . Since minimize distance, differentiating the squared distance at gives
The analogous argument in gives
Consequently,
because
The hyperplane perpendicular to the segment joining and , through its midpoint, strongly separates the sets.
Reduction to separation from the origin
For general disjoint convex sets, consider their difference set
This set is convex and does not contain . A separation theorem for a point and a convex set yields a nonzero satisfying
It follows that
which gives a weak separating hyperplane.
One finite-dimensional proof separates from the closure of . If lies outside that closure, a nearest-point argument applies. If 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 is nonempty and convex and is a boundary point of , there exists such that
The hyperplane through therefore bounds a half-space containing .
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
for every nonempty closed convex set . 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 and vector , exactly one of the following holds:
or
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 , this yields
Here the gradient determines the slope of a supporting hyperplane to the epigraph at .
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
Both are closed and convex, and they are disjoint. Nevertheless, their distance is zero because as . They cannot be strongly separated.
They also cannot be strictly separated in the two-sided pointwise sense defined above. The horizontal boundary of forces any separator to be horizontal, while approaches that boundary arbitrarily closely. They do admit one-sided strict separation:
Convexity cannot generally be omitted
Let
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.