Convex Analysis

Overview & Motivation

Here is the single most important fact in all of optimization:

Every local minimum of a convex function is a global minimum.

This one sentence is why convex optimization is tractable and general optimization is not. In a non-convex landscape — say a deep neural network loss surface — gradient descent can get trapped in local minima, saddle points, or flat regions, and we have no guarantee that the point we converge to is anywhere near optimal. But if the function we’re minimizing is convex, then any point where the gradient vanishes (or, more generally, where $0$ lies in the subdifferential) is a global minimizer. No restarts, no escaping saddle points, no hoping for the best.

This topic develops the mathematical infrastructure behind that fact. We start with the two geometric primitives — convex sets (closed under line segments) and convex functions (whose epigraph is a convex set) — and build up through three layers:

1. Characterization: First-order and second-order conditions that connect convexity to gradients and Hessians.
2. Closure: Operations that preserve convexity — the toolkit that lets us certify complex functions as convex without checking from scratch.
3. Duality: Conjugate functions and subdifferentials that extend calculus to non-smooth settings, enabling the analysis of functions like $\|x\|_1$ and $\max(0, x)$ that appear throughout modern ML.

The separating hyperplane theorem provides the geometric backbone: it says that disjoint convex sets can always be separated by a hyperplane. This seemingly simple geometric fact has far-reaching consequences — it is the foundation of support vector machines, LP duality, and the entire theory of Lagrangian optimization.

What We Cover

1. Convex Sets — the line-segment definition, convex combinations, and a gallery of examples.
2. Convex Hull & Extreme Points — how to construct the smallest convex set containing a given set.
3. Convex Functions — the chord inequality, epigraphs, and Jensen’s inequality.
4. First-Order & Second-Order Conditions — connecting convexity to tangent lines and Hessian eigenvalues (via the Spectral Theorem).
5. Operations Preserving Convexity — nonneg. weighted sums, pointwise max, composition rules (DCP).
6. Conjugate Functions — the Legendre–Fenchel transform and biconjugation.
7. Subdifferentials & Subgradients — generalized gradients for non-smooth functions.
8. Separation Theorems — the geometric foundation of duality.
9. Computational Notes — DCP rules, CVXPY, and numerical convexity verification.

---

Convex Sets

Everything begins with a definition that is geometric at its core: a set is convex if you can draw a straight line between any two of its points and the line stays inside the set.

This is the line-segment test, and it is the only thing you need to verify. An ellipse passes — every chord stays inside. An L-shape fails — there exist pairs of points whose connecting segment exits the set.

A Gallery of Convex Sets

Convex sets are everywhere. Here are the workhorses:

• Halfspaces: $\{x : a^T x \leq b\}$ for a fixed $a \neq 0$ and $b$. Every linear inequality defines a halfspace, and every halfspace is convex.
• Balls: $\{x : \|x - c\| \leq r\}$ in any norm. Euclidean balls, $\ell_1$ balls (cross-polytopes), $\ell_\infty$ balls (cubes).
• Polyhedra: $\{x : Ax \leq b\}$ — intersections of finitely many halfspaces.
• Cones: $\{x : \|x\|_2 \leq t\}$ (the second-order cone), and the positive semidefinite cone $\mathbb{S}^n_+ = \{X \in \mathbb{R}^{n \times n} : X = X^T, X \succeq 0\}$.
• The PSD cone $\mathbb{S}^n_+$: The set of all $n \times n$ symmetric positive semidefinite matrices. Its structure is governed by the Spectral Theorem — a symmetric matrix is PSD if and only if all its eigenvalues are nonneg.

Convexity is preserved by intersection (any intersection of convex sets is convex), by affine maps (if $C$ is convex, then $f(C) = \{Ax + b : x \in C\}$ is convex), and by inverse affine maps (if $C$ is convex, then $f^{-1}(C) = \{x : Ax + b \in C\}$ is convex).

Try the interactive explorer below — drag the two points around and watch whether the line segment between them stays inside the set.

---

Convex Hull & Extreme Points

Given any set $S$ — convex or not — we can always construct the smallest convex set that contains it.

The vertices of the convex hull are special — they are the points that cannot be written as convex combinations of other points.

The Krein–Milman theorem says that every compact convex set is the convex hull of its extreme points. This is a foundational result in functional analysis, and it has practical consequences: to optimize a linear function over a compact convex set, we need only check the extreme points — a fact that underpins the simplex method for linear programming.

# Compute and plot convex hull of a point set
import numpy as np
from scipy.spatial import ConvexHull

points = np.random.randn(30, 2) * 1.5
hull = ConvexHull(points)

# hull.vertices gives the indices of extreme points
extreme_points = points[hull.vertices]

---

Convex Functions

