Libraries for sequential non-linear optimization in haskel?

Question

Are there any libraries for sequential non-linear optimization with upper and lower bounds, as well as inequality constraints, that are written in or easily callable from Haskell?

Travertine

Answer 1

The bindings-levmar package provides bindings to a C Levenberg-Marquardt optimizer.

Monteith

Answer 2

A quick grep of Hackage suggests that nonlinear-optimization is the best (only) already-written thing; however, it doesn't seem to include anything for bounded optimization.

Your best bet seems to be one of these (in order of increasing attractiveness):

1. Start your own project.
2. Extend the above package.
3. Find a decent C library and learn enough FFI to bind to it.

Plaintiff

Answer 3

I know the OP asked for a general optimization library, where my experience is:

• The levmar package depends on the blas and lapack libraries and that makes things very complicated to install, I didn't manage to install it such that ghci is still working on Windows.
• The nonlinear-optimization package requires a gradient function
• The optimization package seems also to require gradients, though I couldn't figure out how to actually use it.

Besides, all of the mentioned packages do not seem to have any real documentation.

Fortunately, for simple problems a simple solution can be enough. If you want to optimize a one-dimensional, smooth and convex function which has a single bracketed extremum but you do not know a gradient function (see below if you do¹) then a simple method like Golden Section Search will do.

Translated from the Wikipedia page:

import Data.Maybe (fromMaybe)

-- 1 / phi
invphi = (sqrt 5 - 1) / 2
-- 1 / phi^2
invphi2 = (3 - sqrt 5) / 2

-- | Enable optional arguments syntax. Use with Maybe a as parameter type, then in the function write param // defaultValue
(//) :: Maybe a -> a -> a
(//) = flip fromMaybe

-- Just a wrapper function because of all the ugly Nothing's of the recursive function
goldenSectionSearch f a b tolerance = goldenSectionSearchRecursive f a b tolerance Nothing Nothing Nothing Nothing Nothing

-- | Golden section search, recursive.
-- Given a function f with a single local maximum in the interval [a, b], golden section search returns a subset interval [c, d] that contains the maximum with d-c <= tolerance
-- Taken from the python implementation at https://en.wikipedia.org/wiki/Golden-section_search
goldenSectionSearchRecursive ::
    (Double -> Double) -- ^ Function with a single maximum in [a, b]
    -> Double -- ^ One side of the interval
    -> Double -- ^ Other side of the interval
    -> Double -- ^ Tolerance
    -> Maybe Double -- ^ h, Current search interval
    -> Maybe Double -- ^ c, New left interval point. If Nothing, a new point is chosen.
    -> Maybe Double -- ^ d, New right interval point.
    -> Maybe Double -- ^ f(c), Function value at c
    -> Maybe Double -- ^ f(d), Function value at d
    -> (Double, Double) -- ^ The interval in which the maximum is

goldenSectionSearchRecursive f a' b' tolerance h' c' d' fc' fd'
    | h < tolerance = (a, b)
    | fc > fd = goldenSectionSearchRecursive f a d tolerance (Just (h * invphi)) Nothing (Just c) Nothing (Just fc)
    | otherwise = goldenSectionSearchRecursive f c b tolerance (Just (h * invphi)) (Just d) Nothing (Just fd) Nothing
    where
        a = min a' b'
        b = max a' b'
        h = h' // (b - a)
        c = c' // (a + invphi2 * h)
        d = d' // (a + invphi * h)
        fc = fc' // f c
        fd = fd' // f d

and then you call with goldenSectionSearch (\x -> -(x-2)^2) 1 5 1e-5 which returns (1.9999959837979107,2.0000050911830893). This simple function of course would be much easier to solve by hand, but it's just an example.

PS Interesting about Golden Section Search is that the convergence rate is exactly known: on each iteration the length of the interval in which the optimum resides is divided by the golden ratio.

PPS I put it on GitHub

[1] Note that if you know a gradient function, equating it to zero and applying a root finding method is often much faster. For example in one dimension, Will Ness pointed to his answer which has a simple method with a faster convergence rate than the Golden Section Search. You could also use one of the mentioned packages which require a gradient function, of course.

Cloudberry

I prefer this method. – Within

@WillNess I see that method converges faster, I like it, but it's for finding roots. I'm not sure how you would apply it to finding a maximum, if you don't know the function value of said maximum? – Cloudberry

can't the object function (what's the proper term?) be tweaked so it's the root that we're searching for? for instance, in least squares, the minimum coincides with the root of a derivative. for instance, en.wikipedia.org/wiki/Levenberg%E2%80%93Marquardt_algorithm says, "The sum of square deviations has at its minimum a zero gradient [...]". – Within

*"objective function". – Within

@WillNess Sometimes, namely in the cases there is a gradient function available you are right. (The nonlinear-optimization and optimization packages require such a gradient function.) In that sense the example function I gave does not make sense, because that one has a clear derivative and would be much easier to solve just by hand! For my application I didn't have a derivative, so that's why I used this method. But I should add this to the answer, it's important to see. – Cloudberry

thanks. even when we don't have derivatives directly available, we can always estimate them by probing the neighborhood. then the principle of bracketed secant still applies. :) – Within