Two numbers that have to meet

A linear program in two variables is a small object. There is a linear form to be made as large as possible, and there are some inequalities saying where the point is allowed to sit. Maximise $3x_1 + 4x_2$ subject to $3x_1 + 2x_2 \le 12$ and $x_1 + 4x_2 \le 10$, with neither variable negative. The answer is a corner and a number, and the number is $\frac{78}{5}$.

Eight whole numbers were used to ask that: two in the objective, four in the constraint matrix, two on the right-hand side. Read the same matrix down its columns rather than across its rows, exchange the objective with the right-hand side, and turn every $\le$ into a $\ge$. Out comes a different question — minimise $12y_1 + 10y_2$ subject to $3y_1 + y_2 \ge 3$ and $2y_1 + 4y_2 \ge 4$, with neither variable negative. Different sense, different region, different shape, different corner.

Same number.

The second program, built by transposition #

The recipe has no cleverness in it, which is part of what makes the result strange. Write the first program as $\max c^\mathsf{T}x$ subject to $Ax \le b$ and $x \ge 0$. Then its dual is $\min b^\mathsf{T}y$ subject to $A^\mathsf{T}y \ge c$ and $y \ge 0$, and nothing has been supplied that was not already present. The matrix is transposed, the two vectors trade places, and the inequalities reverse.

Applied to the program above, the constraint matrix $\begin{pmatrix} 3 & 2 \\ 1 & 4\end{pmatrix}$ transposes to $\begin{pmatrix} 3 & 1 \\ 2 & 4\end{pmatrix}$, so the dual’s two constraints are $3y_1 + y_2 \ge 3$ and $2y_1 + 4y_2 \ge 4$ — one dual constraint for each variable of the original, one dual variable for each constraint. A program with two constraints and two variables happens to dualise into another with two of each, which is why both can be drawn; that coincidence is an accident of size and not a feature of the construction.

The two pictures do not resemble each other. The first region hugs the origin, because the origin satisfies every $\le$ constraint when the right-hand side is non-negative. The second is a wedge opening away from the origin, because the origin satisfies no $\ge$ constraint with a positive right-hand side. One is bounded and the other runs off for ever upward. One is asked for its largest value and the other for its smallest. The optimum of the first sits at $\left(\frac{14}{5}, \frac{9}{5}\right)$ and the optimum of the second at $\left(\frac{4}{5}, \frac{3}{5}\right)$, and those are points in different planes with different meanings, not two names for one place.

What they share is a number: $12 \times \frac{4}{5} + 10 \times \frac{3}{5} = \frac{78}{5}$, and $3 \times \frac{14}{5} + 4 \times \frac{9}{5} = \frac{78}{5}$.

Neither number can overtake the other #

Half of that is easy, and the easy half deserves stating first because it is what makes the hard half look impossible.

Take any $x$ feasible for the first program and any $y$ feasible for the second. Since $A^\mathsf{T}y \ge c$ and $x \ge 0$, multiplying the first inequality through by the non-negative numbers in $x$ preserves it, so

$$c^\mathsf{T}x \;\le\; (A^\mathsf{T}y)^\mathsf{T}x \;=\; y^\mathsf{T}(Ax) \;\le\; y^\mathsf{T}b \;=\; b^\mathsf{T}y,$$

the last step because $Ax \le b$ and $y \ge 0$. That is the whole calculation. It is called weak duality, it holds for every feasible pair whatever, and it says that every value the maximising program can reach lies below every value the minimising program can reach. The two families of numbers are separated: one set entirely to the left, one set entirely to the right, and a gap in between.

Nothing in that argument suggests the gap is small, let alone absent. Two sets of numbers with one wholly below the other is the ordinary situation, and the ordinary expectation is that they stop short of each other. The number line under the figure above is drawn to make the point: the primal vertex values $0$, $10$, $12$ and $\frac{78}{5}$ are marked below it, the dual vertex values $\frac{78}{5}$, $24$ and $30$ above it, and the two lists creep towards each other from opposite directions. The theorem is that they touch.

Where the regions come from #

Before the meeting can be believed it has to be established that the numbers are right, and this site’s habit is that a picture of a decision is the decision performed rather than a drawing checked afterwards.

A vertex of a polygon cut out by inequalities is a point where two of them hold with equality. So the vertex enumeration forms every pair of constraints, solves each pair as a two-by-two system, and keeps the resulting point exactly when it satisfies all the others. Six pairs are formed here from four constraints — the two written inequalities and the two non-negativity conditions, which are constraints like any other. Two of the six points fail: $(0, 6)$ violates the second constraint and $(10, 0)$ violates the first. Four survive, and the largest objective value over those four is $\frac{78}{5} = 15.6$.

