Optimization

Convex Sets and Functions

The geometric and analytic building blocks of convex optimization: sets closed under line segments and functions that curve upward.

Convex sets

A set C is convex if for any two points x and y in C, the entire segment between them stays in C: for all t in [0,1], t*x + (1-t)*y is in C. Examples include lines, halfspaces, balls, ellipsoids, polyhedra, and the positive semidefinite cone. Intersections of convex sets are convex, which is why feasible regions defined by many convex constraints remain convex.

Convex functions

Kronos motion — q curve

A function f is convex if its domain is convex and for all x, y and t in [0,1]: f(t*x + (1-t)*y) <= t*f(x) + (1-t)*f(y). Geometrically, the chord between any two points on the graph lies on or above the graph. Strict convexity replaces <= with < for x not equal to y and guarantees a unique minimizer.

First- and second-order tests

First order: f is convex iff f(y) >= f(x) + grad f(x) dot (y - x) for all x, y (the tangent lies below the graph).
Second order: for twice-differentiable f, convexity holds iff the Hessian is positive semidefinite everywhere.
A function is concave iff its negative is convex.

Operations that preserve convexity

Nonnegative weighted sums, composition with an affine map, pointwise supremum over a family of convex functions, and partial minimization all preserve convexity. These rules let you build complex convex objectives from simple pieces and verify convexity mechanically.

Epigraph view

The epigraph of f is the set of points on or above its graph. A function is convex exactly when its epigraph is a convex set, linking the two concepts. Sublevel sets of a convex function are convex, which is why convex constraints carve out convex feasible regions.

python

import numpy as np
def is_psd(H, tol=1e-9):
    return np.all(np.linalg.eigvalsh(H) >= -tol)

Recognizing and preserving convexity is the practical skill that turns a hard-looking model into a reliably solvable one.