B. Calculus, Convexity & Optimization

Gradients, Lipschitz continuity, convex sets and functions, descent methods and constraints

Book contents · Apply this chapter to a real decision · Glossary

The modules certify safety with inequalities and compute controllers, multipliers and weights by optimisation. Both rest on one toolbox: multivariable derivatives, bounds on how fast functions change, convexity, and algorithms that turn "find the best feasible point" into iterations. Each concept comes with a definition, a small example, the general statement, and pointers to where the modules use it.

First-course refresher: algebra and single-variable calculus

Multivariable calculus reuses the rules below, one coordinate or one curve at a time. Rebuild a rule with the tiny example before using its vector notation.

Check before continuing: recover $[(t-1)^2]\prime=2(t-1)$ and $[e^{2t}]\prime=2e^{2t}$, and explain why the constrained minimum of $(t-2)^2$ over $t\le1$ is at the boundary. If one step is unfamiliar, keep its recap open for the first local Easy exercise.

1. Gradients, Jacobians, Hessians & the Chain Rule

Almost every argument in the modules that involves motion (a state along a trajectory, weights during training, an input inside a ball) uses one trick: restrict a function of many variables to a line or a curve, and apply single-variable calculus there.

1.1 Gradients and directional slopes

Example. $f(x)=x_1^2+3x_1x_2$ has $\nabla f=(2x_1+3x_2,\ 3x_1)$, so $\nabla f(1,2)=(8,3)$ and along $v=(1,1)/\sqrt2$ the slope is $11/\sqrt2\approx7.78$. By Cauchy–Schwarz $\nabla f^{\top}v\le\|\nabla f\|$ for unit $v$, with equality for $v=\nabla f/\|\nabla f\|$: the steepest slope is $\sqrt{73}\approx8.54$.

1.2 Jacobians: derivatives of vector outputs

1.3 Chain rules along curves and networks

Derivatives along trajectories. For $\dot x=f(x)+g(x)u$ and $C^1$ $h$, the first case gives the Lie derivatives ($L_gh$ is a row when $u\in\mathbb R^m$):

The product rule gives $\tfrac{d}{dt}(x^{\top}Px)=\dot x^{\top}Px+x^{\top}P\dot x=2x^{\top}P\dot x$ for symmetric $P$, and the chain rule applied to $\nabla f$ (whose Jacobian is the Hessian) gives $\tfrac{d}{dt}\nabla f(x(t))=\nabla^2f(x(t))\,\dot x$. A path $q(s)$, $s\in[0,1]$, run with timing $s(t)$ has $\dot q=q'(s)\dot s$ and $\ddot q=q''(s)\dot s^2+q'(s)\ddot s$; with $\dot s\ge0$ the same points are visited in the same order, so time scaling changes only the timing, never the geometric path ($\dot s=0$ means stopping on it). Example: $\dot x_1=x_2$, $\dot x_2=-x_1+u$ and $h=1-x_1^2-x_2^2$ give $L_fh=-2x_1x_2+2x_2x_1=0$ and $L_gh=-2x_2$; at the boundary point $(0.6,0.8)$, $\dot h=-1.6u$, so exactly the inputs $u\le0$ keep $h$ from decreasing.

