Convex sets and convex functions

Linear programming is tractable because its feasible sets are convex and its objectives are linear. Convex optimization keeps the first property and relaxes the second, allowing any convex objective. The class is enormous, containing least squares, portfolio selection, support vector machines, optimal control and much of signal processing, and it keeps the decisive property that made LP work: a local minimum is a global minimum. As R. Tyrrell Rockafellar put it in 1993, the great watershed in optimization is not between linearity and nonlinearity but between convexity and nonconvexity. This lesson develops the basic theory: convex sets and the operations that preserve them, the separating hyperplane theorem, convex functions and their first- and second-order characterizations, and the optimality theorem that every local minimizer of a convex problem is global.

Convex sets

A set \(C \subseteq \mathbb{R}^n\) is convex if for all \(x, y \in C\) and \(\lambda \in [0, 1]\), the point \(\lambda x + (1 - \lambda)y\) lies in \(C\). Geometrically, the segment between any two points of the set stays in the set. A convex combination of points \(x_1, \ldots, x_k\) is a sum \(\sum \lambda_ix_i\) with \(\lambda_i \ge 0\) and \(\sum\lambda_i = 1\); by induction on \(k\), a convex set contains all convex combinations of its points. The convex hull of a set \(S\), the smallest convex set containing it, is the set of all convex combinations of points of \(S\).

Many sets are convex. A hyperplane \(\{x : a^Tx = \beta\}\) and a half-space \(\{x : a^Tx \le \beta\}\) are convex, as lesson 2 showed for half-planes. A Euclidean ball \(\{x : \|x - x_0\| \le r\}\) is convex: if \(x\) and \(y\) are in it, then by the triangle inequality \(\|\lambda x + (1 - \lambda)y - x_0\| = \|\lambda(x - x_0) + (1 - \lambda)(y - x_0)\| \le \lambda r + (1 - \lambda)r = r\). The same argument works for the ball of any norm. An ellipsoid \(\{x : (x - x_0)^TP^{-1}(x - x_0) \le 1\}\) with \(P\) positive definite is convex, being the image of a ball under an affine map. The set of positive semidefinite matrices is a convex cone, since \(v^T(\lambda X + (1 - \lambda)Y)v = \lambda v^TXv + (1 - \lambda)v^TYv \ge 0\).

Convexity is preserved by a few operations, and recognizing a set as built from them is usually the quickest proof that it is convex. An intersection of any family of convex sets is convex, since a segment lying in each set lies in their intersection; this is why polyhedra are convex. The image and the preimage of a convex set under an affine map \(x \mapsto Mx + q\) are convex. The Minkowski sum \(C + D = \{c + d : c \in C,\ d \in D\}\) of convex sets is convex. Unions, on the other hand, are generally not convex, and neither are complements.

Separating hyperplanes

The most important structural fact about closed convex sets is that a point outside one can be cut off by a hyperplane. The proof uses the nearest-point projection, and its existence uses the theory of lesson 1.

Theorem (projection). Let \(C\) be nonempty, closed and convex, and \(z \in \mathbb{R}^n\). There is a unique point \(p \in C\) nearest to \(z\), and it is characterized by \((z - p)^T(x - p) \le 0\) for every \(x \in C\).

Proof. The function \(x \mapsto \|x - z\|^2\) is continuous and coercive, so by the corollary of lesson 1 it attains its minimum on the closed set \(C\) at some \(p\). For \(x \in C\) and \(t \in (0, 1]\), the point \(p + t(x - p)\) lies in \(C\), so \(\|p + t(x - p) - z\|^2 \ge \|p - z\|^2\). Expanding, \(2t(p - z)^T(x - p) + t^2\|x - p\|^2 \ge 0\); dividing by \(t\) and letting \(t \to 0\) gives \((z - p)^T(x - p) \le 0\). Conversely, if \(p \in C\) satisfies this inequality, then for any \(x \in C\), \(\|x - z\|^2 = \|x - p\|^2 + \|p - z\|^2 - 2(z - p)^T(x - p) \ge \|p - z\|^2\), so \(p\) is nearest; if \(x\) is also nearest, equality forces \(\|x - p\| = 0\), giving uniqueness. \(\square\)

Theorem (separating hyperplane). If \(C\) is nonempty, closed and convex and \(z \notin C\), there are \(a \ne 0\) and \(\beta\) with \(a^Tx \le \beta < a^Tz\) for every \(x \in C\).

