2021/10/26 by Ivo Fagundes David de Oliveira, de Oliveira, Ivo Fagundes David, Ricardo Hiroshi Caldeira Takahashi +1
Computer Science · Mathematics · #49K35 #49M37 #65K10 #90C47 #FOS: Mathematics #G.1.5 #G.1.6 #Numerical Analysis (math.NA) #Optimization and Control (math.OC) #acm:49K35 #acm:49M37 #acm:65K10 #acm:90C47 #cs.NA #math.NA #math.OC #msc:49K35 #msc:49M37 #msc:65K10 #msc:90C47
paper · pdf · doi:10.48550/arxiv.2110.14072
Keywords: inexact line search, Armijo-type methods, backtracking, bracketing algorithms, geometric bisection
arxiv created 2021/10/26 · arxiv updated 2021/10/28
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.