Line search

From Wikipedia, the free encyclopedia

In (unconstrained) optimization, the line search strategy is one of two basic iterative approaches to finding a local minimum \mathbf{x}^* of an objective function f:\mathbb R^n\to\mathbb R. The other method is that of trust regions.

Contents

[edit] Algorithms

[edit] Gradient method

[1]

  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 \phi(\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, \displaystyle k=k+1
  6. Until \|\nabla f(\mathbf{x}_k)\| > tolerance

In step 4 we can either exactly minimize \displaystyle \phi, by solving \displaystyle \phi'(\alpha_k)=0, or loosely, by asking for a sufficient decrease in \displaystyle \phi. 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] Direct search methods

First the minimum must be bracketed, that is, it should lie between x1 and x2. 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. ^ N. I. M. Gould and S. Leyffer, An introduction to algorithms for nonlinear optimization. In J. F. Blowey, A. W. Craig, and T. Shardlow, Frontiers in Numerical Analysis, pages 109-197. Springer Verlag, Berlin, 2003.
  2. ^ M.J. Box, D. Davies and W.H. Swann, Non-Linear optimisation Techniques, Oliver & Boyd, 1969