Backtracking line search

From Wikipedia, the free encyclopedia

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.

Contents

[edit] 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\to\mathbb 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.)

[edit] 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}=\tau\alpha^j,\,
j=j+1.\,
iii) Return \scriptstyle \alpha=\alpha^j.\,

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

[edit] See also

[edit] References

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