Convex Optimization Cheat Sheet

Updated 2026-05-21

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. Below is a complete table-by-table outline of this topic, spanning foundational concepts through advanced details.

Table 1: Convex Sets — Definitions and Key ExamplesTable 2: Convex Functions — Properties and RecognitionTable 3: Composition Rules for Recognizing ConvexityTable 4: Standard Convex Problem ClassesTable 5: Lagrangian Duality and the Dual ProblemTable 6: KKT Optimality ConditionsTable 7: Gradient Descent and Subgradient MethodsTable 8: Accelerated and Stochastic Gradient MethodsTable 9: Proximal Gradient and Proximal OperatorsTable 10: Projected Gradient and Constrained OptimizationTable 11: ADMM — Alternating Direction Method of MultipliersTable 12: Interior-Point Methods and Barrier FunctionsTable 13: CVXPY, CVXR, and cvxopt — Usage PatternsTable 14: Applications in Machine Learning and Signal ProcessingTable 15: Newton's Method and Quasi-Newton MethodsTable 16: SOCP and SDP — Conic ExtensionsTable 17: Convex vs. Non-Convex Problems — Key Distinctions and Common Pitfalls

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
Convex set (definition)	$\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.
Hyperplane	$\{x \mid a^T x = b\}$	A convex (and affine) set defined by a single linear equality.
Halfspace	$\{x \mid a^T x \leq b\}$	Convex set bounded by a hyperplane on one side.
Polyhedron	$\{x \mid Ax \preceq b,\; Cx = d\}$	• Intersection of finitely many halfspaces and hyperplanes • always convex
Ball (Euclidean)	$\{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
Ellipsoid	$\{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$ .

Table 1: Convex Sets — Definitions and Key Examples

Type	Example	Description
Convex set (definition)	$\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.
Hyperplane	$\{x \mid a^T x = b\}$	A convex (and affine) set defined by a single linear equality.
Halfspace	$\{x \mid a^T x \leq b\}$	Convex set bounded by a hyperplane on one side.
Polyhedron	$\{x \mid Ax \preceq b,\; Cx = d\}$	• Intersection of finitely many halfspaces and hyperplanes • always convex
Ball (Euclidean)	$\{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
Ellipsoid	$\{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$ .