Proof. Let \(p\) be the projection of \(z\) and \(a = z - p\), which is nonzero since \(z \notin C\). By the projection theorem \(a^Tx \le a^Tp\) for \(x \in C\). Set \(\beta = a^Tp\). Then \(a^Tz - \beta = a^T(z - p) = \|a\|^2 > 0\). \(\square\)

Farkas's lemma of lesson 6 is a special case: the cone generated by the columns of \(A\) is closed and convex, and when \(b\) is outside it, a separating hyperplane through the origin gives the certificate \(y\). Separation is also the engine behind duality theory for general convex programs, and behind the supporting hyperplane theorem, which says every boundary point of a convex set lies on a hyperplane with the whole set on one side.

Convex functions

A function \(f\) defined on a convex set \(C\) is convex if

Geometrically, the chord between two points of the graph lies on or above the graph. It is strictly convex if the inequality is strict whenever \(x \ne y\) and \(0 < \lambda < 1\), and concave if \(-f\) is convex. Equivalently, \(f\) is convex exactly when its epigraph \(\{(x, t) : x \in C,\ t \ge f(x)\}\) is a convex set, which links convex functions to convex sets. Applying the definition repeatedly gives Jensen's inequality \(f(\sum\lambda_ix_i) \le \sum\lambda_if(x_i)\) for convex combinations.

Linear and affine functions are both convex and concave. Every norm is convex, by the triangle inequality and homogeneity. The functions \(e^{ax}\), \(x^2\), \(|x|^p\) for \(p \ge 1\), and \(-\log x\) on \(x > 0\) are convex. Operations that preserve convexity include nonnegative weighted sums, composition with an affine map (so \(\|Ax - b\|^2\) is convex), and pointwise maxima: if each \(f_k\) is convex, so is \(\max_k f_k\), because its epigraph is the intersection of the epigraphs. A sublevel set \(\{x : f(x) \le \alpha\}\) of a convex function is convex, which is why constraints \(g_i(x) \le 0\) with convex \(g_i\) define convex feasible sets.

First- and second-order tests

For differentiable functions convexity has a powerful equivalent form: the tangent plane is a global underestimator.

Theorem (first-order condition). Let \(f\) be differentiable on an open convex set \(C\). Then \(f\) is convex if and only if \(f(y) \ge f(x) + \nabla f(x)^T(y - x)\) for all \(x, y \in C\).

Proof. Suppose \(f\) is convex. For \(t \in (0, 1]\), convexity gives \(f(x + t(y - x)) \le (1 - t)f(x) + tf(y)\), so \(\frac{f(x + t(y - x)) - f(x)}{t} \le f(y) - f(x)\). As \(t \to 0\) the left side tends to the directional derivative \(\nabla f(x)^T(y - x)\), giving the inequality. Conversely, assume the inequality, take \(x, y \in C\), \(\lambda \in [0, 1]\) and \(z = \lambda x + (1 - \lambda)y\). Applying the inequality at \(z\) to \(x\) and to \(y\): \(f(x) \ge f(z) + \nabla f(z)^T(x - z)\) and \(f(y) \ge f(z) + \nabla f(z)^T(y - z)\). Multiply by \(\lambda\) and \(1 - \lambda\) and add; since \(\lambda(x - z) + (1 - \lambda)(y - z) = 0\), we get \(\lambda f(x) + (1 - \lambda)f(y) \ge f(z)\). \(\square\)

An immediate and important consequence: if \(\nabla f(x^*) = 0\) for a convex differentiable \(f\), then \(f(y) \ge f(x^*)\) for every \(y\), so a stationary point of a convex function is a global minimizer. The calculus condition that was only necessary in lesson 1 becomes sufficient.

Theorem (second-order condition). Let \(f\) be twice continuously differentiable on an open convex set \(C\). Then \(f\) is convex if and only if its Hessian \(\nabla^2f(x)\) is positive semidefinite for every \(x \in C\).

