f is convex when f(λx + (1−λ)y) ≤ λf(x) + (1−λ)f(y) for λ ∈ [0, 1]. A twice-differentiable f is convex exactly when its Hessian is positive semi-definite. Every local minimum of a convex function is global.
Shape check
The Hessian of f : ℝⁿ → ℝ is n×n and symmetric.
Worked line
f(x) = x²: f″ = 2 > 0, so convex, and x = 0 is the only minimum.
Almost nothing trained in this corpus is convex. The reason the entry is here is that every intuition about optimisation was formed on convex problems, and it is worth knowing which ones stop applying.
Used byI.2 · I.5 · I.7
0.OP.02
Gradient descent
Statement
θ ← θ − η ∇L(θ). The gradient supplies the direction; η supplies the distance, and nothing in the gradient tells you what it should be.
Shape check
∇L has the shape of θ, so the update is elementwise and shape-preserving.
Worked line
L(w) = w², w₀ = 1, η = 0.1: w₁ = 1 − 0.1(2) = 0.8, w₂ = 0.8 − 0.1(1.6) = 0.64. Each step multiplies by 0.8.
For a quadratic, convergence requires η < 2/λ_max. That single condition explains most learning-rate failures, including the ones blamed on the data.
v ← βv + ∇L, θ ← θ − ηv. The velocity accumulates a geometric sum of past gradients with effective horizon 1/(1 − β).
Shape check
v has the shape of θ, and is a second copy of the parameters in memory.
Worked line
β = 0.9 gives a horizon of 10 steps, and a constant gradient g reaches a steady velocity of 10g.
The factor 1/(1 − β) is why raising β also raises the effective step size, and why the two cannot be tuned independently.
Used byI.7
0.OP.04
Lagrange multipliers
Statement
To minimise f subject to g = 0, form ℒ = f − λg and solve ∇f = λ∇g together with g = 0. The multiplier is the rate at which the optimum moves as the constraint is relaxed.
Shape check
One multiplier per equality constraint; ∇f and ∇g share the shape of the variable.
Worked line
Maximise xᵀΣx subject to ‖x‖ = 1: Σx = λx, so the answer is the top eigenvector and λ is its eigenvalue.
That worked line is the whole of principal component analysis. It reappears in the compute-optimal allocation derivation of Book III.
Used byIV.4 · IV.5 · VII.4
0.OP.05
The KKT conditions
Statement
With inequality constraints gᵢ ≤ 0, an optimum satisfies stationarity, primal and dual feasibility, and complementary slackness μᵢgᵢ = 0: a constraint is either tight or its multiplier is zero.
Shape check
One multiplier per constraint, all non-negative.
Worked line
Minimise x² subject to x ≥ 1. The constraint binds, x* = 1, μ = 2.
Complementary slackness is the useful half. It says which constraints are actually doing work, and in practice that is a much shorter list than the one you wrote down.