Line search

In (unconstrained) optimization, the linesearch 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.

Algorithm

i) Set iteration counter

k=0

, and make an initial guess,

\mathbf {x} _{0}

for the minimum.

ii) Compute a descent direction

\mathbf {p} _{k}

.

iii) Choose

\alpha _{k}

to 'loosely' minimize

\phi (\alpha )=f(\mathbf {x} _{k}+\alpha \mathbf {p} _{k})

over

\alpha \in \mathbb {R}

.

iv) Update

\mathbf {x} _{k+1}=\mathbf {x} _{k}+\alpha _{k}\mathbf {p} _{k}

,

k=k+1

.

If

\|\nabla f(\mathbf {x} _{k})\|\leq

tolerance, STOP.

Else, goto ii).

In step iii) we can either exactly minimize $\phi$ , by solving $\phi '(\alpha _{k})=0$ , or loosely, by asking for a sufficient decrease in $\phi$ . The latter may be performed in a number of ways, perhaps by doing a backtracking linesearch 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.

References

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.