When one of the two numbers is missing

Two numbers that have to meet stated the duality theorem the way it is nearly always stated: a linear program, maximising, and its dual, minimising, built from the same numbers, reach exactly the same optimum. What a constraint is worth read the dual’s variables as prices. Both essays worked with programs that had an optimum, and both of their duals had one too.

That is only one case of the theorem. A linear program can fail to have an optimum in two different ways — it can have no feasible point at all, or it can have feasible points on which the objective grows without limit — and the dual can fail in the same two ways. The full theorem says which combinations can happen, and the answer is sharper than the equality alone.

The table is a count, not a sample. Every program of this size with small coefficients was built, its feasible region was enumerated exactly, and it was classified as having an optimum, running away, or being empty; its dual was classified the same way. The occupied cells are the whole of the theorem. If both sides have feasible points, both have optima and the optima are equal. If one side runs away, the other is empty. And both sides can be empty at once — the cell in the bottom right, which holds 427 programs, is the one case in which duality says nothing at all.

Why an optimum on one side forces one on the other #

Five cells are empty, and three of them are emptied by a one-line argument that needs nothing but the definitions. Take any feasible point $x$ of the program, maximise $c^\top x$ subject to $Ax \le b$ and $x \ge 0$, and any feasible point $y$ of the dual, minimise $b^\top y$ subject to $A^\top y \ge c$ and $y \ge 0$. Then

$$c^\top x \;\le\; (A^\top y)^\top x \;=\; y^\top A x \;\le\; y^\top b.$$

The first inequality uses $A^\top y \ge c$ and $x \ge 0$, the second uses $Ax \le b$ and $y \ge 0$. This is weak duality, and it is the reason every value of the program lies below every value of the dual — the gap on the number line in two numbers that have to meet, closing to a point.

Its consequences fill three empty cells at once. If the program runs away, its values exceed every number, so no dual point can exist to bound them: an unbounded program has an empty dual, and so the cells “unbounded with dual optimal” and “unbounded with dual unbounded” are empty. By the same argument read backwards, a runaway dual forces an empty program, which empties “optimal with dual unbounded”. Weak duality alone decides three of the five impossible cells.

The last two — an optimal program whose dual is empty, and the mirror image — are not touched by weak duality. They need the hard half of the theorem, the one that says the two numbers not only never cross but actually meet. If the program has an optimum and the dual were empty, there would be nothing to meet. That strong duality holds is the separating-line argument of a wall between two bodies, and the table confirms it for these 6,561 programs: whenever the program has an optimum, so does the dual, and in all 2,956 cases the two optima are the same number.

A program that runs away, and the proof it leaves behind #

The cell “unbounded, dual empty” deserves a picture, because the proof that the dual is empty can be read straight off the program.

The region on the left is open: it contains a whole ray, starting from a corner and running off in the direction $(1, 1)$, and along that ray the objective $x_1 + x_2$ increases by two for every unit step. A region runs away in a direction $d$ exactly when moving along $d$ never violates a constraint — $Ad \le 0$ and $d \ge 0$ — and the objective runs away with it when $c^\top d > 0$ as well. The set of such $d$ is the region’s cone of escape directions, and the figure’s arrow is one of its edges.

Now the dual. Its constraints are $A^\top y \ge c$. Multiply the first by $d_1$, the second by $d_2$, and add; since $d$ is non-negative the inequality survives:

$$d^\top A^\top y \;\ge\; c^\top d.$$

The left side is $(Ad)^\top y$, and $Ad \le 0$ while $y \ge 0$, so it is at most nought. The right side is positive. Nothing satisfies that, so the dual is empty — and the proof is the escaping direction itself. In the figure’s numbers, $d = (1, 1)$ turns the two dual constraints into $-y_2 \ge 2$, which is visibly impossible for a non-negative $y_2$; the two shaded regions on the right, one for each dual constraint, do not overlap anywhere in the quadrant, and this one inequality is why.

The ray is a certificate. Someone who claims a program is unbounded can prove it by handing over a single feasible point and a single direction; anyone can check both in a few multiplications, and the same numbers then prove the dual empty. Solvers report unboundedness exactly this way, and in practice an unbounded program almost always means a constraint has been left out of the model — a price with no ceiling, a quantity with no supply.

An empty program, and the dual that runs away #

The mirror image is a program with no feasible point at all.

The two constraints on the left ask for the sum of the coordinates to be at most two and at least four. Nothing does both, and the proof is to add them: with weights $1$ and $1$, the left sides cancel to nought and the right sides add to $-2$, giving $0 \le -2$. That combination is a certificate of emptiness, exactly as the ray was a certificate of runaway.

