Backtracking line search

In (unconstrained) optimization, the backtracking linesearch strategy is used as part of a linesearch method, to compute how far one should move along a given search direction.

Motivation

Usually it is undesirable to exactly minimize the function $$displaystyle phi(alpha) in the generic linesearch algorithm. One way to inexactly minimize $$displaystyle phi is by finding an $$displaystyle alpha_k that gives a sufficient decrease in the objective function $$f:mathbb R^n omathbb R (assumed smooth), in the sense of the Armijo condition holding. This condition, when used appropriately as part of a backtracking linesearch, is enough to generate an acceptable step length. (It is not sufficient on its own to ensure that a reasonable value is generated, since all $$displaystyle alpha small enough will satisfy the Armijo condition. To avoid the selection of steps that are too short, the additional curvature condition is usually imposed.)

Algorithm

:i) Set iteration counter $$scriptstyle j,=,0. Make an initial guess $$scriptstyle alpha^j,>,0 and choose some $$scriptstyle au,in,(0,1).,

:ii) Until $$scriptstyle alpha^j, satisfies the Armijo condition:

::$$alpha^{j+1}= aualpha^j,,

::$$j=j+1.,

:iii) Return $$scriptstyle alpha=alpha^j.,

In other words, reduce $$scriptstyle alpha^0 geometrically, with rate $$scriptstyle au,, until the Armijo condition holds.

ee also

*linesearch

References

* J. Nocedal and S. J. Wright, Numerical optimization. Springer Verlag, New York, NY, 1999.