Numeric.Optimization.Algorithms.HagerZhang05.Backprop

This package enhance nonlinear-optimization's usability by using ad's automatic differentiaion. You only need to specify a function to minimize and don't need to specify its gradient explicitly.

Main function

optimize

Arguments

:: (MonoTraversable a, Backprop a, Element a ~ Double)

=> Parameters

How should we optimize.

-> Double

grad_tol, see stopRules.

-> a

Initial guess.

-> (forall s. Reifies s W => BVar s a -> BVar s Double)

Function to be minimized.

-> IO (a, Result, Statistics)

Run the CG_DESCENT optimizer and try to minimize the function.

It uses reverse mode automatic differentiation to compute the gradient.

Result and statistics

data Result

Constructors

ToleranceStatisfied

Convergence tolerance was satisfied.

FunctionChange

Change in function value was less than funcEpsilon * |f|.

MaxTotalIter

Total iterations exceeded maxItersFac * n.

NegativeSlope

Slope was always negative in line search.

MaxSecantIter

Number of secant iterations exceed nsecant.

NotDescent

Search direction not a descent direction.

LineSearchFailsInitial

Line search fails in initial interval.

LineSearchFailsBisection

Line search fails during bisection.

LineSearchFailsUpdate

Line search fails during interval update.

DebugTol

Debug tolerance was on and the test failed (see debugTol).

FunctionValueNaN

Function value became NaN.

StartFunctionValueNaN

Initial function value was NaN.

Instances

Enum Result

Defined in Numeric.Optimization.Algorithms.HagerZhang05

Methods

succ :: Result -> Result

pred :: Result -> Result

toEnum :: Int -> Result

fromEnum :: Result -> Int

enumFrom :: Result -> [Result]

enumFromThen :: Result -> Result -> [Result]

enumFromTo :: Result -> Result -> [Result]

enumFromThenTo :: Result -> Result -> Result -> [Result]

Eq Result

Defined in Numeric.Optimization.Algorithms.HagerZhang05

Methods

(==) :: Result -> Result -> Bool

(/=) :: Result -> Result -> Bool

Ord Result

Defined in Numeric.Optimization.Algorithms.HagerZhang05

Methods

compare :: Result -> Result -> Ordering

(<) :: Result -> Result -> Bool

(<=) :: Result -> Result -> Bool

(>) :: Result -> Result -> Bool

(>=) :: Result -> Result -> Bool

max :: Result -> Result -> Result

min :: Result -> Result -> Result

Read Result

Defined in Numeric.Optimization.Algorithms.HagerZhang05

Methods

readsPrec :: Int -> ReadS Result

readList :: ReadS [Result]

readPrec :: ReadPrec Result

readListPrec :: ReadPrec [Result]

Show Result

Defined in Numeric.Optimization.Algorithms.HagerZhang05

Methods

showsPrec :: Int -> Result -> ShowS

show :: Result -> String

showList :: [Result] -> ShowS

data Statistics

Statistics given after the process finishes.

Constructors

Statistics

Fields

• finalValue :: Double

  Value of the function at the solution.

• gradNorm :: Double

  Maximum absolute component of the gradient at the solution.

• totalIters :: CInt

  Total number of iterations.

• funcEvals :: CInt

  Total number of function evaluations.

• gradEvals :: CInt

  Total number of gradient evaluations.

Instances

Eq Statistics

Defined in Numeric.Optimization.Algorithms.HagerZhang05

Methods

(==) :: Statistics -> Statistics -> Bool

(/=) :: Statistics -> Statistics -> Bool

Ord Statistics

Defined in Numeric.Optimization.Algorithms.HagerZhang05

Methods

compare :: Statistics -> Statistics -> Ordering

(<) :: Statistics -> Statistics -> Bool

(<=) :: Statistics -> Statistics -> Bool

(>) :: Statistics -> Statistics -> Bool

(>=) :: Statistics -> Statistics -> Bool

max :: Statistics -> Statistics -> Statistics

min :: Statistics -> Statistics -> Statistics

Read Statistics

Defined in Numeric.Optimization.Algorithms.HagerZhang05

Methods

readsPrec :: Int -> ReadS Statistics

readList :: ReadS [Statistics]

readPrec :: ReadPrec Statistics

readListPrec :: ReadPrec [Statistics]

Show Statistics

Defined in Numeric.Optimization.Algorithms.HagerZhang05

Methods

showsPrec :: Int -> Statistics -> ShowS

show :: Statistics -> String

showList :: [Statistics] -> ShowS

Storable Statistics

Defined in Numeric.Optimization.Algorithms.HagerZhang05

Methods

sizeOf :: Statistics -> Int

