什么是最合适的无导数优化算法

计算科学 优化 凸优化
2021-12-17 09:57:32

我们可以使用随机优化/无导数/直接搜索来找到一些黑盒函数的最小值f.

如果我有一些 2D 黑盒功能,f(x,y)- 我知道它是凸的 - 最好的无导数方法是什么?

即从速度的角度来看,最好使用Nelder-MeadCompass/Pattern searchMADS等?

3个回答

正如“搜索没有免费午餐定理”[ 1 ] 所述,没有一种特定的优化算法对每个问题都最有效,即引用作者的话:

当对所有可能的成本函数进行平均时,所有搜索成本函数极值的算法的性能完全相同。特别是,如果算法 A 在某些成本函数上优于算法 B,那么粗略地说,肯定存在与 B 优于 A 的许多其他函数一样多的函数。

但是,为了获得真正好的指导,我建议查看最近的文章 [ 2 ](由两位著名的优化器撰写),其中介绍了在由 502 个组成的测试集上执行的 22 种无导数算法的回顾和比较 凸/非凸平滑/非平滑优化问题。

参考

1:Wolpert,DH 和 Macready,WG(1995 年)。搜索没有免费的午餐定理(第 10 卷)。技术报告 SFI-TR-95-02-010,圣达菲研究所。

2: Rios, LM, & Sahinidis, NV (2013)。无导数优化:算法回顾和软件实现比较。全球优化杂志,56(3),1247-1293。

正如@Remis 所说,它非常依赖于问题。我认为最好的办法是使用带有一套方法的漂亮包,然后对它们进行全部测试。NLopt.jl可以轻松尝试大量算法(包括许多无导数方法)。最适合您的问题的是性能最好的那个。

我遇到了类似的问题,一般来说,在 Python 世界中这很困难,因为选择无衍生优化器需要比较 scipy.optimize、dlib、ax-platform、hyperopt、nevergrad、optuna、bayesopt、鸭嘴兽、pymoo、pySOT 和skopt (当你阅读本文时更多)并且几乎没有共同的约定。

我最终决定我会一劳永逸地做这件事。因此,现在我计算 60 多个无衍生优化器的 Elo 评级,正如博客文章HumpDay:帮助您选择 Python 全局优化器的软件包中所解释的那样。您还可以将目标函数直接放入 colab笔记本中,它会告诉您哪个包做得最好。

我不会假设知道哪种方法适用于您的情况,但不要忽视以下内容:dlib、pySOT (dycors); skopt; 永不毕业(ngopt8);嘘。如果您想将目标函数添加到测试套件中,请联系我。我确实怀疑 1960 年代的算法在你的情况下可以正常工作。

顺便说一句,如果你和 Julia 一起去,你会更有力量!