We now turn from sets to functions. The definition is again geometric: a function is convex if the chord between any two points on its graph lies above the graph.

The connection between convex functions and convex sets runs through the epigraph.

This equivalence is powerful: it lets us transfer results about convex sets directly to convex functions.

Jensen’s Inequality

The chord inequality generalizes from two points to any weighted average — this is Jensen’s inequality, one of the most widely used results in probability and information theory.

---

First-Order & Second-Order Conditions

The chord inequality is the definition, but there are more practical characterizations for differentiable functions.

The Tangent Line Condition

The Hessian Condition

For twice-differentiable functions, convexity is equivalent to the Hessian being positive semidefinite — and this is where the Spectral Theorem enters.

This is the bridge between convexity and spectral theory. When we check whether a neural network loss function is locally convex around a critical point, we compute the Hessian and check its eigenvalues. The Spectral Theorem guarantees these eigenvalues are real and the eigenvectors are orthogonal — the entire machinery of eigendecomposition is built for exactly this purpose.

Example. Consider $f(x_1, x_2) = 2x_1^2 + x_2^2 + x_1 x_2$. The Hessian is:

$\nabla^2 f = \begin{pmatrix} 4 & 1 \\ 1 & 2 \end{pmatrix}$

Its eigenvalues are approximately $4.62$ and $1.38$ — both positive. So $f$ is strictly convex.

---

Operations Preserving Convexity

Checking convexity from the definition or from the Hessian can be tedious. A more practical approach is to build convex functions from known convex building blocks using operations that preserve convexity. This is the idea behind Disciplined Convex Programming (DCP).

Nonnegative Weighted Sums

If $f_1, \ldots, f_k$ are convex and $\alpha_1, \ldots, \alpha_k \geq 0$, then $\sum \alpha_i f_i$ is convex. This follows directly from the definition — the chord inequality distributes over sums.

Pointwise Maximum and Supremum

This result is remarkably useful. The maximum of finitely many convex functions is convex: $\max(f_1(x), f_2(x), f_3(x))$ is convex if each $f_i$ is. The $\ell_\infty$ norm $\|x\|_\infty = \max_i |x_i|$ is convex because it’s the max of convex functions $|x_i|$.

Composition Rules (DCP)

The composition $h \circ g$ is convex under specific monotonicity conditions:

Outer $h$	Inner $g$	Result $h \circ g$	Condition
Convex, nondecreasing	Convex	Convex	—
Convex, nonincreasing	Concave	Convex	—
Concave, nondecreasing	Concave	Concave	—
Convex	Affine	Convex	Always

These rules are the backbone of solvers like CVXPY. They verify convexity by parsing the composition structure of the objective function rather than computing second derivatives.

The Perspective Function

If $f$ is convex, then its perspective $g(x, t) = t \, f(x/t)$ for $t > 0$ is also convex. This construction appears in information theory (the KL divergence is the perspective of $-\log$) and in conic optimization.

---

Conjugate Functions

The Legendre–Fenchel conjugate provides a dual representation of convex functions — a powerful tool that transforms optimization problems into their dual forms.

The conjugate $f^*$ is always convex (it’s a pointwise supremum of affine functions in $s$), even if $f$ is not. Here are the classic conjugate pairs:

Function $f(x)$	Conjugate $f^*(s)$
$\frac{1}{2}x^2$	$\frac{1}{2}s^2$
$\|x\|$ (any norm)	$\delta_{\{s : \|s\|_* \leq 1\}}$ (indicator of dual norm ball)
$e^x$	$s \ln s - s$ for $s > 0$
$\delta_C(x)$ (indicator of $C$)	$\sup_{x \in C} s^T x$ (support function)

The biconjugation theorem is the central duality result: applying the conjugate twice recovers the original function — but only if it was convex to begin with.

Biconjugation is the foundation of Lagrangian duality in optimization: the dual problem is the conjugate of the primal, and strong duality says that solving the dual recovers the primal optimum — under convexity.

---

Subdifferentials & Subgradients

Not all convex functions are differentiable. The $\ell_1$ norm $\|x\|_1$, the hinge loss $\max(0, 1 - y \hat{y})$, and the ReLU $\max(0, x)$ all have kinks where the gradient does not exist. Subgradients generalize the gradient to handle these cases.

Example: For $f(x) = |x|$:

• At $x > 0$: $\partial f(x) = \{1\}$ (the ordinary derivative)
• At $x < 0$: $\partial f(x) = \{-1\}$
• At $x = 0$: $\partial f(0) = [-1, 1]$ (any slope between $-1$ and $1$ gives a valid underestimator)

The subdifferential gives us a complete optimality condition for convex optimization:

Subdifferential Calculus

The subdifferential obeys sum and chain rules (with some caveats):