alignment :: Statistics -> Int

peekElemOff :: Ptr Statistics -> Int -> IO Statistics

pokeElemOff :: Ptr Statistics -> Int -> Statistics -> IO ()

peekByteOff :: Ptr b -> Int -> IO Statistics

pokeByteOff :: Ptr b -> Int -> Statistics -> IO ()

peek :: Ptr Statistics -> IO Statistics

poke :: Ptr Statistics -> Statistics -> IO ()

Options

defaultParameters :: Parameters

Default parameters. See the documentation for Parameters and TechParameters to see what are the defaults.

data Parameters

Parameters given to the optimizer.

Constructors

Parameters

Fields

• printFinal :: Bool

  Print final statistics to stdout. Defaults to True.

• printParams :: Bool

  Print parameters to stdout before starting. Defaults to False

• verbose :: Verbose

  How verbose we should be while computing. Everything is printed to stdout. Defaults to Quiet.

• lineSearch :: LineSearch

  What kind of line search should be used. Defaults to AutoSwitch 1e-3.

• qdecay :: Double

  Factor in [0, 1] used to compute average cost magnitude C_k as follows:

  Q_k = 1 + (qdecay)Q_{k-1},   Q_0 = 0
  C_k = C_{k-1} + (|f_k| - C_{k-1})/Q_k

  Defaults to 0.7.

• stopRules :: StopRules

  Stop rules that define when the iterations should end. Defaults to DefaultStopRule 0.

• estimateError :: EstimateError

  How to calculate the estimated error in the function value. Defaults to RelativeEpsilon 1e-6.

• quadraticStep :: Maybe Double

  When to attempt quadratic interpolation in line search. If Nothing then never try a quadratic interpolation step. If Just cutoff, then attemp quadratic interpolation in line search when |f_{k+1} - f_k| / f_k <= cutoff. Defaults to Just 1e-12.

• debugTol :: Maybe Double

  If Just tol, then always check that f_{k+1} - f_k <= tol * C_k. Otherwise, if Nothing then no checking of function values is done. Defaults to Nothing.

• initialStep :: Maybe Double

  If Just step, then use step as the initial step of the line search. Otherwise, if Nothing then the initial step is programatically calculated. Defaults to Nothing.

• maxItersFac :: Double

  Defines the maximum number of iterations. The process is aborted when maxItersFac * n iterations are done, where n is the number of dimensions. Defaults to infinity.

• nexpand :: CInt

  Maximum number of times the bracketing interval grows or shrinks in the line search. Defaults to 50.

• nsecant :: CInt

  Maximum number of secant iterations in line search. Defaults to 50.

• restartFac :: Double

  Restart the conjugate gradient method after restartFac * n iterations. Defaults to 1.

• funcEpsilon :: Double

  Stop when -alpha * dphi0, the estimated change in function value, is less than funcEpsilon * |f|. Defaults to 0.

• nanRho :: Double

  After encountering NaN while calculating the step length, growth factor when searching for a bracketing interval. Defaults to 1.3.

• techParameters :: TechParameters

  Technical parameters which you probably should not touch.

Instances

Eq Parameters

Defined in Numeric.Optimization.Algorithms.HagerZhang05

Methods

(==) :: Parameters -> Parameters -> Bool

(/=) :: Parameters -> Parameters -> Bool

Ord Parameters

Defined in Numeric.Optimization.Algorithms.HagerZhang05

Methods

compare :: Parameters -> Parameters -> Ordering

(<) :: Parameters -> Parameters -> Bool

(<=) :: Parameters -> Parameters -> Bool

(>) :: Parameters -> Parameters -> Bool

(>=) :: Parameters -> Parameters -> Bool

max :: Parameters -> Parameters -> Parameters

min :: Parameters -> Parameters -> Parameters

Read Parameters

Defined in Numeric.Optimization.Algorithms.HagerZhang05

Methods

readsPrec :: Int -> ReadS Parameters

readList :: ReadS [Parameters]

readPrec :: ReadPrec Parameters

readListPrec :: ReadPrec [Parameters]

Show Parameters

Defined in Numeric.Optimization.Algorithms.HagerZhang05

Methods

showsPrec :: Int -> Parameters -> ShowS

show :: Parameters -> String

showList :: [Parameters] -> ShowS

Storable Parameters

Defined in Numeric.Optimization.Algorithms.HagerZhang05

Methods

sizeOf :: Parameters -> Int

alignment :: Parameters -> Int

peekElemOff :: Ptr Parameters -> Int -> IO Parameters

pokeElemOff :: Ptr Parameters -> Int -> Parameters -> IO ()

peekByteOff :: Ptr b -> Int -> IO Parameters

