Matpic
mathematics, in pictures
Concept

Linear program

The problem of making a weighted sum as large or as small as possible subject to finitely many straight-line inequalities. Its optimum is always at a corner of the feasible region, which is what makes searching corners a complete method.

Named by 14 essays across 3 fields — each of them below, with the objects they name alongside it.

Two polytopes, two optima, one number. The feasible regions of a linear program and of its dual, side by side, each with its optimal vertex, and a number line on which the gap between the two optima closes to nothing.

Two numbers that have to meet

Every linear program has a shadow — a second program built from the same numbers read the other way, whose minimum can never fall below the first's maximum. That much is a one-line calculation; the theorem is that the two numbers are always exactly equal.

applied · Duality What one more unit of constraint 1 is worth. The optimum of a linear program plotted against one of its right-hand sides, as an exact piecewise linear graph, with the breakpoints marked and each piece's slope named as a dual variable.

What a constraint is worth

A linear program and its dual reach the same number. What the dual's variables are is a separate question, and the answer converts a solution into a rate for every constraint — piecewise constant, zero on the constraints that are not doing any work.

applied · Duality The value of a 2×3 zero-sum game, named from both sides. The row chooser's expected payoff against each column as a line over the mixing probability, with the lower envelope and its maximum, beside the same construction from the column chooser's side. Both give 19/15.

The value from both sides

Two choosers move at the same instant, and each asks the cautious question — how much can be guaranteed, whatever the other does. With pure choices the two answers are usually different numbers; allow a probability and they are forced to be the same one.

applied · Equilibrium A table of shares written as a lottery over 3 whole assignments. A doubly stochastic table of shares, and beneath it the permutation matrices and weights that add up to it exactly, each drawn as a grid with one marked cell per row.

A lottery over whole assignments

A table of shares in which every person's shares add to one task and every task is exactly covered is never anything more than a mixture of whole assignments — and finding the mixture is a matter of taking one complete assignment out at a time.

applied · Assignment A signal both can see, and neither wants to disobey. A two-by-two game with a distribution over its four cells, drawn as the weight on each. Obeying the recommendation is a best reply for both choosers, and the pair collects 21/2 between them.

A signal both can see

Two choosers who randomise privately can reach a set of outcomes that is smaller, and worse, than the set they reach when a device draws one cell and whispers each of them their half of it. Nothing is enforced and nobody is bound, and the arrangement is stable anyway.

applied · Equilibrium Three pairs of places sharing one hub. A hub with three spokes of capacity one, the three pairs of outer places each routing half a unit through it, beside the total that can be sent fractionally, in whole units, and the cost of the cheapest set of roads separating every pair.

When several pairs share the roads

For one pair of places, the most that can travel between them equals the cheapest cut that separates them. Give three pairs a hub of three roads to share and the two numbers come apart: the pairs can send 3/2 between them, while separating every pair costs 2. Two pairs still meet their cut, but only by splitting units in half.

discrete · Network flow Five certificates against any two of three decide. A table of every minimal balanced family on three players, what each demands of the game, and whether the grand coalition's value covers it — the complete test for whether a stable split exists.

Five weighings and the question is closed

Searching the triangle of splits can only ever fail to find a stable one, which is not the same as there being none. Weighing five families of coalitions against the whole settles the question outright — and the family that fails is the proof that nothing survives.

applied · The core The most mass 2 deviations out, with only a mean and a variance. The distribution putting as much probability as possible outside a window 2 standard deviations wide, found by searching every triple of support points, with the quadratic certificate that bounds it drawn over.

The bound is the answer to a search

Chebyshev's inequality is not a clever estimate that happens to be sharp. It is the exact answer to a maximisation over all distributions with a stated mean and variance, and the polynomial that proves nothing beats it is the certificate a search of that kind always produces.

probability · Concentration The duality theorem's four cases, counted over 6,561 small programs. A three-by-three table crossing the status of a linear program — optimal, unbounded or infeasible — with the status of its dual, counting every small program with coefficients from minus one to one. Five of the nine cells are empty.

When one of the two numbers is missing

The duality theorem is usually quoted as an equality: a linear program and its dual reach the same number. That is one of four cases. A program can run away to infinity, or have no feasible point at all, and then its dual is forced into a matching failure. Every small program with coefficients from minus one to one has been classified, and the table has exactly four occupied cells out of nine.

applied · Duality The optimum as the lowest of 3 lines, one per dual vertex. The optimal value of a linear program plotted against one right-hand side, drawn over a family of straight lines, one for each vertex of the dual feasible region. The optimum follows the lowest line throughout.

The lines the optimum lies under

Change the resources a linear program is given and its best value changes too, tracing a graph. Every solution of the dual is a straight line lying above that graph, and the graph is exactly the lowest of those lines — a bent roof of finitely many planks. Require the answer to be in whole numbers and the roof stays where it was while the graph falls away beneath it in steps, and the space between is the part of the problem no price can see.

applied · Duality Three places cut apart for 13. A network of eight places with road capacities, three of them lettered, coloured by which of the three sides of the cheapest three-way cut each place falls on, with the cut roads dashed.

Three places cut apart

Separating two places as cheaply as possible is solved exactly by a flow. Separating three from one another is a different problem: no flow measures it, the pairwise answers do not add up to it, and the best shortcut known in 1994 — cut each place off on its own and throw the dearest cut away — is guaranteed only to within a third of the truth.

discrete · Network flow The cheapest way to send 4 units, for 25. A directed network from s to t with a capacity and a price on each road, showing the whole-number flow of 4 units with the least total cost, the arrows thickened by the amount they carry.

The cheapest way to send

Put a price on every road as well as a capacity and ask for the cheapest way to send four units. Twenty-eight ways exist and one is cheapest, and two certificates prove it without comparing it with the other twenty-seven: no cycle of roads it leaves unused costs less than nothing to push round, and there are prices at the places that every usable road fails to beat.

discrete · Network flow 3 moves along the edges to the corner that maximises 2x₁ + 3x₂. The simplex method on a two-variable program with 5 constraints, started at the origin. It visits (0, 0), (0, 8), (1, 8), (5/2, 15/2), with objective values 0, 24, 26, 55/2, and stops where the prices on both binding constraints are non-negative.

Prices at every corner

The duality theorem says a linear program's best value equals its dual's, and says nothing about how to find either. The simplex method finds both at once — it walks from corner to corner, and at each one asks the constraints that meet there for prices. A negative price names an edge that climbs; when none is negative, the prices are the proof.

applied · Duality Eight corners of a squashed cube, visited in order by the simplex method. Klee and Minty's program in 3 variables drawn as its own deformed cube and as a plain one. The simplex method with the largest-price rule visits all 8 corners, with objective values 0, 4, 6, 10, 15, 19, 21, 25; the optimum is one edge from the start.

The cube that takes every corner

The simplex method is fast on every program anybody meets in practice. In 1972 Victor Klee and George Minty squashed a cube so that the method, choosing the steepest edge each time, visits all of its corners — 2ⁿ − 1 moves in n variables, with the optimum one edge from the start.

applied · Duality

Named alongside it

The objects these essays reach for when they reach for this one.

DualityConvexityCertificateExhaustive searchExistence proofShadow priceFeasible regionFlowComplementary slacknessCorrelated equilibriumCounterexampleCut

All concepts