Optimization · Module 3 of 10
Line Search and Steepest Descent
To find a minimum you walk downhill. A line search picks a descent direction and a step length that guarantees progress, and the negative gradient is the steepest way down, if not always the fastest overall.
Readiness check
This module walks downhill to a minimum. Tick only what you can do closed-notes.
- Compute the gradient of a function.
- Recall that the negative gradient points downhill.
- Minimise a one-variable function by setting its derivative to zero.
- Evaluate a dot product of two vectors.
- Recall an iterative update xk+1 = xk + step.
The core idea
A line-search method repeats two choices: a descent direction and a step length along it. The steepest-descent direction is the negative gradient; the step is chosen to guarantee a sufficient decrease in the objective.
xk+1 = xk + αk pksteepest descent: pk = −∇f(xk)descent if ∇fTp < 0Most optimization methods are iterative: from the current point xk they move to xk+1 = xk + αk pk, choosing a search direction pk and a step length αk. A direction is a descent direction if it makes an obtuse angle with the gradient, ∇fTp < 0, so that moving along it lowers the objective. The steepest-descent method takes the most obvious choice, pk = −∇f(xk), the direction of fastest local decrease. The step length is then set by a line search along that direction: an exact line search minimises f exactly along the line, while a cheaper backtracking search accepts the first step that meets a sufficient-decrease (Armijo) condition, f(xk + α p) ≤ f(xk) + c1 α ∇fTp. Steepest descent always makes progress and is simple, but on stretched, elliptical contours it zig-zags and converges slowly, which motivates the smarter directions of the next module.
The skills, taught in order
Five skills build the descent direction, the step length, and the guarantee of progress.
3.1 Descent directions
A direction p is a descent direction at xk if the directional derivative is negative, ∇fTp < 0, meaning f decreases at least initially along it. Any such direction can be used; the method's quality depends on which one and how long a step.
3.2 The steepest-descent method
Steepest descent chooses pk = −∇f(xk), the direction of fastest local decrease. It is intuitive and always a descent direction, but each step is perpendicular to the contour, so on elongated valleys it crosses back and forth, converging linearly and often slowly.
3.3 Exact line search
Given a direction, an exact line search finds the step α that minimises f along the line, by solving d/dα f(xk + α p) = 0. For a quadratic this α has a closed form. It gives the best step on that line but costs a sub-problem each iteration.
| Line search | Chooses α by | Cost |
|---|---|---|
| Exact | minimising f along the line | a sub-problem each step |
| Backtracking | first α meeting sufficient decrease | a few function evaluations |
Exact line search is optimal on the line but expensive; backtracking is cheap and good enough, which is why it is the practical default.
3.4 The sufficient-decrease condition
A backtracking search accepts a step when it meets the Armijo sufficient-decrease condition f(xk + α p) ≤ f(xk) + c1 α ∇fTp, with a small c1. It starts from a full step and halves it until the condition holds, guaranteeing real progress without an exact minimisation.
3.5 Convergence and scaling
Steepest descent converges for any starting point but only linearly, and its rate worsens as the contours become more elongated (ill-conditioned). Scaling the variables, or using curvature information as in the next module, cures the zig-zag and speeds convergence.
Engineering connection: gradient descent, with modern step rules, is the workhorse behind training the models in data-driven engineering, the same idea at scale.
Worked example 1: one steepest-descent step with exact line search
For f(x, y) = x2 + 4y2, take one steepest-descent step from the point (4, 1) using an exact line search. Report the new point and the drop in the objective.
- ProblemTake one exact-line-search steepest-descent step for the point in Figure 1.
- Given / findf(x, y) = x2 + 4y2, start (4, 1). Find the direction, α, the new point, and the objective drop.
- AssumptionsSteepest-descent direction; exact line search along it.
- Modelp = −∇f; minimise φ(α) = f((4, 1) + αp) over α by φ′(α) = 0.
- Equations∇f = (2x, 8y) = (8, 8) at (4, 1)φ′(α) = 0 ⇒ α = 0.2
- SolveDirection p = −(8, 8). Along it, φ(α) = (4 − 8α)2 + 4(1 − 8α)2; setting φ′ = 0 gives α = 0.2. New point (4 − 1.6, 1 − 1.6) = (2.4, −0.6). Objective: f(4, 1) = 20 → f(2.4, −0.6) = 5.76 + 1.44 = 7.2.
- CheckAt the new point the gradient (4.8, −4.8) is perpendicular to the step direction (8, 8), the defining property of an exact line search: the search stops where the direction is tangent to a contour.
- ConclusionOne step drops the objective from 20 to 7.2. Because the contours are stretched (x versus 4y2), the next step will turn sharply, the zig-zag that slows steepest descent.
Worked example 2: a backtracking line search
Minimise f(x) = x2 from x = 2 along the steepest-descent direction p = −∇f = −4, using backtracking with the Armijo condition (c1 = 0.1). Start from a full step α = 1 and halve until it is accepted.
- ProblemBacktrack to an accepted step for the search in Figure 2.
- Given / findf(x) = x2, x = 2, p = −4, c1 = 0.1. Find the accepted α and the new point.
- AssumptionsSteepest-descent direction p = −∇f; halve α on each rejection.
- ModelAccept α when f(x + αp) ≤ f(x) + c1 α ∇fTp, with ∇f = 4 so ∇fTp = 4(−4) = −16.
- Equationsbound(α) = f(x) + c1 α ∇fTp = 4 − 1.6α
- Solveα = 1: x + αp = 2 − 4 = −2, f = 4; bound = 4 − 1.6 = 2.4; 4 > 2.4, reject. α = 0.5: x + αp = 2 − 2 = 0, f = 0; bound = 4 − 0.8 = 3.2; 0 ≤ 3.2, accept. New point x = 0.
- CheckThe full step overshot the minimum to x = −2 (no better than the start), while the halved step landed exactly at the minimum x = 0. Backtracking found a productive step in one halving.
- ConclusionBacktracking accepts α = 0.5, reaching the minimum. The sufficient-decrease test rejects the overshoot and guarantees genuine progress without an exact minimisation.
Misconceptions and diagnostics
| Mistake | Symptom | Diagnostic question | Correction |
|---|---|---|---|
| Non-descent direction | Objective rises after a step | "Is ∇fTp negative?" | Use a direction that decreases f initially. |
| Step too long | Overshoots and fails to decrease | "Did it meet sufficient decrease?" | Backtrack until the Armijo condition holds. |
| Expecting fast steepest descent | Slow zig-zag on stretched contours | "Are the contours ill-scaled?" | Scale variables or use curvature (Newton). |
| Fixed step for every problem | Divergence or crawling | "Is α adapted to the function?" | Choose α by a line search, not a constant. |
Practice ladder
At (3, 2) for f = x2 + y2, give the steepest-descent direction.
Show answer
∇f = (2x, 2y) = (6, 4), so the steepest-descent direction is −(6, 4).
Is p = (−1, 1) a descent direction at (3, 2) for that function?
Show answer
∇fTp = (6)(−1) + (4)(1) = −6 + 4 = −2 < 0, so yes, it is a descent direction.
For f(x) = x2 from x = 3, p = −6, find the exact line-search step α and the new point.
Show answer
f(3 + α(−6)) = (3 − 6α)2; minimise: 3 − 6α = 0 ⇒ α = 0.5, giving x = 0, the minimum in one exact step.
A gradient-descent optimisation of a design crawls after a fast start. Explain what the contours are likely doing and one fix.
What good work looks like
The contours are elongated (ill-conditioned), so steepest descent zig-zags across a narrow valley. Rescaling the design variables to equalise sensitivities, or switching to a Newton or quasi-Newton direction, removes the zig-zag.
Working with AI, and proving it yourself
Use AI as an examiner, not a solver
Portfolio task
Run a few steepest-descent steps on a two-variable objective with a line search, plot the path, and note where the zig-zag begins.
Retrieval and spaced review
Closed notes. Answer out loud, then reveal.
1. Write the line-search update.
xk+1 = xk + αk pk.
2. When is p a descent direction?
When ∇fTp < 0.
3. What direction does steepest descent use?
The negative gradient, p = −∇f.
4. State the sufficient-decrease condition.
f(x + αp) ≤ f(x) + c1 α ∇fTp.
5. Why is steepest descent slow on stretched contours?
Its steps are perpendicular to the contours, so they zig-zag across a narrow valley.
Textbook mapping
This module follows Nocedal and Wright, Numerical Optimization, 2nd edition. Use these references to read further.
| Topic in this module | Where to read more |
|---|---|
| Descent directions and steepest descent | Nocedal & Wright, Chapter 3 |
| Step length and line search | Nocedal & Wright, Chapter 3 |
| The sufficient-decrease condition | Nocedal & Wright, Chapter 3 |
Chapter numbers refer to the 2nd edition. The line-search framework is standard, so any recent edition will align closely.