Optimisation
Named by 12 essays across 6 fields — each of them below, with the objects they name alongside it.
A price for every person and task
The cheapest assignment can be found without comparing it to any other. Attach a number to each person and each task so that no pair's two numbers exceed its cost, and if the numbers add to an assignment's total, that assignment is cheapest — proved, by an argument that never mentions the alternatives.
A line under every point
The chord above the curve is one definition of convexity. There is a second — a line under the curve at every point, staying under everywhere — and it is the one that turns a statement about a derivative at a point into a statement about the whole function.
The function seen from its tangents
A convex function is the upper envelope of its own tangent lines, so it can be described by giving, for each slope, how far the line of that slope has to be pushed down. That description is a second function, and applying the construction twice returns the original.
Where the guarantee stops
Convexity converts every downhill method into a correct one, and its absence removes the guarantee entirely rather than degrading it. What is left is a collection of partial answers, and knowing which of them apply to a given problem is most of what non-convex optimisation is.
Moves that only ever add edges
Turán's theorem says the densest graph avoiding a complete graph on r + 1 points is the balanced r-part graph. Zykov's proof finds it by a sequence of moves — turn a point into a copy of a better-connected one it is not joined to — each of which adds edges and none of which can create the forbidden clique. A second proof spreads a unit of weight over the points and gets the same bound from a maximum.
The streets a postman walks twice
A postman must walk every street of a district and come back. If every corner has an even number of streets, no street needs walking twice. If not, some must — and the ones repeated always join the odd corners in pairs. Pricing every way of pairing them finds the shortest round; pairing the nearest corners first does not.
The highest point on the sphere is an eigenvalue
For a symmetric matrix, walk a unit arrow over every direction and record the value of xᵀAx. The highest value reached is the largest eigenvalue, the lowest is the smallest, and every eigenvalue in between is a saddle height, a minimum of maxima. From that one description comes a theorem no formula for the roots could give: delete a row and its column, and every eigenvalue of what is left sits between two of the original's.
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.
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.
How nearly equal an odd number of triangles can be
A square cannot be cut into an odd number of triangles of equal area. It can be cut into five triangles whose areas differ by about two hundredths, seven that differ by three thousandths, nine by a ten-thousandth and a half — the spread falling by a factor of seven or more with every two triangles added, closing on equality and never reaching it. A search for the closest finds that the best five it can make have the golden ratio in their areas.
Three circles that touch and are not the largest
In 1803 Gian Francesco Malfatti asked how to cut three round columns from a triangular block of marble with as little waste as possible, and answered with three circles each touching the other two and two sides. The circles exist in every triangle and are found by solving three equations. They are never the answer to his question: the plain greedy rule — the inscribed circle first, then the largest circle that still fits, twice — always does better, by 1.4 per cent on the equilateral triangle and by almost double on a thin one.
The point nearest in total to three corners
Three towns want one depot with the least total road to all of them. The answer is not the centroid or any of the classical centres: it is the point from which every side of the triangle is seen at 120°, found by building equilateral triangles on the sides. Three straight lines through it have the same length, and that length is the least total. When an angle of the triangle reaches 120°, the answer jumps to that corner — and the same 120° rule shapes soap films and the shortest networks joining many points.
Named alongside it
The objects these essays reach for when they reach for this one.
ConvexityDualityCertificateComplementary slacknessCounterexampleGradientGraphLinear programLocal minimumMatchingSimplex methodSupporting line