Optimisation · The Lumenary

MotivationH

The best possible

A furniture workshop in Kumasi makes two products. Each uses time in three workshops, each workshop has only so many hours a week, and each product earns a different profit. How many of each should it make? In 1939 Leonid Kantorovich, asked by a plywood trust in Leningrad how to allocate machines to materials, saw that such problems share one mathematical form, and that every solution comes with a set of hidden prices — what an extra hour of each scarce resource is worth. Today the same mathematics schedules airline crews, routes delivery vans through Jakarta, plans electricity generation and allocates vaccines.

A different kind of optimisation runs on every phone. Training a machine-learning model means choosing millions of numbers to make an error as small as possible. Nobody can search all choices. Instead the computer repeatedly takes a small step downhill — gradient descent, an idea Cauchy published in 1847. Does it reach the bottom? How fast? And how could we ever know that a valley we have found is the lowest one, rather than a hollow halfway up the mountain?

This lesson develops the core of the theory: linear programming and its duality, convexity (the property that makes "local" mean "global"), Lagrange multipliers and the KKT conditions for constraints, and gradient descent with a proof of its convergence rate.

IntuitionH

Landscapes, corners and slopes

Picture the function to be minimised as a landscape. A local minimum is the bottom of some hollow; a global minimum is the lowest point anywhere. In a rugged landscape a hiker who always walks downhill can get stuck in a hollow far above the sea. In a convex landscape — a single bowl, with no ridges or false valleys — that cannot happen: every hollow is the bottom.

A linear program maximises a linear function over a region cut out by linear inequalities, a convex polygon or polyhedron. The level sets of the objective are parallel lines; slide them in the direction of improvement, and the last point of the region they touch is a corner (or, in a tie, an edge). The simplex method walks from corner to corner along edges, always improving.

With constraints, a minimum need not be a point where the slope vanishes. A ball rolling in a bowl that hits a wall comes to rest against the wall: there the downhill force is balanced by the wall pushing back, perpendicular to it. The size of that push is a Lagrange multiplier; it measures how much the optimum would improve if the wall moved. That is exactly Kantorovich's hidden price.

DefinitionsH

Definitions

Definition— optimisation problem, local and global minimum

An optimisation problem asks for $\min_{x \in S} f(x)$ , where $f : \R^n \to \R$ is the objective and $S \subseteq \R^n$ the feasible set (maximising $f$ is minimising $-f$ ). A point $x^* \in S$ is a global minimiser if $f(x^*) \le f(x)$ for all $x \in S$ , and a local minimiser if this holds for all $x \in S$ in some ball around $x^*$ . The problem is infeasible if $S = \varnothing$ and unbounded if $\inf_S f = -\infty$ .

Definition— linear program and its dual

A linear program (LP) optimises a linear function subject to finitely many linear equations and inequalities. In inequality form, the primal problem and its dual are

\text{(P)}\quad \max\; c^{\mathsf T}x \;\text{ s.t. }\; Ax \le b,\; x \ge 0, \qquad\qquad \text{(D)}\quad \min\; b^{\mathsf T}y \;\text{ s.t. }\; A^{\mathsf T}y \ge c,\; y \ge 0,

with $A$ an $m \times n$ matrix and inequalities between vectors meant entry by entry. A vertex of the feasible polyhedron is a feasible point at which $n$ linearly independent constraints are tight.

Definition— convex set, convex function

A set $C \subseteq \R^n$ is convex if $tx + (1 - t)y \in C$ whenever $x, y \in C$ and $0 \le t \le 1$ . A function $f$ on a convex set is convex if

f(tx + (1 - t)y) \le t f(x) + (1 - t) f(y) \qquad \text{for all } x, y \text{ and } 0 \le t \le 1,

strictly convex if the inequality is strict for $x \neq y$ and $0 < t < 1$ , and $\mu$ -strongly convex if $f(x) - \frac\mu2\|x\|^2$ is convex. A differentiable $f$ is $L$ -smooth if its gradient is $L$ -Lipschitz: $\|\nabla f(x) - \nabla f(y)\| \le L\|x - y\|$ .

Definition— Lagrangian and KKT conditions

