A wall between two bodies

A line under every point is a statement about one convex set and one of its boundary points: the set lies entirely on one side of a line through that point. This rung is the same statement about two sets, and the difference in what it buys is out of all proportion to the difference in what it says.

Two convex sets that share no point can be put on opposite sides of a straight line. That line is a certificate. It is a single object; checking it means checking an inequality; and once checked, it proves something about every point of two possibly infinite sets at once. Nearly everything in optimisation that produces an answer together with a proof that it is the answer is this theorem, applied somewhere.

Where the line comes from #

The construction in the figure is the proof, for sets that are closed and bounded, and it is worth following because it explains why the theorem needs both sets to be convex rather than one.

Take the two sets and find the pair of points, one in each, at minimum distance. Such a pair exists because the sets are closed and bounded and the distance function is continuous. Draw the segment between them and take the line perpendicular to it through its midpoint.

The claim is that neither set crosses that line. Suppose one did — suppose some point of the first set lay on the far side. Then the segment from that point to the nearest point, which lies inside the first set because the set is convex, would contain points closer to the second set than the nearest point was. That contradicts minimality, and the contradiction consumed convexity in exactly one place: the assertion that the segment stays inside the set.

So the hypothesis is not decoration. It is used once, at the only step that could fail, and the failure is easy to arrange.

Disjointness, on its own, buys nothing. The two sets in that figure are as separate as two sets can be — a positive distance apart, both closed, both bounded — and no line separates them, because one of them bends around the other. What a line can express is a single linear inequality, and a set that is not convex is not the solution set of any collection of them.

The three versions, and which one is true #

The theorem is usually stated in three strengths, and quoting the wrong one is the standard error.

Strict separation. Two disjoint compact convex sets have a line with one strictly on each side, and a corridor of positive width between them. That is the case above, and it is the strongest form.

Separation with contact. Two convex sets whose interiors are disjoint have a line with each on one side, allowing points of either to lie on it. Two discs touching at a point have exactly one such line, the common tangent, and no corridor at all.

And the case that fails. Two disjoint closed convex sets need not be strictly separable if neither is bounded. The region above the curve $y = 1/x$ for positive $x$, and the positive half of the $x$-axis, are closed, convex, and share no point — and the only line with one on each side is the axis itself, which touches one of them. The distance between them is zero without their meeting, so the construction above has no minimum to start from.

That third case is the reason the hypotheses are always stated in full, and it is the reason the infinite-dimensional version of this theorem — the Hahn–Banach theorem — is a substantial piece of work rather than a corollary. In finite dimensions with compact sets, the construction is a page. Without compactness it needs care; without finite dimension it needs the axiom of choice.

The same theorem as arithmetic #

A geometric statement about two bodies becomes an algebraic statement about a system of equations, and the algebraic form is the one that is actually used.

Ask whether a vector $b$ can be written as a non-negative combination of some given vectors. The set of all such combinations is a cone, which is convex. So either $b$ is in it, or $b$ and the cone are disjoint convex sets and a separating line exists — and a line separating a cone from a point can be taken through the origin, since the cone contains the origin and is closed under scaling.

That is Farkas’ lemma: exactly one of the following holds. Either $b$ is a non-negative combination of the given vectors, or there is a direction making $b$ positive and every given vector non-positive.

Exactly one, and both halves of that matter. That the two cannot both hold is a line of arithmetic: if $b = \sum c_j v_j$ with every $c_j \ge 0$ and $y \cdot v_j \le 0$ for every $j$, then $y \cdot b \le 0$, contradicting $y \cdot b > 0$. That at least one must hold is the separation theorem, and there is no easy proof of it.

The pair is what makes “no solution” into a checkable claim. Without the lemma, the statement this system has no non-negative solution is a claim about infinitely many candidate solutions, and the only evidence for it is a failed search. With it, the statement has a witness of its own — a single direction — that anybody can verify in a moment. A theorem of the form “exactly one of these two things is true” is a theorem that turns an absence into an object.

