Matpic
mathematics, in pictures
Concept

Local minimum

A point at which a function is no larger than at every nearby point. For a convex function there is only one such value and it is the global minimum; without convexity a local minimum can be arbitrarily worse than the best, and nothing local tells them apart.

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

A scatter walking towards its own centres. 4 panels of the same 24 sites: the initial clumpy scatter and the Voronoi diagram after 1, 3, 12 rounds of Lloyd's iteration, with the cost falling to 52% of the scatter's as the cells even out.

Every site in the middle of its own cell

Move each point to the centre of mass of its own Voronoi cell, then redraw the diagram, then do it again. The rule is two lines long, it never mentions hexagons, and what it settles into is a honeycomb.

geometry · Voronoi 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 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.

ConvexityGradientOptimisationCentroidComplexityCounterexampleDerivativeFixed pointHexagonal packingInequalityIterationQuantisation

All concepts