Optimization: Steepest Descent, Conjugate Gradient, and Newton
Claude prompt
This page was generated by Claude Code from the following prompt (with additional prompting):
Let's make a new demo for the next lecture: newton. The demo should show steepest descent, conjugate gradient (PR+), and newton on a moderately conditioned quadratic, classic rosenbrock, and maybe one other test function. Add a checkbox for line search, and for Newton, a checkbox to show the contour lines of the fitted quadratic.
The Methods
All three methods pick a search direction \(\vec{p}_k\) and then step along it, \(\vec{x}_{k+1} = \vec{x}_k + \alpha_k\, \vec{p}_k\). They differ in the direction:
- Steepest descent uses \(\vec{p}_k = -\nabla f(\vec{x}_k)\).
- Conjugate gradient (Polak–Ribière+) bends the new direction with the previous one, \(\vec{p}_k = -\nabla f_k + \beta_k\, \vec{p}_{k-1}\), with \(\beta_k = \max\!\left(0,\; \dfrac{\nabla f_k^\mathsf{T}(\nabla f_k - \nabla f_{k-1})} {\nabla f_{k-1}^\mathsf{T} \nabla f_{k-1}}\right)\).
- Newton fits a quadratic to \(f\) at \(\vec{x}_k\) using the gradient and Hessian, \[ q(\vec{x}) = f_k + \nabla f_k^\mathsf{T}(\vec{x} - \vec{x}_k) + \tfrac{1}{2}(\vec{x} - \vec{x}_k)^\mathsf{T} H_k (\vec{x} - \vec{x}_k), \] and jumps to its stationary point: \(H_k \vec{p}_k = -\nabla f_k\) with \(\alpha_k = 1\).
The step size \(\alpha_k\) can be chosen three ways. Fixed uses the slider's \(\alpha\) every time. Exact line search minimizes \(f\) along \(\vec{p}_k\) with the bracketing and golden-section search from the previous lecture, starting the bracket at the slider's \(\alpha\). Armijo backtracking starts from the slider's \(\alpha\) and halves it (\(\rho = 0.5\)) until the sufficient decrease condition \[ f(\vec{x}_k + \alpha\, \vec{p}_k) \le f(\vec{x}_k) + \mu_1\, \alpha\, \nabla f_k^\mathsf{T} \vec{p}_k, \qquad \mu_1 = 10^{-4}, \] holds. Newton ignores the slider: its natural step is \(\alpha = 1\), which it uses as the fixed step and as the starting point for either line search. If the Newton direction is not a descent direction (the Hessian is not positive definite), the line-search versions fall back to a steepest descent step.
Results
Click on the contour plot to move the starting point.
On the quadratic, Newton lands on the minimum in a single step because the fitted quadratic is the function. Conjugate gradient with an exact line search needs only two steps (one per dimension); with Armijo backtracking the directions are no longer conjugate and it takes more, but it still avoids the zig-zag of steepest descent. On Rosenbrock the banana valley is curved, so no quadratic fits for long, but Newton still follows the valley far faster than the gradient methods. Himmelblau's function has four minima, a local maximum, and four saddles. Newton jumps to the stationary point of its quadratic model, whichever kind it is, so from a start where the Hessian is not positive definite it can converge happily to a maximum or saddle. Turn on the fitted quadratic and watch what it is aiming at.