Convex Functions

f'' ≥ 0 means every chord sits on or above the graph. The unifying notion of optimization.

The idea

A convex function is one whose graph curves upward everywhere, like a bowl. Convexity is central to optimization because every local minimum of a convex function is a global minimum.

To state "curves upward" precisely, pick two points on the graph and join them by a straight segment, the chord. As $\lambda$ runs from $0$ to $1$, the input $\lambda x + (1 - \lambda) y$ sweeps from $y$ to $x$; there the graph has height $f(\lambda x + (1 - \lambda) y)$, while the chord has height $\lambda f(x) + (1 - \lambda) f(y)$, the same blend of the endpoint heights. Convexity says the graph never rises above the chord.

Definition (Convex function).

A function $f$ is convex when, for all $x, y$ in its domain and all $\lambda$ in $[0, 1]$, $f(\lambda x + (1 - \lambda) y) \leq \lambda f(x) + (1 - \lambda) f(y).$ It is concave when the reversed inequality holds, equivalently when $-f$ is convex.

For a twice-differentiable $f$ there is a cheaper test.

Proposition (Second-derivative test).

A twice-differentiable function $f$ on an interval is convex if and only if $f'' \geq 0$ throughout the interval, and concave if and only if $f'' \leq 0$.

The test holds because $f'' \geq 0$ says the slope never decreases, and a graph whose slope never decreases cannot rise above any of its chords.

Ways to work on it

• Walkthrough. The definition, and standard functions classified as convex or concave.
• Practice. Classify a random function as convex or concave.
• Hardest. Determine exactly where a given function is convex.

Not sure where to start? Take the ten-question placement test.