-- Hoogle documentation, generated by Haddock -- See Hoogle, http://www.haskell.org/hoogle/ -- | Numerical optimization -- -- These are a set of implementations of various numerical optimization -- methods in Haskell. Note that these implementations were originally -- written as part of a class project; while at one point they worked no -- attention has been given to numerical stability or the many other -- potential difficulties of implementing robust numerical methods. That -- being said, they should serve to succinctly illustrate a number of -- optimization techniques from the modern optimization literature. -- -- Those seeking a high-level overview of some of these methods are -- referred to Stephen Wright's excellent tutorial from NIPS 2010 -- http://videolectures.net/nips2010_wright_oaml/. A deeper -- introduction can be found in Boyd and Vandenberghe's /Convex -- Optimization/ which available freely online, -- http://web.stanford.edu/~boyd/cvxbook/. Vandenberghe's lecture -- at the 2009 Machine Learning Summer School may also be of interest -- http://videolectures.net/mlss09uk_vandenberghe_co/. @package optimization @version 0.1.9 module Optimization.Constrained.Penalty -- | Opt d f gs hs is a Lagrangian optimization problem with -- objective f equality (g(x) == 0) constraints -- gs and less-than (h(x) < 0) constraints -- hs data Opt f a newtype FU f a FU :: (forall s. Mode s => f (AD s a) -> AD s a) -> FU f a [runFU] :: FU f a -> forall s. Mode s => f (AD s a) -> AD s a optimize :: (forall s. Mode s => f (AD s a) -> AD s a) -> Opt f a constrainEQ :: (forall s. Mode s => f (AD s a) -> AD s a) -> Opt f a -> Opt f a constrainLT :: (forall s. Mode s => f (AD s a) -> AD s a) -> Opt f a -> Opt f a constrainGT :: (Num a) => (forall s. Mode s => f (AD s a) -> AD s a) -> Opt f a -> Opt f a -- | Minimize the given constrained optimization problem This is a basic -- penalty method approach minimize :: (Functor f, RealFrac a, Ord a, g ~ V) => (FU f a -> f a -> [f a]) -> Opt f a -> a -> f a -> g a -> [f a] -- | Maximize the given constrained optimization problem maximize :: (Functor f, RealFrac a, Ord a, g ~ V) => (FU f a -> f a -> [f a]) -> Opt f a -> a -> f a -> g a -> [f a] -- | The Lagrangian for the given constrained optimization lagrangian :: (Num a) => Opt f a -> (forall s. Mode s => f (AD s a) -> V (AD s a) -> AD s a) module Optimization.Constrained.ProjectedSubgradient -- | projSubgrad stepSizes proj a b x0 minimizes the objective -- A x - b potentially projecting iterates into a feasible space -- with proj with the given step-size schedule projSubgrad :: (Additive f, Traversable f, Metric f, Ord a, Fractional a) => StepSched f a -> (f a -> f a) -> (f a -> f a) -> (f a -> a) -> f a -> [f a] -- | linearProjSubgrad stepSizes proj a b x0 minimizes the -- objective A x - b potentially projecting iterates into a -- feasible space with proj with the given step-size schedule linearProjSubgrad :: (Additive f, Traversable f, Metric f, Ord a, Fractional a) => StepSched f a -> (f a -> f a) -> f a -> a -> f a -> [f a] -- | A step size schedule A list of functions (one per step) which, given a -- function's gradient and value, will provide a size for the next step type StepSched f a = [f a -> a -> a] -- | The optimal step size schedule when the optimal value of the objective -- is known optimalStepSched :: (Fractional a, Metric f) => a -> StepSched f a -- | Constant step size schedule constStepSched :: a -> StepSched f a -- | A non-summable step size schedule sqrtKStepSched :: Floating a => a -> StepSched f a -- | A square-summable step size schedule invKStepSched :: Fractional a => a -> StepSched f a -- | A linear constraint. For instance, Constr LT 2 (V2 1 3) -- defines the constraint x_1 + 3 x_2 <= 2 data Constraint f a Constr :: Ordering -> a -> (f a) -> Constraint f a -- | Project onto a the space of feasible solutions defined by a set of -- linear constraints linearProjection :: (Fractional a, Ord a, RealFloat a, Metric f) => [Constraint f a] -> f a -> f a instance (GHC.Show.Show (f a), GHC.Show.Show a) => GHC.Show.Show (Optimization.Constrained.ProjectedSubgradient.Constraint f a) -- | 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. module Optimization.LineSearch -- | 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) gradient of function -> f a search direction -> f a starting point -> a step size -- | 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 -- | Constant line search -- -- constantSearch c always chooses a step-size c. constantSearch :: a -> 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. armijoSearch :: (Num a, Ord a, Metric f) => a -> a -> a -> (f a -> a) -> 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. wolfeSearch :: (Num a, Ord a, Metric f) => a -> a -> a -> a -> (f a -> a) -> LineSearch f a module Optimization.LineSearch.BFGS -- | Broyden–Fletcher–Goldfarb–Shanno (BFGS) method bfgs search df b0 -- x0 where b0 is the inverse Hessian (the identity is -- often a good initial value). bfgs :: (Metric f, Additive 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] module Optimization.LineSearch.BarzilaiBorwein -- | 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] module Optimization.LineSearch.ConjugateGradient -- | Conjugate gradient method with given beta and line search method -- -- The conjugate gradient method avoids the trouble encountered by the -- steepest descent method on poorly conditioned problems (e.g. those -- with a wide range of eigenvalues). It does this by choosing directions -- which satisfy a condition of A orthogonality, ensuring that -- steps in the "unstretched" search space are orthogonal. conjGrad :: (Num a, RealFloat a, Additive f, Metric f) => LineSearch f a -> Beta f a -> (f a -> f a) -> f a -> [f a] -- | A beta expression beta df0 df1 p is an expression for the -- conjugate direction contribution given the derivative df0 and -- direction p for iteration k, df1 for -- iteration k+1 type Beta f a = f a -> f a -> f a -> a -- | Fletcher-Reeves expression for beta fletcherReeves :: (Num a, RealFloat a, Metric f) => Beta f a -- | Polak-Ribiere expression for beta polakRibiere :: (Num a, RealFloat a, Metric f) => Beta f a -- | Hestenes-Stiefel expression for beta hestenesStiefel :: (Num a, RealFloat a, Metric f) => Beta f a module Optimization.LineSearch.MirrorDescent -- | Mirror descent method. -- -- Originally described by Nemirovsky and Yudin and later elucidated by -- Beck and Teboulle, the mirror descent method is a generalization of -- the projected subgradient method for convex optimization. Mirror -- descent requires the gradient of a strongly 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] module Optimization.LineSearch.SteepestDescent -- | Steepest descent method -- -- steepestDescent search f df x0 optimizes a function -- f with gradient df with step size schedule -- search starting from initial point x0 -- -- The steepest descent method chooses the negative gradient of the -- function as its step direction. steepestDescent :: (Num a, Ord a, Additive f, Metric f) => LineSearch f a -> (f a -> f a) -> f a -> [f a] module Optimization.TrustRegion.Fista -- | Fast Iterative Shrinkage-Thresholding Algorithm (FISTA) with constant -- step size fista :: (Additive f, Fractional a, Floating a) => a -> (f a -> f a) -> f a -> [f a] module Optimization.TrustRegion.Nesterov1983 -- | Nesterov 1983 optimalGradient kappa l df alpha0 x0 is -- Nesterov's optimal gradient method, first described in 1983. This -- method requires 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] module Optimization.TrustRegion.Newton -- | 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] -- | 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 value of A bicInv :: (Functor m, Distributive m, Additive m, Applicative m, Apply m, Foldable m, Conjugate a) => a -> m (m a) -> [m (m a)] -- | Inverse by iterative method of Ben-Israel and Cohen with given -- starting condition bicInv' :: (Functor m, Distributive m, Additive m, Applicative m, Apply m, Foldable m, Conjugate a) => m (m a) -> m (m a) -> [m (m a)]