packages feed

optimization 0.1.1 → 0.1.2

raw patch · 10 files changed

+123/−41 lines, 10 files

Files

optimization.cabal view
@@ -1,6 +1,6 @@ name:          optimization category:      Math-version:       0.1.1+version:       0.1.2 license:       BSD3 cabal-version: >= 1.10 license-file:  LICENSE
src/Optimization/LineSearch.hs view
@@ -6,25 +6,32 @@ -- Stability   : provisional -- Portability : portable --+-- 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 are distinguished by the characteristic of,--- starting from a point @x0@, choosing a direction @d@ (by some method)--- to advance and then finding an optimal distance @a@ (known as the--- step-size) to advance in this direction.+-- 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. ----- Here we provide several methods for determining this optimal--- distance. These can be used with any of line-search optimization--- algorithms found in this namespace.  module Optimization.LineSearch     ( -- * Line search methods       LineSearch     , backtrackingSearch+      -- * Other line search methods+    , constantSearch+    --, newtonSearch+    --, secantSearch+      -- * Wolfe conditions+      -- Nocedal gives typical values of 10^-4 for @c1@ and 0.9 for+      -- @c2@     , armijoSearch     , wolfeSearch-    , newtonSearch-    , secantSearch-    , constantSearch     ) where  import Prelude hiding (pred)@@ -32,7 +39,10 @@  -- | A line search method @search df p x@ determines a step size -- in direction @p@ from point @x@ for function @f@ with gradient @df@-type LineSearch f a = (f a -> f a) -> f a -> f a -> a+type LineSearch f a = (f a -> f a)    -- ^ gradient of function+                   -> f a             -- ^ search direction+                   -> f a             -- ^ starting point+                   -> a               -- ^ step size  -- | Armijo condition --@@ -41,23 +51,40 @@ -- as predicted by its gradient. This often finds its place as a criterion -- for line-search armijo :: (Num a, Additive f, Ord a, Metric f)-       => a -> (f a -> a) -> (f a -> f a) -> f a -> f a -> a -> Bool+       => a            -- ^ Armijo condition strength+       -> (f a -> a)   -- ^ function value+       -> (f a -> f a) -- ^ gradient of function+       -> f a          -- ^ point to evaulate at+       -> f a          -- ^ search direction+       -> a            -- ^ search step size+       -> Bool         -- ^ is Armijo condition satisfied? armijo c1 f df x p a =     f (x ^+^ a *^ p) <= f x + c1 * a * (df x `dot` p)  -- | Curvature condition curvature :: (Num a, Ord a, Additive f, Metric f)-          => a -> (f a -> f a) -> f a -> f a -> a -> Bool+          => a             -- ^ curvature condition strength c2+          -> (f a -> f a)  -- ^ gradient of function+          -> f a           -- ^ point to evaluate at+          -> f a           -- ^ search direction+          -> a             -- ^ search step size+          -> Bool          -- ^ is curvature condition satisfied curvature c2 df x p a =     df (x ^+^ a *^ p) `dot` p >= c2 * (df x `dot` p)  -- | 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. backtrackingSearch :: (Num a, Ord a, Metric f)-                   => a -> a -> (a -> Bool) -> LineSearch f a+                   => a            -- ^ step size reduction factor gamma+                   -> a            -- ^ initial step size alpha+                   -> (a -> Bool)  -- ^ search condition+                   -> LineSearch f a backtrackingSearch gamma alpha pred _ _ _ =     head $ dropWhile (not . pred) $ nonzero $ iterate (*gamma) alpha   where nonzero (x:xs) | not $ x > 0 = error "Backtracking search failed: alpha=0" -- FIXME@@ -71,18 +98,28 @@ -- and reduces it by a factor of @gamma@ until the Armijo condition -- is satisfied. armijoSearch :: (Num a, Ord a, Metric f)-             => a -> a -> a -> (f a -> a) -> LineSearch f a+             => a                   -- ^ step size reduction factor gamma+             -> a                   -- ^ initial step size alpha+             -> a                   -- ^ Armijo condition strength c1+             -> (f a -> a)          -- ^ function value+             -> LineSearch f a armijoSearch gamma alpha c1 f df p x =     backtrackingSearch gamma alpha (armijo c1 f df x p) df p x {-# INLINEABLE armijoSearch #-} --- | Wolfe backtracking line search algorithm+-- | 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. wolfeSearch :: (Num a, Ord a, Metric f)-             => a -> a -> a -> a -> (f a -> a) -> LineSearch f a+             => 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 wolfeSearch gamma alpha c1 c2 f df p x =     backtrackingSearch gamma alpha wolfe df p x   where wolfe a = armijo c1 f df p x a && curvature c2 df x p a@@ -91,14 +128,17 @@ -- | Line search by Newton's method newtonSearch :: (Num a) => LineSearch f a newtonSearch = undefined+{-# INLINEABLE newtonSearch #-}  -- | Line search by secant method with given tolerance secantSearch :: (Num a, Fractional a) => a -> LineSearch f a secantSearch = undefined+{-# INLINEABLE secantSearch #-}  -- | Constant line search -- -- @constantSearch c@ always chooses a step-size @c@.-constantSearch :: a -> LineSearch f a+constantSearch :: a                 -- ^ step size+               -> LineSearch f a constantSearch c _ _ _ = c {-# INLINEABLE constantSearch #-}
src/Optimization/LineSearch/BFGS.hs view
@@ -1,6 +1,11 @@ {-# LANGUAGE ScopedTypeVariables #-} -module Optimization.LineSearch.BFGS (bfgs) where+module Optimization.LineSearch.BFGS+    ( -- * Broyden-Fletcher-Goldfarb-Shanna (BFGS) method+      bfgs+      -- * Step size methods+    , module Optimization.LineSearch+    ) where  import Linear import Optimization.LineSearch@@ -14,7 +19,11 @@ -- identity is often a good initial value). bfgs :: ( Metric f, Additive f, Distributive f, Foldable f, Traversable f, Applicative f         , Fractional a, Epsilon a)-     => LineSearch f a -> (f a -> f a) -> f (f a) -> f a -> [f a]+     => LineSearch f a   -- ^ line search method+     -> (f a -> f a)     -- ^ gradient of function+     -> f (f a)          -- ^ inverse Hessian at starting point+     -> f a              -- ^ starting point+     -> [f a]            -- ^ iterates bfgs search df = go     where go b0 x0 = let p1 = negated $ b0 !* df x0                          alpha = search df p1 x0
src/Optimization/LineSearch/BarzilaiBorwein.hs view
@@ -1,12 +1,19 @@ module Optimization.LineSearch.BarzilaiBorwein-    ( barzilaiBorwein+    ( -- * Barizilai-Borwein method+      barzilaiBorwein+      -- * Step size methods+    , module Optimization.LineSearch     ) where  import Linear+import Optimization.LineSearch  -- | Barzilai-Borwein 1988 is a non-monotonic optimization method barzilaiBorwein :: (Additive f, Metric f, Functor f, Fractional a, Epsilon a)-                => (f a -> f a) -> f a -> f a -> [f a]+                => (f a -> f a)  -- ^ gradient of function+                -> f a           -- ^ starting point, @x0@+                -> f a           -- ^ second starting point, @x1@+                -> [f a]         -- ^ iterates barzilaiBorwein df = go   where go x0 x1 = let s = x1 ^-^ x0                        z = df x1 ^-^ df x0
src/Optimization/LineSearch/ConjugateGradient.hs view
@@ -1,7 +1,7 @@ module Optimization.LineSearch.ConjugateGradient     ( -- * Conjugate gradient methods       conjGrad-      -- * General line search+      -- * Step size methods     , module Optimization.LineSearch       -- * Beta expressions     , Beta@@ -26,29 +26,32 @@ -- satisfy a condition of @A@ orthogonality, ensuring that steps in the -- "unstretched" search space are orthogonal. -- TODO: clarify explanation-{-# INLINEABLE conjGrad #-} conjGrad :: (Num a, RealFloat a, Additive f, Metric f)-         => LineSearch f a -> Beta f a-         -> (f a -> f a) -> f a -> [f a]+         => LineSearch f a  -- ^ line search method+         -> Beta f a        -- ^ beta expression+         -> (f a -> f a)    -- ^ gradient of function+         -> f a             -- ^ starting point+         -> [f a]           -- ^ iterates conjGrad search beta df x0 = go (negated $ df x0) x0   where go p x = let a = search df p x                      x' = x ^+^ a *^ p                      b = beta (df x) (df x') p                      p' = negated (df x') ^+^ b *^ p                  in x' : go p' x'+{-# INLINEABLE conjGrad #-}  -- | Fletcher-Reeves expression for beta-{-# INLINEABLE fletcherReeves #-} fletcherReeves :: (Num a, RealFloat a, Metric f) => Beta f a fletcherReeves df0 df1 _ = norm df1 / norm df0+{-# INLINEABLE fletcherReeves #-}  -- | Polak-Ribiere expression for beta-{-# INLINEABLE polakRibiere #-} polakRibiere :: (Num a, RealFloat a, Metric f) => Beta f a polakRibiere df0 df1 _ = df1 `dot` (df1 ^-^ df0) / norm df0+{-# INLINEABLE polakRibiere #-}  -- | Hestenes-Stiefel expression for beta-{-# INLINEABLE hestenesStiefel #-} hestenesStiefel :: (Num a, RealFloat a, Metric f) => Beta f a hestenesStiefel df0 df1 p0 =     - (df1 `dot` (df1 ^-^ df0)) / (p0 `dot` (df1 ^-^ df0))+{-# INLINEABLE hestenesStiefel #-}
src/Optimization/LineSearch/MirrorDescent.hs view
@@ -1,5 +1,8 @@ module Optimization.LineSearch.MirrorDescent-    ( mirrorDescent ) where+    ( mirrorDescent+      -- * Step size methods+    , module Optimization.LineSearch+    ) where  import Optimization.LineSearch import Linear@@ -13,8 +16,12 @@ -- convex function @psi@ (and its dual) as well as a way to get a -- subgradient for each point of the objective function @f@. mirrorDescent :: (Num a, Additive f)-              => LineSearch f a -> (f a -> f a) -> (f a -> f a)-              -> (f a -> f a) -> f a -> [f a]+              => LineSearch f a  -- ^ line search method+              -> (f a -> f a)    -- ^ strongly convex function, @psi@+              -> (f a -> f a)    -- ^ dual of @psi@+              -> (f a -> f a)    -- ^ gradient of function+              -> f a             -- ^ starting point+              -> [f a]           -- ^ iterates mirrorDescent search dPsi dPsiStar df = go   where go y0 = let x0 = dPsiStar y0                     t0 = search df (df x0) x0
src/Optimization/LineSearch/SteepestDescent.hs view
@@ -1,6 +1,8 @@ module Optimization.LineSearch.SteepestDescent     ( -- * Steepest descent method       steepestDescent+      -- * Step size methods+    , module Optimization.LineSearch     ) where  import Optimization.LineSearch@@ -13,10 +15,13 @@ -- -- The steepest descent method chooses the negative gradient of the function -- as its step direction.-{-# INLINEABLE steepestDescent #-} steepestDescent :: (Num a, Ord a, Additive f, Metric f)-                => LineSearch f a -> (f a -> f a) -> f a -> [f a]+                => LineSearch f a    -- ^ line search method+                -> (f a -> f a)      -- ^ gradient of function+                -> f a               -- ^ starting point+                -> [f a]             -- ^ iterates steepestDescent search df x0 = iterate go x0   where go x = let p = negated (df x)                    a = search df p x                in x ^+^ a *^ p+{-# INLINEABLE steepestDescent #-}
src/Optimization/TrustRegion/Fista.hs view
@@ -6,12 +6,15 @@ import Linear  -- | Fast Iterative Shrinkage-Thresholding Algorithm (FISTA) with--- constant stepsize-{-# INLINEABLE fista #-}+-- constant step size fista :: (Additive f, Fractional a, Floating a)-      => a -> (f a -> f a) -> f a -> [f a]+      => a             -- ^ Lipschitz constant, @l@+      -> (f a -> f a)  -- ^ gradient of function+      -> f a           -- ^ starting point+      -> [f a]         -- ^ iterates fista l df x0' = go x0' x0' 1   where go x0 y1 t1 = let x1 = y1 ^-^ df y1 ^/ l                           t2 = (1 + sqrt (1 + 4 * t1^2)) / 2                           y2 = x1 ^+^ (t1-1) / t2 *^ (x1 ^-^ x0)                       in x1 : go x1 y2 t2+{-# INLINEABLE fista #-}
src/Optimization/TrustRegion/Nesterov1983.hs view
@@ -11,7 +11,12 @@ -- knowledge of the Lipschitz constant @l@ of the gradient, the condition -- number @kappa@, as well as an initial step size @alpha0@ in @(0,1)@. optimalGradient :: (Additive f, Functor f, Ord a, Floating a, Epsilon a)-                => a -> a -> (f a -> f a) -> a -> f a -> [f a]+                => a               -- ^ condition number, @kappa@+                -> a               -- ^ Lipschitz constant, @l@+                -> (f a -> f a)    -- ^ gradient of function+                -> a               -- ^ initial step size, @alpha0@+                -> f a             -- ^ starting point+                -> [f a]           -- ^ iterates optimalGradient kappa l df a0' x0' = go a0' x0' x0'   where go a0 x0 y0 = let x1 = y0 ^-^ df y0 ^/ l                           alphas = quadratic 1 (a0^2 - 1/kappa) (-a0^2)
src/Optimization/TrustRegion/Newton.hs view
@@ -14,7 +14,10 @@  -- | Newton's method newton :: (Num a, Ord a, Additive f, Metric f, Foldable f)-       => (f a -> f a) -> (f a -> f (f a)) -> f a -> [f a]+       => (f a -> f a)         -- ^ gradient of function+       -> (f a -> f (f a))     -- ^ inverse Hessian+       -> f a                  -- ^ starting point+       -> [f a]                -- ^ iterates newton df ddfInv x0 = iterate go x0   where go x = x ^-^ ddfInv x !* df x {-# INLINEABLE newton #-}@@ -30,7 +33,7 @@  -- | Inverse by iterative method of Ben-Israel and Cohen -- starting from @alpha A^T@. Alpha should be set such that--- 0 < alpha < 2/sigma^2 where sigma denotes the largest singular+-- 0 < alpha < 2/sigma^2 where @sigma@ denotes the largest singular -- value of A bicInv :: (Functor m, Distributive m, Additive m,            Applicative m, Apply m, Foldable m, Conjugate a)