In (unconstrained) minimization, a backtracking line search, a search scheme based on the Armijo–Goldstein condition, is a line search method to determine the maximum amount to move along a given search direction. It involves starting with a relatively large estimate of the step size for movement along the search direction, and iteratively shrinking the step size (i.e., "backtracking") until a decrease of the objective function is observed that adequately corresponds to the decrease that is expected, based on the local gradient of the objective function.
Contents
Motivation
Given a starting position
The backtracking line search starts with a large estimate of
Define the local slope of the function of
Based on a selected control parameter
This condition, when used appropriately as part of a line search, can ensure that the step size is not excessively large. However, this condition is not sufficient on its own to ensure that the step size is nearly optimal, since any value of
Thus, the backtracking line search strategy starts with a relatively large step size, and repeatedly shrinks it by a factor
The search will terminate after a finite number of steps for any positive values of
Algorithm
Starting with a maximum candidate step size value
- Set
t = − c m and iteration counterj = 0 . - Until the condition is satisfied that
f ( x ) − f ( x + α j p ) ≥ α j t , repeatedly incrementj and setα j = τ α j − 1 . - Return
α j
In other words, reduce