Optimization

⚡ Key Takeaways

Optimization is the mathematical study of finding the best element — a minimizer or maximizer of an objective function — from a set of feasible alternatives, possibly subject to constraints. Key result: at an interior optimum of a smooth function the gradient vanishes ( $\nabla f = 0$ ); under constraints, the gradient of the objective is a linear combination of constraint gradients (Lagrange/KKT conditions). Applies in: economics, engineering design, machine learning, operations research, physics (least action), statistics. Foundations: Fermat (1630s), Lagrange (1788), Karush (1939) & Kuhn–Tucker (1951), Dantzig (1947).

💡 The Core Insight

At an unconstrained optimum, no direction is "downhill" — so the first-order rate of change in every direction is zero, forcing $\nabla f = 0$ . With constraints, you may only move along the feasible set, so the objective's gradient need not vanish; it need only have no component that improves the objective while staying feasible. That residual must therefore be "absorbed" by the constraint gradients — the geometric origin of Lagrange multipliers and the KKT conditions.

DefinitionThe General Optimization Problem

A mathematical optimization problem is written

1

\quad \min_{x\in\mathbb{R}^n} f(x)\quad\text{subject to}\quad g_i(x)\le 0,\ i=1,\dots,m,\quad h_j(x)=0,\ j=1,\dots,p.

Derivation hint: This is a definition, not a theorem; maximization is recovered by minimizing $-f$ , and any $\ge$ constraint is negated to fit the $\le$ convention. Symbols: $x\in\mathbb{R}^n$ is the decision variable (vector of unknowns); $f:\mathbb{R}^n\to\mathbb{R}$ is the objective (or cost) function; $g_i$ are inequality constraint functions; $h_j$ are equality constraint functions. The feasible set is

2

\quad \mathcal{S}=\{x\in\mathbb{R}^n : g_i(x)\le 0\ \forall i,\ h_j(x)=0\ \forall j\}.

Derivation hint: Intersection of the sublevel sets $\{g_i\le 0\}$ and the level sets $\{h_j=0\}$ ; emptiness of $\mathcal{S}$ means the problem is infeasible. A point $x^\star$ is a global minimizer if $f(x^\star)\le f(x)$ for all $x\in\mathcal{S}$ , and a local minimizer if this holds only for $x$ in some neighborhood $\mathcal{S}\cap B(x^\star,\varepsilon)$ . The optimal value is $p^\star=\inf_{x\in\mathcal{S}} f(x)$ .

DefinitionConvex Problem

Problem [1] is convex if $f$ and all $g_i$ are convex functions and all $h_j$ are affine ( $h_j(x)=a_j^\top x - b_j$ ). A function $f$ is convex iff

3

\quad f(\lambda x + (1-\lambda)y)\le \lambda f(x) + (1-\lambda)f(y)\quad\forall\, x,y,\ \lambda\in[0,1].

Derivation hint: The chord between any two points lies on or above the graph; equivalently, for twice-differentiable $f$ , the Hessian $\nabla^2 f \succeq 0$ (positive semidefinite).

TheoremFirst-Order Necessary Conditions (Unconstrained)

If $f$ is differentiable and $x^\star$ is a local minimizer of $f$ over an open set, then

4

\quad \nabla f(x^\star) = 0.

Derivation hint: Along any line $x^\star + t d$ , the scalar function $\phi(t)=f(x^\star+td)$ has a local min at $t=0$ , so $\phi'(0)=\nabla f(x^\star)^\top d = 0$ for all $d$ . Points satisfying [4] are stationary points. The second-order sufficient condition adds $\nabla^2 f(x^\star)\succ 0$ (positive definite) to guarantee a strict local minimum.

TheoremKarush–Kuhn–Tucker (KKT) Conditions

Suppose $f, g_i, h_j$ are differentiable and a constraint qualification holds at $x^\star$ . If $x^\star$ is a local minimizer of [1], there exist multipliers $\mu_i\ge 0$ and $\lambda_j\in\mathbb{R}$ such that

5

\quad \nabla f(x^\star) + \sum_{i=1}^{m}\mu_i\nabla g_i(x^\star) + \sum_{j=1}^{p}\lambda_j\nabla h_j(x^\star)=0,

Derivation hint: Stationarity of the Lagrangian $L(x,\mu,\lambda)=f+\sum\mu_i g_i+\sum\lambda_j h_j$ with respect to $x$ . together with primal feasibility ( $g_i\le 0$ , $h_j=0$ ), dual feasibility ( $\mu_i\ge 0$ ), and complementary slackness:

6

\quad \mu_i\, g_i(x^\star)=0\quad\text{for each } i.

Derivation hint: An inactive constraint ( $g_i<0$ ) exerts no force, so its multiplier must be zero; only active constraints ( $g_i=0$ ) can have $\mu_i>0$ . For convex problems, the KKT conditions are also sufficient for global optimality.

