在 Go 中实现无约束优化的数值方法

计算科学 优化
2021-12-24 19:07:20

我想用我最喜欢的 Go 语言实现一个数值优化器。它应该找到这个问题的解决方案:最大化一个函数f(x),其中f是非线性的并且x是维度 10 或 20 的实向量。 f是实值的。

就以下方面而言,最好的方法是什么:

  • 实施简单
  • 并行化的机会

该算法应该在具有多核的 x64 CPU 上运行。也许需要看不同的情况,所以我可以实现 2 或 3 个算法。

有趣的案例:

  • f是有理的或者 f是有理函数的组合,exp也许log
  • f有多个最大值

这不是一个开放的问题。所以我不是在寻找列出尽可能多算法的答案。或者无休止地讨论哪种算法可能是最好的。选择算法可能有点主观,所以我想强调一个体面的解决方案,而不是一个完美的解决方案。

如果听说模拟退火在涉及多个最大值和固定域时被认为是最先进的。虽然这听起来像:如果我不修复域,虽然我可以先验地修复它,但模拟退火可能不如其他算法。

更新:次优解决方案很好,但是我想确保算法不会轻易集中在单个最大值上。

关于函数:我想对估计时间序列的函数进行最大似然拟合。就像y_{n+1} = a_1 * y_n + a_2 + y_{n-1} + ... + b_1 * epsilon_n + ... + epsilon_n在一个简单的案例中一样。epsilon是 iid 噪声、y一些时间序列a_ib_i真实参数。)目前我正在通过假设epsilon是正态分布来做到这一点,但我想更改为柯西分布。此外,我想添加一些非线性项并将其从 y 实值扩展到 y 作为实向量。不幸的是,我还不知道我到底想要什么,所以优化器的范围不应该太大。

2个回答

如果你有明确的梯度,带有 More-Thuente 线搜索的 BFGS 是首选方法。它是一种串行算法,相当容易实现,而且非常健壮。(在http://prod.sandia.gov/techlib/access-control.cgi/2010/101422.pdf中描述了 BFGS/More-Thuente 变体的 Matlab 实现。代码是公开的,可以指导您重新实现.)

并行化需要一些修改,您可以在了解算法的工作原理后轻松发明自己。您需要多个起点选项(起点较远)才能找到具有广泛吸引力的多个 mimina。

使用凸松弛进行分支定界可以确保找到全局最小值,但要提高效率远非易事。

如果你没有梯度,我建议你重新实现我的 SNOBFIT 包,它是一个非常健壮的包,用于对昂贵的函数进行无导数优化,具有出色的并行化能力。http://www.mat.univie.ac.at/~neum/software/snobfit/

您的问题称为 ARMA(p,q) 模型的最大似然估计。您将把它扩展到一般的 VAR(向量自回归)案例。这个问题已经解决了很多次,现有的时间序列分析软件套件可以做到这一点,此外,相关测试的输出统计数据(ML、Wald 和似然比,对于初学者来说)。例如,为此存在 R 包;商业统计软件具有 ML 例程的各种实现。很不幸,要利用丰富的现有知识,您必须以最具体的方式命名您的问题。

也就是说,关于实施的一些想法。首先,我完全不知道 Go 编程语言中的计算特性和 IEEE-754 一致性。对于(比如说)Fortran,细节是众所周知的。有一些语言/数学库让我在计算方面头疼(Java,我在看着你!)。

其次,并行化是您希望从已经工作的代码中采取的最后一步。此处并行化的自然方法是从相距较远的起点运行相同的例程到收敛。

第三,如果您热衷于自己实现算法并且没有获得预先打包的解决方案,建议您尝试使用 Powell 的可微函数算法 (BOBYQA)。您可以从NLOPT移植它。

第四,你关于柯西错误的想法听起来有趣。

一些让您忙碌的书籍和文章:

  • 汉密尔顿,JD 时间序列分析,1994 年。普林斯顿大学。
  • Box, GEP, Jenkins, GM 和 Reinsel, GC, 1994。时间序列分析:预测和控制。霍尔顿日。
  • Box, GEP 和 Luceño, A., 1997。通过监测和反馈调整进行统计控制。威利。
  • EJ 汉南和 AJ 麦克杜格尔。ARMA 估计的回归程序。美国统计协会杂志卷。83, No. 402, Jun., 1988. pp.490-498

请注意,此类问题可以在Stats SE(交叉验证)上得到更好的回答。