Backtracking line search
Usually it is undesirable to exactly minimize the function in the generic linesearch algorithm. One way to inexactly minimize is by finding an that gives a sufficient decrease in the objective function (assumed smooth), in the sense of the Armijo-Goldstein 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.)
- i) Set iteration counter . Make an initial guess and choose some
- ii) Until satisfies the Armijo-Goldstein condition:
- iii) Return
In other words, reduce geometrically, with rate , until the Armijo-Goldstein condition holds.
- Dennis, J. E.; Schnabel, R. B. (1996). Numerical Methods for Unconstrained Optimization and Nonlinear Equations. Philadelphia: SIAM Publications.
- Nocedal, J.; Wright, S. J. (1999). Numerical optimization. New York, NY: Springer Verlag.