Convexity: recognising convex functions and sets

The idea

A problem is convex when its bowl has no second dip: every valley you can walk into leads to the same lowest point. That is why convex problems are the ones a solver can finish with a guarantee. So the first question about any model is: is it convex? You do not need to test it from scratch; a short list of building rules answers it.

The math, with a comment on each formula

A set C is convex if the straight segment between any two of its points stays inside it: x, y \in C,\; 0 \le \theta \le 1 \;\Longrightarrow\; \theta x + (1-\theta) y \in C . In words: a disc is convex; a ring (a disc with a hole) is not, because a segment can cross the hole.

A function f is convex if its graph never rises above the chord between two points: f\bigl(\theta x + (1-\theta) y\bigr) \le \theta f(x) + (1-\theta) f(y). In words: the value at a blend of two points is at most the blend of their values.

The rules you use in practice:

In words: build the model from these pieces and it is convex; every local minimum is then the global minimum.

Worked example

Take f(x) = (x-3)^2 + 2|x|: a convex square plus twice a convex absolute value, so it is convex by the rules. The kernel solved it (status optimal):

minimize (x - 3)^2 + 2*abs(x)

The lowest point is at x = 2 with value 5. Because the function is convex, no other valley exists to check. A second convex example, e^{x}+e^{-x} (a sum of two convex functions), has its minimum value 2 at x = 0.

Try it

Is x^2 + |x-2| convex? Yes: a square plus an absolute value of a linear expression. Solve it:

minimize x^2 + abs(x - 2)
# x = a real number

The minimum is 1.75 at x = 0.5. Now try x^2 - |x-2| in your head: subtracting a convex function is not one of the rules, and the graph has a downward-pointing kink at x=2, so it is not convex.