For the problem $\min f(x)$ subject to $g_i(x) \le 0$ ( $i = 1, \dots, m$ ) and $h_j(x) = 0$ ( $j = 1, \dots, p$ ), with differentiable functions, the Lagrangian is $\mathcal L(x, \mu, \lambda) = f(x) + \sum_i \mu_i g_i(x) + \sum_j \lambda_j h_j(x)$ . A point $x^*$ with multipliers $\mu, \lambda$ satisfies the Karush–Kuhn–Tucker (KKT) conditions if

\nabla f(x^*) + \sum_i \mu_i \nabla g_i(x^*) + \sum_j \lambda_j \nabla h_j(x^*) = 0, \quad g_i(x^*) \le 0, \quad h_j(x^*) = 0, \quad \mu_i \ge 0, \quad \mu_i\, g_i(x^*) = 0.

The last condition is complementary slackness: a multiplier can be non-zero only for a constraint that is tight.

Definition— gradient descent and Newton's method

Gradient descent with step size $\eta > 0$ iterates $x_{k+1} = x_k - \eta\nabla f(x_k)$ . Newton's method iterates $x_{k+1} = x_k - \big(\nabla^2 f(x_k)\big)^{-1}\nabla f(x_k)$ , using the Hessian matrix $\nabla^2 f$ .

Worked examplesH

Examples and non-examples

Example— A production problem, solved by looking

The Kumasi workshop makes $x$ units of product 1 and $y$ of product 2, using $1$ hour of workshop A and $3$ of workshop C per unit of product 1, and $2$ hours of B and $2$ of C per unit of product 2. A, B and C have $4$ , $12$ and $18$ hours a week, and the profits are $3$ and $5$ per unit:

\max\; 3x + 5y \quad \text{s.t.}\quad x \le 4,\quad 2y \le 12,\quad 3x + 2y \le 18,\quad x, y \ge 0.

The feasible region is a pentagon with vertices $(0, 0)$ , $(4, 0)$ , $(4, 3)$ , $(2, 6)$ , $(0, 6)$ , where the objective takes the values $0, 12, 27, 36, 30$ . The optimum is $(2, 6)$ , with profit $36$ : workshops B and C are fully used, while A has $2$ hours to spare. (The visualisation lets you slide the profit line.)

Example— LPs without optimal solutions

$\max\; x$ subject to $x \le 0$ and $x \ge 1$ is infeasible. $\max\; x + y$ subject to $x - y \le 1$ , $x, y \ge 0$ is unbounded: $(t + 1, t)$ is feasible for every $t \ge 0$ , with objective $2t + 1$ . A feasible LP whose objective is bounded always has an optimal solution, and if its feasible region has a vertex, one optimal solution is a vertex.

Example— Convex and not convex

Convex functions: affine functions, $x^2$ , $e^x$ , $|x|$ and every norm, $-\log x$ on $(0, \infty)$ , the maximum of finitely many convex functions, and $\|Aw - y\|^2$ . Convex sets: half-spaces $\{a \cdot x \le b\}$ , balls, polyhedra (intersections of finitely many half-spaces), and sublevel sets $\{f \le r\}$ of convex functions. Not convex: $x^3$ , $\sin x$ , the double well $x^4 - x^2$ (with two global minima $\pm 1/\sqrt2$ and a local maximum at $0$ ), and the annulus $1 \le \|x\| \le 2$ . Note that $|x|$ is convex but not differentiable at its minimum.

Example— A constrained minimum, by KKT

Minimise $(x - 2)^2 + (y - 2)^2$ — the squared distance to $(2, 2)$ — subject to $x + y \le 2$ . The unconstrained minimiser $(2, 2)$ is infeasible, so the constraint will be tight. KKT: $(2(x - 2), 2(y - 2)) + \mu(1, 1) = 0$ gives $x = y = 2 - \mu/2$ , and $x + y = 2$ gives $\mu = 2 \ge 0$ , so $x^* = (1, 1)$ with minimum value $2$ . The multiplier $\mu = 2$ is the rate at which the optimal value would fall if the constraint were relaxed to $x + y \le 2 + \varepsilon$ (it becomes $2 - 2\varepsilon + O(\varepsilon^2)$ ).

ProofH

Linear programming and duality