That arithmetic is done in exact rationals throughout, and the reason is visible in the table. The winning point lies exactly on two of the constraints it is being tested against. The test $3 \times \frac{14}{5} + 2 \times \frac{9}{5} \le 12$ is a true statement about rational numbers; the same test in floating point asks whether $11.999999999999998$ is at most $12$ and gets the right answer by luck. A count of feasible vertices that depends on which of those the machine happened to compute is not a report of a decision.

The enumeration is a way of deciding the question by exhaustion, not a proposal about how to solve linear programs. It forms every pair of constraints and throws away the ones that do not work; on a program with fifty variables there would be nothing to form and no way to form it. What it can do is settle a small program completely, and settling a small program completely is what this essay needs. How much work a solver does, and how that work grows, is a question about cost, and cost belongs to another site in this collection; nothing here states a running time.

The same vertex enumeration is run on the dual region, with the sense of the inequalities reversed and the objective minimised instead, and it is the identical piece of machinery: form every pair, solve exactly, keep what satisfies the rest. Both halves of every figure below come out of it.

The vertex list is also checked against something coarser, in the manner of an exhaustive sweep over a finite space: a quarter-unit lattice is laid over the whole box, every feasible point of it is evaluated, and none of the 130 that survive does better than the best corner. That the optimum of a linear form over a convex region is attained at a corner is a theorem; the lattice is there so that the picture is not simply asserting it.

Three more programs, and the same coincidence #

One example proves nothing about a coincidence, so here are three more, chosen to look as different from each other as two-variable programs can.

Here $x_1 + 4x_2 \le 20$ never bites: anything satisfying $x_1 + x_2 \le 4$ satisfies it already. The primal region loses a corner and becomes a triangle, and the dual answers by putting its optimum on an axis, at $(5, 0)$, giving the redundant constraint a price of zero. The two optima are both $20$. A constraint that does nothing is worth nothing, which is a sentence about the dual that could not have been read off the primal picture at all.

This is the case worth staring at. The primal optimum sits at $(0, 8)$ — one variable at zero, the other as large as a single constraint allows. The dual optimum sits at $(5, 0)$ — again one variable at zero, but a different one, in a different plane, on a different region, reached by minimising rather than maximising. The two corners have nothing in common as points. Both programs are worth $40$.

And here the primal has a tie — two of its corners are worth $5$ apiece — while the dual has no tie at all, three distinct vertex values, and an optimum at a point with fractional coordinates. The structures of the two vertex lists do not match. The top of one list and the bottom of the other do.

Four programs, four pairs of pictures with no visible family resemblance, and in every case the largest number one region can produce is the smallest number the other can produce. That is not what two lists of numbers separated by an inequality usually do.

Why the equality is not obvious #

It is worth being precise about how much of a jump the second half is, because familiarity flattens it.

Weak duality is a chain of two inequalities and takes one line. Strong duality — that the maximum and the minimum are equal whenever the first program has a feasible region and a bounded objective — is not a chain of anything. It is an existence claim: there is a feasible $y$ achieving the primal’s value. Proving it means producing that $y$, or proving it cannot fail to exist, and the standard route does the latter.

The route is a separating argument. If no feasible $y$ reached the primal value, then a certain system of linear inequalities would have no solution, and a system of linear inequalities with no solution admits a certificate of its own insolubility — a non-negative combination of the inequalities adding up to a contradiction. That is Farkas’ lemma, published in 1902, and geometrically it says a point outside a closed convex cone can be separated from it by a plane. Convexity is doing the work: the same property that makes the region an intersection of half-planes, exactly as the cells of a nearest-point diagram are, is what guarantees the separating plane exists.

The result is therefore an existence proof with no picture in it. It does not exhibit the dual optimum; it shows that a world in which the gap stays open is contradictory. That is the same species of argument as the one that turns two injections into a bijection: there, too, two one-sided comparisons are forced into an equality by a construction nobody would have guessed from either side alone, and the equality is far stronger than the inequalities that produced it.

The history matches the difficulty. The transposed program was written down by John von Neumann in 1947, in conversation with George Dantzig, who had the maximisation problem and no idea it had a shadow. The first published proof came in 1951, from David Gale, Harold Kuhn and Albert Tucker. The gap between noticing the pairing and proving the equality was four years, and the pairing itself is an afternoon’s algebra.

What the drawing settles, and what it does not #

The two halves of the theorem are settled to very different degrees by anything drawn here, and the difference is the point of this section.

Weak duality is checked exhaustively, and only on these programs. For each figure, every feasible primal vertex is tested against every feasible dual vertex — the whole cross product, twelve pairs in the first program, six in the triangle, eight in the third, twelve again in the fourth — and $c^\mathsf{T}x \le b^\mathsf{T}y$ holds in every one. That is a complete check of a finite claim about four particular programs. It is not the theorem, which quantifies over every feasible pair in every linear program, including the infinitely many non-vertex points of these four.