pokeByteOff :: Ptr b -> Int -> Parameters -> IO ()

peek :: Ptr Parameters -> IO Parameters

poke :: Ptr Parameters -> Parameters -> IO ()

data Verbose

How verbose we should be.

Constructors

Quiet

Do not output anything to stdout, which most of the time is good.

Verbose

Print what work is being done on each iteraction.

VeryVerbose

Print information about every step, may be useful for troubleshooting.

Instances

Enum Verbose

Defined in Numeric.Optimization.Algorithms.HagerZhang05

Methods

succ :: Verbose -> Verbose

pred :: Verbose -> Verbose

toEnum :: Int -> Verbose

fromEnum :: Verbose -> Int

enumFrom :: Verbose -> [Verbose]

enumFromThen :: Verbose -> Verbose -> [Verbose]

enumFromTo :: Verbose -> Verbose -> [Verbose]

enumFromThenTo :: Verbose -> Verbose -> Verbose -> [Verbose]

Eq Verbose

Defined in Numeric.Optimization.Algorithms.HagerZhang05

Methods

(==) :: Verbose -> Verbose -> Bool

(/=) :: Verbose -> Verbose -> Bool

Ord Verbose

Defined in Numeric.Optimization.Algorithms.HagerZhang05

Methods

compare :: Verbose -> Verbose -> Ordering

(<) :: Verbose -> Verbose -> Bool

(<=) :: Verbose -> Verbose -> Bool

(>) :: Verbose -> Verbose -> Bool

(>=) :: Verbose -> Verbose -> Bool

max :: Verbose -> Verbose -> Verbose

min :: Verbose -> Verbose -> Verbose

Read Verbose

Defined in Numeric.Optimization.Algorithms.HagerZhang05

Methods

readsPrec :: Int -> ReadS Verbose

readList :: ReadS [Verbose]

readPrec :: ReadPrec Verbose

readListPrec :: ReadPrec [Verbose]

Show Verbose

Defined in Numeric.Optimization.Algorithms.HagerZhang05

Methods

showsPrec :: Int -> Verbose -> ShowS

show :: Verbose -> String

showList :: [Verbose] -> ShowS

data LineSearch

Line search methods that may be used.

Constructors

ApproximateWolfe

Use approximate Wolfe line search.

AutoSwitch Double

Use ordinary Wolfe line search, switch to approximate Wolfe when

|f_{k+1} - f_k| < AWolfeFac * C_k

where C_k is the average size of cost and AWolfeFac is the parameter to this constructor.

Instances

Eq LineSearch

Defined in Numeric.Optimization.Algorithms.HagerZhang05

Methods

(==) :: LineSearch -> LineSearch -> Bool

(/=) :: LineSearch -> LineSearch -> Bool

Ord LineSearch

Defined in Numeric.Optimization.Algorithms.HagerZhang05

Methods

compare :: LineSearch -> LineSearch -> Ordering

(<) :: LineSearch -> LineSearch -> Bool

(<=) :: LineSearch -> LineSearch -> Bool

(>) :: LineSearch -> LineSearch -> Bool

(>=) :: LineSearch -> LineSearch -> Bool

max :: LineSearch -> LineSearch -> LineSearch

min :: LineSearch -> LineSearch -> LineSearch

Read LineSearch

Defined in Numeric.Optimization.Algorithms.HagerZhang05

Methods

readsPrec :: Int -> ReadS LineSearch

readList :: ReadS [LineSearch]

readPrec :: ReadPrec LineSearch

readListPrec :: ReadPrec [LineSearch]

Show LineSearch

Defined in Numeric.Optimization.Algorithms.HagerZhang05

Methods

showsPrec :: Int -> LineSearch -> ShowS

show :: LineSearch -> String

showList :: [LineSearch] -> ShowS

data StopRules

Stop rules used to decided when to stop iterating.

Constructors

DefaultStopRule Double

DefaultStopRule stop_fac stops when

|g_k|_infty <= max(grad_tol, |g_0|_infty * stop_fac)

where |g_i|_infty is the maximum absolute component of the gradient at the i-th step.

AlternativeStopRule

AlternativeStopRule stops when

|g_k|_infty <= grad_tol * (1 + |f_k|)

Instances

Eq StopRules

Defined in Numeric.Optimization.Algorithms.HagerZhang05

Methods

(==) :: StopRules -> StopRules -> Bool

(/=) :: StopRules -> StopRules -> Bool

Ord StopRules

Defined in Numeric.Optimization.Algorithms.HagerZhang05

Methods

compare :: StopRules -> StopRules -> Ordering

(<) :: StopRules -> StopRules -> Bool

