A line under every point

The anchor’s first rung defines convexity by chords: the segment joining two points of the graph lies above the graph between them. That is the definition to use when averaging is the operation of interest, and it is the wrong one for almost everything else.

The second definition looks at one point rather than two. At every point of a convex curve there is a line through it that stays below the curve everywhere — not merely nearby, and not merely on one side.

The two definitions are the same #

The equivalence is the first thing to establish and it is short in both directions.

Chords above implies lines below. Fix a point $x_0$ and consider the slope of the chord from $x_0$ to $x$. Convexity makes that slope non-decreasing in $x$ — which is the chord condition restated, and is worth checking once on a picture — so its limits from the left and right at $x_0$ exist and the left limit is at most the right. Any line through $x_0$ with slope between them stays below the curve on both sides: to the right because every chord slope there is at least the line’s, and to the left because every chord slope there is at most it.

A convex function therefore has one-sided derivatives everywhere, whether or not it is differentiable, and they agree except at countably many points. That is a stronger conclusion than the argument seems to be aiming at, and it arrives free.

Lines below implies chords above. Take two points $a$ and $b$ and a point $c$ between them. The supporting line at $c$ lies below the curve at $a$ and at $b$, so it lies below the chord’s endpoints; being a line, it therefore lies below the chord at every point between them, since a line below another line at two points is below it in between. And it passes through the curve at $c$. Hence the curve at $c$ is below the chord, which is the chord condition.

So there are two definitions and one notion, and which to use is a matter of what is being proved. The chord definition is the one for inequalities; the supporting line is the one for optimisation.

Why a local minimum is global #

That is the consequence everything else rests on, and it is one line.

Suppose $x_0$ is a local minimum of a convex function $f$. Take the supporting line at $x_0$: it lies below $f$ everywhere, and it touches at $x_0$. Being a local minimum, $f$ does not decrease near $x_0$, so the supporting line cannot slope — a sloping line through $x_0$ would go below $f(x_0)$ on one side, and then $f$ would have to go below it, contradicting the local minimality.

So the supporting line is horizontal at height $f(x_0)$, and it lies below $f$ everywhere. Therefore $f(x) \ge f(x_0)$ for every $x$, which is what global means.

Notice how much of the work the supporting line does. A local minimum is by definition a statement about a neighbourhood, and the conclusion is about the whole domain; what bridges them is an object that is constructed locally — from the derivative at one point — and valid globally. That is the only kind of thing that can bridge them, and convexity is exactly the condition under which one exists.

What that buys an optimiser #

The consequence is the reason convexity is the dividing line in optimisation, and stating it precisely is worth doing because the usual summary is too strong.

A method that only ever moves downhill is correct on a convex function, in the sense that wherever it stops is the answer — and it stops only where it cannot improve locally, which by the argument above is the global minimum. Gradient descent, coordinate descent, any local search — all of them have the same guarantee, and the guarantee has nothing to do with the method.

On a non-convex function the same methods have no guarantee whatever. They stop at a local minimum, which may be arbitrarily worse than the global one, and nothing local distinguishes the two situations.

And that is a statement about certification, not about speed. The distinction matters because it is what the theorem does and does not promise. A convex problem is not necessarily quick to solve; what it is, is checkable. Where a downhill method stops, the supporting line certifies optimality, and the certificate is available at no extra cost. That is the same trade as a dual solution certifying an assignment, and it is the same reason: an inequality that holds everywhere and is tight somewhere proves an optimum.

Running the check on a second function is worth doing because it is the sort of claim a reader might take to be about the particular curve. It is not: the supporting-line property is equivalent to convexity, so every convex function has it and no other function does, and the figure’s assertion is the same assertion in both cases.

The exponential is worth having as the example for a further reason. It is convex, it is strictly convex, and it has no minimum at all — so it separates three properties that are easy to conflate, and the sections below use it for exactly that.

The certificate in general #

The supporting-line argument generalises immediately and it is worth having in the general form, because that is how it is used.