ProofLagrange multipliers from feasible directions

We derive [5] for equality constraints $h_j(x)=0$ only (the inequality case adds the sign and slackness conditions). 1. Feasible directions. At a minimizer $x^\star$ on the surface $\mathcal{M}=\{h_j=0\}$ , consider any smooth curve $\gamma(t)$ in $\mathcal{M}$ with $\gamma(0)=x^\star$ . Its velocity $v=\dot\gamma(0)$ is tangent to $\mathcal{M}$ , meaning $\nabla h_j(x^\star)^\top v = 0$ for all $j$ (differentiate $h_j(\gamma(t))=0$ at $t=0$ ). 2. No first-order decrease. Since $f(\gamma(t))$ has a local min at $t=0$ , differentiating gives $\nabla f(x^\star)^\top v = 0$ for every tangent $v$ . 3. Orthogonality. Thus $\nabla f(x^\star)$ is orthogonal to the entire tangent space $T_{x^\star}\mathcal{M}$ . But that tangent space is exactly the orthogonal complement of $\mathrm{span}\{\nabla h_j(x^\star)\}$ . 4. Conclusion. Therefore $\nabla f(x^\star)$ lies in $\mathrm{span}\{\nabla h_j(x^\star)\}$ , i.e. there exist scalars $\lambda_j$ with $\nabla f(x^\star)=-\sum_j\lambda_j\nabla h_j(x^\star)$ , which rearranges to [5]. $\blacksquare$

∎

ProofLocal equals global for convex problems

1. Let $f$ be convex on convex $\mathcal{S}$ and let $x^\star$ be a local minimizer. Suppose for contradiction some $y\in\mathcal{S}$ has $f(y)<f(x^\star)$ . 2. By convexity [3], for $\lambda\in(0,1]$ : $f(\lambda y+(1-\lambda)x^\star)\le \lambda f(y)+(1-\lambda)f(x^\star) < f(x^\star)$ . 3. As $\lambda\to 0^+$ , the point $\lambda y+(1-\lambda)x^\star$ enters every neighborhood of $x^\star$ , yet has strictly smaller objective value. 4. This contradicts $x^\star$ being a local minimizer. Hence $f(x^\star)\le f(y)$ for all $y$ : the local minimum is global. $\blacksquare$

∎

Figure

Constrained minimization: the gradient of

f

aligns with the constraint gradient at the optimum.

mathematician · Joseph-Louis Lagrange | 1736–1813

The Turin-born, Berlin- and Paris-active analyst introduced the method of multipliers in his Mécanique analytique (1788), recasting mechanics entirely in terms of stationarity of a single functional. His insight that constrained extrema can be found by adjoining constraints with undetermined coefficients turned a geometric puzzle into pure algebra and remains, two centuries later, the conceptual backbone of constrained optimization, control theory, and economics.

🧠 Intuition

Picture standing on a hillside (the graph of $f$ ) in fog. To minimize you walk where the ground slopes down. At the bottom of a valley, every direction is uphill or flat — that flatness in all directions is $\nabla f = 0$ . Now add a fence you must stay on (a constraint). You can no longer roam freely; you walk only along the fence. You stop descending when the fence stops going downhill — i.e. where the downhill direction of the terrain ( $-\nabla f$ ) points straight through the fence, perpendicular to it ( $\nabla h$ ). At that spot the two gradients are parallel: that is exactly equation [5]. The multiplier $\lambda$ measures how hard the fence is "pushing back" — equivalently, how much the optimal value would improve if you relaxed the constraint by one unit (its shadow price).

ExampleUnconstrained minimization of a quadratic

Given: Minimize $f(x,y)=x^2+xy+y^2-3y$ over $\mathbb{R}^2$ .

Steps: 1. Gradient: $\nabla f = (2x+y,\ x+2y-3)$ . 2. Set $\nabla f = 0$ : $2x+y=0$ and $x+2y=3$ . 3. From the first, $y=-2x$ . Substitute: $x+2(-2x)=3\Rightarrow -3x=3\Rightarrow x=-1$ , so $y=2$ . 4. Hessian $\nabla^2 f=\begin{pmatrix}2&1\\1&2\end{pmatrix}$ has eigenvalues $1,3>0$ ⇒ positive definite ⇒ strict local (and, since $f$ is convex, global) minimum. 5. Value: $f(-1,2)=1-2+4-6=-3$ .

\boxed{x^\star=(-1,\,2),\quad f^\star=-3\ \text{(dimensionless)}}

ExampleConstrained optimization with Lagrange multipliers

Given: A box with no top, surface area fixed at $S=12\ \text{m}^2$ , maximize volume $V=xyz$ . Constraint: $xy+2xz+2yz=12$ .

Steps: 1. Lagrangian: $L=xyz-\lambda(xy+2xz+2yz-12)$ . 2. Stationarity:

$\partial_x: yz=\lambda(y+2z)$
$\partial_y: xz=\lambda(x+2z)$
$\partial_z: xy=\lambda(2x+2y)$