(<=) :: StopRules -> StopRules -> Bool

(>) :: StopRules -> StopRules -> Bool

(>=) :: StopRules -> StopRules -> Bool

max :: StopRules -> StopRules -> StopRules

min :: StopRules -> StopRules -> StopRules

Read StopRules

Defined in Numeric.Optimization.Algorithms.HagerZhang05

Methods

readsPrec :: Int -> ReadS StopRules

readList :: ReadS [StopRules]

readPrec :: ReadPrec StopRules

readListPrec :: ReadPrec [StopRules]

Show StopRules

Defined in Numeric.Optimization.Algorithms.HagerZhang05

Methods

showsPrec :: Int -> StopRules -> ShowS

show :: StopRules -> String

showList :: [StopRules] -> ShowS

data EstimateError

How to calculate the estimated error in the function value.

Constructors

AbsoluteEpsilon Double

AbsoluteEpsilon eps estimates the error as eps.

RelativeEpsilon Double

RelativeEpsilon eps estimates the error as eps * C_k.

Instances

Eq EstimateError

Defined in Numeric.Optimization.Algorithms.HagerZhang05

Methods

(==) :: EstimateError -> EstimateError -> Bool

(/=) :: EstimateError -> EstimateError -> Bool

Ord EstimateError

Defined in Numeric.Optimization.Algorithms.HagerZhang05

Methods

compare :: EstimateError -> EstimateError -> Ordering

(<) :: EstimateError -> EstimateError -> Bool

(<=) :: EstimateError -> EstimateError -> Bool

(>) :: EstimateError -> EstimateError -> Bool

(>=) :: EstimateError -> EstimateError -> Bool

max :: EstimateError -> EstimateError -> EstimateError

min :: EstimateError -> EstimateError -> EstimateError

Read EstimateError

Defined in Numeric.Optimization.Algorithms.HagerZhang05

Methods

readsPrec :: Int -> ReadS EstimateError

readList :: ReadS [EstimateError]

readPrec :: ReadPrec EstimateError

readListPrec :: ReadPrec [EstimateError]

Show EstimateError

Defined in Numeric.Optimization.Algorithms.HagerZhang05

Methods

showsPrec :: Int -> EstimateError -> ShowS

show :: EstimateError -> String

showList :: [EstimateError] -> ShowS

Technical parameters

data TechParameters

Technical parameters which you probably should not touch. You should read the papers of CG_DESCENT to understand how you can tune these parameters.

Constructors

TechParameters

Fields

• techDelta :: Double

  Wolfe line search parameter. Defaults to 0.1.

• techSigma :: Double

  Wolfe line search parameter. Defaults to 0.9.

• techGamma :: Double

  Decay factor for bracket interval width. Defaults to 0.66.

• techRho :: Double

  Growth factor when searching for initial bracketing interval. Defaults to 5.

• techEta :: Double

  Lower bound for the conjugate gradient update parameter beta_k is techEta * ||d||_2. Defaults to 0.01.

• techPsi0 :: Double

  Factor used in starting guess for iteration 1. Defaults to 0.01.

• techPsi1 :: Double

  In performing a QuadStep, we evaluate the function at psi1 * previous step. Defaults to 0.1.

• techPsi2 :: Double

  When starting a new CG iteration, our initial guess for the line search stepsize is psi2 * previous step. Defaults to 2.

Instances

Eq TechParameters

Defined in Numeric.Optimization.Algorithms.HagerZhang05

Methods

(==) :: TechParameters -> TechParameters -> Bool

(/=) :: TechParameters -> TechParameters -> Bool

Ord TechParameters

Defined in Numeric.Optimization.Algorithms.HagerZhang05

Methods

compare :: TechParameters -> TechParameters -> Ordering

(<) :: TechParameters -> TechParameters -> Bool

(<=) :: TechParameters -> TechParameters -> Bool

(>) :: TechParameters -> TechParameters -> Bool

(>=) :: TechParameters -> TechParameters -> Bool

max :: TechParameters -> TechParameters -> TechParameters

min :: TechParameters -> TechParameters -> TechParameters

Read TechParameters

Defined in Numeric.Optimization.Algorithms.HagerZhang05

Methods

readsPrec :: Int -> ReadS TechParameters

readList :: ReadS [TechParameters]

readPrec :: ReadPrec TechParameters

readListPrec :: ReadPrec [TechParameters]

Show TechParameters

Defined in Numeric.Optimization.Algorithms.HagerZhang05

Methods

showsPrec :: Int -> TechParameters -> ShowS

show :: TechParameters -> String

showList :: [TechParameters] -> ShowS

Re-export

module Numeric.Backprop