Optimization.LineSearch

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.

Line search methods

type LineSearch f a

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

backtrackingSearch

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

constantSearch

Arguments

:: a

step size

-> LineSearch f a

Constant line search

constantSearch c always chooses a step-size c.

Wolfe conditions

armijoSearch

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.

wolfeSearch

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.