Matpic
mathematics, in pictures
Ladder

Convexity — the ladder

6 distinct arguments against one idea, from the one that introduces it to the one that assumes the rest.
  1. A chord of x², and the curve under it. The curve x² with one chord drawn across it, the region between them shaded, and the midpoint heights of both marked. The comparison is computed at four hundred sample points.

    The curve of the average, and the average of the curve

    A curve that bends upwards keeps every one of its chords above it. That single fact, applied to a weighted average instead of a midpoint, turns into an inequality that produces the arithmetic–geometric mean inequality, Cauchy–Schwarz and the entropy bound as special cases.

    rung 1 · analysis
  2. 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.

    rung 2 · analysis
  3. 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.

    rung 3 · analysis
  4. 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.

    rung 4 · analysis
  5. Every point of a hull, as a mixture of three of 11 points. A scatter of points with its convex hull outlined, and several interior points each shown inside a triangle of three of the scattered points, found by trying every triple.

    Three points, however many there are

    A point inside the hull of a thousand points is inside the hull of three of them. Any four points split into two groups whose hulls meet. And a family of convex sets, every three of which have a common point, has one common to all — three, in each case, being one more than the dimension.

    rung 5 · analysis
  6. Two convex sets 1.50 apart, and the line that separates them. Two convex polygons with a straight line drawn between them, together with the shortest segment joining the two sets, whose perpendicular bisector the line is.

    A wall between two bodies

    Two convex sets that do not meet can be told apart by a single straight line, and the line is a certificate — one object, checkable in a moment, proving something about every point of both. Remove convexity from either and no line exists, which is what the hypothesis was for.

    rung 6 · analysis

All ladders