Matpic
mathematics, in pictures
Concept

Optimisation

Finding the value of a variable that makes a quantity as small or as large as possible, subject to constraints. Whether it is tractable turns almost entirely on convexity, which decides not how fast an answer is found but whether a found answer can be recognised.

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

A cheapest assignment, and the proof that it is cheapest. A 4 by 4 cost table with the cheapest assignment marked, and a row price and column price beside each. Every used cell's two prices add to its cost, and the prices total the assignment's cost.

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.

applied · Assignment A line under every point of x². The curve x² with 4 tangent lines drawn, each extended across the whole interval and each staying below the curve throughout.

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.

analysis · Convexity x² and its conjugate. Two panels: the curve x² with tangent lines of several slopes, and the conjugate function plotted against slope, whose value at each slope is the intercept of the corresponding tangent.

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.

analysis · Convexity One minimum, or several. Two curves side by side with their local minima marked: a convex one with a single minimum, and a fourth-power well with 2.

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.

analysis · Convexity

Named alongside it

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

ConvexityDualityGradientLocal minimumSupporting lineAlgorithmAssignmentCertificateComplementary slacknessComplexityConjugateCounterexample

All concepts