For a function of several variables, a supporting hyperplane at $x_0$ is a linear function agreeing with $f$ at $x_0$ and lying below it everywhere. Where $f$ is differentiable it is the tangent plane; where it is not — at a kink — there is a whole set of them, and the set of their slopes is the subdifferential.

The condition for a minimum is that zero is in the subdifferential. For a differentiable function that is the vanishing of the gradient; for one with kinks it is a genuinely more general statement, and it is what makes the theory work for functions like the absolute value, which has no derivative at its minimum and is perfectly well behaved. At zero the absolute value has every slope between minus one and one as a supporting slope, and zero is among them, so the condition holds — where “the derivative vanishes” would have nothing to say.

That extension is not a technicality. A great many optimisation problems in practice have kinks — a maximum of several linear functions, an absolute value, a hinge — and the subdifferential is what lets a downhill method be defined and proved correct on them.

What convexity does not give #

Three limits, and the first is the most often forgotten.

It does not make the minimum unique. A convex function can be flat on an interval — a constant is convex — so the set of minimisers is a convex set which may be large. Strict convexity, where chords lie strictly above, gives uniqueness; ordinary convexity does not.

It does not make the minimum exist. The exponential function is convex on the whole line and has no minimum. Existence needs a further condition — that the function grows at infinity, or that the domain is closed and bounded — and it is a separate argument.

It does not survive most operations. A sum of convex functions is convex and a product of them need not be; a composition of convex functions need not be; a difference of them almost never is. That is why the closure rules below are a short list rather than a general principle, and why a formula’s convexity has to be established rather than assumed from its ingredients.

And it does not make the problem easy. A convex problem in a million variables is still a million variables, and convexity guarantees that a local answer is right without saying how long it takes to find one. What it removes is the risk of being wrong, not the cost of being slow.

The inequality machine, run the other way #

The supporting-line definition is not only for minima. It generates inequalities, and the generation is mechanical enough to be worth stating as a procedure.

Take any convex $f$ and any point $x_0$. The supporting line gives

$$f(x) \ge f(x_0) + f'(x_0)(x - x_0)$$

for every $x$ — a valid inequality for every choice of $x_0$, of which there are as many as there are points.

Choosing $x_0$ well is the whole art. Take $f = -\log$, which is convex, and $x_0 = 1$: the inequality becomes $-\log x \ge -(x-1)$, that is $\log x \le x - 1$, which is the workhorse inequality of information theory and of half the proofs in probability.

Take $f(x) = e^x$ and $x_0 = 0$: it gives $e^x \ge 1 + x$, which is the estimate every bound on a product of probabilities uses.

Each is one supporting line at one well-chosen point, and there is no cleverness in either beyond the choice. That is a fair description of how a great many standard inequalities are actually obtained, and it is why recognising a function as convex is worth so much: it converts an inequality one might have to invent into one that can be read off.

Recognising convexity #

Since the whole value is in the property holding, it is worth knowing how it is established, and there are three routes.

The second derivative. A twice-differentiable function of one variable is convex exactly when $f'' \ge 0$; of several, exactly when the matrix of second derivatives is positive semidefinite everywhere. That is checkable and is the standard method for a formula — though “positive semidefinite everywhere” is itself a condition on a matrix at every point, and verifying it can be harder than the original question.

Closure under operations. Sums of convex functions are convex; maxima of convex functions are convex; a convex function of a linear function is convex; a non-decreasing convex function of a convex function is convex. Almost every convex function met in practice is built from a short list of basic ones by those four rules, and recognising it means recognising the construction rather than differentiating anything. That is how modelling software decides: it tracks the construction and refuses a formula it cannot certify.

And the supporting-line test itself, which is what the hero figure performs. For a function given by data rather than a formula it may be the only route, and it is what a numerical check does.

What is not a route is looking at the graph. A function can look convex over the range plotted and fail outside it, and in several variables there is no graph to look at. Convexity is established, never observed.

