Applied and computational mathematics

Convex optimization

Minimizing convex functions over convex sets: why every local minimum is global, the KKT conditions that certify optimality, and the duality that turns a hard search into an easier one.

IntuitionWhy shape matters: convex versus non-convex

Imagine searching for the lowest point in a landscape by always stepping downhill. In a landscape shaped like a single bowl, this greedy strategy always finds the true lowest point, no matter where you start. In a landscape with several dips, ridges, and saddle-shaped passes, the same strategy can get stuck at a dip that is not the lowest point at all. Convex optimization studies exactly the "single bowl" case — and explains, precisely, why it is so much easier.

z = x^2 + y^2

: a paraboloid. Every direction curves upward, so there is exactly one lowest point.

z = x^2 - y^2

: a saddle. The surface curves up along one axis and down along the other, so the flat point at the origin is neither a minimum nor a maximum.

A 1-D version of the same trap: a cubic curve can have a valley (local minimum) that is not the lowest point overall, because the curve keeps descending further out. Convexity is exactly the property that rules this out.

y = x^3 - 3x

. The marked points are a local maximum, a local minimum, and an inflection point — the local minimum is not the global minimum, since the curve goes to

-\infty

x \to -\infty

UndergraduateConvex sets and convex functions

Definition: Convex set

A set $C \subseteq \mathbb{R}^n$ is convex if for every $x, y \in C$ and every $\theta \in [0,1]$ , the point $\theta x + (1-\theta) y$ also lies in $C$ : the whole segment between any two points of $C$ stays inside $C$ .

Definition: Convex function

A function $f : C \to \mathbb{R}$ on a convex set $C$ is convex if for every $x, y \in C$ and $\theta \in [0,1]$ , $f(\theta x + (1-\theta) y) \le \theta f(x) + (1-\theta) f(y)$ : the graph of $f$ never lies above the segment joining any two of its points.

f(\theta x + (1-\theta) y) \le \theta f(x) + (1-\theta) f(y), \qquad \theta \in [0,1]

When $f$ is twice differentiable, this is equivalent to the Hessian $\nabla^2 f(x)$ being positive semidefinite at every point of $C$ — the multivariable analogue of $f'' \ge 0$ . A convex optimization problem minimizes a convex $f$ over a convex feasible set $C$ (for example, $C = \{x : g_i(x) \le 0, h_j(x) = 0\}$ with each $g_i$ convex and each $h_j$ affine).

Theorem: Local minima of convex functions are global

If $f$ is convex on a convex set $C$ and $x^\star$ is a local minimum of $f$ on $C$ , then $x^\star$ is a global minimum of $f$ on $C$ .

Why is it true?

Suppose $x^\star$ is only a local minimum and some $y \in C$ has $f(y) < f(x^\star)$ . Convexity forces $f$ to lie below the segment from $x^\star$ to $y$ arbitrarily close to $x^\star$ : for small $\theta > 0$ , $f(\theta y + (1-\theta) x^\star) \le \theta f(y) + (1-\theta) f(x^\star) < f(x^\star)$ . That contradicts $x^\star$ being a local minimum, since points $\theta y + (1-\theta)x^\star$ come arbitrarily close to $x^\star$ .

Proof

Suppose $x^\star \in C$ is a local minimum, so there exists a radius $r > 0$ such that $f(z) \ge f(x^\star)$ for all $z \in C$ satisfying $\|z - x^\star\| \le r$ . Assume for contradiction that there exists a point $y \in C$ with $f(y) < f(x^\star)$ .

For any $\theta \in (0, 1)$ , convexity of the set and function ensures $z_\theta = \theta y + (1 - \theta)x^\star \in C$ and $f(z_\theta) \le \theta f(y) + (1 - \theta)f(x^\star) = f(x^\star) + \theta(f(y) - f(x^\star)) < f(x^\star)$ .

Since $\|z_\theta - x^\star\| = \theta \|y - x^\star\|$ , choosing $0 < \theta \le \dfrac{r}{\|y - x^\star\|}$ guarantees $\|z_\theta - x^\star\| \le r$ while $f(z_\theta) < f(x^\star)$ , contradicting that the point is a local minimum.

UndergraduateConstrained problems and the KKT conditions

For an unconstrained differentiable convex $f$ , $x^\star$ is a global minimum if and only if $\nabla f(x^\star) = 0$ . When there are constraints — minimize $f(x)$ subject to $g_i(x) \le 0$ ( $i=1,\dots,m$ ) and $h_j(x) = 0$ ( $j=1,\dots,p$ ) — we introduce the Lagrangian by attaching a nonnegative multiplier $\lambda_i \ge 0$ to each inequality and a free multiplier $\nu_j \in \mathbb{R}$ to each equality:

\mathcal{L}(x,\lambda,\nu) = f(x) + \sum_{i=1}^m \lambda_i\, g_i(x) + \sum_{j=1}^p \nu_j\, h_j(x)