Strong duality is checked as one exact rational identity, four times. In the first program the two optima are both $\frac{78}{5}$; in the others, $20$, $40$ and $7$. Four equalities between rationals, each verified with no tolerance anywhere. Four is not every linear program, and no number of examples would be.

So the drawing settles that the phenomenon is real and reproducible on programs that look nothing alike, and settles nothing at all about why. The theorem’s actual content — that the equality holds for every linear program with a feasible region and a bounded objective — is the separating argument above, and that argument has no diagram. A picture can show that two numbers met. Only a proof can show they had to.

There is a third limit, and it is structural. The dual can only be drawn when the primal has exactly two constraints, because otherwise the dual has more than two variables and is not a polygon in a plane. The primal vertex enumeration has no such restriction:

Ten pairs, one of them parallel — the new constraint $x_1 \le 3$ runs parallel to $x_1 \ge 0$ and the two meet nowhere — and five surviving vertices. The theorem applies to this program exactly as it applies to the others, and its dual is a polyhedron in three-dimensional space that this family declines to project onto a page rather than drawing dishonestly. Counting the faces and corners of such a thing is a separate pleasure, taken up where every corner pays for itself.

The same theorem in a payoff matrix #

Now the connection that makes the equality feel less like a coincidence, because it turns out to have been met before under another name.

Consider a two-player game given by a matrix of payoffs, one player choosing a row and the other a column. The row chooser, being cautious, asks for the mixture of rows whose worst outcome is best — a guaranteed floor. The column chooser, equally cautious, asks for the mixture of columns whose worst outcome is best from the other side — a guaranteed ceiling. The floor can never exceed the ceiling, for a reason that is one line of algebra and is the same line as the weak duality calculation above.

Von Neumann’s minimax theorem says the floor and the ceiling are equal. The cautious player and the cautious opponent, planning independently against a worst case, name the same number. And that theorem is not merely analogous to strong duality: each is a consequence of the other, by a translation that turns the row chooser’s problem into a linear program whose dual is the column chooser’s problem. The minimax value is the meeting point of the figure above, wearing different clothes. The essay one rung across this field writes the same equality in the language of a payoff matrix and computes it there.

That is why von Neumann recognised the dual immediately in 1947. He had proved the minimax theorem in 1928, and Dantzig’s maximisation problem was the same statement in another notation.

Where this duality has already appeared #

The word duality is used on this site for four other things, and this essay joins them rather than starting a fifth usage.

There is the duality of the logical connectives, where swapping every and with every or and negating everything carries true statements to true statements — De Morgan’s laws as a symmetry of the whole system. There is the duality of the Fano plane, where points and lines can be exchanged wholesale and every theorem survives. There is the duality of the regular solids, where the cube’s faces become the octahedron’s corners and the five solids fall into pairs. And there is the duality of the nearest-point diagram and its triangulation, where each is completely determined by the other and neither is prior.

Every one of those has the same shape: two structures, built from the same data by exchanging the roles of two kinds of thing, carrying the same information. That is precisely what a linear program and its dual are — the constraints of one are the variables of the other, and the transposition is the exchange. What is added here is that the correspondence is not merely structural but numerical: the two objects do not just mirror each other, they agree on a number. The other four dualities pair objects; this one pairs objects and then makes them answer the same question identically.

Getting the same number from two arrangements of the same data is also this collection’s oldest trick, the one behind counting a rectangle twice. The difference is that a double count arranges the same objects two ways on purpose, and here the two arrangements were not obviously counting anything in common.

What the meeting point is worth #

Once the two numbers are known to be equal, the dual optimum stops being a curiosity and starts being an answer to a question the primal did not ask.

At the optimum, the slack in a constraint multiplied by that constraint’s dual variable is zero in every row, and there are two different ways for a product to vanish. A constraint with room to spare gets a price of zero. A variable held at zero has a positive reduced cost. The table’s four rows split two and two, and the two kinds of zero are not the same fact. Note that this figure uses a tilted objective, $3x_1 + x_2$, on the same region: at the original optimum both constraints bind and every row would be zero on the same side, showing nothing.

And the dual variable turns out to be a rate. Sweep one right-hand side and re-solve the program at every value, and the optimum traces a piecewise linear graph whose slope on each piece is exactly the dual variable for that constraint. Three pieces here, with slopes $2$, $\frac{4}{5}$ and $0$, breaking where a different vertex takes over — which is the same event as the dual solution jumping, seen from the other side. Above $b_1 = 30$ the constraint has stopped mattering and one more unit of it is worth nothing at all.

That is where this anchor goes next. The equality proved here is the fact that makes those readings legitimate; what a constraint is worth is the essay that takes them seriously, and it needs the meeting point to exist before it can ask what the meeting point means. The bound is the easy half. The theorem is that there is no room left between the halves — and the strangeness of that never quite wears off, however many pairs of polygons are drawn.