Convex optimization is the study of minimizing convex functions over convex sets — a subfield of mathematical optimization that includes least-squares, linear programming, and a vast range of practical problems as special cases. It matters because any local minimum of a convex problem is automatically a global minimum, making these problems tractable in a way that general nonlinear programs are not. The field is anchored by Boyd and Vandenberghe's seminal textbook and the Stanford EE364a course, which together define the modern curriculum. A key insight practitioners often miss: recognizing convexity is as important as solving the problem — if you can reformulate a nonconvex problem into a convex one, you unlock guarantees and industrial-strength solvers.
What This Cheat Sheet Covers
This topic spans 17 focused tables and 143 indexed concepts, 126 flashcards. Below is a complete table-by-table outline of this topic, spanning foundational concepts through advanced details.
A jump-to index of every table row in this cheat sheet.
An interactive map of every table and concept in this topic.
Table 1: Convex Sets — Definitions and Key Examples
Convex sets are the feasible regions of convex optimization problems. A set is convex if every line segment between two of its points lies entirely within it; understanding which sets are convex and how convexity is preserved under operations is foundational before tackling functions or algorithms.
| Type | Example | Description | |
|---|---|---|---|
$\theta x + (1-\theta)y \in C$ for all $x,y \in C$, $0 \leq \theta \leq 1$ | A set $C$ is convex if it contains the line segment between any two of its points. | ||
${x \mid a^T x = b}$ | A convex (and affine) set defined by a single linear equality. | ||
${x \mid a^T x \leq b}$ | Convex set bounded by a hyperplane on one side. | ||
${x \mid Ax \preceq b,; Cx = d}$ | • Intersection of finitely many halfspaces and hyperplanes • always convex | ||
${x \mid \lVert x - x_c \rVert_2 \leq r}$ | • Convex set • more generally any norm ball $\lVert x - x_c \rVert \leq r$ is convex | ||
${x \mid (x-x_c)^T P^{-1}(x-x_c) \leq 1}$, $P \succ 0$ | • Convex • generalizes the ball with a positive definite shape matrix $P$. | ||
$\mathbb{S}^n_+ = {X \in \mathbb{S}^n \mid X \succeq 0}$ | • The set of $n \times n$ symmetric positive semidefinite matrices • a proper cone. | ||
${(x,t) \mid \lVert x \rVert_2 \leq t}$ | • Convex cone • the constraint type defining second-order cone programs (SOCP). | ||
$\text{conv}(C) = {\sum_i \theta_i x_i \mid x_i \in C, \theta_i \geq 0, \sum \theta_i = 1}$ | • The smallest convex set containing $C$ • formed by all convex combinations | ||
$\theta_1 x_1 + \theta_2 x_2$ for $\theta_i \geq 0$ | A proper cone must be convex, closed, solid, and pointed. | ||
$C_1 \cap C_2 \cap \cdots \cap C_k$ | • Intersection of any collection of convex sets is convex • Cartesian product also preserves convexity | ||
$f(C) = {Ax + b \mid x \in C}$ | Linear/affine images and preimages of convex sets are convex. |