Continuous Optimisation

Real problems have limits: a budget that cannot be exceeded, a beam that cannot be thinner than a millimetre. In 1939 William Karush, a master's student at Chicago, worked out the conditions for a minimum with inequality constraints. His thesis was never published. The same conditions appeared in 1951 in a paper by Harold Kuhn and Albert Tucker, which launched nonlinear programming as a field, alongside the linear programming of combinatorial optimisation. Karush's work was rediscovered in the 1970s, and the conditions now carry all three names.

In 1959 William Davidon, a physicist at Argonne National Laboratory whose computer kept crashing before his long optimisations finished, found a way to learn the second-derivative matrix gradually from the gradients themselves. His report was rejected for publication. It was printed, as a historical document, only in 1991. Roger Fletcher and Michael Powell refined the method in 1963, and in 1970 four people independently found the BFGS formula. Quasi-Newton methods became the standard for smooth problems of moderate size.

Take the function

$$f(x, y) = \tfrac12\left(x^2 + 10y^2\right),$$

a bowl ten times steeper in one direction than the other. Its minimum is at $(0, 0)$ and its gradient is $(x, 10y)$. Gradient descent with step size $h$ updates

$$x \leftarrow (1 - h)\,x, \qquad y \leftarrow (1 - 10h)\,y.$$

The two directions shrink at different rates. The best fixed step balances them, $h = 2/11$, and then both shrink by a factor of $9/11 \approx 0.818$ at every step. Start at $(10, 1)$, where $f = 55$:

Step	$x$	$y$	$f(x, y)$
0	10	1	55
1	8.18	−0.818	36.8
2	6.69	0.669	24.7
5	3.67	−0.367	7.39
10	1.34	0.134	0.994
20	0.181	0.0181	0.0180

The steps zigzag across the valley, the sign of $y$ flipping each time, while creeping along it. A slightly larger step, $h = 0.21$, makes $1 - 10h = -1.1$, and the $y$ coordinate grows by 10% per step: after 20 steps $f$ has risen from 55 to 226. Any step above $2/10 = 0.2$ diverges.

The ratio of the steepest to the shallowest curvature, here 10, is the condition number $\kappa$. With the best step, the error shrinks by $(\kappa - 1)/(\kappa + 1)$ per step. To cut it by a factor of a million:

Condition number $\kappa$	Gradient descent steps	Best momentum method
10	69	22
100	691	69
1,000	6,908	219

The cost grows in proportion to $\kappa$. Methods with momentum, which let each step carry on partly in the direction of the last, such as conjugate gradients and Nesterov's accelerated method, need a number of steps proportional to about $\sqrt{\kappa}$ instead. For badly conditioned problems, that difference decides whether an optimisation finishes at all.

For a convex function, one whose graph curves upwards everywhere, every local minimum is the global minimum, and there is hope of guarantees. In 1984 Narendra Karmarkar gave a fast method for linear programming that moves through the interior of the feasible region. Yurii Nesterov and Arkadi Nemirovski showed in 1994 that interior-point methods solve a very wide class of convex problems in polynomial time. Convex optimisation became a reliable technology, used in engineering design, signal processing, finance and control.

The largest problems went the other way. Herbert Robbins and Sutton Monro had shown in 1951 that steps based on noisy estimates still converge if the step sizes shrink correctly. Estimating a gradient from a small random batch of data, rather than all of it, is exactly such a step, and stochastic gradient descent, often with momentum, now trains neural networks with billions of parameters. Their training functions are not convex, and theory gives little reason to expect success. Yet training usually works, and explaining why is one of the central open questions where Monte Carlo methods, linear algebra and optimisation meet.