Why steepest descent is so slow

Before we can understand why the conjugate-direction method is so fast, we need to see why the steepest-descent methodsteepest descent is so slow. Imagine yourself sitting on the edge of a circular bowl. If you jump off the rim, you'll slide straight to the bottom at the center. Now imagine an ellipsoidal bowl of very large ellipticity. As you jump off the rim, you'll first move in the direction of the gradient. This is not towards the bottom at the center of the ellipse (unless you were sitting on the major or minor axis).

We can formalize the situation. A parametric equation for a line is $\bold x=\bold x_{\rm old} +\alpha \Delta \bold x$where $\alpha$ is the parameter for moving on the line. The process of selecting $\alpha$ is called ``line search." Think of a two-dimensional example where the vector of unknowns $\bold x$has just two components, x₁ and x₂. Then the size of the residual vector $\bold r \cdot \bold r$ can be displayed with a contour plot in the plane of (x₁,x₂). Our ellipsoidal bowl has ellipsoidal contours of constant altitude. As we move in a line across this space by adjusting $\alpha$,equation(45) gives our altitude. This equation has a unique minimum because it is a parabola in $\alpha$.As we approach the minimum, our trajectory becomes tangential to a contour line in (x₁,x₂)-space. This is where we stop. Now we compute our new residual $\bold r$and we compute the new gradient $\Delta\bold x = \bold g = \bold F' \bold r$.OK, we are ready for the next slide down. When we turn ourselves from "parallel to a contour line" to the direction of $\Delta \bold x$ which is "perpendicular to that contour", we are turning $90^\circ$.Our path to the bottom of the bowl will be made of many segments, each turning $90^\circ$ from the previous. We will need an infinite number of such steps to reach the bottom. It happens that the amazing conjugate-direction method would reach the bottom in just two jumps (because (x₁,x₂) is a two dimensional space.) Missing figure (ls-sawtooth) A search path for steepest descent.