An exact line search makes the best move on the current line, not among all possible future paths. On an elongated quadratic, its next negative gradient can point across the valley, causing the path to cross the valley again. We can quantify this behavior without assuming the iterates terminate in finitely many steps.
The method and its geometry
Let be a real symmetric positive-definite matrix and set
Definition 3.2.1
(Exact steepest descent on a quadratic)
The objective gap is . If , stop: . Otherwise exact steepest descent takes
The denominator is positive. Differentiating the line restriction shows that minimizes it over all real step lengths; it is positive. Moreover , so . Consecutive gradients are Euclidean orthogonal, but this alone neither makes them -conjugate nor makes the second gradient zero.
A sharp decrease theorem
Theorem 3.2.2
(Exact line-search rate for an SPD quadratic)
Suppose the eigenvalues of lie in with , and put . Each nonterminal exact steepest-descent step satisfies
In exact arithmetic this yields the same bound with after steps. If , one step reaches the minimizer.
Proof
(From spectral bounds to a decrease factor)
Suppress the iteration index and write . Substitution of the exact step into the quadratic gives
Dividing by the initial gap gives the ratio
To bound the denominator, expand in an orthonormal eigenbasis of . Let be the squared coefficients divided by ; then . For every eigenvalue ,
because . With and , averaging gives . Since , it follows that . Thus
Inserting this bound proves the stated factor, since . Apply the one-step inequality repeatedly, retaining the minimizer after termination. If , symmetry implies , and the exact step is .
Proof X-ray
Where the spectral interval enters
The proof has two independent parts. The first is an exact identity: the one-step decrease uses only that the step minimizes along the line and that ; no eigenvalue bound is involved. The spectrum enters only in the second part, the bound . Its key move is the pointwise inequality on : it is linear in the weights , so it survives averaging, and the elementary inequality then converts a bound on a sum into a bound on a product. Both inequalities are tight exactly when the weights sit on the extreme eigenvalues with each, which is why the bound is sharp; positive definiteness is used throughout, since is needed to divide by .
The bound measures objective gap, not the Euclidean error or a residual norm. It uses the extreme eigenvalues; the actual step can be much better. Large makes the worst-case factor close to one, but does not force slow progress for every starting point.
A worst-case path calculated exactly
Worked example 3.2.3
(Orthogonal gradients and a recurring zigzag)
Take , , and . Then , , and . Hence
The initial objective is and the next is , so their ratio is , exactly for , . The next step also has length and gives . Consequently the pattern repeats at smaller scale: exact line searches do not solve this two-dimensional problem in two steps. Although , we have , so the two search directions are not -conjugate.
Worked example 3.2.4
(Exactly when the worst case is attained)
The proof shows when the ratio equals with . Equality in forces every eigenvalue carrying positive weight to be or . Writing for those weights, equality in requires , that is
Hence : the gradient has equal squared components along an eigenvector for and one for , and none elsewhere. For this is , and both and above have this form, so every step of that path attains the bound.
Worked example 3.2.5
(A start that beats the bound)
Keep and , and take . Then , , and , so
As a check, the decrease is . The ratio is , well below , because the squared gradient components and are far from equal.
Counterexample mode
A large condition number need not mean slow convergence
With the same but , the gradient is an eigenvector. The line minimizer has , and . The condition number describes a worst-case guarantee; it is not the observed rate for every initial error. Nor is the theorem valid for a negative-definite Hessian: for , the restriction along the negative gradient at is unbounded below, so an exact line minimizer does not exist.
The explorer below runs exact steepest descent in exact fractions and compares each ratio with , attaining it from on and beating it from other starts.
Common mistakes
Common mistake
(Exact line search does not terminate in n steps)
Consecutive gradients are orthogonal, so it is tempting to expect termination after steps, as for conjugate directions. The first worked example refutes this: on a two-dimensional problem the path repeats at scale forever, because .
Common mistake
(The rate is for the objective gap, not the error)
The theorem contracts with . Since , the Euclidean error only satisfies ; quoting alone for omits the factor .
Practice with solutions
Quick check
(If is an eigenvector of with eigenvalue , determine and .)
Solution · Answer
and . The quadratic's unique minimizer is reached in one step.
Quick check
(If , , and the initial gap is , bound the gap after three steps.)
Solution · Answer
, so the gap is at most ; it may be smaller or already zero.
Quick check
(For , let , . Are they Euclidean orthogonal and -conjugate?)
Solution · Answer
, but , so they are not -conjugate.