A refutation, worked #

The lemma is easiest to believe on a system small enough to do by hand, and the example is worth carrying because it shows what a certificate actually consists of.

Ask for numbers $x$ and $y$, both at least zero, with

$$x + y \le 2, \qquad x - y \ge 3.$$

There is no such pair, and the reason is not obvious from staring: the first says the two cannot be large, the second says $x$ must exceed $y$ by a good margin, and neither on its own forbids anything.

Write both the same way round. The first is $x + y \le 2$ already; the second, negated, is $-x + y \le -3$. Now add the two left sides and the two right sides. The left sides give $2y$, because the two copies of $x$ cancel. The right sides give $2 - 3 = -1$. So $2y \le -1$, and $y$ was required to be non-negative. The system is refuted by one addition, and the cancellation of $x$ is the whole trick.

That addition is the certificate. It is a pair of multipliers — one and one, here — applied to the two constraints, producing a consequence that contradicts the sign requirements. Farkas’ lemma says such multipliers always exist when the system is infeasible, and never exist when it is not, so the recipe above is not a lucky find but the general form of the answer.

The multipliers here are both one, which is why the arithmetic is so short. In general they are whatever non-negative numbers make the variables cancel, and finding them is a linear programme in its own right — the dual of the one being refuted. That circularity is not a defect: it says that finding a certificate and finding an answer are the same computation, which is why solvers hand back both.

Notice what has been avoided. Nobody searched over pairs $(x, y)$; nobody argued about the shape of the region; the refutation is two numbers and a line of arithmetic, and it can be handed to a sceptic who need not repeat any of the reasoning that produced it. That is the whole practical content of separation, and the geometry above is what guarantees the arithmetic is always available.

When the wall is not unique #

A theorem promising existence rarely says how many, and here the count is informative.

If the two sets are a positive distance apart, there are infinitely many separating lines — the corridor between them is a region, and every line across it works, at a range of angles and offsets. The one the figures draw is a canonical choice, the perpendicular bisector of the shortest segment, and it is the only one that leaves an equal margin on both sides.

If the sets touch, the count collapses. Two discs meeting at a single point have exactly one separating line: the common tangent there. A disc and a square meeting along a flat edge also have exactly one. Uniqueness of the wall means the sets are in contact, and the direction of the unique wall is the direction in which they touch — which is why an optimisation algorithm that has converged is one whose separating direction has stopped moving.

If one of the sets has a corner and they touch at it, the count goes back up: a square and a line touching at the square’s corner are separated by a whole fan of lines. So the number of walls measures smoothness at the contact point, and the three cases — a corridor, a single tangent, a fan — are the three things that can happen where two convex bodies meet. The supporting line at a point of a curve is the same trichotomy with one body shrunk to a point, and the fan is what appears at a kink in the graph.

What the certificate is worth #

The dual of a linear programme is this lemma applied once, and the essay on duality gives the consequence: two numbers computed from the same data that must be equal. Here is the mechanism underneath it, and the mechanism is more portable than the consequence.

Any method that stops and announces an answer faces a question it usually cannot answer: how does anyone know? For a general search the honest reply is that the method stopped, which — as the rung about what convexity buys puts it — is a statement about the search rather than about the problem. A separating direction changes the kind of claim available. It is not evidence that the search was thorough; it is a proof that no better answer exists, and it is short.

The pattern recurs wherever an optimum is certified. A shortest path is certified by distances that satisfy the triangle inequality along every edge. A maximum flow is certified by a cut of the same value, which is the bottleneck argument in its most familiar form. A minimum of a convex function is certified by a supporting line that is horizontal. Each of these is a separating object, and the reason the pattern exists at all is that the feasible set in each case is convex.

Reading the wall as a price #

There is a second reading of the separating direction, and it is the one that makes the theorem feel less like geometry.

A line in the plane is given by a direction and a number: the direction says which linear function to evaluate, the number says where to cut. So a separating line is a linear function that is small on one set and large on the other. Finding a wall is finding a function that tells two sets apart, and once it is put that way, the connection to the rung about tangents is immediate.

