TheoremProved

Local minima of convex functions are global

Statement

Let $f : C \to \mathbb{R}$ be a convex function on a convex set $C \subseteq \mathbb{R}^n$ . If $x^* \in C$ is a local minimum of $f$ , then $x^*$ is a global minimum of $f$ over $C$ . If $f$ is strictly convex, the global minimum, when it exists, is unique.

Why is it true?

A convex function's graph never dips below the straight line joining any two of its points, so it has no separate 'valleys' — the whole graph curves upward like a single bowl. If you sit at the bottom of a small dip, convexity forces every direction away from you to only go up, and since that holds along the entire straight path to any other point of $C$ , no far-away point can be lower either.

Proof sketch

Suppose $x^*$ is a local minimum but not global: there is $y \in C$ with $f(y) < f(x^*)$ . For $t \in (0,1)$ small, convexity gives $f((1-t)x^* + ty) \le (1-t)f(x^*) + t f(y) < f(x^*)$ . But points $(1-t)x^* + ty$ lie arbitrarily close to $x^*$ for small $t$ , contradicting that $x^*$ is a local minimum. Hence no such $y$ exists.

Topics that use this theorem

Convex optimization

Related theorems

Karush–Kuhn–Tucker conditions Strong duality in linear programming

Step-by-step proofs

No step-by-step proof yet for this theorem.

References

Stephen Boyd, Lieven Vandenberghe (2004). Convex Optimization
R. Tyrrell Rockafellar (1970). Convex Analysis