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.