Line search

From Wikipedia, the free encyclopedia

Jump to: navigation, search

In optimization, a line search strategy is an approach to finding the minimum value of a function in one dimension. Usually, this is a single direction in an objective function f:\mathbb R^n\to\mathbb R of the form[1]

h(α) = f(x + αd)

where x,d \in \mathbb R^n and \alpha \in \mathbb R.

Another method for a similar goal is called trust regions.

Contents

[edit] Example use

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)=f(\mathbf{x}_k+\alpha\mathbf{p}_k) over \alpha\in\mathbb R
  5.     Update \mathbf{x}_{k+1}=\mathbf{x}_k+\alpha_k\mathbf{p}_k, and \displaystyle k=k+1
  6. Until \|\nabla f(\mathbf{x}_k)\| < tolerance

At the line search step (4) the algorithm might either exactly minimize h, by solving h'(αk) = 0, or loosely, by asking for a sufficient decrease in h. The latter may be performed in a number of ways, perhaps by doing 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.

[edit] Algorithms

[edit] Direct search methods

In this method, the minimum must first be bracketed, so the algorithm must identify points x1 and x2 that are above the minimum. The interval is then divided by computing f(x) at two internal points, x3 and x4, and rejecting whichever of the two outer points has the highest function value. Subsequently only one extra internal point needs to be calculated. Of the various methods of dividing the interval[2], those that use the golden ratio are particularly simple and effective .

x_4-x_1=x_2-x_3=\frac{1}{\tau}(x_2-x_1), \tau=\frac{1}{2}(1+\sqrt 5)

[edit] See also

[edit] References

  1. ^ Kenneth Lange. Optimization.Springer texts in statistics, 2004.
  2. ^ M.J. Box, D. Davies and W.H. Swann, Non-Linear optimisation Techniques, Oliver & Boyd, 1969
Retrieved from "http://en.wikipedia.org/wiki/Line_search"