Line search

Not to be confused with linear search.

In optimization, line search is a basic iterative approach to find a local minimum $\mathbf {x} ^{*}$ of an objective function $f:\mathbb {R} ^{n}\to \mathbb {R}$. It first finds a descent direction along which the objective function $f$ will be reduced, and then computes a step size that determines how far $\mathbf {x}$ 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, $f:\mathbb {R} \to \mathbb {R}$, 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:

• Ternary search: pick some two points b,c such that a<b<c<z. If f(b)≤f(c), then x* must be in [a,c]; if f(b)≥(c), then x* must be in [b,z]. In both cases, we can replace the search interval with a smaller one. If we pick b,c very close to the interval center, then the interval shrinks by ~1/2 at each iteration, but we need two function evaluations per iteration. Therefore, the method has linear convergence with rate ${\sqrt {0.5}}\approx 0.71$. If we pick b,c such that the partition a,b,c,z has three equal-length intervals, then the interval shrinks by 2/3 at each iteration, so the method has linear convergence with rate ${\sqrt {2/3}}\approx 0.82$.
• Fibonacci search: This is a variant of ternary search in which the points b,c are selected based on the Fibonacci sequence. At each iteration, only one function evaluation is needed, since the other point was already an endpoint of a previous interval. Therefore, the method has linear convergence with rate $1/\varphi \approx 0.618$ .
• Golden-section search: This is a variant in which the points b,c are selected based on the golden ratio. Again, only one function evaluation is needed in each iteration, and the method has linear convergence with rate $1/\varphi \approx 0.618$ . This ratio is optimal among the zero-order methods.

Zero-order methods are very general - they do not assume differentiability or even continuity.

First-order methods

First-order methods assume that f is continuously differentiable, and that we can evaluate not only f but also its derivative.

• The bisection method computes the derivative of f at the center of the interval, c: if f'(c)=0, then this is the minimum point; if f'(c)>0, then the minimum must be in [a,c]; if f'(c)<0, then the minimum must be in [c,z]. This method has linear convergence with rate 0.5.

Curve-fitting methods

Curve-fitting methods try to attain superlinear convergence by assuming that f has some analytic form, e.g. a polynomial of finite degree. At each iteration, there is a set of "working points" in which we know the value of f (and possibly also its derivative). Based on these points, we can compute a polynomial that fits the known values, and find its minimum analytically. The minimum point becomes a new working point, and we proceed to the next iteration.

Newton's method is a special case of a curve-fitting method, in which the curve is a degree-two polynomial, constructed using the first and second derivatives of f. If the method is started close enough to a non-degenerate minimum point (= with a positive second derivative), then it has quadratic convergence.

Multi-dimensional line search

In general, we have a multi-dimensional objective function $f:\mathbb {R} ^{n}\to \mathbb {R}$. The line-search method first finds a descent direction along which the objective function $f$ will be reduced, and then computes a step size that determines how far $\mathbf {x}$ 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.

Example use

See also: Backtracking line search

Here is an example gradient method that uses a line search in step 4.

1. Set iteration counter $\displaystyle k=0$, and make an initial guess $\mathbf {x} _{0}$ for the minimum
2. Repeat:
3.     Compute a descent direction $\mathbf {p} _{k}$
4.     Choose $\displaystyle \alpha _{k}$ to 'loosely' minimize $h(\alpha _{k})=f(\mathbf {x} _{k}+\alpha _{k}\mathbf {p} _{k})$ over $\alpha _{k}\in \mathbb {R} _{+}$
5.     Update $\mathbf {x} _{k+1}=\mathbf {x} _{k}+\alpha _{k}\mathbf {p} _{k}$, and ${\textstyle k=k+1}$
6. Until $\|\nabla f(\mathbf {x} _{k+1})\|$ < tolerance

At the line search step (4) the algorithm might either exactly minimize h, by solving $h'(\alpha _{k})=0$, or loosely, by asking for a sufficient decrease in h. One example of the former is conjugate gradient method. The latter is called inexact line search and may be performed in a number of ways, such as a backtracking line search or using the Wolfe conditions.

Like other optimization methods, line search may be combined with simulated annealing to allow it to jump over some local minima.

See also

• Trust region - a dual approach for finding a local minimum: it first computes a step size, and then determines the descent direction.
• Grid search
• Learning rate
• Pattern search (optimization)
• Secant method

Further reading

• Dennis, J. E. Jr.; Schnabel, Robert B. (1983). "Globally Convergent Modifications of Newton's Method". Numerical Methods for Unconstrained Optimization and Nonlinear Equations. Englewood Cliffs: Prentice-Hall. pp. 111–154. ISBN 0-13-627216-9.
• Nocedal, Jorge; Wright, Stephen J. (1999). "Line Search Methods". Numerical Optimization. New York: Springer. pp. 34–63. ISBN 0-387-98793-2.
• Sun, Wenyu; Yuan, Ya-Xiang (2006). "Line Search". Optimization Theory and Methods: Nonlinear Programming. New York: Springer. pp. 71–117. ISBN 0-387-24975-3.