It is also a direction in the dual. The dual’s feasible region is the wedge on the right, and moving along $(1, 1)$ keeps every dual constraint satisfied — the combination cancels the variables, so it changes nothing the constraints can see — while the dual objective $2y_1 - 4y_2$ falls by two per step. The weights that prove the program empty are a direction in which the dual falls for ever. That is the symmetry the table shows as two equal counts of 1,589: the two failure modes are each other’s reflections, and the certificate for one is the ray for the other.

The statement that one of these two things always happens — either the program has a feasible point, or there is a non-negative combination of its constraints reading $0 \le$ something negative — is Farkas’s lemma, from 1902. It is the whole content of the theorem in its emptiest form, and it is the version the proof of strong duality actually uses.

Both sides empty #

The last occupied cell is the strangest, because it is the one where duality gives no information whatever.

The program asks $x_2$ to be at least one more than $x_1$ and at least one less; the dual asks the same of its own variables. Both are empty, and each has its own certificate of emptiness. Nothing runs away, because there is nowhere to run from.

This case matters for how the theorem is stated. It is tempting to say “the program has an optimum if and only if its dual does”, which is true, and to conclude that an empty program must have a runaway dual, which is false. Emptiness on one side leaves the other side two options, runaway or empty, and which one happens depends on the objective of the empty side — which the empty side’s own emptiness says nothing about. The 427 programs in the table’s corner are exactly those in which the objective chosen for the program also leaves its dual empty.

Which objectives run away #

The runaway case depends on both the region and the objective, and fixing the region shows how the two interact.

The region is fixed and the objective is turned round a full circle. For seventeen of the thirty-two directions the program runs away; for fifteen it has an optimum. The dividing line is the wedge of escape directions, which runs from $(2, 1)$ to $(1, 1)$: an objective runs away exactly when it makes an acute angle with some direction in the wedge. And, checked direction by direction, the objectives that run away are exactly the objectives whose dual is empty — seventeen out of seventeen, with no exception in either direction.

That is Farkas’s lemma again, this time in the space of objectives. The dual is feasible for $c$ exactly when $c$ can be written as a non-negative combination of the rows of $A$ minus something non-negative, and that set of $c$ is the cone of directions making an obtuse or right angle with every escape direction. Two cones, one of escape directions and one of objectives that do not escape, each the other’s polar — the same pairing of a convex shape with the set of lines that support it that the function seen from its tangents builds for curves. A feasible, unbounded region has a whole range of objectives with no optimum, and the range is determined by the region’s shape at infinity and nothing else.

The same shape of proof, elsewhere #

The certificates in these figures have a shape that recurs all over this subject, and seeing it once makes it recognisable everywhere. A claim that something exists is proved by exhibiting it. A claim that something does not exist looks as though it needs an exhaustive search — and the theorem here says it never does: there is always a small object on the other side whose existence rules the first thing out.

Hall’s theorem is the same statement for matchings. Either every person can be assigned a task, or there is a group of people whose acceptable tasks, taken together, are too few — one bottleneck set, checkable at a glance, instead of a failed search through every assignment. Max-flow min-cut is the same statement for networks: a flow is proved as large as possible by exhibiting a cut of equal capacity, and both are what the duality theorem gives when the linear program is a network. In both cases the certificate of impossibility is the dual’s optimal solution, and in both cases the theorem is a special case of the one drawn here.

The pattern even reaches logic. A failed search is a proof found that a set of clauses with no satisfying assignment always has a refutation — a derivation of the empty clause — so that unsatisfiability, a statement about every assignment, has a finite witness. The difference is one of size. A Farkas combination has one weight per constraint, a refutation can be exponentially long, and the gap between those two is roughly the gap between problems that linear programming solves and problems nobody knows how to solve quickly.

And it reaches games. The value from both sides met the minimax theorem, where each player’s guaranteed payoff is a certificate that the other cannot do better. That is the duality theorem for a program whose constraints are a payoff table, and it inherits the four cases: a game always has a value, because both of its programs are always feasible and bounded — which puts every finite zero-sum game in the table’s top-left cell by construction.

What exhaustion can and cannot say #

The table checks the theorem on every program of one small size and finds no exception. That is a strong check of one kind and a weak one of another.

