Optimisation
Named by 18 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.
What a junction can save
Join a set of towns by roads that may meet only at towns, and the shortest such network is easy to find. Allow junctions anywhere and the network gets shorter — but never, it is conjectured, by more than 13.4%, the saving the Fermat point makes on an equilateral triangle. Computed exactly on 1,304 random sets of up to seven towns, the average saving is about 3%. An adversarial search drives it down to the bound and no further, and a hexagon with its centre attains it exactly. The proof of the bound that was accepted for twenty years has a gap.
A cube through a hole in a cube
Prince Rupert of the Rhine bet that a hole could be cut through a cube large enough for an equal cube to pass through it, and won. The trick is to look at the cube along a direction near its long diagonal, where its shadow is a hexagon wide enough to hold a square face with room to spare: a cube 6% larger can pass. All five Platonic solids turn out to have such a passage, found by searching over the directions from which a solid is seen — and in 2025 a solid was found that has none.
Where charges settle on a sphere
Put equal electric charges on a sphere and let them push each other apart until nothing moves. Four settle at the corners of a tetrahedron, six of an octahedron, twelve of an icosahedron — but eight do not make a cube, and twenty do not make a dodecahedron. The cube loses to two squares turned half a corner apart, because charges on a sphere prefer triangles; and however many charges there are, exactly twelve more of them have five neighbours than have seven.
The largest polygon of diameter one
Among pentagons whose points are never more than one unit apart, the regular pentagon has the most area, and the same is true for every odd number of sides. For six sides it is false: a lopsided hexagon found in 1975 beats the regular one by four per cent. Symmetry wins half the cases and loses the other half, and the reason is parity.
Valleys a search cannot count
Let equal charges on a sphere push each other apart from a random start, and they settle into an arrangement where nothing moves. Up to fifteen charges every start settles into the same one. Sixteen is the first number with two, a hundredth of a unit apart in energy; by fifty-two there are at least four, and for fifty-six charges only one start in ten finds the lowest. The other valleys sit a few parts in a million above it, and nothing in the arrangement a search returns says whether it is the bottom.
A chain of tetrahedra saves more
In the plane, junctions never seem to shorten a network of roads by more than the equilateral triangle's 13.4%. In space the regular tetrahedron allows 18.7%, and the obvious guess — that it is the worst case, as the triangle is in the plane — is wrong. Points spaced along a chain of tetrahedra glued face to face do better with every point added: 20.5% at twelve, 21.4% at sixty, and about 21.6% in the limit. Random points come nowhere near, and a search that only goes downhill does not find the chain.
Named alongside it
The objects these essays reach for when they reach for this one.
ConvexityDualityExhaustive searchLocal minimumSteiner treeTriangulationCertificateComplementary slacknessConjectureCounterexampleEquilateral triangleEuler characteristic