Optimization

Optimization seeks $x^{\star }\in \mathcal{S}$ minimizing (or maximizing) an objective $f:\mathcal{S}\to \mathbb{R}$, where $\mathcal{S}\subseteq {\mathbb{R}}^n$ is the feasible set defined by equality and inequality constraints. It matters because an enormous range of quantitative decisions — minimizing cost, maximizing utility, fitting data, designing structures — reduce to this single template. The central machinery is differential: stationarity conditions identify candidate solutions, while convexity guarantees those candidates are global. A surprising fact is that for convex problems, the local-versus-global distinction disappears entirely — any local minimum is automatically a global one — which is why so much modern computation is spent recognizing or engineering convexity. The discipline splits into continuous vs. discrete, constrained vs. unconstrained, and convex vs. nonconvex, each with its own theory and algorithms.

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.

Formal Statement

The General Optimization Problem

A mathematical optimization problem is written

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

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 },\epsilon )$. The optimal value is $p^{\star }={\inf }_{x\in \mathcal{S}}f(x)$.

Convex 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

First-Order Necessary Conditions (Unconstrained)

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

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.

Karush–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

together with primal feasibility ($g_i\le 0$, $h_j=0$), dual feasibility (${\mu }_i\ge 0$), and complementary slackness:

For convex problems, the KKT conditions are also sufficient for global optimality.

Why It Holds / Derivation

Lagrange 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$).

1. 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$.

1. 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 })\}$.

1. 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]. $■$

Local 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 })$.

1. 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 })$.

1. As $\lambda \to 0^{+}$, the point $\lambda y+(1-\lambda )x^{\star }$ enters every neighborhood of $x^{\star }$, yet has strictly smaller objective value.

1. This contradicts $x^{\star }$ being a local minimizer. Hence $f(x^{\star })\le f(y)$ for all $y$: the local minimum is global. $■$

Constrained minimization: the gradient of $f$ aligns with the constraint gradient at the optimum.

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.

Building 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).

Worked Examples

Unconstrained minimization of a quadratic

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=\left(\begin{array}{cc}2& 1\\ 1& 2\end{array}\right)$ 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$.

Constrained optimization with Lagrange multipliers

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

1. By symmetry of the first two, $x=y$. Substituting and dividing yields $x=2z$.
2. 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$.
3. 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.

Common Misconceptions

Consider $f(x)=x^3$ on $\mathbb{R}$. Then $f^{\prime }(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^{\prime \prime }(0)=0$), and inspection shows $f$ decreases through $0$.

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^{\prime }(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.

Connections

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.

Real-World Applications

• Portfolio optimization (Markowitz, 1952): minimize variance $w^{\top }\Sigma w$ subject to a target return ${\mu }^{\top }w=r$ and $\sum w_i=1$ — a quadratic program solved with multipliers.
• Machine learning training: minimize empirical loss (e.g. cross-entropy) plus an $L_2$ regularizer; modern deep networks use stochastic gradient descent and Adam on nonconvex objectives.
• Structural engineering / topology optimization: distribute material to minimize compliance (maximize stiffness) under a mass budget, used in aerospace bracket design (e.g. Airbus 3D-printed parts).
• Logistics & operations research: vehicle routing, airline crew scheduling, and supply-chain planning as large mixed-integer linear programs (solved by CPLEX, Gurobi).
• Power systems: optimal power flow minimizes generation cost subject to Kirchhoff's laws and capacity limits, run by grid operators every few minutes.
• Economics: consumers maximize utility subject to a budget constraint; the Lagrange multiplier equals the marginal utility of income.
• Imaging & compressed sensing: reconstruct signals by minimizing $\Vert x{\Vert }_1$ subject to $Ax=b$, enabling fast MRI scans.

Historical Development

• 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^{\prime }(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.

Subtleties & Limits

See Also