16.77 min read

Convex Sets

A set $C \subseteq \mathbb{R}^n$ is convex if for any two points $\mathbf{u}, \mathbf{v} \in C$ , the entire line segment connecting them stays inside $C$ .

The line segment from $\mathbf{u}$ to $\mathbf{v}$ consists of all points $(1-t)\mathbf{u} + t\mathbf{v}$ for $t \in [0, 1]$ . Convexity says: if both endpoints are in $C$ , every intermediate point is too.

Examples: all of $\mathbb{R}^n$ (obviously convex), any halfspace $\{\mathbf{x} : \mathbf{b}^t \mathbf{x} \leq r\}$ , balls, cubes, and any intersection of convex sets. Non-examples: a donut (you can draw a chord that exits the hole), an L-shape, a star.

Intersections of convex sets are convex — a key fact that lets us build complex feasible regions for optimization from simple halfspace constraints.

Formal View

Definition 16.5 — Convex Set

A subset

C \subseteq \mathbb{R}^n

is convex if for all

\mathbf{u}, \mathbf{v} \in C

and all

t \in (0, 1)

(1-t)\mathbf{u} + tv \in C

Equivalently: the line segment between any two points in

C

lies entirely in

C

Lemma 16.1 — Intersection of Convex Sets

The intersection of any collection of convex sets is convex. In particular, the intersection of halfspaces (a polytope) is convex.

Interactive Visualization

Convex Set Visualizer

Why This Matters

Convex domains appear everywhere in optimization: linear programs live on polytopes, semidefinite programs live on the cone of PSD matrices, and ball constraints regularize machine learning models.

Linear programming feasible regions are polytopes (intersections of halfspaces)
Semidefinite programming feasible regions are PSD matrix cones — convex
$\ell_2$ regularization: feasible region is a ball (convex)
Support vector machine margins: convex feasible region

Learning Resources

Convex sets and functions

Stanford — Convex Optimization (Boyd)

Comprehensive treatment of convex sets with many examples from optimization.

20 min

Convex optimization overview

Visually Explained

Intuitive visual introduction to convex sets and why they matter for optimization.

16 min

Quiz

Question 1

Which of these sets is NOT convex?

Question 2

The intersection of two convex sets is always convex.

Question 3

A polytope in $\mathbb{R}^n$ is the intersection of:

Question 4

The set of symmetric PSD $n \times n$ matrices is a convex set.

Common Mistakes

Confusing "connected" with "convex" — a set can be connected (one piece) without being convex (e.g., a donut).
Assuming the union of convex sets is convex — unions are generally not convex, only intersections are.