Proof. First the case \(n = 1\). If \(f'' \ge 0\), then \(f'\) is nondecreasing, and by the mean value theorem \(f(y) - f(x) = f'(\xi)(y - x)\) for some \(\xi\) between \(x\) and \(y\); in either order of \(x\) and \(y\), \(f'(\xi)(y - x) \ge f'(x)(y - x)\), which is the first-order condition. Conversely if \(f\) is convex, adding the first-order inequalities at \(x\) and at \(y\) gives \((f'(y) - f'(x))(y - x) \ge 0\), so \(f'\) is nondecreasing and \(f'' \ge 0\). For general \(n\), \(f\) is convex if and only if its restriction to every line, \(g(t) = f(x + tv)\) on the interval where \(x + tv \in C\), is convex, because convexity is a statement about segments. And \(g''(t) = v^T\nabla^2f(x + tv)v\). So \(f\) is convex if and only if \(v^T\nabla^2f(x)v \ge 0\) for all \(x \in C\) and all \(v\). \(\square\)

A positive definite Hessian everywhere implies strict convexity, but not conversely: \(x^4\) is strictly convex with \(f''(0) = 0\). To test a symmetric matrix for semidefiniteness, check that all its eigenvalues are nonnegative, or that all its principal minors (determinants of submatrices on matching row and column sets) are nonnegative. Checking only the leading principal minors is enough for positive definiteness (Sylvester's criterion) but not for semidefiniteness: \(\begin{pmatrix} 0 & 0 \\ 0 & -1 \end{pmatrix}\) has leading minors 0 and 0 and is not semidefinite.

Local minima of convex problems are global

Theorem. Let \(f\) be convex on a convex set \(C\). Then every local minimizer of \(f\) on \(C\) is a global minimizer; the set of minimizers is convex; and if \(f\) is strictly convex, there is at most one minimizer.

Proof. Let \(x^*\) be a local minimizer, so \(f(x^*) \le f(x)\) for \(x \in C\) with \(\|x - x^*\| < r\). Suppose some \(y \in C\) had \(f(y) < f(x^*)\). For small \(t > 0\), the point \(x_t = x^* + t(y - x^*)\) lies in \(C\) within distance \(r\) of \(x^*\), and by convexity \(f(x_t) \le (1 - t)f(x^*) + tf(y) < f(x^*)\), contradicting local minimality. The set of minimizers is the sublevel set \(\{x \in C : f(x) \le f^*\}\), which is convex. If \(x\) and \(y\) were distinct minimizers of a strictly convex \(f\), their midpoint would have \(f < \frac12f^* + \frac12f^* = f^*\), a contradiction. \(\square\)

Theorem (optimality condition on a convex set). Let \(f\) be convex and differentiable on an open set containing the convex set \(C\). Then \(x^* \in C\) minimizes \(f\) over \(C\) if and only if \(\nabla f(x^*)^T(y - x^*) \ge 0\) for all \(y \in C\).

Proof. If the condition holds, the first-order inequality gives \(f(y) \ge f(x^*) + \nabla f(x^*)^T(y - x^*) \ge f(x^*)\). Conversely if \(\nabla f(x^*)^T(y - x^*) < 0\) for some \(y \in C\), then the derivative of \(f(x^* + t(y - x^*))\) at \(t = 0\) is negative, so small steps toward \(y\), which stay in \(C\), decrease \(f\), and \(x^*\) is not a minimizer. \(\square\)

The condition says that no feasible direction is a descent direction. At an interior point it reduces to \(\nabla f(x^*) = 0\). On the boundary it says \(-\nabla f(x^*)\) points out of the set, making an angle of at least 90 degrees with every feasible direction. Lesson 11 turns this geometric statement into equations with Lagrange and Karush–Kuhn–Tucker multipliers when \(C\) is described by constraints. Linear programming is the case of a linear \(f\) on a polyhedron, and the condition is then exactly the optimality test of the simplex method in disguise.

Checking convexity numerically

The program estimates Hessians by central differences at 400 random points for six functions and tests them for positive semidefiniteness through all principal minors. As an independent check of the definition itself, it tests the midpoint inequality \(f(\frac{a + b}{2}) \le \frac{f(a) + f(b)}{2}\) on 2000 random pairs. Finally it runs a simple descent on a convex quadratic from two very different starting points.

import math, random
from itertools import combinations

def hessian(f, x, h=1e-4):
    """Central-difference Hessian of f at the point x (a list)."""
    n = len(x)
    H = [[0.0] * n for _ in range(n)]
    for i in range(n):
        for j in range(n):
            def g(di, dj):
                y = list(x); y[i] += di; y[j] += dj
                return f(y)
            H[i][j] = (g(h, h) - g(h, -h) - g(-h, h) + g(-h, -h)) / (4 * h * h)
    return H

def det(M):
    if len(M) == 1:
        return M[0][0]
    return sum((-1) ** k * M[0][k] * det([row[:k] + row[k + 1:] for row in M[1:]]) for k in range(len(M)))

def psd(H, tol=1e-6):
    """Symmetric H is positive semidefinite iff every principal minor is >= 0."""
    n = len(H)
    for r in range(1, n + 1):
        for S in combinations(range(n), r):
            if det([[H[i][j] for j in S] for i in S]) < -tol:
                return False, S
    return True, None

funcs = {
    "x^2 + xy + y^2":        lambda v: v[0] ** 2 + v[0] * v[1] + v[1] ** 2,
    "x^2 - y^2":             lambda v: v[0] ** 2 - v[1] ** 2,
    "log(e^x + e^y)":        lambda v: math.log(math.exp(v[0]) + math.exp(v[1])),
    "x^4 + y^4":             lambda v: v[0] ** 4 + v[1] ** 4,
    "Rosenbrock":            lambda v: (1 - v[0]) ** 2 + 100 * (v[1] - v[0] ** 2) ** 2,
    "x^2 + y^2 + z^2 - xz":  lambda v: v[0] ** 2 + v[1] ** 2 + v[2] ** 2 - v[0] * v[2],
}
rng = random.Random(9)
for name, f in funcs.items():
    n = 3 if "z" in name else 2
    pts = [[rng.uniform(-2, 2) for _ in range(n)] for _ in range(400)]
    bad = None
    for p in pts:
        ok, S = psd(hessian(f, p))
        if not ok:
            bad = (p, S); break
    # independent test of the definition: f(midpoint) <= average of f at the ends
    viol = 0
    for _ in range(2000):
        a = [rng.uniform(-2, 2) for _ in range(n)]
        b = [rng.uniform(-2, 2) for _ in range(n)]
        m = [(s + t) / 2 for s, t in zip(a, b)]
        if f(m) > (f(a) + f(b)) / 2 + 1e-9:
            viol += 1
    verdict = "Hessian PSD at all 400 sample points" if bad is None else \
        f"Hessian not PSD at ({', '.join(f'{t:.2f}' for t in bad[0])}), minor on rows {bad[1]} negative"
    print(f"{name:22s}: {verdict}; midpoint inequality failed {viol} of 2000 times")

# a convex function has every local minimizer global: x^2 + xy + y^2 - 3x from two starts
f = lambda v: v[0] ** 2 + v[0] * v[1] + v[1] ** 2 - 3 * v[0]
for start in ([5.0, 5.0], [-4.0, 3.0]):
    x = list(start)
    for _ in range(200):
        g = [2 * x[0] + x[1] - 3, x[0] + 2 * x[1]]
        x = [x[0] - 0.2 * g[0], x[1] - 0.2 * g[1]]
    print(f"descent from {start}: ends at ({x[0]:.6f}, {x[1]:.6f}), f = {f(x):.6f}")

x^2 + xy + y^2        : Hessian PSD at all 400 sample points; midpoint inequality failed 0 of 2000 times
x^2 - y^2             : Hessian not PSD at (-0.22, 0.27), minor on rows (1,) negative; midpoint inequality failed 1003 of 2000 times
log(e^x + e^y)        : Hessian PSD at all 400 sample points; midpoint inequality failed 0 of 2000 times
x^4 + y^4             : Hessian PSD at all 400 sample points; midpoint inequality failed 0 of 2000 times
Rosenbrock            : Hessian not PSD at (0.97, 1.30), minor on rows (0, 1) negative; midpoint inequality failed 128 of 2000 times
x^2 + y^2 + z^2 - xz  : Hessian PSD at all 400 sample points; midpoint inequality failed 0 of 2000 times
descent from [5.0, 5.0]: ends at (2.000000, -1.000000), f = -3.000000
descent from [-4.0, 3.0]: ends at (2.000000, -1.000000), f = -3.000000

The convex functions pass both tests everywhere. For \(x^2 - y^2\) the second diagonal entry \(-2\) is a negative principal minor at once, and the midpoint inequality fails about half the time, whenever the two points differ more in \(y\) than in \(x\). For the Rosenbrock function the Hessian test fails at a point just above the parabola \(y = x^2\), where the determinant is negative, and the midpoint test fails for some pairs. A numerical test can disprove convexity with a single counterexample but can never prove it; proofs come from the Hessian formula or from the composition rules. The two descents end at the same point \((2, -1)\) with value \(-3\), as the theorem predicts for a strictly convex function: there is nowhere else to stop.