It is strong because nothing was chosen. A theorem confirmed on hand-picked examples is confirmed on the examples its author thought of; this one is confirmed on every program with two variables, two constraints and coefficients from $\{-1, 0, 1\}$, including thousands of degenerate ones with zero rows, parallel constraints and ties. Any mistake in the statement would have to avoid all of them.

It is weak because the programs are tiny. With two variables every region is a polygon and every escape cone is a wedge, and the arguments that fail in higher dimensions — where a region can have faces of every dimension and an unbounded region can escape along a face rather than a ray — have no room to fail here. The theorem is true in every dimension, and the proof that it is has no picture: the separating-hyperplane argument works in any number of variables and is exactly as short in a thousand as in two.

The counts themselves carry information worth noticing. Almost half the programs, 2,956 of 6,561, have an optimum. The two failure modes are exactly as common as each other, 1,589 each, a symmetry that is the table’s picture of the dual of the dual being the original program. And about one program in fifteen is empty on both sides — not a curiosity at the edge of the theory but a common outcome among small random programs.

How near the cells lie to one another #

The four cells look like four separate kinds of program. They are much closer than that, and a single number can move a program from one to another.

Take the empty program of the third figure, $x_1 + x_2 \le 2$ and $x_1 + x_2 \ge 4$, and lower the $4$. At $4$, $3$ or $2.5$ the program stays empty and its dual runs away. At exactly $2$ the region is suddenly a segment — every point with $x_1 + x_2 = 2$ — and the program has an optimum; so does the dual, and they agree. Below $2$ the region is a band between the two lines, and the optimum stays. The program crossed from the bottom-middle cell to the top-left one at a single value of the data, and at that value the region had no interior at all.

That is typical. The boundaries between the cells are where regions become too thin to have an inside, or where an objective lines up exactly with an escape direction, and a program sitting on such a boundary can be pushed into either neighbouring cell by an arbitrarily small change in its numbers. The both-empty cell is the most fragile of all: its programs are empty on both sides, and nudging the right-hand sides or the objective can open either side up. For the prices of what a constraint is worth and a price for every person and task, this is the edge of meaning: a price exists while both sides have optima, and near the boundary of that cell the price can grow without limit as the dual’s optimum runs off towards the direction that would make it unbounded.

What the pictures cannot show #

Unboundedness on the page. Every region is drawn inside a box, and a region that runs away is cut off at the edge. The shaded region in the unbounded figure has no outline along the top and right precisely because those edges are the box’s, not the region’s — but a reader could still take the drawing for a bounded polygon. That the region really does continue for ever is the arrow’s claim, and it rests on the algebra of the escape cone rather than on anything visible.

Why strong duality holds. Weak duality is drawn, in a sense: every figure where both sides are feasible shows the primal values below the dual ones. Strong duality — that the gap closes to nothing — is checked in 2,956 cases and not explained. The explanation is a separating line between a point and a convex set, and it has no two-variable picture that shows more than the special case.

The size of the certificates. Here the certificates are tiny — weights of $1$ and $1$, a ray of $(1, 1)$. For a program with thousands of constraints, a certificate of emptiness is a combination of thousands of rows with carefully balanced weights, and finding it is as hard as solving the program. The figures make certificates look like observations; in general they are the output of a computation.

Still open: deciding which case holds, in a number of steps set by the shape #

Deciding which of the four cells a program falls into is the same problem as solving it, and linear programs can be solved in time polynomial in the number of digits needed to write them down — the ellipsoid method of 1979 and the interior-point methods after it established that. Whether they can be solved in a number of arithmetic operations bounded by a polynomial in the number of variables and constraints alone, with no dependence on how large the coefficients are, is not known. It is the question of a strongly polynomial algorithm for linear programming, which Stephen Smale listed in 1998 among the mathematical problems for the next century.

For some special families — programs whose constraint matrices have small entries, network flow problems, programs with two variables per inequality — strongly polynomial methods exist. For general linear programs, the four-case classification this essay drew by exhaustion on a two-by-two table has no known procedure whose running time depends only on the size of the table and not on the numbers written in it.

Four cases, and the certificate that decides each #

The duality theorem in full is a list: both sides optimal and equal; one side running away and the other empty; both empty. Weak duality — a single chain of two inequalities — rules out three of the five impossible pairings, and strong duality rules out the other two.

Each failure carries its own proof. A runaway program is proved runaway by one point and one direction, and the direction proves its dual empty. An empty program is proved empty by one combination of its constraints, and the combination is a direction along which its dual runs away. The two failures are reflections of each other through the dual, and the table’s two equal counts of 1,589 are what that reflection looks like when every small program is counted.