Where the dividing line actually is #

“Convex problems are easy and non-convex ones are hard” is the standard summary, and it is worth refining because both halves are wrong in specific ways.

Some convex problems are hard. Semidefinite programming is convex and its worst cases are expensive; convex optimisation in a very high dimension can be intractable for reasons of size alone. Convexity removes the risk of a wrong answer, not the cost.

And some non-convex problems are easy. Minimising a function over a sphere, finding the largest eigenvalue, factoring certain matrices — all are non-convex and all have efficient exact methods, obtained by understanding the specific structure rather than by any general principle.

What convexity really provides is a guarantee that transfers. Any method that improves locally is correct, whatever it is, without a separate argument. For a non-convex problem each method needs its own analysis, and most methods have none.

That is why the practical advice — reformulate a problem to be convex if possible — is good advice. Not because the convex version will be quicker, but because it will be checkable, and a computation whose answer cannot be checked has to be trusted instead.

What the pictures cannot show #

One variable is not the case of interest. Every figure here is a curve in the plane, and the theorems are about functions of many variables where the supporting object is a hyperplane and there is no picture. The one-dimensional case is where the argument can be seen and not where it is used.

A tangent is drawn as a segment. It is a line, and the claim is that it stays below the curve everywhere — including outside the frame. The figure checks four hundred points across the plotted interval and the claim is about the whole domain.

The local-minimum comparison uses a sweep of thousands of points, which is not how a minimum is found. The figure locates the minima by examining every point of a fine grid, which is a method available only in one variable on a bounded interval. What it illustrates is the conclusion of the argument, and the argument’s value is precisely that it holds where no sweep is possible.

And the subdifferential has no figure. At a kink there is a set of supporting slopes, which would be a fan of lines through one point; drawing it needs a function with a kink, and every function in this family is smooth.

Where the ladder goes next #

The next rung takes the supporting lines seriously as data rather than as certificates: a convex function is determined by its family of tangents, and describing it that way is a transform with a life of its own.

Named here as a debt: the subdifferential proper, described above and not drawn, which is the object that makes the theory apply to the functions with corners that most practical problems produce.

Sideways, the chord definition is the anchor’s first rung, the tangent that approximates a function near a point is Taylor’s — and the contrast is instructive, since Taylor’s tangent is an approximation valid nearby while this one is a bound valid everywhere. The certificate that proves an optimum without examining alternatives is the same device an assignment’s prices are, and the isoperimetric problem is an optimisation whose convexity is what makes the answer unique.

That figure is worth reading with the previous section in hand, because the classical presentation conceals what is happening. The arithmetic–geometric mean inequality is usually proved by an ingenious induction, or by a rearrangement, or by a clever substitution. It is also a supporting line at one point of the logarithm, and once that is seen the proof is a substitution and the ingenuity is unnecessary.

A great many named inequalities are one supporting line each. Cauchy–Schwarz, Hölder, Young, the entropy bound, Markov’s — each has a convex function and a point behind it, and finding the pair is usually easier than reconstructing the classical argument.

Sideways: the most area a fence can hold is an optimisation whose answer this machinery certifies, and where the guarantee stops is what happens to all of it when the function is not convex.

What is worth carrying away #

The useful definition of a property is the one that makes the theorem one line, and a property worth having usually has several definitions.

Convexity by chords is about averages, and Jensen’s inequality is its theorem. Convexity by supporting lines is about points, and “a local minimum is global” is its theorem — one line, given the definition, and unavailable from the chord definition without first proving they agree.

The habit worth taking is to collect a property’s equivalent definitions before using it. They are not interchangeable in practice: each makes a different theorem trivial, and choosing the wrong one turns a one-line argument into a page.

There is a practical corollary in that. When a proof of a convexity fact stalls, the first thing to try is not a harder argument but the other definition — the chord version if the tangent version has stalled, and the other way round. On this rung the two definitions were proved equivalent, which means that move is always available and costs nothing.