Portability | portable |
---|---|

Stability | provisional |

Maintainer | Ben Gamari <bgamari@gmail.com> |

Safe Haskell | Safe-Inferred |

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 aSource

= (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`

:: (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

:: a | step size |

-> LineSearch f a |

Constant line search

`constantSearch c`

always chooses a step-size `c`

.

# Wolfe conditions

:: (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.

:: (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.