The Legendre transform said that a convex function is recoverable from its tangent lines. Separation is why: two different closed convex sets can be separated from any point that lies in one and not the other, so the collection of linear functions bounding a set determines the set exactly. That is also what makes a convex region large enough to swallow a lattice point a statement one can reason about at all: the region is known by its inequalities rather than by a description of its interior. A convex object is nothing more than the list of linear inequalities it satisfies, and everything on this ladder from the third rung onwards is that sentence in different clothes.

The economic reading writes the direction as prices. If the achievable outcomes form a convex set and a target lies outside it, the separating direction assigns a number to each coordinate such that the target’s total exceeds anything achievable — which is a price system under which the target is unaffordable. That the prices exist whenever the target is genuinely out of reach is the separation theorem, and it is where the convexity assumptions in economics come from and what they cost.

The hypothesis nobody states #

One condition has been used silently throughout and is worth dragging into the open, because it is the one that fails first in practice.

Every set drawn here is closed. Drop that and strict separation goes, even in the plane, even with bounded sets: the open unit disc and the point on its boundary share nothing, and every line through that point cuts the disc. There is a separating line in the weak sense — the tangent — and no corridor at all, which is the second of the three versions rather than the first.

The reason to raise it is that the sets one actually meets are described by inequalities, and whether they come out closed depends on whether the inequalities are strict. A feasible region written with $\le$ throughout is closed; the same region written with $<$ is not; and the two describe the same picture to a reader and different objects to this theorem. That is the most common way a separation argument fails in a write-up, and it fails silently, because the picture is the same.

The general lesson is the one the counterexample sweep already made in a different register. The theorem’s hypotheses are convexity, disjointness, closedness and — for the strict form — boundedness of at least one of the two. Three of the four are easy to check and one is easy to assume, and each of them is doing work that the others cannot do.

What the pictures cannot show #

Everything drawn here is planar and bounded. The unbounded failure case is described and not drawn, for the good reason that a picture of two sets approaching each other without meeting is a picture of a limit, and no finite figure distinguishes it from a small gap.

The refutation sweep tries 720 directions and reports that none separates. That is a fine sample of the circle and it is a sample: the honest statement is that no line in any of those directions works, and the theorem behind it is what makes that conclusive rather than suggestive.

And the infinite-dimensional theorem — the one that actually carries the weight in analysis — is out of reach of a drawing entirely. Its statement is the same and its proof is not, and the difference is the whole subject of functional analysis rather than a detail this rung skips.

Where the ladder goes next #

This rung closes the ladder. Convexity by chords, by supporting lines, by conjugates, by its absence, by the counting theorems, and now by the one theorem the rest of them are consequences of.

Named here as debts: cones and their duals in full, of which the Farkas figure is one instance; and the minimax theorem, which is separation applied to a pair of strategy sets and is where the same argument arrives in game theory.

Sideways, the number of sets a convex conclusion needs is the rung below, the certificate this produces is priced in the dual’s variables, and the guarantee that vanishes without convexity is what its absence removes.

What is worth carrying away #

A proof that something is impossible is worth more when it is an object rather than an argument, and convexity is the condition under which the object exists.

Two convex sets that miss each other are separated by a line; a vector outside a cone is refuted by a direction; an infeasible system of inequalities is refuted by a combination of its own constraints. In each case the negative statement — these do not meet, this cannot be written, no solution exists — acquires a witness that is checked rather than trusted.

The habit worth taking is to ask what a negative claim’s certificate would look like. If the objects involved are convex, one exists, and finding it is usually the same work as establishing the claim. If they are not, no amount of searching produces one, and the crescent above is the reason.

The corollary is a diagnosis. When a method can find answers but cannot certify them, the useful question is not how to search harder but whether the feasible set is convex — because that single property is what decides whether a certificate is available at all, and no amount of effort supplies one where the geometry forbids it.