Line search

Line search is a basic iterative approach in mathematical optimization for finding a local minimum of an objective function. Each iteration first finds a descent direction along which the objective function will be reduced, and then computes a step size that determines how far the current point should move along that direction. The descent direction can come from methods such as gradient descent or a quasi-Newton method, and the step size can be chosen exactly or inexactly. For a one-dimensional unimodal function, line search can use zero-order methods such as ternary search, Fibonacci search and golden-section search, first-order methods such as bisection, or curve-fitting methods such as Newton's method, regula falsi and cubic fit. Like other optimization methods, it can be combined with simulated annealing to jump over some local minima. Trust region methods are described as a dual approach.