Prev
Unit 11 · Numerical Optimisation
Line Search and Gradient Methods
55m100 XP
Next
⛰️Numerical Optimisation

Line Search and Gradient Methods

Optimality conditions, golden-section and Brent in one dimension, steepest descent, Armijo backtracking

Paris, 1847
Augustin-Louis Cauchy, the most prolific mathematician of his century, is thinking about astronomy. Determining the orbit of a body from observations means solving a system of nonlinear equations in several unknowns, and the methods of the day are laborious. In a three-page note to the Académie des Sciences — Méthode générale pour la résolution des systèmes d'équations simultanées — he proposes something new. Combine the equations into a single function that is zero exactly at the solution and positive elsewhere: the sum of their squares. Then repeatedly move the unknowns in the direction in which that function decreases fastest — against its gradient — by an amount chosen to make it as small as possible along that line. It is the first gradient method, and the ancestor of every optimisation algorithm in this unit. The same idea, with millions of unknowns and some refinements, trains today's neural networks.
An optimisation problem asks for the x\mathbf x that minimises an objective f(x)f(\mathbf x): mass, cost, fuel, error, energy. (Maximising ff is minimising −f-f.) For a smooth ff, a local minimum satisfies the first-order condition ∇f(x∗)=0\nabla f(\mathbf x^*) = \mathbf 0 — a nonlinear system (Unit 2) — and the second-order condition that the Hessian ∇2f(x∗)\nabla^2f(\mathbf x^*) is positive semi-definite (positive definite guarantees a strict local minimum). A local minimum need not be global; for convex ff every local minimum is global.
Derivation
Where the optimality conditions come from, and why −∇f-\nabla f is steepest
Expand ff about a candidate point x∗\mathbf x^* in a direction d\mathbf d (multivariable Taylor, lesson 2-4):
f(x∗+d)=f(x∗)+∇fTd+12dT∇2f d+…f(\mathbf x^* + \mathbf d) = f(\mathbf x^*) + \nabla f^{\mathsf T}\mathbf d + \tfrac12\mathbf d^{\mathsf T}\nabla^2f\,\mathbf d + \dots
First order. If ∇f≠0\nabla f \ne \mathbf 0, take d=−t∇f\mathbf d = -t\nabla f with a small t>0t > 0: the change is −t∥∇f∥2+O(t2)-t\|\nabla f\|^2 + O(t^2), negative for small enough tt. So x∗\mathbf x^* was not a minimum. At a minimum the gradient must vanish.
Second order. With ∇f=0\nabla f = \mathbf 0, the change is 12dT∇2f d\tfrac12\mathbf d^{\mathsf T}\nabla^2f\,\mathbf d to leading order. A minimum needs it to be ≥0\ge 0 for every direction: the Hessian is positive semi-definite. If it is positive definite every direction goes strictly uphill — a strict local minimum.
The steepest direction. For a unit direction d\mathbf d the rate of change of ff is ∇fTd\nabla f^{\mathsf T}\mathbf d. By the Cauchy–Schwarz inequality ∇fTd≥−∥∇f∥ ∥d∥=−∥∇f∥\nabla f^{\mathsf T}\mathbf d \ge -\|\nabla f\|\,\|\mathbf d\| = -\|\nabla f\|, with equality only for d=−∇f/∥∇f∥\mathbf d = -\nabla f/\|\nabla f\|. Cauchy's direction is the one that decreases ff fastest — locally.
💡One dimension: golden-section search and Brent
A function that decreases then increases on [a,b][a, b] (unimodal) can be minimised without derivatives by shrinking a bracket — like bisection (lesson 2-1) but with two interior points: compare f(x1)f(x_1) and f(x2)f(x_2) and discard the part of the interval beyond the larger one. Placing the points at the golden-ratio positions lets one of them be reused each step, so every step costs one evaluation and shrinks the bracket by 0.6180.618. For an aircraft's drag D(V)=aV2+b/V2D(V) = aV^2 + b/V^2, golden-section search finds the minimum-drag speed 230.0327 m/s to 10−610^{-6} in 43 evaluations. Brent's method (1973) — scipy.optimize.minimize_scalar — adds parabolic interpolation through three points and needs only 16. One-dimensional minimisation is also the inner loop of most multi-dimensional methods: the line search.
Derivation
The golden ratio, and the minimum-drag speed
Why 0.618. Scale the bracket to [0,1][0, 1] and place the two interior points symmetrically at 1−φ1 - \varphi and φ\varphi. Suppose f(1−φ)<f(φ)f(1 - \varphi) < f(\varphi), so we keep [0,φ][0, \varphi]. To reuse the surviving point, 1−φ1 - \varphi must sit in the new bracket where φ\varphi sat in the old one — at the fraction φ\varphi of its length:
1−φ=φ⋅φ⟹φ2+φ−1=0⟹φ=5−12=0.618034.1 - \varphi = \varphi \cdot \varphi \qquad\Longrightarrow\qquad \varphi^2 + \varphi - 1 = 0 \qquad\Longrightarrow\qquad \varphi = \frac{\sqrt5 - 1}{2} = 0.618034.
Every step then costs one new evaluation and keeps 0.618 of the bracket — slower per step than bisection's 0.5, but bisection needs a sign, which a minimum does not provide.
The exact answer the lab checks against. For D(V)=aV2+b/V2D(V) = aV^2 + b/V^2:
D′(V)=2aV−2bV3=0⟹V4=ba,V∗=(ba)1/4.D'(V) = 2aV - \frac{2b}{V^3} = 0 \qquad\Longrightarrow\qquad V^4 = \frac ba, \qquad V^* = \Big(\frac ba\Big)^{1/4}.
At V∗V^*, aV∗2=b/V∗2aV^{*2} = b/V^{*2}: the parasite drag (growing with speed) equals the induced drag (falling with speed) — the classical condition for minimum drag.
💡Steepest descent
At xk\mathbf x_k, −∇f-\nabla f is the direction of fastest local decrease. Step xk+1=xk−tk∇f(xk)\mathbf x_{k+1} = \mathbf x_k - t_k\nabla f(\mathbf x_k) with a step length tk>0t_k > 0 from a line search. For a quadratic with exact line searches the error shrinks per step by at most (κ−1)/(κ+1)(\kappa - 1)/(\kappa + 1) — the condition number of the Hessian again (lesson 4-3). With κ=10,100,1000\kappa = 10, 100, 1000, steepest descent needs 105, 1,169 and 12,838 iterations: the zig-zag across a narrow valley that you met in the CG interactive.
Inexact line searches. Minimising exactly along each line wastes evaluations. The Armijo condition (1966) asks only for sufficient decrease: accept tt if f(xk+td)≤f(xk)+c t ∇fTdf(\mathbf x_k + t\mathbf d) \le f(\mathbf x_k) + c\,t\,\nabla f^{\mathsf T}\mathbf d with a small cc such as 10−410^{-4}, halving tt from 1 until it holds (backtracking). Together with a curvature condition (Wolfe) this guarantees convergence of descent methods without ever solving the 1-D problem exactly.
📐Rosenbrock's valley
Howard Rosenbrock's 1960 test function f=(1−x)2+100(y−x2)2f = (1 - x)^2 + 100(y - x^2)^2 has its minimum at (1,1)(1, 1) at the bottom of a long, narrow, curved valley. Steepest descent with Armijo backtracking from the standard start (−1.2,1)(-1.2, 1) reaches the minimum to 10−510^{-5} in the gradient after 10,916 iterations. Every step goes almost straight across the valley floor. The landscape is not hard to understand; the method is simply blind to curvature.
It seems that perfection is attained not when there is nothing more to add, but when there is nothing more to remove.
– Antoine de Saint-Exupéry, Terre des hommes (1939)
💡Where you will use this
Optimal Guidance: gradient-based trajectory optimisation, and the inner loops of sequential convex programming. Structures: sizing and topology optimisation use gradients computed by adjoint methods. Control: tuning gains to minimise a cost. Machine learning: stochastic gradient descent — Cauchy's method with noisy gradients — is how every neural network is trained.
📚Further reading
  • Jorge Nocedal and Stephen Wright, Numerical Optimization (2nd ed., Springer, 2006), chapters 2–3, 'Fundamentals of Unconstrained Optimization' and 'Line Search Methods' — optimality conditions, Armijo and Wolfe conditions, steepest descent.
  • Stephen Boyd and Lieven Vandenberghe, Convex Optimization (Cambridge University Press, 2004), chapter 9, 'Unconstrained minimization' — free online from the authors; why convexity makes local minima global.
  • Augustin-Louis Cauchy, 'Méthode générale pour la résolution des systèmes d'équations simultanées', Comptes Rendus de l'Académie des Sciences 25, 536–538 (1847) — three pages.
↓But there is a problem
Steepest descent uses only the slope. Ten thousand iterations for a two-variable function is the price of ignoring curvature — the very information Newton's method used in Unit 2 to double its digits every step. In 1959 William Davidon, a physicist at the Argonne National Laboratory, was tired of waiting for his slow minimisation runs to finish on the laboratory's computer. He invented a method that learns the curvature as it goes, from nothing but gradients. His report was rejected by the journal he sent it to. It circulated for thirty years as a technical report, and was finally published — as the lead article of the first issue of a new journal — in 1991.