In optimization, line search is a basic iterative approach to find a local minimum <math>\mathbf{x}^*</math> of an objective function <math>f:\mathbb R^n\to\mathbb R</math>. It first finds a descent direction along which the objective function <math>f</math> will be reduced, and then computes a step size that determines how far <math>\mathbf{x}</math> should move along that direction. The descent direction can be computed by various methods, such as gradient descent or quasi-Newton method. The step size can be determined either exactly or inexactly.
One-dimensional line search
Suppose f is a one-dimensional function, <math>f:\mathbb R\to\mathbb R</math>, and assume that it is unimodal, that is, contains exactly one local minimum x* in a given interval [a,z]. This means that f is strictly decreasing in [a,x*] and strictly increasing in [x*,z]. There are several ways to find an (approximate) minimum point in this case.
Zero-order methods
Zero-order methods use only function evaluations (i.e., a value oracle) - not derivatives: