Line search

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\; omathbb\; R$. The other method is that of trust regions.

Algorithms

Gradient method

[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.]

# Set iteration counter $displaystyle\; k=0$, and make an initial guess, $mathbf\{x\}\_0$ for the minimum
# Repeat:
# Compute a descent direction $mathbf\{p\}\_k$
# Choose $displaystyle\; alpha\_k$ to 'loosely' minimize $phi(alpha)=f(mathbf\{x\}\_k+alphamathbf\{p\}\_k)$ over $alphainmathbb\; R$
# Update $mathbf\{x\}\_\{k+1\}=mathbf\{x\}\_k+alpha\_kmathbf\{p\}\_k$, $displaystyle\; k=k+1$
# Until $|\; abla\; f(mathbf\{x\}\_k)|$ < tolerance

In step 4 we can either "exactly" minimize $displaystyle\; phi$, by solving $displaystyle\; phi\text{'}(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.

Direct search methods

First the minimum must be bracketed, that is, it should lie between x₁ and x₂. The interval is then divided by computing f(x) at two internal points, x₃ and x₄, 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 [M.J. Box, D. Davies and W.H. Swann, Non-Linear optimisation Techniques, Oliver & Boyd, 1969] , those that use the golden ratio are particularly simple and effective. :$x\_4-x\_1=x\_2-x\_3=frac\{1\}\{\; au\}(x\_2-x\_1),\; au=frac\{1\}\{2\}(1+sqrt\; 5)$

ee also

* Secant method
* Newton–Raphson method

References