  Backtracking is an inexact line search procedure that selects the first value
in a sequence $x_0, x_0\beta, x_0\beta^2...$ that satisfies $g(x)\leq 0$ on
$\mathbb{R}_+$ with $g(x)\leq 0$ iff $x\leq x^*$. This procedure is widely used
in descent direction optimization algorithms with Armijo-type conditions. It
both returns an estimate in $(\beta x^*,x^*]$ and enjoys an upper-bound $\lceil
\log_{\beta} \epsilon/x_0 \rceil$ on the number of function evaluations to
terminate, with $\epsilon$ 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 \log_2 \log_{\beta} \epsilon/x_0 \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 $\sim \log
\log \log \epsilon/x_0 $ 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.

Optimization and Control;Numerical Analysis;Numerical Analysis