Backpropagation is the chain rule in reverse. $f(x)=W_2\sigma(W_1x+b_1)+b_2$ with scalar output has $\nabla f(x)=W_1^{\top}\operatorname{diag}(\sigma'(v))W_2^{\top}$, $v=W_1x+b_1$. Backpropagation evaluates it from the output side ($W_2^{\top}$, then $\operatorname{diag}(\sigma'(v))$, then $W_1^{\top}$) by matrix-vector products, so a gradient costs a few forward passes (finite differences need $n+1$). Take the ReLU $\sigma(z)=\max(z,0)$, applied to each coordinate: neuron $i$ is active when $v_i\gt0$, where $\sigma'(v_i)=1$, and inactive when $v_i\lt0$, where $\sigma'(v_i)=0$. With $W_1=\begin{bmatrix}1 & 2\\ 1 & -2\end{bmatrix}$, $b_1=0$, $W_2=[1\ \ 1]$ and $x=(1,0.25)$: $v=(1.5,0.5)$, both neurons active, $\operatorname{diag}(\sigma'(v))=I$ and $\nabla f=W_1^{\top}(1,1)^{\top}=(2,0)$; indeed $f=2x_1$ near $x$. ReLU networks are not differentiable on finitely many hyperplane pieces (zero volume), where autodiff uses a convention such as $\sigma'(0)=0$; along a segment they stay continuous and piecewise affine. More in Primer E.

1.4 Hessians: curvature in every direction

1.5 Taylor models and finite-change bounds

O-notation (Primer 0). $e(\delta)=O(\|\delta\|^k)$ as $\delta\to0$ means $|e(\delta)|\le C\|\delta\|^k$ for small $\delta$; $o(\|\delta\|^k)$ means $e/\|\delta\|^k\to0$. As $n\to\infty$ the same symbol bounds growth: "$O(n^2)$ operations" means at most $Cn^2$. Same definition, opposite limit: always say which variable goes where. Two $C^2$ functions that agree to first order at $x_0$ (value and gradient) differ by $O(\|\delta\|^2)$: first-order agreement fixes the gradient but says nothing quantitative at a finite step, which needs a second-order bound.

Practice: Gradients, chain rules and Taylor models

Work from Easy to Medium before trying Hard. Use the review link for a missing definition, then try again with the explanation closed.

2. Matrix Calculus You Will Need

All gradients with respect to vectors and matrices follow from one habit: write the first-order change of the function (its differential) and read the gradient off it.

Why $X^{-1}$ for $\log\det$. $\det(X+\varepsilon E)=\det X\det(I+\varepsilon X^{-1}E)$ and $\det(I+\varepsilon M)=\prod_i(1+\varepsilon\mu_i)=1+\varepsilon\operatorname{tr}M+O(\varepsilon^2)$ ($\mu_i$ the eigenvalues of $M$), so $\log\det(X+\varepsilon E)=\log\det X+\varepsilon\operatorname{tr}(X^{-1}E)+O(\varepsilon^2)$. Check with $X=\begin{bmatrix}2 & 1\\ 1 & 2\end{bmatrix}$, $E=\begin{bmatrix}0 & 1\\ 1 & 0\end{bmatrix}$: $\det(X+\varepsilon E)=3-2\varepsilon-\varepsilon^2$ has log-slope $-\tfrac23$ at $0$, and $\operatorname{tr}(X^{-1}E)=\tfrac13(-1-1)=-\tfrac23$. For the inverse, $dX\,X^{-1}+X\,d(X^{-1})=d(I)=0$ (scalar case: $d(1/x)=-dx/x^2$).

Example (least squares). Fitting $y\approx\theta_1+\theta_2t$ to $(0,1),(1,2),(2,2)$: $A=\begin{bmatrix}1 & 0\\ 1 & 1\\ 1 & 2\end{bmatrix}$, $b=(1,2,2)$, and $\nabla\|A\theta-b\|^2=0$ gives the normal equations $\begin{bmatrix}3 & 3\\ 3 & 5\end{bmatrix}\theta=\begin{bmatrix}5\\ 6\end{bmatrix}$, so $\theta=(7/6,1/2)$; the residual $(1/6,-1/3,1/6)$ is orthogonal to both columns. The Hessian $2A^{\top}A\succ0$ makes this the global minimiser (Section 4). The ridge objective $\|y-K\alpha\|^2+\lambda\alpha^{\top}K\alpha$ of GP regression has gradient $-2K(y-(K+\lambda I)\alpha)$, which vanishes at $\alpha=(K+\lambda I)^{-1}y$.

Inverses, linear solves, optimisers. For $\|E\|\lt1$, $(I+E)^{-1}=I-E+E^2-\cdots$ (Neumann series), so $(X+\varepsilon E)^{-1}=X^{-1}-\varepsilon X^{-1}EX^{-1}+O(\varepsilon^2)$ and, for $\lambda\gt\|K\|$, $(K+\lambda I)^{-1}=\lambda^{-1}I-\lambda^{-2}K+O(\lambda^{-3})$, a matrix of norm at most $C\lambda^{-3}$ (eigenvalue by eigenvalue: $\tfrac1{\lambda+k_i}=\tfrac1\lambda-\tfrac{k_i}{\lambda^2}+O(\lambda^{-3})$). If $A(\theta)x=b(\theta)$, then $A\,dx+dA\,x=db$, so $dx=A^{-1}(db-dA\,x)$. If $x^\star(\theta)$ solves $\nabla_xF(x^\star,\theta)=0$ with $\nabla^2_{xx}F\succ0$, then $\partial x^\star/\partial\theta=-(\nabla^2_{xx}F)^{-1}\nabla^2_{x\theta}F$ (implicit function theorem): this is how sensitivities of an optimisation layer or an MPC problem are computed.

Hessian-vector products. For fixed $v$, $\nabla^2f(x)\,v=\nabla_x\big(\nabla f(x)^{\top}v\big)$, which autodiff computes for about the cost of two gradients without forming the $n\times n$ matrix. Example: $f=x_1^2x_2$ gives $\nabla f^{\top}v=2x_1x_2v_1+x_1^2v_2$, whose gradient $(2x_2v_1+2x_1v_2,\ 2x_1v_1)$ equals $\begin{bmatrix}2x_2 & 2x_1\\ 2x_1 & 0\end{bmatrix}v$. A cheaper approximation is $(\nabla f(x+\varepsilon v)-\nabla f(x))/\varepsilon$. In trust-region RL the matrix is the Hessian of the KL divergence at $\theta_k$ (the Fisher matrix), often damped to $(H+\beta I)v$, and conjugate gradients (Section 5) solve $Hx=g$ with these products alone.

Practice: Matrix derivatives and sensitivity

Work from Easy to Medium before trying Hard. Use the review link for a missing definition, then try again with the explanation closed.

3. Lipschitz Continuity, Smoothness & Sensitivity

A Lipschitz constant is a worst-case exchange rate between input change and output change. It turns one measurement at one point into a guarantee on a whole neighbourhood, which is why it appears in nearly every safety certificate of the section.

Intuition and examples. Every chord has slope at most $L$, so around each point the graph stays in the cone $|f(x')-f(x)|\le L|x'-x|$. $|x|$ and $\sin x$ are $1$-Lipschitz on $\mathbb R$. $x^2$ is not Lipschitz on $\mathbb R$ (chord slope $x+x'$) but is $2R$-Lipschitz on $[-R,R]$, hence locally Lipschitz. $\sqrt x$ on $[0,1]$ is continuous but not Lipschitz (infinite slope at $0$), and a step function is not even continuous: Lipschitz $\Rightarrow$ continuous, not conversely.

Example. $f(x)=3x_1-x_2$ has gradient $g=(3,-1)$ everywhere, so $|f(x)-f(y)|$ is at most $3\|x-y\|_1$ ($\|g\|_\infty=3$), $4\|x-y\|_\infty$ ($\|g\|_1=4$) or $\sqrt{10}\|x-y\|_2$, each constant exact: an $\ell_\infty$ gradient bound gives an $\ell_1$ Lipschitz constant. For nonlinear $f$ bound each dual norm over $D$ separately: $(2.1,2.1)$ has a smaller $\ell_2$ but a larger $\ell_1$ norm than $(3,-1)$. With several smooth branches (an input saturation switching on and off) take the largest gradient norm over all branches.

Sensitivity along trajectories. Compositions of non-expansive maps are non-expansive, so trajectories of $x_{t+1}=F(x_t)$ with $L(F)\le1$ never separate; the Euler step $x^+=(1-hk)x$ of $\dot x=-kx$ is non-expansive iff $0\le hk\le2$. For nonempty families of real values $a_t,b_t$ bounded below, with $|a_t-b_t|$ bounded above, $|\inf_ta_t-\inf_tb_t|\le\sup_t|a_t-b_t|$ (compare each family with the other plus the finite uniform difference bound). Thus, with an $L$-Lipschitz $\bar g$ and non-expansive dynamics, the real margin $\inf_t\bar g(x_t)$ is $L$-Lipschitz in $x_0$ provided every trajectory has $\bar g(x_t)$ bounded below; this condition makes each margin finite. For a model $\hat f$ with $\|f^\star-\hat f\|\le e$ and $f^\star$ $L_f$-Lipschitz, prediction errors obey $d_{t+1}\le L_fd_t+e$, so $d_t\le L_f^td_0+e\sum_{j\lt t}L_f^j$. From the same initial state ($d_0=0$) this is $e(L_f^t-1)/(L_f-1)$, or $et$ if $L_f=1$: $e=0.01$, $L_f=1.1$ give $d_{10}\le0.159375$ (the exact bound is $0.15937424601$, rounded upward), and margins grow geometrically when $L_f\gt1$. In continuous time a Lipschitz vector field gives unique solutions with $\|x(t)-x'(t)\|\le e^{Lt}\|x(0)-x'(0)\|$ (Primer D); a merely continuous one need not: $\dot x=\sqrt{|x|}$, $x(0)=0$ is solved by $x\equiv0$ and by $x=t^2/4$.

Practice: Lipschitz bounds, grids and model errors

Work from Easy to Medium before trying Hard. Use the review link for a missing definition, then try again with the explanation closed.

4. Convex Sets, Convex Functions & Conjugates

Convexity makes local information global: a tangent plane underestimates the whole function, a stationary point is a global minimiser, and a feasible region has no hidden pockets. It separates problems that solvers answer reliably from problems they only attack heuristically.

Not convex: $\{\|x\|\ge1\}$, two disjoint intervals, the ReLU graph, $\{0,1\}^n$. Convexity is preserved by arbitrary intersections, Cartesian products, and affine images and preimages; linear maps commute with hulls, $A\operatorname{conv}S=\operatorname{conv}(AS)$, since $A\sum_i\theta_ix_i=\sum_i\theta_iAx_i$. Polytopes as quadratic constraints: for $x\in\{Hx\le h\}$ each product $(h-Hx)_i(h-Hx)_j\ge0$, so $(Hx-h)^{\top}\Gamma(Hx-h)\ge0$ for every $\Gamma$ with nonnegative entries, one quadratic form in $(x,1)$ once the constant coordinate is appended. It is an outer approximation: a point violating two facets also makes their product positive.

Recognising convexity. Convex: norms, $\|Ax+b\|$, $e^x$, $-\log x$, $x\log x$, $\tfrac12x^{\top}Qx$ ($Q\succeq0$), maxima of affine functions such as $\nu\mapsto(z-\nu)_+$, and the KL divergence (jointly). Concave: $\log x$, $\sqrt x$, $\log\det X$ ($X\succ0$), $\lambda_{\min}(X)=\min_{\|v\|=1}v^{\top}Xv$, and every infimum of affine functions, such as a Lagrange dual function. Rules: (i) nonnegative sums and expectations ($\theta\mapsto\mathbb E_zf(\theta,z)$ is convex if each $f(\cdot,z)$ is); (ii) composition with affine maps; (iii) pointwise maxima and suprema; (iv) partial minimisation: $\inf_yF(x,y)$ is convex if $F$ is jointly convex (and the infimum is $\gt-\infty$); (v) perspectives $t\,f(x/t)$, $t\gt0$.

Example. $x_1^2+x_2^2+ax_1x_2$ has Hessian eigenvalues $2\pm a$: convex iff $|a|\le2$. For $a=3$ the diagonal is positive, yet $f(t,-t)=-t^2$: nonnegative curvature along the axes does not make a Hessian PSD.

Slopes and potentials: in one variable, for $0\le\mu\le L$, "$\Phi'$ has chord slopes in $[\mu,L]$" is exactly "$\Phi$ is $\mu$-strongly convex and $L$-smooth", so an activation slope-restricted in $[\alpha,\beta]$ with $0\le\alpha\le\beta$ (nondecreasing, as Module 12 assumes) is the derivative of the convex potential $\int_0^u\varphi$ (ReLU is the derivative of $\tfrac12(u)_+^2$). Negative slopes break this: $\varphi(u)=-u$ has the concave potential $-u^2/2$. A set $R$ of pairs is a monotone relation if $(a-a')(b-b')\ge0$ for all $(a,b),(a',b')\in R$; it may be multivalued, like the subdifferential of $|x|$, whose graph contains the vertical segment $\{0\}\times[-1,1]$.

Example. $Z$ uniform on $\{0,1,2,3\}$ and $F(\nu)=\nu+2\,\mathbb E(Z-\nu)_+$ (the Rockafellar–Uryasev function at level $\tfrac12$, Primer C), convex by rules (i) and (iii), with $F'_+(\nu)=1-2\,\mathbb P(Z\gt\nu)$, $F'_-(\nu)=1-2\,\mathbb P(Z\ge\nu)$. At $\nu=1$: $[-0.5,0]\ni0$; at $\nu=2$: $[0,0.5]\ni0$; in between $F'=0$. The minimisers form the interval $[1,2]$, and $\min F=2.5$, the mean of the upper half $\{2,3\}$ (the CVaR).

Examples. $X$ uniform on $\{1,4,9,16\}$: $\mathbb E\sqrt X=2.5\le\sqrt{\mathbb EX}=\sqrt{7.5}\approx2.74$. Concavity of $\log$: $\sum_{i=1}^d\log(1+\mu_i/\lambda)\le d\log(1+\tfrac1d\sum_i\mu_i/\lambda)$, with equality iff all $\mu_i$ are equal; for $\lambda=1$, $\mu_1+\mu_2=4$: $(3,1)$ gives $\log8\approx2.08$, $(2,2)$ gives $\log9\approx2.20$. Sublevel sets $\{f\le c\}$ of convex $f$ are convex (e.g. the ellipsoid $\{x^{\top}Px\le c\}$, $P\succ0$), and $\{h\ge0\}$ is convex for concave $h$; the converse fails ($\sqrt{|x|}$).

log det and matrix convexity. $\log\det(X+tE)=\log\det X+\sum_i\log(1+t\mu_i)$ with $\mu_i$ the eigenvalues of $X^{-1/2}EX^{-1/2}$: concave in $t$, so $\log\det$ is concave on $X\succ0$ and maximising $\log\det S$ under LMIs is a convex problem (determinant maximisation, not an SDP with linear objective; interior-point solvers handle it). $F$ is matrix-convex if $F(\theta X+(1-\theta)Y)\preceq\theta F(X)+(1-\theta)F(Y)$ in the PSD order; $W\mapsto W^{\top}W$ is, since the difference equals $\theta(1-\theta)(A-B)^{\top}(A-B)\succeq0$. So $\{W:W^{\top}W\preceq M\}$ is convex, while a term such as $-W^{\top}TW$ on the side that must stay small is matrix-concave and destroys convexity. A product $TW$ of two unknowns is bilinear: a BMI, nonconvex jointly and affine once $T$ is fixed.

Bregman divergence. $D_\varphi(x,y)=\varphi(x)-\varphi(y)-\nabla\varphi(y)^{\top}(x-y)\ge0$ for convex $\varphi$ (first-order condition). $\varphi=\tfrac12\|x\|^2$ gives $\tfrac12\|x-y\|^2$; the negative entropy $\sum_ip_i\log p_i$ gives $\mathrm{KL}(x\|y)$ on the simplex. It is not symmetric.

Convex problems (convex $f_0$, convex $f_i\le0$, affine $h_j=0$) have no bad local minima: if $y$ beat a local minimiser $x$, the points $x+\theta(y-x)$ for small $\theta$ would beat it too. A convex feasible region alone is not enough (maximising a nonconcave acquisition over a ball is nonconvex), and convexity depends on the variables: an objective can be convex in an auxiliary $\nu$ or in occupancy measures but not in network weights.

Practice: Convexity, subgradients and conjugates

Work from Easy to Medium before trying Hard. Use the review link for a missing definition, then try again with the explanation closed.

5. Gradient Descent, Newton's Method & Step Sizes

Controllers, multipliers and network weights are improved step by step. What matters is the step size, the information each step uses (gradients, noisy gradients, function values, curvature) and how many steps an accuracy costs.

Step size and conditioning. On $f=\tfrac L2x^2$ with $L\gt0$, the iteration $x_{k+1}=(1-\eta L)x_k$ from a nonzero initial point converges iff $0\lt\eta\lt2/L$ (at $\eta=2/L$ it oscillates forever, $x_{k+1}=-x_k$), and $\eta=1/L$ lands on the minimiser at once; with $L=4$, $\eta=0.4$ multiplies by $-0.6$ (oscillating convergence) and $\eta=0.6$ by $-1.4$ (divergence). On $f=\tfrac12(x_1^2+10x_2^2)$ the curvatures are $\mu=1$ and $L=10$, the condition number is $\kappa=L/\mu=10$, and with $\eta=1/L$ the coordinate $x_2$ is solved in one step while $x_1$ shrinks only by $0.9$ per step: the flattest direction sets the pace, about $\kappa\ln(1/\varepsilon)$ steps (see the explorer).

Rates and budgets (Primer 0). "An $O(1/\sqrt T)$ rate" means error $\le C/\sqrt T$ for large $T$, with $C$ hiding constants such as $L$, $\|x_0-x^\star\|$ or a noise level; $\Omega$ is a lower bound, $\Theta$ both. Solve for the budget: $C/\sqrt T\le\varepsilon$ needs $T\ge C^2/\varepsilon^2$, while $(1-1/\kappa)^T$ needs only $O(\kappa\log(1/\varepsilon))$ steps. Count iterations, work per iteration (a dense $n\times n$ solve $O(n^3)$, a matrix-vector product $O(n^2)$) and measurements per iteration separately.

Example. $f(x)=\tfrac12\mathbb E(x-Z)^2$, $Z$ uniform on $\{1,2,3,6\}$: at $x=0$ the gradient is $-3$; the minibatch $\{1,6\}$ gives $-3.5$, $\{2,3\}$ gives $-2.5$, and the six minibatches of size two average exactly $-3$. Variants: momentum adds $\beta(x_k-x_{k-1})$, and accelerated methods improve $\kappa$ to $\sqrt\kappa$ in iteration counts; Adam rescales each coordinate by running averages of $g$ and $g^2$ (treat it as a black box). Zeroth-order methods see only values: $\hat g_i=(f(x+he_i)-f(x-he_i))/(2h)$ has error $O(h^2)$ but costs $2d$ evaluations, and noise is amplified by $1/h$; random search keeps random perturbations that improve $f$.

Example. $f(x)=x-\log x$ ($x\gt0$, minimiser $1$) gives $x^+=2x-x^2$, i.e. $1-x^+=(1-x)^2$: from $0.5$, the iterates $0.75,\ 0.9375,\ 0.99609,\ 0.9999847$ square the error. From $3$ the full step lands at $-3$, outside the domain; backtracking rejects $t=1$ and $t=\tfrac12$ (which gives $0$) and accepts $t=\tfrac14$: $x=1.5$, with $f(1.5)=1.095\le f(3)-0.25\cdot\tfrac14\cdot4=1.651$. Conjugate gradients solve $Hv=g$ ($H\succ0$) using only products $Hp$: they minimise $\tfrac12v^{\top}Hv-g^{\top}v$ over growing subspaces, finish in at most $n$ steps in exact arithmetic, report accuracy by the residual $\|g-Hv\|$, and need about $\sqrt{\kappa(H)}\log(1/\varepsilon)$ iterations; with Hessian-vector products (Section 2) this gives Newton-type steps for millions of parameters.

Four more ideas. (1) Majorise–minimise: a surrogate $u(\cdot\mid x_k)\ge f$ touching $f$ at $x_k$ gives $f(x_{k+1})\le u(x_{k+1}\mid x_k)\le u(x_k\mid x_k)=f(x_k)$ for its minimiser; gradient descent with $\eta=1/L$ is MM with the upper bound of Section 3, and minorise–maximise is the mirror image. (2) Mirror descent / multiplicative weights on the simplex: $p_{k+1}(a)\propto p_k(a)e^{-\eta g_k(a)}$, a step measured in KL instead of Euclidean distance that never leaves the simplex; $p=(\tfrac12,\tfrac12)$, $g=(1,0)$, $\eta=\ln2$ give $(\tfrac13,\tfrac23)$. (3) Trust regions for black-box search: accept only steps within a radius $\Delta_k$, enlarged after success and shrunk after failure. (4) Multi-start: minimising $x^4-2x^2+0.5x$, gradient descent from $0.5$ stops at the local minimiser $0.930$ ($f=-0.517$), from $-0.5$ at the global one $-1.057$ ($f=-1.515$); restarts help but certify nothing for nonconvex objectives.

Practice: Steps, curvature and line searches

Work from Easy to Medium before trying Hard. Use the review link for a missing definition, then try again with the explanation closed.

6. Constraints: Lagrange Multipliers, Projections, Penalties & Barriers

Safety enters optimisation as constraints, handled in four ways: attach a price (multiplier), project onto the feasible set, penalise violations, or erect a barrier. The crucial difference is whether the answer is guaranteed to satisfy the constraint.

Lagrange multipliers. If $x^\star$ minimises $f$ subject to $h(x)=0$ and $\nabla h(x^\star)\ne0$, then $\nabla f(x^\star)+\nu\nabla h(x^\star)=0$ for some number $\nu$. Geometrically, the level set of $f$ is tangent to the constraint surface; otherwise sliding along the surface would decrease $f$. Example: minimise $x_1+x_2$ on the circle $x_1^2+x_2^2=2$. The conditions $(1,1)+\nu(2x_1,2x_2)=0$ and the constraint give $\nu=\pm\tfrac12$; $\nu=\tfrac12$ yields $x^\star=(-1,-1)$ and $p^\star=-2$. The multiplier is a price: with right-hand side $c$ instead of 2, $p^\star(c)=-\sqrt{2c}$, and $dp^\star/dc=-\tfrac12=-\nu$ at $c=2$.

Inequalities. Take one smooth constraint $f_1\le0$ and a local minimiser $x^\star$ in the interior of $\mathcal D$. Either the constraint is inactive ($f_1(x^\star)\lt0$): then it plays no role locally, $\lambda=0$ and $\nabla f_0(x^\star)=0$. Or it is active ($f_1(x^\star)=0$): then, if $\nabla f_1(x^\star)\ne0$, $\nabla f_0+\lambda\nabla f_1=0$ with $\lambda\ge0$, because the downhill direction must point out of the feasible set. Both cases are summarised by $\lambda\ge0$ and $\lambda f_1(x^\star)=0$ (complementary slackness). The condition $\nabla f_1(x^\star)\ne0$ is a constraint qualification; without one, no multiplier need exist (see below).

Running example ($f_0=(x-2)^2$, $f_1=x-1$): the unconstrained minimum $x=2$ is infeasible, so the constraint is active at $x^\star=1$, and $2(1-2)+\lambda=0$ gives $\lambda^\star=2$. For the looser constraint $x\le3$ the optimum $x=2$ is interior and $\lambda=0$. The general rules for several constraints at once are the KKT conditions below; duality behind them is in Module 2.

The KKT conditions: several inequality constraints at once

In plain words. Picture a ball rolling downhill inside a fenced field. It comes to rest either in a dip in the middle of the field, where the ground is flat, or pressed against one or more fences. At a fence, gravity pulls the ball outward, into the fence, and the fence pushes back. The Karush–Kuhn–Tucker (KKT) conditions say exactly this. At a constrained minimum, the downhill pull $-\nabla f_0$ is cancelled by pushes from the constraints the point is touching. Each push has a strength $\lambda_i\ge0$, and a fence that is not touched pushes with strength zero.

When must a minimum satisfy KKT? Constraint qualifications

KKT is a test that every well-behaved minimiser passes. Well-behaved is made precise by a constraint qualification (CQ): a condition on the constraints at the point, which guarantees that their gradients describe the feasible set correctly nearby. Without one, a true minimiser can fail the test. Minimise $x$ subject to $x^2\le0$: the only feasible point is $x^\star=0$, so it is the minimiser. But $\nabla(x^2)=2x$ vanishes at $0$, so stationarity, $1+\lambda\cdot0=0$, has no solution. To first order the constraint looks like "$0\le0$", which allows every direction, while in reality no direction is allowed.

KKT points in non-convex problems. Without convexity, KKT is necessary (under a CQ) but not sufficient: a KKT point can be a local minimum, a saddle point, or even a local maximum. Algorithms for non-convex problems therefore usually promise convergence to a KKT point, or to an approximate one (below), not to a minimum. Examples are the primal–dual policy-gradient methods of Module 8 and the log-barrier method LB-SGD in Module 4.

Examples. $(1.7,-0.4,0.3)\mapsto(1,0,0.3)$ on $[0,1]^3$; $(3,4)\mapsto(0.6,0.8)$ on the unit ball; $(2,1)\mapsto(1,0)$ on $\{x_1+x_2\le1\}$. Clipping is a two-ReLU network, $\operatorname{clip}_{[l,u]}(x)=u-(u-l-(x-l)_+)_+$: input saturation inside a network model. The interval must be closed and nonempty (on the open $(0,1)$ the point $2$ has no nearest point). Nonconvex sets can have several nearest points: $0$ projects onto $\{|x|\ge1\}$ as the set $\{-1,1\}$ (a tie-break is needed), and the nearest orthogonal matrix to an invertible $W=U\Sigma V^{\top}$ is $UV^{\top}$. The norm matters: projecting transformed coordinates is a different operation.

Projected gradient $x_{k+1}=P_C(x_k-\eta\nabla f(x_k))$ keeps iterates feasible, its fixed points satisfy $-\nabla f\in N_C$, and for $L$-smooth convex $f$ with $\eta=1/L$ it has the rates of Section 5. Projected gradient ascent over a box also serves to falsify a certificate by maximising its violation (a violation found refutes it; none found proves nothing) and to tighten a bound valid for every parameter value (e.g. relaxation slopes in $[0,1]^n$), where soundness never depends on reaching the optimum.

Running example. The quadratic penalty gives $x_\rho=\tfrac{4+\rho}{2+\rho}$: $1.5,\ 1.1,\ 1.01$ for $\rho=2,18,198$, always infeasible (violation $2/(2+\rho)$). The curvature is $2$ on one side and $2+\rho$ on the other, so large $\rho$ mixes very different scales (ill-conditioning): gradient steps must shrink like $1/\rho$, and errors in an approximate objective are amplified. The exact penalty returns $x=1$ for $\rho\ge2=\lambda^\star$, at the price of a kink; in general $\rho\gt\|\lambda^\star\|_\infty$ makes it exact for a convex problem with an attained optimal multiplier (strong duality), but a nonconvex problem can defeat it: $-x^4+\rho(x^2-1)_+$ is unbounded below for every $\rho$, although the constrained minimisers $\pm1$ of $-x^4$ s.t. $x^2\le1$ have $\lambda^\star=2$. A linear slack penalty has the same threshold: $s=1-p/2$ for $p\lt2$ ($x=1.5$ at $p=1$) and $s=0$ for $p\ge2$. Softening keeps every problem feasible (useful for recursive feasibility in MPC), but the constraint is violated whenever that is cheaper, so feasibility of the softened problem proves nothing about the original: keep safety constraints hard, use slack for soft performance terms. The augmented Lagrangian with $\rho=2$ gives $(x,\lambda)=(1.5,1),(1.25,1.5),(1.125,1.75)\to(1,2)$: the multiplier absorbs the price, so a finite $\rho$ suffices, and its positive part is the "proportional violation correction" $\max\{0,\lambda+c\cdot\text{violation}\}$.

ADMM splits $\min f(x)+g(z)$ s.t. $x=z$: minimise the augmented Lagrangian over $x$, then $z$ (often a projection), then update the multiplier; guaranteed for convex problems, a heuristic for nonconvex training.

Approximate KKT points

Iterative algorithms stop after finitely many steps, so what they deliver is a point that satisfies the KKT conditions only approximately. Module 4 uses the following version. A feasible $x$ with multipliers $\lambda_i\ge0$ is an $\epsilon$-KKT point if

Papers differ in the details, for example in which residuals they bound and in which norm, so check the definition before comparing rates.

Practice: Feasibility, KKT and penalty residuals

Work from Easy to Medium before trying Hard. Use the review link for a missing definition, then try again with the explanation closed.

7. Linear & Quadratic Programs

LPs and QPs are what solvers handle reliably at scale, so the modules reduce to them where possible and treat the solver as a black box. You need the forms, the geometry, and what a solver's answer certifies.

Examples. Maximise $x_1+x_2$ s.t. $x_1+2x_2\le4$, $3x_1+x_2\le6$, $x\ge0$: vertices $(0,0),(2,0),(0,2),(1.6,1.2)$ give $0,2,2,2.8$, so $(1.6,1.2)$ is optimal. Slack allocation: maximise $\sum_s\epsilon_s$ s.t. $w^{\top}\epsilon\le B$, $\epsilon\ge0$, $w\ge0$: each vertex puts the budget on one coordinate (value $B/w_s$), so the smallest $w_s$ wins; $w=(2,1,0.5)$, $B=1$ give $\epsilon=(0,0,2)$, and if some $w_s=0$, $e_s$ is a recession direction and the LP is unbounded. Strict feasibility: $\sigma_i(a_i^{\top}x+b_i)\gt0$ for all $i$ (e.g. "does this ReLU activation pattern occur?") is solvable iff $\max s$ s.t. $\sigma_i(a_i^{\top}x+b_i)\ge s$, $s\le1$ has optimum $s^\star\gt0$; the cap keeps the LP bounded.

Solvers as black boxes. Interior-point (Newton on a barrier), simplex and active-set methods (moving between vertices or active sets) and first-order splitting (ADMM-based, e.g. OSQP, SCS) return an optimal point with multipliers, or a certificate of infeasibility or unboundedness. "Optimal" means residuals below a tolerance (about $10^{-8}$ for interior point, $10^{-3}$ to $10^{-5}$ for first-order methods), so returned points may violate constraints by that much: for a safety certificate, re-check the solution independently with a margin, or in exact or interval arithmetic. Numerical feasibility is not a validated proof.

Hardness and relaxations. LPs and convex QPs are solvable in time polynomial in the bit size of the data. SOCPs and SDPs are solvable to accuracy $\varepsilon$ in time polynomial in the size and $\log(1/\varepsilon)$ only under assumptions on the encoding and conditioning (for instance a known bound $R$ on the size of a solution, entering as $\log R$, and a strictly feasible point), not for every input: in a Khachiyan-type example the LMIs $\begin{bmatrix}x_{i+1} & x_i\\ x_i & 1\end{bmatrix}\succeq0$, i.e. $x_{i+1}\ge x_i^2$, with $x_0=2$ force $x_n\ge2^{2^n}$, a number with exponentially many bits (Pataki & Touzov, arXiv 2021). Nonconvex problems can be NP-hard: at least as hard as every problem in NP (yes/no questions whose "yes" answers can be checked quickly from a certificate, such as an input violating a property), with no known polynomial-time algorithm. NP-complete = NP-hard and in NP; the complementary "no violating input exists" questions of verification form coNP. Hardness is worst case; many instances are easy. Mixed-integer programs add integer variables: $y=\max(0,v)$ with bounds $l\lt0\lt u$ is exactly $y\ge v$, $y\ge0$, $y\le uz$, $y\le v-l(1-z)$, $z\in\{0,1\}$ (big-M); $z\in[0,1]$ gives an LP relaxation (an outer bound), tightened by valid cuts, inequalities satisfied by every integer solution. SDP relaxations: for $x\in\{\pm1\}^n$, $x^{\top}Wx=\operatorname{tr}(WX)$ with $X=xx^{\top}$; replacing $X=xx^{\top}$ by $X\succeq0$, $\operatorname{diag}X=\mathbf 1$ upper-bounds $\max x^{\top}Wx$ (the MAXCUT idea).

Practice: Linear programs, quadratic programs and feasibility

Work from Easy to Medium before trying Hard. Use the review link for a missing definition, then try again with the explanation closed.

8. argmax, Min-Max Problems & Saddle Points

The modules optimise over infinite sets (inputs, policies, controllers, signals) and nest optimisations. Here is what $\sup$, $\operatorname{arg\,max}$ and $\min\max$ promise, and what they do not.

Examples. $\operatorname{arg\,max}_{[-1,1]}x^2=\{-1,1\}$ (tie); $\sup_{(0,1)}x=1$ with empty argmax; $\inf_{x\ge0}e^{-x}=0$ is not attained; $\sup_{u\in\mathbb R}u=+\infty$; the CVaR function of Section 4 has argmin $[1,2]$.

Suprema over inputs, signals, policies. $\sup_{u\in[-1,1]}(a+bu)=a+|b|$ at $u=\operatorname{sign}(b)$, but $+\infty$ over $u\in\mathbb R$ when $b\ne0$: a condition $\sup_{u\in U}[L_fh+L_gh\,u+\alpha(h)]\ge0$ is automatic where $L_gh\ne0$ if inputs are unbounded, and a real restriction for bounded $U$. A supremum inequality need not provide an input: $\sup_{u\in(0,1)}u\ge1$, yet no $u\in(0,1)$ has $u\ge1$; attainment needs e.g. compact $U$ and continuity. For signals, $\|d\|_\infty=\sup_{t\ge0}\|d(t)\|_2$ is a supremum over time of the Euclidean norm, not the largest coordinate of a vector (measurable signals use the essential supremum). Optimising over a policy class or over controllers uses the same definitions on sets of functions; attainment is an assumption. If $\varphi:[0,\infty)\to\mathbb R$ is strictly increasing, $\varphi^{-1}(s)$ exists only for $s$ in its range, below $\sup\varphi$.

Infima, distances, level searches, max-min. $\inf_t\bar g(x_t)$ need not be attained at a visited state ($x_t=2^{-t}$, $\bar g(x)=x$: infimum $0$, every value positive). $\operatorname{dist}(x,S)=\inf_{s\in S}\|x-s\|$ is attained for closed nonempty $S$. A level search $c^\ast=\inf\{V(x):x\in B\}$ is $+\infty$ for empty $B$, and the acceptable levels may form $[0,c^\ast)$, with a supremum but no largest element. To choose a backup, first take each candidate's worst constraint margin, then the best candidate, $s^\star\in\operatorname{arg\,max}_s\min_im_i(s)$: margins $(0.4,0.1)$, $(0.3,0.25)$, $(0.5,-0.1)$ have worst cases $0.1,\ 0.25,\ -0.1$, so the second wins although the third has the best single margin.

Examples. $x^2-y^2$ on $[-1,1]^2$: saddle $(0,0)$, value $0$. $(x-y)^2$ on $[0,1]^2$ is not concave in $y$: $\min_x\max_y=\min_x\max(x^2,(1-x)^2)=\tfrac14$ but $\max_y\min_x=0$. Matching pennies, $x,y\in\{\pm1\}$, $L=xy$: $\min\max=1$, $\max\min=-1$; with mixed strategies ($p,q$ = probabilities of $+1$) the payoff $(2p-1)(2q-1)$ is bilinear with saddle $p=q=\tfrac12$ and value $0$: randomising convexifies the game. If both players run no-regret learners, their time-averaged strategies approach a saddle point (statement).

Where min-max appears: duality, since $\sup_{\lambda\ge0}(f_0+\lambda^{\top}f)$ is $f_0(x)$ for feasible $x$ and $+\infty$ otherwise, so $\inf_x\sup_\lambda$ is the primal, $\sup_\lambda\inf_x$ the dual, weak duality is the max-min inequality, and strong duality means these two values are equal (e.g. under Slater's condition). A saddle point exists exactly when they are equal and both optima are attained; equal values alone do not give one ($\inf_xe^x$ s.t. $-1\le0$ satisfies Slater's condition and has $p^\star=d^\star=0$ and $\lambda^\star=0$, but no minimiser) (Module 2; running example: $d(\lambda)=\lambda-\lambda^2/4$, $d^\star=1=p^\star$); robust control, min over controllers of the max over disturbances; adversarial training, min over weights of the max loss over a perturbation ball, the inner max approximated by projected gradient ascent. With several objectives the nondominated trade-offs form a Pareto front (Primer E).

Practice: Optimisers, worst cases and saddle points

Work from Easy to Medium before trying Hard. Use the review link for a missing definition, then try again with the explanation closed.

Interactive: Descent, Projection & Barriers in 2-D

Minimise $f(x)=\tfrac12(x-c)^{\top}Q(x-c)$, $c=(1.5,1.1)$, $Q=R_\theta\operatorname{diag}(1,\kappa)R_\theta^{\top}$ (so $\mu=1$, $L=\kappa$), over a convex set $C$ that excludes $c$. From the black point (click to move it) run gradient descent ignoring $C$, projected gradient $x_{k+1}=P_C(x_k-\eta\nabla f(x_k))$ started at $x_0=P_C(\text{black point})$, the penalty minimisers of $f+\tfrac\rho2\sum_i(f_i)_+^2$ for $\rho=1,4,\dots,1024$, and the barrier method (damped Newton on $tf+\phi$, $t\leftarrow4t$ until $m/t\lt10^{-3}$). Green dot: a reference optimum (closed form for the half-space, numerical bisection for the disc, or 5000 projected steps for the box). The latter two are numerical approximations, with accuracy limited by their stopping rules.

What to look for. (1) Gradient descent heads for $c$ and leaves $C$; projected gradient slides along the boundary to $x^\star$. (2) Beyond $\eta L=2$ the guarantee is gone: the steepest error component is multiplied by $|1-\eta L|\gt1$ per step, so gradient descent diverges from every start with such a component (almost every start), and at $\eta L=2$ that component flips sign forever without decaying. Larger $\kappa$ means zig-zags and more steps. (3) Penalty minimisers stay infeasible and the violation shrinks like $1/\rho$. The Hessian condition number usually grows with $\rho$, because the penalty adds curvature $\rho$ across the constraint only (half-space, disk, a single violated box bound); it does not when curvature is added in every direction: at a box corner with both upper bounds violated the Hessian is $Q+\rho I$ and the condition number falls towards $1$ (exactly $1$ for $\kappa=1$). (4) Barrier iterates never leave $C$, and at each centre $x^\star(t)$ the gap stays below $m/t$ (the readout compares the two at the last centre); from a start outside $C$ the barrier method cannot run.

Exercises

Ready to use optimisation in the modules?

Try the Easy and Medium exercises in derivatives, Lipschitz bounds, convexity, and KKT with the solutions closed. You should be able to compute a gradient, explain the norm and domain of a Lipschitz bound, and check feasibility separately from stationarity.

Before a filter or learning algorithm, redo the step-size exercise and the actuator-box QP. Explain why a penalty minimiser can be infeasible and why the minimax order matters. Revisit only the linked section that causes difficulty; the Hard exercises can be spaced over later study sessions. Next: Primer C: probability and uncertainty, then Module 1.

Further Reading

Flashcards