• Sum rule: $\partial(f_1 + f_2)(x) \supseteq \partial f_1(x) + \partial f_2(x)$ (Minkowski sum). Equality holds when a constraint qualification is satisfied (e.g., one of the functions is continuous at $x$).
• Scalar multiplication: $\partial(\alpha f)(x) = \alpha \, \partial f(x)$ for $\alpha > 0$.
• Chain rule: For $h(x) = g(Ax + b)$ with $g$ convex, $\partial h(x) = A^T \partial g(Ax + b)$.
• Connection to conjugates: $s \in \partial f(x)$ if and only if $x \in \partial f^*(s)$ if and only if $f(x) + f^*(s) = s^T x$ (the Fenchel–Young equality).

---

Separation Theorems

The separation theorems are the geometric bedrock of convex optimization. They say, loosely, that convex sets that don’t overlap can be separated by a hyperplane.

These theorems have far-reaching consequences:

• SVM margin: The separating hyperplane between two classes of labeled data is the maximum-margin classifier.
• Farkas’ lemma: A direct consequence of separation, and the foundation of LP duality and the KKT conditions.
• Duality in convex optimization: The entire theory of Lagrangian duality rests on separating the epigraph of the objective from a set defined by the constraints.

---

Computational Notes

Disciplined Convex Programming (DCP)

Rather than checking convexity analytically, modern solvers like CVXPY use the DCP composition rules to verify convexity syntactically. A problem is DCP-compliant if the objective and constraints can be parsed into a composition tree where every node preserves convexity according to the rules in the table above.

import cvxpy as cp
import numpy as np

# Non-negative Lasso: min ||Ax - b||_2^2 + lambda * ||x||_1  s.t. x >= 0
A = np.random.randn(50, 20)
b = np.random.randn(50)
lam = 0.1

x = cp.Variable(20)
objective = cp.Minimize(cp.sum_squares(A @ x - b) + lam * cp.norm1(x))
constraints = [x >= 0]
problem = cp.Problem(objective, constraints)
problem.solve()

print(f"Optimal value: {problem.value:.4f}")
print(f"Solution sparsity: {np.sum(np.abs(x.value) < 1e-6)} / {x.size} zeros")

CVXPY verifies that sum_squares is convex nondecreasing, the affine map A @ x - b composes correctly, norm1 is convex, and x >= 0 is a valid convex constraint. If any rule is violated, CVXPY rejects the problem before solving.

Numerical Convexity Verification

For a function given as code rather than a formula, we can check convexity numerically by sampling the Hessian at random points and verifying $\lambda_{\min}(\nabla^2 f(x)) \geq 0$:

# Check convexity by sampling Hessian eigenvalues
def check_convexity(f, grad2_f, n_samples=100, dim=5):
    """Returns True if all sampled Hessians are PSD."""
    for _ in range(n_samples):
        x = np.random.randn(dim)
        H = grad2_f(x)
        min_eig = np.linalg.eigvalsh(H)[0]
        if min_eig < -1e-10:
            return False
    return True

---

Connections & Further Reading

Convex analysis is the foundation of the Optimization track, connecting backward to spectral theory and forward to gradient methods, proximal operators, and duality theory.

Topic	Connection
The Spectral Theorem	The second-order condition: $\nabla^2 f \succeq 0$ (PSD Hessian) is verified through the eigendecomposition guaranteed by the Spectral Theorem. The PSD cone $\mathbb{S}^n_+$ is a fundamental convex set.
Singular Value Decomposition	The nuclear norm $\|X\|_* = \sum \sigma_i$ is convex, and its subdifferential involves the SVD. Convex relaxations of rank constraints use the nuclear norm ball.
PCA & Low-Rank Approximation	PCA solves a non-convex rank-constrained problem. Its convex relaxation — nuclear norm minimization — is a cornerstone of compressed sensing and matrix completion.
Gradient Descent & Convergence	Convexity guarantees that gradient descent converges to the global minimum. The convergence rate depends on the strong convexity constant.
Proximal Methods	Subgradients motivate proximal operators — the proximal map of $f$ at $x$ minimizes $f(y) + \frac{1}{2}\|y - x\|^2$, a regularized subgradient step.
Lagrangian Duality & KKT	Conjugate functions are the engine of Lagrangian duality. The separation theorems lead to Farkas’ lemma, which leads to the KKT conditions — the first-order optimality conditions for constrained convex optimization.

The Optimization Track

Convex Analysis is the root of the track: everything that follows either applies its results (gradient descent, proximal methods) or extends its duality machinery (Lagrangian duality, KKT conditions).

Convex Analysis (this topic)
    ├── Gradient Descent & Convergence
    │       └── Proximal Methods
    └── Lagrangian Duality & KKT