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 5 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 The lowest mode of the regular pentagon. Level lines of the first Dirichlet eigenfunction of a regular 5-gon; λ times area 18.9191.

Three sides and four are proved

Among all shapes of a given area, the disc has the smallest lowest eigenvalue. Among triangles it is the equilateral one, among quadrilaterals the square — both proved by sliding chords to an axis. For five sides the regular pentagon wins every computation, every nudge raises its value by the square of the nudge, and there is still no proof.

geometry · Isoperimetric Two valleys for sixteen charges. N = 16: 92.911655 (48 starts), 92.920354 (12 starts).

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.

geometry · Regular polyhedra

Named alongside it

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

ConvexityOptimisationGradientCentroidComplexityCounterexampleDerivativeEigenvalueEuler characteristicExhaustive searchFixed pointHexagonal packing

All concepts