Backtracking linesearch

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^ntomathbb 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 tau,in,(0,1).,

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

alpha^{j+1}=taualpha^j,,

j=j+1.,

iii) Return scriptstyle alpha=alpha^j.,

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

See also

References

  • J. Nocedal and S. J. Wright, Numerical optimization. Springer Verlag, New York, NY, 1999.
Search another word or see Backtracking linesearchon Dictionary | Thesaurus |Spanish
Copyright © 2014 Dictionary.com, LLC. All rights reserved.
  • Please Login or Sign Up to use the Recent Searches feature