Optimization.LineSearch

Line search algorithms are a class of iterative optimization methods. These methods are distinguished by the characteristic of, starting from a point x0, choosing a direction d (by some method) to advance and then finding an optimal distance a (known as the step-size) to advance in this direction.

Here we provide several methods for determining this optimal distance. These can be used with any of line-search optimization algorithms found in this namespace.

Line search methods

type LineSearch f a = (f a -> f a) -> f a -> f a -> a

A LineSearch method 'search df p x' determines a step size in direction p from point x for function f with gradient df

backtrackingSearch :: (Num a, Ord a, Metric f) => a -> a -> (a -> Bool) -> LineSearch f a

Backtracking line search algorithm

backtrackingSearch gamma alpha pred starts with the given step size alpha and reduces it by a factor of gamma until the given condition is satisfied.

armijoSearch :: (Num a, Ord a, Metric f) => a -> a -> a -> (f a -> a) -> LineSearch f a

Armijo backtracking line search algorithm

armijoSearch gamma alpha c1 starts with the given step size alpha and reduces it by a factor of gamma until the Armijo condition is satisfied.

wolfeSearch :: (Num a, Ord a, Metric f) => a -> a -> a -> a -> (f a -> a) -> LineSearch f a

Wolfe backtracking line search algorithm

wolfeSearch gamma alpha c1 starts with the given step size alpha and reduces it by a factor of gamma until both the Armijo and curvature conditions is satisfied.

newtonSearch :: Num a => LineSearch f a

Line search by Newton's method

secantSearch :: (Num a, Fractional a) => a -> LineSearch f a

Line search by secant method with given tolerance

constantSearch :: a -> LineSearch f a

Constant line search

constantSearch c always chooses a step-size c.