Haskell中用于顺序非线性优化的库？

Question

是否有在Haskell中编写或轻松调用的具有上下界限和不等式约束的顺序非线性优化库?

- pyCthon

Answer 1

bindings-levmar包提供了一个C Levenberg-Marquardt优化器的绑定。

- Anthony

Answer 2

快速查询Hackage可以发现，nonlinear-optimization是最好（也是唯一）的已经编写好的内容；但是，它似乎不包括任何有关有界优化的信息。

以下是您最好的选择（按吸引力递增的顺序）：

1. 开始自己的项目。
2. 扩展上述包。
3. 找到一个不错的C库并学习足够的FFI绑定它。

- Daniel Wagner

Answer 3

我知道OP要求一个通用的优化库，我的经验是：

• levmar包依赖于blas和lapack库，这使得安装变得非常复杂，我没有成功在Windows上安装它并使ghci仍然工作。
• nonlinear-optimization包需要梯度函数
• optimization包似乎也需要梯度，尽管我无法弄清楚如何实际使用它。

此外，所有提到的软件包似乎都没有真正的文档。

幸运的是，对于简单问题，简单的解决方案就足够了。如果您想要优化一个一维、平滑且凸函数，该函数具有单个括号极值，但您不知道梯度函数（如果您知道，请参见下文¹），那么像黄金分割搜索这样的简单方法就可以解决问题。

从维基百科页面翻译。

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

然后，您使用goldenSectionSearch (\x -> -(x-2)^2) 1 5 1e-5进行调用，它返回(1.9999959837979107,2.0000050911830893)。当然，这个简单的函数手动解决会更容易，但这只是一个例子。

PS：有趣的是，黄金分割搜索的收敛速度是确切已知的：在每次迭代中，包含最优解的区间长度被黄金比例分割。

PPS：我将其放在GitHub上。

[1]请注意，如果您知道梯度函数，则将其归零并应用根查找方法通常更快。例如，在一维情况下，Will Ness指向了他的答案，其中有一种简单的方法，收敛速度比黄金分割搜索更快。当然，您也可以使用其中提到需要梯度函数的软件包。

- PHPirate

---

我更喜欢这种方法。 - Will Ness

@WillNess 我看到这个方法收敛更快，我喜欢它，但它是用于寻找根的。如果您不知道所述最大值的函数值，我不确定如何将其应用于查找最大值？ - PHPirate

对象函数（什么是正确的术语？）不能被调整，以便我们搜索根目录吗？例如，在最小二乘法中，最小值与导数的根重合。例如，https://en.wikipedia.org/wiki/Levenberg%E2%80%93Marquardt_algorithm说：“平方偏差的总和在其最小值处具有零梯度[...]”。 - Will Ness

"目标函数" - Will Ness

@WillNess 有时候，特别是在梯度函数可用的情况下，你是正确的。（非线性优化和优化包需要这样的梯度函数。）从这个意义上讲，我给出的示例函数是没有意义的，因为它具有明确的导数，可以通过手动计算来轻松解决！对于我的应用程序，我没有导数，所以我使用了这种方法。但我应该将其添加到答案中，这很重要。 - PHPirate

即使我们没有直接可用的导数，我们仍然可以通过探测邻域来估计它们。然后括号割线法的原则仍然适用。 :) - Will Ness