| Copyright | (c) 2012-2013 Ben Gamari |
|---|---|
| License | BSD-style (see the file LICENSE) |
| Maintainer | Ben Gamari <bgamari@gmail.com> |
| Stability | provisional |
| Portability | portable |
| Safe Haskell | None |
| Language | Haskell2010 |
Optimization.LineSearch
Description
This module provides various methods for choosing step sizes for
line search optimization methods. These methods can be used with
any of line-search algorithms in the Optimization.LineSearch
namespace. This module is re-exported from these modules
so there should be no need to import it directly.
Line search algorithms are a class of iterative optimization
methods. These methods start at an initial point x0 and then choose
a direction p (by some method) to advance in. The algorithm then
uses one of the methods in this module to identify an optimal distance
a (known as the step-size) by which to advance.
- 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
- constantSearch :: a -> 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
Line search methods
type LineSearch f a Source #
Arguments
| = (f a -> f a) | gradient of function |
| -> f a | search direction |
| -> f a | starting point |
| -> a | step size |
A line search method search df p x determines a step size
in direction p from point x for function f with gradient df
Arguments
| :: (Num a, Ord a, Metric f) | |
| => a | step size reduction factor gamma |
| -> a | initial step size alpha |
| -> (a -> Bool) | search condition |
| -> LineSearch f a |
Backtracking line search algorithm
This is a building block for line search algorithms which reduces its step size until the given condition is satisfied.
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.
Other line search methods
Arguments
| :: a | step size |
| -> LineSearch f a |
Constant line search
constantSearch c always chooses a step-size c.
Wolfe conditions
Arguments
| :: (Num a, Ord a, Metric f) | |
| => a | step size reduction factor gamma |
| -> a | initial step size alpha |
| -> a | Armijo condition strength c1 |
| -> (f a -> a) | function value |
| -> 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.
Arguments
| :: (Num a, Ord a, Metric f) | |
| => a | step size reduction factor gamma |
| -> a | initial step size alpha |
| -> a | Armijo condition strength c1 |
| -> a | curvature condition strength c2 |
| -> (f a -> a) | function value |
| -> LineSearch f a |
Wolfe backtracking line search algorithm (satisfies both Armijo and curvature conditions)
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.