Gradient descent
Why it matters
Gradient descent turns local derivative information into an auditable sequence of candidate solutions.
Learning objectives
- Trace updates, objective history and gradient norms.
- Diagnose sign, step-size and stopping failures.
- Validate iterations, feasibility, convergence evidence and limitations independently.
Prerequisites
Canonical prerequisites: Courses 6.1 Numerical Methods and 8.1 Mathematical Optimization. Supporting connections: 6.2 Numerical Linear Algebra, 7.1 Python for Scientific Computing, 7.2 Computational Experimentation, and prior 8.2 classes where applicable.
Concept and explanation
At xₖ, the gradient points toward greatest local increase; −∇f is a descent direction. The finite update xₖ₊₁=xₖ−αₖ∇f(xₖ) also depends on step size. Descent alone does not prove global optimality for a nonconvex objective.
Key terms
gradient; descent direction; step size; iterate; objective history; gradient norm; tolerance
Definitions
Objective function: maps a candidate to the quantity minimized. Gradient: vector of partial derivatives. Negative gradient: local steepest-descent direction. Step size: distance multiplier applied to that direction. Iterate: current candidate in the algorithm.
Mathematical / computational notation
xₖ is the current vector, ∇f(xₖ) its gradient, αₖ>0 the step size, and xₖ₊₁=xₖ−αₖ∇f(xₖ). Record k, xₖ, f(xₖ), ‖∇f(xₖ)‖, αₖ and constraint violation.
Optimization model
Declare variables, objective, domain, initial point, α, iteration limit and stopping rule before computing.
Algorithm before software
Evaluate f and ∇f; record evidence; stop only under the declared test; otherwise update in the negative-gradient direction; finally validate independently.
Mathematical and computational development
For f=(x−3)², ∇f=2(x−3). With α=0.25, the error halves each iteration. A poor α can stall, oscillate or diverge.
Worked computational examples
Worked example 1
Problem: Minimize (x−3)² from x₀=0.
Decision variables: x∈ℝ.
Objective and direction: minimize f(x)=(x−3)².
Constraints and domain: none; domain ℝ.
Initialization and parameters: x₀=0, α=0.25, tolerance 0.8, maximum 10 updates.
Method: fixed-step gradient descent.
Algorithm: x←x−0.25·2(x−3), recording f and |g| before each update.
Iterations / candidate result: candidate x=2.625 after three updates; f=0.140625.
Constraint check: No constraints; x remains real.
Optimality / convergence evidence: Objective decreases 9→2.25→0.5625→0.140625 and |g| decreases.
Independent validation: Analytic minimizer x=3 with f=0 confirms the trace approaches the unique global solution; tolerance not yet met at k=3 if tested before update.
Interpretation: The trace demonstrates progress, not completion at x=2.625.
Limitations: Guarantee uses this strictly convex quadratic; it does not transfer automatically to nonconvex functions.
Transparent code / pseudocode:
x=0.0
for k in range(4):
g=2*(x-3)
print(k,x,(x-3)**2,abs(g),0.25)
x=x-0.25*gExpected/precomputed output — not executed: Expected/precomputed trace: objective and gradient norm decrease geometrically; no live execution claimed.
| k | x | f(x) | gradient norm | step | violation |
|---|---|---|---|---|---|
| 0 | 0 | 9 | 6 | 0.25 | 0 |
| 1 | 1.5 | 2.25 | 3 | 0.25 | 0 |
| 2 | 2.25 | 0.5625 | 1.5 | 0.25 | 0 |
| 3 | 2.625 | 0.140625 | 0.75 | 0.25 | 0 |
Worked example 2
Problem: Compare stable and unstable steps for f=x² from x₀=1.
Decision variables: x∈ℝ.
Objective and direction: minimize x².
Constraints and domain: none.
Initialization and parameters: x₀=1; α=0.25 or 1.1; four updates.
Method: step-size race.
Algorithm: Use xₖ₊₁=(1−2α)xₖ.
Iterations / candidate result: α=.25 contracts by .5; α=1.1 multiplies by −1.2 and diverges.
Constraint check: Domain is unconstrained.
Optimality / convergence evidence: Stable objective: 1,.25,.0625,.015625; unstable: 1,1.44,2.0736,2.986.
Independent validation: Closed-form multiplier verifies both traces.
Interpretation: Smaller is not always better; it trades progress for stability.
Limitations: The stability interval depends on curvature.
Transparent code / pseudocode:
for alpha in (0.25,1.1):
x=1.0
for k in range(4):
print(alpha,k,x,x*x)
x-=alpha*2*xExpected/precomputed output — not executed: Expected/precomputed: α=.25 converges; α=1.1 oscillates with growing magnitude.
| step | k | x | f(x) | gradient norm | violation |
|---|---|---|---|---|---|
| 0.25 | 0 | 1 | 1 | 2 | 0 |
| 0.25 | 3 | 0.125 | 0.015625 | 0.25 | 0 |
| 1.1 | 0 | 1 | 1 | 2 | 0 |
| 1.1 | 3 | -1.728 | 2.986 | 3.456 | 0 |
Common failure and counterexample
Wrong-sign updates move uphill. Tiny changes can also reflect a tiny step rather than convergence. Diagnose with the objective, gradient norm and stopping rule—not iterate change alone.
x = x + alpha*gradient(x)
if abs(x_new-x)<tol: return 'optimum'Correct method, recheck and close
x_new=x-alpha*gradient(x)
check_objective_gradient_and_declared_tolerance()Guided practice
Guided problem 1
For f(x)=(x−4)², start x₀=0 with α=0.25. Compute x₁ and x₂, then report f and |f′| at both iterates.
Solution / evidence
f′=2(x−4). x₁=2 with f=4 and |f′|=4; x₂=3 with f=1 and |f′|=2.
Guided problem 2
For f(x,y)=(x−1)²+(y+2)², start (3,1) with α=0.25. Compute the gradient and two vector updates.
Solution / evidence
At (3,1), ∇f=(4,6), so x₁=(2,−0.5). Then ∇f=(2,3), so x₂=(1.5,−1.25). Objective falls 13→3.25→0.8125.
A/B/C/D computational practice
A · Foundation
Compute one descent update and label every quantity.
B · Application
Compare two step sizes using a trace.
C · Debugging / error detection
Find a wrong sign and a premature stop.
D · Challenge / transfer
Explain why descent is not global proof on a nonconvex function.
Validation, knowledge check and summary
- Explain why −∇f is local evidence, not global proof.
- Compute one scalar update.
- Compute one vector update and gradient norm.
- Diagnose divergence caused by α.
Required evidence
- Correct direction and update rule.
- Correct numerical iterate and objective.
- Complete vector and norm evidence.
- Failure diagnosis tied to the trace.
Mastery criterion: 4/4 checks plus one independently validated trace; correct every major misconception and complete a fresh equivalent check.
Related laboratory
Next class: Numerical optimization