Convex sets

Convexity is the property that makes optimization tractable: on a convex problem, any local minimum is global and there are no saddles to escape. The geometry starts with convex sets, the shapes a feasible region can take before the objective is even introduced.

Definition

A set $C \subseteq \mathbb{R}^n$ is convex if the line segment between any two of its points stays inside it: for all $x, y \in C$ and $\theta \in [0, 1]$,

The point $\theta x + (1-\theta)y$ is a convex combination of $x$ and $y$, tracing the segment from $y$ ($\theta = 0$) to $x$ ($\theta = 1$). A disk, a solid ball, a half-space, and the whole space are convex; a ring, a crescent, and a pair of separated blobs are not[1].

The definition extends to any number of points: a convex set contains every convex combination $\sum_i \theta_i x_i$ with $\theta_i \ge 0$ and $\sum_i \theta_i = 1$.

Building blocks

Hyperplanes and half-spaces. A hyperplane $\{x : a^\top x = b\}$ and a half-space $\{x : a^\top x \le b\}$ are convex. A half-space is the basic ingredient of linear constraints: each inequality $a^\top x \le b$ carves out one.

Norm balls. $\{x : \lVert x - x_0\rVert \le r\}$ is convex for any norm, by the triangle inequality. The $\ell_1$, $\ell_2$, and $\ell_\infty$ balls are all convex, which is why their unit balls were the feasible regions in the norms lesson.

Operations that preserve convexity

Convexity survives the operations used to assemble feasible regions:

• Intersection. If $C_1, C_2$ are convex, so is $C_1 \cap C_2$. A segment lying in both sets lies in their intersection. This extends to arbitrary intersections, so a polyhedron $\{x : Ax \le b\}$, an intersection of half-spaces, is convex.
• Affine images. If $C$ is convex, so is $\{Ax + b : x \in C\}$. Scaling, rotating, projecting, and translating a convex set keep it convex.

These rules let you certify convexity of a feasible region by construction, without checking the segment condition directly.

The separating hyperplane theorem

Theorem. If $C$ and $D$ are disjoint convex sets, there exists a hyperplane separating them: a nonzero $a$ and scalar $b$ with $a^\top x \le b$ for all $x \in C$ and $a^\top x \ge b$ for all $x \in D$[2].

The picture is that two non-overlapping convex shapes can always be split by a flat wall. This is the geometric root of duality (a separating hyperplane becomes a dual certificate) and of support vector machines (the separating hyperplane is the classifier). The disjointness and convexity are both essential; non-convex sets can interlock so that no flat wall separates them.

Check it on arrays

import numpy as np

rng = np.random.default_rng(0)

# Test convexity empirically: sample pairs, check midpoints stay inside.
def is_convex_region(inside, sampler, trials=100_000):
    P = sampler(trials)
    Q = sampler(trials)
    P, Q = P[inside(P)], Q[inside(Q)]
    m = min(len(P), len(Q))
    theta = rng.random((m, 1))
    mid = theta * P[:m] + (1 - theta) * Q[:m]
    return np.all(inside(mid))

box = lambda n: rng.uniform(-2, 2, size=(n, 2))

# L2 ball: convex
in_ball = lambda X: np.linalg.norm(X, axis=1) <= 1.5
print("L2 ball convex:", is_convex_region(in_ball, box))

# Annulus (ring): NOT convex
in_ring = lambda X: (np.linalg.norm(X, axis=1) >= 0.8) & (np.linalg.norm(X, axis=1) <= 1.5)
print("annulus convex:", is_convex_region(in_ring, box))

# Polyhedron {x : A x <= b} is convex (intersection of half-spaces)
A = np.array([[1, 0], [0, 1], [-1, -1]]); b = np.array([1.0, 1.0, 1.0])
in_poly = lambda X: np.all(X @ A.T <= b, axis=1)
print("polyhedron convex:", is_convex_region(in_poly, box))

The midpoint test confirms the ball and polyhedron are convex and flags the ring as non-convex.

Exercises

Exercise 1. Show directly from the definition that the half-space $H = \{x : a^\top x \le b\}$ is convex, for any nonzero $a$ and scalar $b$.

Exercise 2. Prove the intersection rule: if $C_1$ and $C_2$ are convex, then $C_1 \cap C_2$ is convex. Then explain in one sentence why this makes the polyhedron $\{x : Ax \le b\}$ convex.

Exercise 3 (code). A convex set contains every convex combination of its points, not only midpoints. For the polyhedron with rows $(1,0), (0,1), (-1,-1)$ and $b = (1, 1, 1)$, sample triples of interior points and random barycentric weights $\theta_1, \theta_2, \theta_3 \ge 0$ summing to one, and check the weighted combination stays inside.

import numpy as np

rng = np.random.default_rng(0)
A = np.array([[1, 0], [0, 1], [-1, -1]])
b = np.array([1.0, 1.0, 1.0])
inside = lambda X: np.all(X @ A.T <= b + 1e-12, axis=1)

# Draw points in the box, keep those inside the polyhedron.
box = rng.uniform(-2, 2, size=(300_000, 2))
pts = box[inside(box)]
P, Q, R = pts[0::3], pts[1::3], pts[2::3]
m = min(len(P), len(Q), len(R))
P, Q, R = P[:m], Q[:m], R[:m]

# Random convex weights on the simplex via the sort trick.
u = np.sort(rng.random((m, 2)), axis=1)
t1 = u[:, 0]
t2 = u[:, 1] - u[:, 0]
t3 = 1.0 - u[:, 1]
comb = t1[:, None] * P + t2[:, None] * Q + t3[:, None] * R

assert np.all(inside(comb))
print("all", m, "three-point convex combinations stayed inside")

With convex feasible regions defined, the next lesson puts a convex function on top of them.