An optimality condition describes a solution; an algorithm must find one. Starting from , a line-search method chooses a direction and a step length , then sets . A useful direction should initially decrease the objective, but its eventual performance depends on the step length and on the objective's curvature. Quadratic examples expose these distinctions in calculations that can be checked by hand.
Descent directions and step lengths
Definition 3.1.1
(Descent direction)
Let be continuously differentiable near . A vector is a descent direction for at if .
Differentiability gives
so sufficiently small positive lowers . The negative gradient is a descent direction whenever the gradient is nonzero, since . A zero gradient supplies no such guarantee: is stationary at zero, yet zero is not a local minimum. Moreover, an arbitrary large step in a descent direction can increase the objective; for at , the step , reaches and raises the value from to .
How small a step must be depends on how fast the gradient can change. A Lipschitz bound on the gradient turns the first-order expansion into an inequality valid for every step.
Theorem 3.1.2
(The descent lemma)
If is -Lipschitz on , then for all ,
Proof
(Integrate the gradient along the segment)
Apply the fundamental theorem of calculus to on , whose derivative is . Subtracting the linear term gives
By the Cauchy–Schwarz inequality and the Lipschitz bound, the integrand is at most . Since , the stated inequality follows.
For the fixed gradient step , the lemma gives
a strict decrease whenever and the gradient is nonzero. If is also bounded below, summing these inequalities along fixed-step gradient descent yields , so the gradients tend to zero. This conclusion is weaker than convergence of the iterates, and stationarity alone is weaker than optimality when the objective is nonconvex. The distinction prevents a common overstatement of what a descent calculation proves.
Quadratic line search
Let with symmetric positive definite . The unique minimizer solves : completing the square around gives . Along a nonzero direction ,
The exact line minimizer is , positive precisely for a descent direction. With , this becomes . Exact-line-search steepest descent uses a new such step at each iterate. It can zigzag on an elongated quadratic because Euclidean gradient directions do not generally account for different curvatures.
For comparison, fixed-step gradient iteration has error . In an orthonormal eigenbasis of , component is multiplied by . Every eigencomponent strictly contracts exactly when . This is a statement about the fixed-step method, not the adaptive exact-line-search formula above.
Conjugate directions
Definition 3.1.3
(-conjugate directions)
Let be symmetric positive definite. Nonzero vectors are -conjugate when for all .
Because is positive definite, these directions are linearly independent: if , multiplying by gives , and forces . Hence such directions form a basis.
Concept lensGeometric
Conjugacy is orthogonality in the energy inner product
For SPD , the formula is an inner product, and -conjugacy is exactly orthogonality for it. Equivalently, factor with invertible and change variables to . The objective gap becomes , whose level sets are spheres, and are conjugate exactly when and are Euclidean-orthogonal. In these coordinates an exact search along deletes the error component along that orthogonal axis, and later searches along orthogonal axes cannot reintroduce it. Gram–Schmidt in the -inner product therefore turns any basis into conjugate directions.
Starting anywhere, minimize the quadratic exactly along each direction in turn. The next theorem records what this achieves, and its proof makes the coordinate picture precise without changing variables.
Theorem 3.1.4
(Finite termination along conjugate directions)
Let with SPD , and let be -conjugate. From any , the iteration with the exact steps , where , gives in exact arithmetic.
Proof
(Preserve each orthogonality once it is created)
Since , the gradients satisfy . The exact step is defined because , and it gives
Now fix and let . Conjugacy gives . By induction on , for every ; in particular for . The directions form a basis, so , that is . By the completed square, is the unique minimizer. If some earlier gradient already vanishes, every later exact step is zero, so the minimizer is reached in at most nonzero steps.
Proof X-ray
Where exactness, conjugacy and positive definiteness enter
The proof has two separate moves. Exactness of the line search is used only once per step, to create the orthogonality . Conjugacy is used only to show that later steps leave each such orthogonality intact, because a step along changes by . Positive definiteness enters twice: it makes every exact step well defined, and it makes the directions a basis, which is how the collected orthogonalities close the argument at . Drop conjugacy and the second move fails visibly. For , and , exact searches along and then give and , with . The orthogonality was destroyed by the second step, by exactly .
For example, take , , and . Coordinate directions and are -conjugate. Exact searches give and . Orthogonal directions need not be conjugate for a nondiagonal ; the relevant inner product is , not .
The objective need not drop by the same amount at every step, and a step can be zero if the current gradient is already orthogonal to the next direction. The finite termination statement assumes exact arithmetic, exact line searches and a full set of conjugate directions; roundoff and inexact searches change the practical behavior. Constructing directions beforehand can be costly; conjugate gradient builds suitable directions by a short recurrence that exploits the symmetric quadratic structure. The finite-termination result should not be transferred unchanged to nonlinear objectives.
Quasi-Newton curvature
Newton's method uses the Hessian to transform the gradient. Quasi-Newton methods instead accumulate curvature information from successive iterates and gradients. Write , , and let approximate the inverse Hessian. The inverse BFGS update is
The formula is undefined when . When the curvature condition holds, the update keeps the two properties a line-search method needs.
Proposition 3.1.5
(Secant equation and positive definiteness of the BFGS update)
If is symmetric positive definite and , then is symmetric positive definite and satisfies the secant equation .
Proof
(Factor the quadratic form)
The transpose of is the same product, because is symmetric, so is symmetric. Since and , the secant equation holds. For any , put . Then
because . If the sum is zero, both terms vanish: gives , and then forces .
Proof X-ray
Where the curvature condition is actually used
Symmetry uses only the symmetry of , and the secant equation uses only the identity ; neither needs beyond being defined. The real move is the substitution , which splits into a part governed by and the rank-one term . The curvature condition enters exactly here, by making . Definiteness then closes by a case split: the rank-one term vanishes only when , and there , so the definiteness of takes over. With the rank-one term is negative, and the counterexample later in this unit shows that the conclusion fails.
Thus is a descent direction at a nonstationary point. The curvature condition is essential. A positive-definite approximation and descent direction alone do not establish global convergence for an arbitrary line search.
Backtracking and a computable decrease test
A descent direction guarantees improvement for a sufficiently small step, but does not tell us how small. Backtracking starts with a trial and repeatedly multiplies it by a fixed factor until the Armijo inequality holds:
The right side is below for a descent direction. Differentiability ensures termination: divide the first-order expansion by and let . Its limiting slope is , which is strictly less than because that slope is negative. Thus all sufficiently small positive steps satisfy the inequality. This argument is local to one line search; convergence of an entire sequence requires additional assumptions about directions, smoothness, and the objective. A decrease test is not by itself a universal convergence theorem.
Worked examples: directions and curvature
Worked example 3.1.6
(Exact steepest descent on an anisotropic quadratic)
Take and start at . The gradient is , so the negative-gradient direction is . The exact step is . Hence the new point is . Its gradient is , whose inner product with the old gradient is zero. This orthogonality follows in general from differentiating the objective along the exact search line; it does not mean that the new gradient is zero or that the minimum has been reached.
Worked example 3.1.7
(Checking Armijo backtracking)
Let , start at with , take , initial step and factor . At , the left side is while the right side is , so the test fails. At , the left side is and the right side is , so the step is accepted. The equality in the sufficient-decrease test is permitted. Different parameter choices can accept different steps without changing the definition of a descent direction.
Worked example 3.1.8
(Conjugacy depends on the matrix)
Let . The standard basis vectors have Euclidean inner product zero, but , so they are not -conjugate. Take and instead. Then . Both directions are nonzero, and the SPD property makes them a basis. Sequential exact searches along them therefore solve any quadratic with this Hessian in at most two steps, regardless of the linear term.
The secant equation and positive definiteness
The difference equals the integral of the Hessian along the step applied to , provided the Hessian is continuous on the segment. It is therefore a curvature observation averaged along that segment, rather than necessarily a Hessian at either endpoint. The inverse secant equation asks the updated inverse approximation to reproduce this one observed displacement. One pair of vectors does not determine a full matrix, which is why an update rule must make an additional choice about how to retain prior information.
For any symmetric positive definite , the direction satisfies when . This explains why preserving positive definiteness matters: it makes the next direction locally descending. But the BFGS formula's condition must be verified or enforced by an appropriate algorithm. If the objective has constant SPD Hessian , then and for every nonzero step. For a general nonconvex function the product can be nonpositive.
Counterexample mode
Applying BFGS without the curvature condition
Claim: the inverse BFGS update of a positive definite is positive definite whenever the step decreased . Take , , and , so drops from to . Since , we get and , hence . In one dimension , so the update gives , which indeed satisfies . At the gradient is , and the new direction has slope : it points uphill. The repaired statement is the proposition above, which assumes ; a method must check this condition and skip or modify the update when it fails.
Reading a numerical result
A small step can result from a poor line search or scaling rather than proximity to a solution. A small gradient is a meaningful first-order residual for an unconstrained problem, but at a constrained boundary it need not vanish; an appropriate constrained residual is needed instead. Even an exact stationary point can be a saddle. To interpret an output, record the objective, constraints, stopping test, and assumptions behind any claimed convergence. These checks connect the computation back to the optimality certificates developed earlier.
Conditioning and what the quadratic reveals
For the SPD quadratic, write and diagonalize with positive eigenvalues. The objective gap is , while the gradient is . The same Euclidean distance can produce different objective gaps in different eigenvector directions. If , then
The ratio is the spectral condition number. A large ratio means substantially different curvatures along eigenvectors. In fixed-step iteration, a step small enough to control the largest eigenvalue can make the smallest-eigenvalue component decay slowly. The exact-line-search method adapts its step but can still alternate directions on an elongated contour. This is a geometric explanation, not a claim that every problem with a large condition number takes the same number of iterations.
Suppose the extreme eigenvalues are known and a fixed positive step is chosen to minimize the worst absolute eigenvalue factor. Equating the magnitudes at the endpoints gives , hence . All intermediate eigenvalue factors lie between the endpoint factors because is affine in . The resulting worst factor is . It is less than one but approaches one as grows. This calculation concerns fixed-step error contraction; it is not the exact line-search step, which depends on the current gradient.
Preconditioning changes the geometry rather than changing the optimizer. For a symmetric positive definite matrix , the direction is descending whenever , since . If approximates , solving with can reduce differences in effective curvature, although the computational cost of that solve must be counted. Positive definiteness is essential to the stated descent proof; an arbitrary invertible matrix need not give a descent direction.
For example, with and , the preconditioned direction is . A unit step reaches the exact minimizer of this quadratic. This idealized choice already requires solving with , the original task, so it illustrates the goal of preconditioning rather than giving a universally cheap method. Quasi-Newton methods pursue related curvature information from observed steps, with the secant and positive-definiteness qualifications stated above.
Common mistakes
Three errors recur when these methods are first used; the curvature condition for BFGS was treated above.
Common mistake
(Taking any step along a descent direction)
A descent direction ensures decrease only for sufficiently small positive steps. For at with , the step raises from to . A step rule such as exact search, a fixed step below , or Armijo backtracking is part of the method, not an afterthought.
Common mistake
(Interchanging exact-search and fixed-step formulas)
Exact line search and fixed-step gradient descent are different algorithms. For at the exact step is and depends on the current gradient, while is the range of fixed steps that contract every error component. Neither formula determines the other, and their convergence statements must not be interchanged. Likewise, Euclidean orthogonality is not -conjugacy in general, as the third worked example shows.
Common mistake
(Reading a small gradient as optimality)
A small gradient establishes only approximate stationarity. The function has zero derivative at zero, which is not a local minimizer. Additional structure, such as convexity, is needed to connect stationarity to optimality.
Summary
A line search chooses how far to move along a direction; curvature controls how that choice affects the objective. Conjugate directions preserve earlier quadratic minimizations in exact arithmetic, whereas BFGS accumulates local curvature information through secant pairs. Every practical conclusion depends on the stated assumptions and the stopping criterion.
Exercises
Quick check
(For at , find the exact step along .)
Write as and use the exact line minimizer.
Solution · Answer
Here , and . The exact step is , and the new point is , the minimizer.
Quick check
(With , find the range of fixed positive steps for which both error components strictly contract.)
Each eigencomponent is multiplied by .
Solution
The factors are and . The condition means , and means . Both hold exactly for , that is .
Quick check
(In one dimension let , , . Find from the inverse BFGS update and check its secant equation.)
Compute first; the scalar factors simplify.
Solution · Answer
, and each scalar factor is zero, so . Indeed . In one dimension the update always returns , whatever was.