3. By symmetry of the first two, $x=y$ . Substituting and dividing yields $x=2z$ . 4. Plug into constraint: with $x=y=2z$ : $4z^2 + 2(2z)z + 2(2z)z = 4z^2+4z^2+4z^2=12z^2=12\Rightarrow z=1$ , so $x=y=2$ . 5. Volume: $V=2\cdot 2\cdot 1 = 4\ \text{m}^3$ . The multiplier $\lambda = yz/(y+2z)=2/4=0.5\ \text{m}$ is the marginal volume gain per unit of extra material.

\boxed{x=y=2\ \text{m},\ z=1\ \text{m},\quad V^\star = 4\ \text{m}^3}

⚠️ Common mistake

Stationary points are not always minima. Solving $\nabla f = 0$ yields candidates — they may be maxima, minima, or saddle points. Always check the second-order condition (Hessian) or compare boundary/limit behavior. Also, $\nabla f=0$ is necessary only at interior optima; a minimum on the boundary of the feasible set may have $\nabla f\ne 0$ (the boundary constraint absorbs it via KKT).

⚠️ Common mistake

A solution to the KKT equations need not be optimal for nonconvex problems. KKT is necessary (given a constraint qualification) but sufficient only when the problem is convex. In nonconvex problems a KKT point can be a local max or saddle.

Counterexample

Consider $f(x)=x^3$ on $\mathbb{R}$ . Then $f'(x)=3x^2=0$ gives $x=0$ as the only stationary point — yet $x=0$ is neither a local minimum nor maximum; it is an inflection point. Blindly trusting $\nabla f=0$ would falsely flag $x=0$ as an extremum. The second-order test fails ( $f''(0)=0$ ), and inspection shows $f$ decreases through $0$ .

Counterexample

Minimize $f(x)=x$ subject to $x\ge 0$ (i.e. $g(x)=-x\le 0$ ). The minimizer is $x^\star=0$ , on the boundary, where $f'(x^\star)=1\ne 0$ . There is no contradiction: KKT gives $1+\mu(-1)=0\Rightarrow \mu=1\ge 0$ , with complementary slackness $\mu g=1\cdot 0=0$ satisfied. The "missing" gradient is supplied entirely by the active constraint.

connection

Optimization sits at the crossroads of several fields. The unconstrained conditions [4] rest on Multivariable Calculus and the Gradient; the second-order test invokes Definite Matrices and the Hessian Matrix. Convexity theory connects to Convex Sets and Convex Functions. The Lagrangian dual generalizes through Duality (Optimization), linking primal minima to dual maxima via Weak and Strong Duality. In statistics, Maximum Likelihood Estimation is optimization of a log-likelihood; in machine learning, Gradient Descent and Stochastic Gradient Descent are the workhorse algorithms. The continuous-time analogue underlies the Calculus of Variations and Optimal Control, while the linear special case is Linear Programming.

🔬 Where this appears

⏳ History

- c. 300 BCE — Euclid & Heron: geometric extremal problems (shortest reflected path), early variational reasoning.

- 1630s — Fermat: "adequality" method finds maxima/minima by setting an infinitesimal difference to zero — anticipating

f'(x)=0

.

- 1696 — Johann Bernoulli: poses the brachistochrone problem, launching the calculus of variations.

- 1744 — Euler: systematizes variational problems; the Euler equation generalizes stationarity to functionals.

- 1788 — Lagrange: Mécanique analytique introduces multipliers for constrained extrema.

- 1847 — Cauchy: describes the method of steepest descent (gradient descent).

- 1939 — Karush: in an unpublished master's thesis, derives the inequality-constrained optimality conditions.

- 1947 — Dantzig: invents the simplex algorithm for linear programming.

- 1951 — Kuhn & Tucker: publish the conditions now jointly named KKT; convex programming becomes a discipline. Khachiyan (1979) and Karmarkar (1984) later give polynomial-time interior-point methods.

open-problem

Nonconvex global optimization remains computationally hard: certifying that a candidate is the global minimum of a general nonconvex (or NP-hard combinatorial) problem can require exponential effort, and no efficient universal algorithm is known (this is intertwined with P vs NP). Even for smooth problems, the landscape of saddle points and spurious local minima in high dimensions — central to deep learning — is incompletely understood: why gradient methods so often find good solutions despite nonconvexity is an active research frontier. Constraint qualifications are another subtlety: KKT necessity can fail at irregular points (e.g. where constraint gradients are linearly dependent), requiring weaker conditions (Fritz John, MFCQ). Finally, duality gaps can be nonzero for nonconvex problems, breaking the clean primal–dual correspondence that convexity guarantees.

Formal Statement

Why It Holds / Derivation

Building Intuition

Worked Examples

Common Misconceptions

Connections

Real-World Applications

Historical Development

Subtleties & Limits

See Also