Efficient solvers for Armijo's backtracking problem

Backtracking is an inexact line search procedure that selects the first value in a sequence x0, x0β, x0β2... that satisfies g(x)≤ 0 on ℝ_+ with g(x)≤ 0 iff x≤ x^*. This procedure is widely used in descent direction optimization algorithms with Armijo-type conditions. It both returns an estimate in (β x^*,x^*] and enjoys an upper-bound lceil logβ ε/x0 rceil on the number of function evaluations to terminate, with ε a lower bound on x^*. The basic bracketing mechanism employed in several root-searching methods is adapted here for the purpose of performing inexact line searches, leading to a new class of inexact line search procedures. The traditional bisection algorithm for root-searching is transposed into a very simple method that completes the same inexact line search in at most lceil log2 logβ ε/x0 rceil function evaluations. A recent bracketing algorithm for root-searching which presents both minmax function evaluation cost (as the bisection algorithm) and superlinear convergence is also transposed, asymptotically requiring ~ log log log ε/x0 function evaluations for sufficiently smooth functions. Other bracketing algorithms for root-searching can be adapted in the same way. Numerical experiments suggest time savings of 50% to 80% in each call to the inexact search procedure.