Theorem: Karush–Kuhn–Tucker (KKT) conditions

For a differentiable convex problem satisfying a regularity condition (such as Slater's condition: there exists a point where all $g_i(x) < 0$ and $h_j(x) = 0$ ), a point $x^\star$ is optimal if and only if there exist multipliers $\lambda^\star, \nu^\star$ such that: (1) stationarity $\nabla_x \mathcal{L}(x^\star, \lambda^\star, \nu^\star) = 0$ ; (2) primal feasibility $g_i(x^\star) \le 0$ , $h_j(x^\star) = 0$ ; (3) dual feasibility $\lambda_i^\star \ge 0$ ; and (4) complementary slackness $\lambda_i^\star g_i(x^\star) = 0$ for all $i$ .

Why is it true?

Complementary slackness says that an inequality constraint $g_i(x) \le 0$ either is inactive at $x^\star$ ( $g_i(x^\star) < 0$ , so the boundary is not pushing on $x^\star$ and its multiplier $\lambda_i^\star = 0$ ) or is active ( $g_i(x^\star) = 0$ , so the wall can push back with force $\lambda_i^\star \ge 0$ ). Stationarity then states that $-\nabla f(x^\star)$ is balanced by a nonnegative combination of the outward normals $\nabla g_i(x^\star)$ of the active walls.

Proof

First, suppose $(x^\star, \lambda^\star, \nu^\star)$ satisfies the KKT conditions. Because $\lambda_i^\star \ge 0$ and the constraint functions are convex or affine, the Lagrangian $x \mapsto \mathcal{L}(x, \lambda^\star, \nu^\star)$ is convex, so stationarity $\nabla_x \mathcal{L}(x^\star, \lambda^\star, \nu^\star) = 0$ implies that the candidate point minimizes the Lagrangian over all vectors.

For any feasible $x$ with $g_i(x) \le 0$ and $h_j(x) = 0$ , complementary slackness $\lambda_i^\star g_i(x^\star) = 0$ gives the chain $f(x^\star) = \mathcal{L}(x^\star, \lambda^\star, \nu^\star) \le \mathcal{L}(x, \lambda^\star, \nu^\star) = f(x) + \sum_{i=1}^m \lambda_i^\star g_i(x) + \sum_{j=1}^p \nu_j^\star h_j(x) \le f(x)$ , proving global optimality.

Conversely, under Slater's condition, strong duality provides dual optimal multipliers such that $f(x^\star) = g(\lambda^\star, \nu^\star) = \inf_x \mathcal{L}(x, \lambda^\star, \nu^\star) \le \mathcal{L}(x^\star, \lambda^\star, \nu^\star) = f(x^\star) + \sum_{i=1}^m \lambda_i^\star g_i(x^\star) \le f(x^\star)$ . Both inequalities in this chain must be equalities, which forces stationarity and complementary slackness for every constraint.

Example: Closest point on a line to the origin

Minimize $f(x,y) = x^2 + y^2$ subject to $x + y = 1$ .

Solution

Both $f$ (paraboloid) and the equality $h(x,y) = x + y - 1 = 0$ (affine) define a convex problem. The Lagrangian is $\mathcal{L}(x,y,\nu) = x^2 + y^2 + \nu(x + y - 1)$ . Stationarity gives $2x + \nu = 0$ and $2y + \nu = 0$ , so $x = y$ . Substituting into $x + y = 1$ gives $x^\star = y^\star = \tfrac{1}{2}$ with minimum value $f(x^\star, y^\star) = \tfrac{1}{2}$ . Because the problem is convex, this KKT point is automatically the global minimum.

Example: Active inequality constraint via complementary slackness

Minimize $f(x) = (x - 3)^2$ subject to the inequality constraint $g(x) = x - 1 \le 0$ .

Solution

Form the Lagrangian $\mathcal{L}(x, \lambda) = (x - 3)^2 + \lambda(x - 1)$ . Because the objective is strictly convex and the constraint is affine, the KKT conditions are necessary and sufficient: stationarity $\dfrac{\partial \mathcal{L}}{\partial x} = 2(x - 3) + \lambda = 0$ , primal feasibility $x - 1 \le 0$ , dual feasibility $\lambda \ge 0$ , and complementary slackness $\lambda(x - 1) = 0$ .

Test the two cases from complementary slackness: if $\lambda = 0$ , stationarity gives $x = 3$ , which violates $x - 1 \le 0$ .

Therefore the constraint must be active, giving $x^\star = 1$ and $\lambda^\star = 2(3 - 1) = 4 > 0$ , which satisfies $\lambda \ge 0$ . The unique global minimum is $x^\star = 1$ with optimal value $f(1) = 4$ .

AdvancedDuality and global optimization beyond convexity

Minimizing $\mathcal{L}(x,\lambda,\nu)$ over $x$ (without constraints!) defines the Lagrange dual function $g(\lambda,\nu) = \inf_x \mathcal{L}(x,\lambda,\nu)$ . Because $g$ is the pointwise infimum of affine functions of $(\lambda,\nu)$ , $g$ is always concave, even if the original problem is not convex. For any $\lambda \ge 0$ and any feasible $x$ , every term $\lambda_i g_i(x) \le 0$ and $\nu_j h_j(x) = 0$ , so $g(\lambda,\nu) \le f(x)$ . Maximizing $g(\lambda,\nu)$ over $\lambda \ge 0$ gives the dual problem, whose optimal value $d^\star$ always satisfies weak duality: $d^\star \le p^\star$ (the primal optimal value). When $d^\star = p^\star$ , we say strong duality holds and the duality gap $p^\star - d^\star$ is zero.

Theorem: Strong duality in linear programming

If a primal linear program $\min\{c^\top x : Ax = b,\; x \ge 0\}$ has an optimal solution $x^\star$ , then its dual $\max\{b^\top y : A^\top y \le c\}$ also has an optimal solution $y^\star$ , and the optimal values are equal: $c^\top x^\star = b^\top y^\star$ .

Why is it true?

Linear programs are convex problems with polyhedral feasible sets; for polyhedral constraints no interior-point assumption is needed, and the separating-hyperplane theorem (Farkas' lemma) guarantees a dual multiplier $y^\star$ with zero duality gap. For general convex programs, strong duality holds whenever Slater's condition is satisfied.

Proof

For any primal feasible vector satisfying $Ax = b$ , $x \ge 0$ and any dual feasible vector satisfying $A^\top y \le c$ , taking inner products gives weak duality: $b^\top y = (Ax)^\top y = x^\top(A^\top y) \le x^\top c = c^\top x$ .

Form the Lagrangian $\mathcal{L}(x, y, s) = c^\top x + y^\top(b - Ax) - s^\top x = b^\top y + (c - A^\top y - s)^\top x$ with multiplier $s \ge 0$ . Taking the infimum over unconstrained primal variables yields a finite dual value only when $c - A^\top y - s = 0$ , which recovers the dual constraint and dual objective $g(y, s) = b^\top y$ .

If $x^\star$ is primal optimal with value $p^\star = c^\top x^\star$ , Farkas' lemma (hyperplane separation for polyhedral cones) guarantees a vector $y^\star$ satisfying $A^\top y^\star \le c$ and $b^\top y^\star \ge p^\star$ . Combining this with weak duality forces $b^\top y^\star = c^\top x^\star$ .

Three families of algorithms for smooth convex optimization in $\mathbb{R}^n$
Method family	Information per step	Cost per step	Accuracy $\varepsilon$ in
Gradient / accelerated gradient (Nesterov)	First-order ( $\nabla f$ )	$O(n)$	$O(1/\varepsilon)$ or $O(1/\sqrt{\varepsilon})$
Newton's method	Second-order ( $\nabla f, \nabla^2 f$ )	$O(n^3)$ (linear system)	$O(\log\log(1/\varepsilon))$ locally
Interior-point (barrier)	Second-order on $-\sum \ln(-g_i)$	$O(n^3)$ per Newton step	$O(\sqrt{m}\,\log(1/\varepsilon))$

Research frontier as of 2026

As of 2026, two regimes dominate convex optimization research and practice. For medium-scale problems ( $n$ up to a few tens of thousands) requiring high accuracy, interior-point methods — pioneered by Karmarkar (1984) and systematized via self-concordant barrier theory by Nesterov and Nemirovski (1994) — solve linear, quadratic, second-order-cone, and semidefinite programs in a few dozen Newton steps; recent theoretical work has pushed the worst-case complexity of linear programming close to the matrix-multiplication exponent. For massive-scale problems in machine learning and signal processing ( $n$ in the millions or billions), the $O(n^3)$ cost of a single Newton step is prohibitive, so first-order and stochastic methods — Nesterov's $O(1/k^2)$ accelerated gradient, proximal splitting (ISTA/FISTA, ADMM), variance-reduced stochastic gradients (SVRG, SAGA), and adaptive variants — are the workhorses. Active questions include optimal complexity bounds under higher-order smoothness, communication-optimal distributed convex optimization, and understanding which guarantees of convex theory (implicit regularization, benign saddle geometry) carry over to the non-convex loss landscapes of deep networks.

Which function is convex on all of $\mathbb{R}$ ?

In a convex optimization problem, a point that is a local minimum is

In the KKT conditions, complementary slackness $\lambda_i^\star g_i(x^\star) = 0$ means

For a linear program with a feasible, bounded optimum, strong duality tells us that

References

Stephen Boyd, Lieven Vandenberghe (2004). Convex Optimization
Yurii Nesterov (2004). Introductory Lectures on Convex Optimization: A Basic Course
Harold W. Kuhn, Albert W. Tucker (1951). Nonlinear Programming · DOI:10.1006/hmat.2000.2289
Sébastien Bubeck (2015). Convex Optimization: Algorithms and Complexity · arXiv:1405.4980