Backtracking linesearch

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 1 Motivation 2 Algorithm 3 See also 4 References

[edit] Motivation

Usually it is undesirable to exactly minimize the function φ(α) in the generic linesearch algorithm. One way to inexactly minimize φ is by finding an α_k that gives a sufficient decrease in the objective function (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 α 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 j = 0. Make an initial guess α^j > 0 and choose some .

ii) Until α^j satisfies the Armijo condition:

α^{j + 1} = τα^j,

j = j + 1.

iii) Return α = α^j.

In other words, reduce α⁰ geometrically, with rate τ, until the Armijo condition holds.

[edit] See also

• linesearch

[edit] References

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