Linear Algebra
16.88 min read

Convex Functions

A function ff defined on a convex domain CC is convex if for any two points u,v∈C\mathbf{u}, \mathbf{v} \in C, the function value at any intermediate point is at most the corresponding linear interpolation of the endpoints.

Geometrically: draw the chord (line segment in the graph) between any two points on the graph of ff. For a convex function, the chord always lies above or on the graph. The function's graph "bows downward from the chord" — or equivalently, "curves upward."

A strictly convex function has the chord strictly above the graph at interior points — a unique bowl shape. A linear function f(x)=ctxf(\mathbf{x}) = \mathbf{c}^t \mathbf{x} is convex but not strictly so (chords lie on the graph exactly).

For quadratics: f(x)=12xtMxf(\mathbf{x}) = \frac{1}{2}\mathbf{x}^t M \mathbf{x} is convex iff MM is PSD, and strictly convex iff MM is PD. This connects back to everything we know about definiteness.

Formal View

Definition 16.6 — Convex Function
A function ff over convex domain CC is convex if for all u,v∈C\mathbf{u}, \mathbf{v} \in C and t∈(0,1)t \in (0,1):
f((1−t)u+tv)≤(1−t)f(u)+tf(v)f((1-t)\mathbf{u} + t\mathbf{v}) \leq (1-t)f(\mathbf{u}) + tf(\mathbf{v})
It is strictly convex if the inequality is strict (for u≠v\mathbf{u} \neq \mathbf{v}).
Theorem 16.5 — Convexity and Global Minima
Let ff be a differentiable convex function over convex domain CC. If x0\mathbf{x}_0 is a critical point, then x0\mathbf{x}_0 is simultaneously a local and global minimum. If ff is strictly convex, x0\mathbf{x}_0 is the unique global minimum.

Why This Matters

Convexity is the key property that makes an optimization problem tractable — local search (gradient descent) is guaranteed to find the global optimum.

  • Least squares regression: convex quadratic, unique global minimum
  • Lasso and Ridge regularization in ML: convex objectives
  • Portfolio optimization: convex quadratic objective with linear constraints
  • Support vector machines: convex optimization at their core

Quiz

Question 1

A quadratic f(x)=12xtMxf(\mathbf{x}) = \frac{1}{2}\mathbf{x}^t M \mathbf{x} is convex if and only if:

Question 2

The sum of two convex functions is convex.

Question 3

For a strictly convex differentiable function, how many critical points can it have?

Question 4

A convex function can have local minima that are not global minima.

Question 5

Is a linear function f(x)=ctxf(\mathbf{x}) = \mathbf{c}^t \mathbf{x} convex?

Common Mistakes

  • Thinking "convex function" means the graph is bowl-shaped (that's strictly convex) — linear functions are also convex.
  • Confusing a convex function with a function defined on a convex set — these are separate concepts.
  • Assuming convexity means the function has a global minimum — there might be none if the domain is unbounded.