Theorem— Theorem 1 (weak duality)

If $x$ is feasible for (P) and $y$ is feasible for (D), then $c^{\mathsf T}x \le b^{\mathsf T}y$ .

Proof

Using $x \ge 0$ with $c \le A^{\mathsf T}y$ , and then $y \ge 0$ with $Ax \le b$ :

c^{\mathsf T}x \;\le\; (A^{\mathsf T}y)^{\mathsf T}x \;=\; y^{\mathsf T}(Ax) \;\le\; y^{\mathsf T}b.

∎

Theorem— Corollary 2 (certificates and complementary slackness)

(a) If feasible $x$ and $y$ have $c^{\mathsf T}x = b^{\mathsf T}y$ , both are optimal. (b) In that case $y_i\,(b - Ax)_i = 0$ for every $i$ and $x_j\,(A^{\mathsf T}y - c)_j = 0$ for every $j$ . (c) If (P) is unbounded, (D) is infeasible, and vice versa.

Proof

(a) Every feasible $x'$ has $c^{\mathsf T}x' \le b^{\mathsf T}y = c^{\mathsf T}x$ , and symmetrically for $y$ . (b) Equality of the ends of the chain in Theorem 1 forces both inequalities to be equalities: $y^{\mathsf T}(b - Ax) = 0$ and $(A^{\mathsf T}y - c)^{\mathsf T}x = 0$ . These are sums of non-negative products, so every product vanishes. (c) A dual-feasible $y$ would bound every primal value by $b^{\mathsf T}y$ .

∎

