Convexity

Some regions have no indentations. Pick any two points inside a filled disk and draw the line segment between them. Every point on that segment lies inside the disk. The same is true for filled triangles, rectangles, and half-planes. A crescent fails this test because two interior points can be connected by a line segment that passes outside the crescent. A set that passes the test for every possible pair of its points is called convex. The boundary never curves inward. You can move along a line segment from any point of the set to any other without leaving the set. This property is what makes minimization over such a set, or of such a function, tractable.

The same idea applies to functions. A function $f$ is convex if the chord connecting any two points on its graph never falls below the graph itself. Pick two inputs $x$ and $y$ and any number $t$ between 0 and 1. The point $tx + (1-t)y$ lies on the segment from $y$ to $x$. The function is convex when

\[f(tx + (1-t)y) \leq t\,f(x) + (1-t)\,f(y)\]

for all such choices. The left side evaluates the function at a convex combination of the inputs. The right side takes the same convex combination of the function values. Convexity says that the value at the convex combination of the inputs never exceeds the convex combination of the values. The graph curves upward and never lies above the chord joining any two of its points.

How do you check this without testing every pair? For a twice-differentiable function of one variable, convexity holds exactly when $f^{\prime\prime}(x) \geq 0$ everywhere. A nonnegative second derivative means the slope never decreases, so the graph never bends downward. For a function of several variables, the test uses the Hessian matrix, which holds all the second-order partial derivatives. The function is convex if and only if the Hessian is positive semidefinite at every point, meaning all its eigenvalues are nonnegative. When every eigenvalue is strictly positive, the function is strictly convex.

Take a concrete case. Let $f(x, y) = x^2 + xy + y^2$. The second partial derivatives are $\partial^2 f/\partial x^2 = 2$, $\partial^2 f/\partial y^2 = 2$, and $\partial^2 f/\partial x\,\partial y = 1$. The Hessian is

\[H = \begin{bmatrix} 2 & 1 \\ 1 & 2 \end{bmatrix}.\]

The eigenvalues satisfy $(2 - \lambda)^2 - 1 = 0$, giving $\lambda = 1$ and $\lambda = 3$. Both are positive, so $H$ is positive definite at every point, and the function is strictly convex. Setting the gradient $(2x + y,\, x + 2y)$ to zero gives $x = 0$ and $y = 0$. The minimum value is $f(0, 0) = 0$, and strict convexity guarantees this is the only minimum in the entire plane.

Convexity matters most in optimization. A general function can have many local minima, and an algorithm that finds one has no guarantee it found the global minimum. For a convex function, this problem does not arise. Any local minimum of a convex function is automatically a global minimum, because the shape of the graph prevents the function from decreasing, increasing, and then decreasing again somewhere else. If you reach a point where the gradient is zero and the function is convex, that point is a global minimum. No other point gives a smaller value.