optimization-0.1.3: Numerical optimization

Portability portable provisional Ben Gamari Safe-Inferred

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.

Synopsis

Line search methods

type LineSearch f aSource

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.