Theorem— Theorem 3 (Farkas' lemma)

For a matrix $A$ and vector $b$ , exactly one of the following holds: (i) $Ax = b$ for some $x \ge 0$ ; (ii) there is $y$ with $A^{\mathsf T}y \ge 0$ and $b^{\mathsf T}y < 0$ .

Proof

Not both: otherwise $0 \le (A^{\mathsf T}y)^{\mathsf T}x = y^{\mathsf T}b < 0$ . Suppose (i) fails, so $b \notin K = \{Ax : x \ge 0\}$ . The cone $K$ is convex, and it is closed (a finitely generated cone is closed; this follows from Carathéodory's theorem, which writes each point of $K$ using linearly independent columns of $A$ ). Let $z_0$ be the point of $K$ nearest to $b$ (it exists since $K$ is closed), and put $y = z_0 - b \ne 0$ . For $z \in K$ and $0 < t \le 1$ , the point $z_0 + t(z - z_0)$ is in $K$ and is no closer to $b$ ; expanding $\|z_0 + t(z - z_0) - b\|^2 \ge \|y\|^2$ and letting $t \to 0$ gives $y^{\mathsf T}(z - z_0) \ge 0$ . Taking $z = 0$ and $z = 2z_0$ gives $y^{\mathsf T}z_0 = 0$ , so $y^{\mathsf T}z \ge 0$ for all $z \in K$ — in particular $A^{\mathsf T}y \ge 0$ — and $y^{\mathsf T}b = y^{\mathsf T}z_0 - \|y\|^2 < 0$ .

∎

Theorem— Theorem 4 (strong duality)

If (P) has an optimal solution, then so does (D), and the optimal values are equal. The same holds with the roles of (P) and (D) exchanged.

Proof

Sketch. Let $p^*$ be the optimal value of (P) and $\varepsilon > 0$ . The system $Ax \le b$ , $x \ge 0$ , $c^{\mathsf T}x \ge p^* + \varepsilon$ has no solution. Adding slack variables and applying Farkas' lemma gives $y \ge 0$ and $\tau \ge 0$ with $A^{\mathsf T}y \ge \tau c$ and $b^{\mathsf T}y < \tau(p^* + \varepsilon)$ . Here $\tau > 0$ , since $\tau = 0$ would contradict the feasibility of (P) by Theorem 1. Then $y/\tau$ is dual feasible with value below $p^* + \varepsilon$ . Since $\varepsilon$ was arbitrary and Theorem 1 gives the reverse inequality, $\inf(D) = p^*$ ; a feasible LP whose objective is bounded attains its optimum. Full details are in Matoušek and Gärtner, chapter 6.

∎

The dual as prices. In the workshop problem the dual solution is $y = (0, \tfrac32, 1)$ : one more hour in workshop B would raise the maximum profit by $\tfrac32$ , one more in C by $1$ , and one more in A by nothing, since A already has slack (complementary slackness). Check: $b^{\mathsf T}y = 4 \cdot 0 + 12 \cdot \tfrac32 + 18 \cdot 1 = 36 = c^{\mathsf T}x^*$ . These shadow prices are Kantorovich's "objectively determined valuations".

The simplex method. An LP in inequality form with $b \ge 0$ starts at the vertex $x = 0$ . At each step the method looks for a non-basic variable whose increase improves the objective (a positive reduced cost), increases it until the first constraint becomes tight (the ratio test), and pivots to that adjacent vertex. If no variable can improve the objective, the vertex is optimal, and the final tableau displays a dual solution satisfying Corollary 2(a). If an improving variable can be increased forever, the LP is unbounded. With Bland's smallest-index rule (1977) the method never cycles, so it terminates. Klee and Minty (1972) built LPs on which the classical rule visits exponentially many vertices, yet in practice the method is very fast, a phenomenon explained by Spielman and Teng's smoothed analysis (2004). Provably polynomial-time algorithms exist: Khachiyan's ellipsoid method (1979) and Karmarkar's interior-point method (1984). The first experiment runs the simplex method in exact arithmetic.

ProofH

Convexity: local is global

Theorem— Theorem 5 (local minima of convex functions are global)

Let $f$ be convex on a convex set $C$ . Every local minimiser of $f$ on $C$ is a global minimiser. The set of minimisers is convex, and if $f$ is strictly convex there is at most one.

Proof

Let $x$ be a local minimiser and $y \in C$ . For $t \in (0, 1]$ the point $x + t(y - x) = (1 - t)x + ty$ lies in $C$ , and for $t$ small enough it lies in the ball where $x$ is minimal. Then

f(x) \le f\big((1 - t)x + ty\big) \le (1 - t)f(x) + t f(y),

so $t f(x) \le t f(y)$ , and dividing by $t > 0$ gives $f(x) \le f(y)$ . The minimisers form the sublevel set $\{f \le \min f\}$ , which is convex. If $x \ne y$ were both minimisers of a strictly convex $f$ , their midpoint would have $f < \min f$ .

∎

Theorem— Theorem 6 (first-order characterisation)

A differentiable $f$ on a convex open set is convex if and only if $f(y) \ge f(x) + \nabla f(x) \cdot (y - x)$ for all $x, y$ . Consequently, for convex differentiable $f$ on $\R^n$ , $\nabla f(x^*) = 0$ if and only if $x^*$ is a global minimiser.

Proof

If $f$ is convex, $\frac{f(x + t(y - x)) - f(x)}{t} \le f(y) - f(x)$ for $t \in (0, 1]$ , by the definition with weights $1 - t$ and $t$ ; letting $t \to 0$ the left side tends to $\nabla f(x) \cdot (y - x)$ . Conversely, given the inequality, put $z = tx + (1 - t)y$ and add $t$ times the inequality at $(z, x)$ to $1 - t$ times the inequality at $(z, y)$ : the gradient terms cancel and leave $tf(x) + (1 - t)f(y) \ge f(z)$ . The consequence: if $\nabla f(x^*) = 0$ the inequality gives $f(y) \ge f(x^*)$ for all $y$ .

∎

A twice-differentiable $f$ is convex exactly when its Hessian is positive semidefinite everywhere (by Theorem 6 applied along lines). Without convexity none of this holds: $x^3$ has $f'(0) = 0$ but no minimum, and $x^2 - y^2$ has a saddle at the origin.

ProofH

Lagrange multipliers and the KKT conditions

From multivariable calculus: if $x^*$ is a local minimiser of $f$ subject to $h(x) = 0$ and $\nabla h(x^*) \ne 0$ , then $\nabla f(x^*) = \lambda\nabla h(x^*)$ for some $\lambda$ , because the gradient of $f$ must be perpendicular to the constraint surface. For example, the point of the plane $\langle a, x \rangle = b$ closest to the origin satisfies $2x = \lambda a$ , so $x^* = \frac{b}{\|a\|^2}a$ . Convexity turns this necessary condition into a proof of optimality: $x - x^*$ is orthogonal to $x^*$ for every feasible $x$ , so $\|x\|^2 = \|x - x^*\|^2 + \|x^*\|^2 \ge \|x^*\|^2$ . (This is the Lean theorem least_norm.)

Theorem— Theorem 7 (KKT conditions)

Consider $\min f(x)$ subject to $g_i(x) \le 0$ and $h_j(x) = 0$ , with continuously differentiable functions.

(a) Sufficiency. If $f$ and every $g_i$ are convex, every $h_j$ is affine, and $(x^*, \mu, \lambda)$ satisfies the KKT conditions, then $x^*$ is a global minimiser.

(b) Necessity. If $x^*$ is a local minimiser and a constraint qualification holds at $x^*$ — for example, the gradients of the tight constraints are linearly independent, or (for convex problems) some point satisfies all $g_i < 0$ strictly (Slater's condition) — then there are multipliers making the KKT conditions hold.

Proof

(a) Let $x$ be feasible. By Theorem 6 for $f$ and the KKT equation,

f(x) \ge f(x^*) + \nabla f(x^*) \cdot (x - x^*) = f(x^*) - \sum_i \mu_i \nabla g_i(x^*) \cdot (x - x^*) - \sum_j \lambda_j \nabla h_j(x^*) \cdot (x - x^*).

Since $h_j$ is affine, $\nabla h_j(x^*) \cdot (x - x^*) = h_j(x) - h_j(x^*) = 0$ . By Theorem 6 for $g_i$ , $\nabla g_i(x^*) \cdot (x - x^*) \le g_i(x) - g_i(x^*)$ , and with $\mu_i \ge 0$ and $\mu_i g_i(x^*) = 0$ we get $-\mu_i \nabla g_i(x^*) \cdot (x - x^*) \ge -\mu_i g_i(x) \ge 0$ . So $f(x) \ge f(x^*)$ .

(b) Sketch. Under linear independence of the active gradients, a first-order feasible direction $d$ that decreased $f$ could be followed along a curve of feasible points (implicit function theorem). So no such $d$ exists, and Farkas' lemma converts "no improving feasible direction" into the existence of $\mu \ge 0$ and $\lambda$ . See Nocedal and Wright, chapter 12, or Boyd and Vandenberghe, chapter 5.

∎

For a linear program, the KKT conditions are exactly primal feasibility, dual feasibility and complementary slackness (Corollary 2): the multipliers are the dual variables. Without a constraint qualification, necessity can fail: minimise $x$ subject to $x^2 \le 0$ . The only feasible point is $0$ , but $\nabla x = 1 \neq -\mu \cdot 0$ for every $\mu$ .

ProofH

Gradient descent: a convergence proof

Theorem— Lemma 8 (descent lemma)

If $\nabla f$ is $L$ -Lipschitz, then $f(y) \le f(x) + \nabla f(x) \cdot (y - x) + \frac L2\|y - x\|^2$ . In particular, the step $x^+ = x - \frac1L\nabla f(x)$ gives $f(x^+) \le f(x) - \frac{1}{2L}\|\nabla f(x)\|^2$ .

Proof

By the fundamental theorem of calculus along the segment and Cauchy–Schwarz,

f(y) - f(x) - \nabla f(x) \cdot (y - x) = \int_0^1 \big(\nabla f(x + t(y - x)) - \nabla f(x)\big) \cdot (y - x)\,dt \le \int_0^1 Lt\|y - x\|^2\,dt = \frac L2 \|y - x\|^2.

For $y = x^+$ , the right-hand side becomes $f(x) - \frac1L\|\nabla f(x)\|^2 + \frac1{2L}\|\nabla f(x)\|^2$ .

∎

Theorem— Theorem 9 (rate of gradient descent)

Let $f$ be convex and $L$ -smooth with a minimiser $x^*$ , and let $x_{k+1} = x_k - \frac1L\nabla f(x_k)$ . Then for every $k \ge 1$ ,

f(x_k) - f(x^*) \le \frac{L\,\|x_0 - x^*\|^2}{2k}.

Proof

Write $g_k = \nabla f(x_k)$ . By Lemma 8, $f(x_{k+1}) \le f(x_k) - \frac{1}{2L}\|g_k\|^2$ ; in particular the values decrease. By Theorem 6, $f(x_k) - f(x^*) \le g_k \cdot (x_k - x^*)$ . Combining,

f(x_{k+1}) - f(x^*) \le g_k \cdot (x_k - x^*) - \frac{1}{2L}\|g_k\|^2 = \frac L2\Big(\|x_k - x^*\|^2 - \|x_{k+1} - x^*\|^2\Big),

where the equality is the expansion of $\|x_{k+1} - x^*\|^2 = \|(x_k - x^*) - \frac1L g_k\|^2$ . Summing over $k = 0, \dots, n - 1$ , the right-hand side telescopes to at most $\frac L2\|x_0 - x^*\|^2$ . Since the values decrease, the left-hand sum is at least $n\,(f(x_n) - f(x^*))$ .

∎

Three remarks. Step size. For $f(x) = \frac L2 x^2$ the iteration is $x_{k+1} = (1 - \eta L)x_k$ , which converges exactly when $0 < \eta < 2/L$ . Larger steps overshoot and diverge, as the experiment and the cobweb diagram show. Strong convexity. If $f$ is also $\mu$ -strongly convex, the gap shrinks geometrically, like $(1 - \mu/L)^k$ . The ratio $L/\mu$ , the condition number, governs the speed. Faster methods. Nesterov's accelerated gradient method (1983) achieves $O(1/k^2)$ , which is optimal for first-order methods on this class. Newton's method minimises a quadratic in one step, since it jumps straight to the minimum of the local quadratic model, and converges quadratically near a minimiser with positive definite Hessian; but each step solves a linear system with the Hessian.

Data fitting. Fitting a model $Aw \approx y$ to data by least squares means minimising $F(w) = \|Aw - y\|^2$ , which is convex with gradient $2A^{\mathsf T}(Aw - y)$ . By Theorem 6 its minimisers are exactly the solutions of the normal equations $A^{\mathsf T}Aw = A^{\mathsf T}y$ , unique when $A$ has independent columns. Geometrically $Aw^*$ is the orthogonal projection of $y$ onto the column space of $A$ . For huge data sets one runs (stochastic) gradient descent on $F$ instead of solving the normal equations, and the second experiment checks that both give the same line.

Formal mathematicsF

Optimisation in Lean and Mathlib

Mathlib has convex sets and functions (Convex, ConvexOn), local and global minima (IsLocalMin, IsMinOn), the dot product ⬝ᵥ with the order lemmas needed for linear programming, and real inner product spaces. Weak duality and its corollaries, as in Theorem 1 and Corollary 2:

weak_dualityLean 4Proved here from basic factsFormally verified

/-- **Weak duality.** For the primal problem *maximise `c · x` subject to `A x ≤ b`, `x ≥ 0`*
and its dual *minimise `b · y` subject to `Aᵀ y ≥ c`, `y ≥ 0`*, every feasible `x` and `y` satisfy
`c · x ≤ b · y`. The proof is one line of inequalities:
`c · x ≤ (Aᵀ y) · x = y · (A x) ≤ y · b`, using `x ≥ 0` and then `y ≥ 0`. -/
theorem weak_duality {m n : Type*} [Fintype m] [Fintype n] (A : Matrix m n ℝ) (b : m → ℝ)
    (c : n → ℝ) (x : n → ℝ) (y : m → ℝ) (hx : 0 ≤ x) (hAx : A *ᵥ x ≤ b) (hy : 0 ≤ y)
    (hAy : c ≤ y ᵥ* A) : c ⬝ᵥ x ≤ b ⬝ᵥ y :=
  calc c ⬝ᵥ x ≤ (y ᵥ* A) ⬝ᵥ x := dotProduct_le_dotProduct_of_nonneg_right hAy hx
    _ = y ⬝ᵥ (A *ᵥ x) := (dotProduct_mulVec y A x).symm
    _ ≤ y ⬝ᵥ b := dotProduct_le_dotProduct_of_nonneg_left hAx hy
    _ = b ⬝ᵥ y := dotProduct_comm _ _