Portability | portable |
---|---|
Stability | provisional |
Maintainer | Ben Gamari <bgamari@gmail.com> |
Safe Haskell | Safe-Inferred |
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.
- type LineSearch f a = (f a -> f a) -> f a -> f a -> a
- backtrackingSearch :: (Num a, Ord a, Metric f) => a -> a -> (a -> Bool) -> LineSearch f a
- armijoSearch :: (Num a, Ord a, Metric f) => a -> a -> a -> (f a -> a) -> LineSearch f a
- wolfeSearch :: (Num a, Ord a, Metric f) => a -> a -> a -> a -> (f a -> a) -> LineSearch f a
- newtonSearch :: Num a => LineSearch f a
- secantSearch :: (Num a, Fractional a) => a -> LineSearch f a
- constantSearch :: a -> LineSearch f a
Line search methods
type LineSearch f a = (f a -> f a) -> f a -> f a -> aSource
A line search 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 aSource
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 aSource
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 aSource
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 aSource
Line search by Newton's method
secantSearch :: (Num a, Fractional a) => a -> LineSearch f aSource
Line search by secant method with given tolerance
constantSearch :: a -> LineSearch f aSource
Constant line search
constantSearch c
always chooses a step-size c
.