具有近似导数的数值优化算法

计算科学 优化 数字
2021-12-27 23:48:18

假设我有一个取决于 X 的能量泛函 E,其中 X 是 N 维实值向量,N 可能非常大(~=2000)。我假设 E 存在(至少)一个(本地)最小化器。我现在正在处理几个问题:

  • 首先,泛函 E 非常“复杂”,几乎不可能计算出它的精确梯度和 Hessian。所以“输入”数据总是近似的。(通过有限差分公式近似梯度,近似 Hessian,...)

  • 其次,N 非常大:N ~= 2000。所以我想这可以称为大规模问题。

  • 第三,在我的代码中,我需要多次重复这个优化问题(大约 100 次迭代),所以一个快速高效的优化求解器是非常必要的。

有没有什么好的算法可以满足以上所有要求?

2个回答

考虑模拟退火 或类似算法。

简而言之,此类算法在您的维空间中执行随机游走,但是否采取新步骤取决于此步骤损失的能量¹:N

  • 如果步长减小,则进行。E
  • 如果步长增加,则该步的概率取决于该步所损失的能量。这个概率随着时间的推移而降低(即退火)。E

优点是:

  • 您根本不需要计算导数(除非您选择混合技术)。
  • 您还可以找到全局最小值。

缺点是:

  • 您需要对进行大量评估。E
  • 这是一种蒙特卡洛算法,因此它可能并不总能找到您想要的答案(特别是如果您必须减少计算量)。

这是否真的是您的最佳解决方案显然只有您可以决定,因为这取决于很多因素。


¹ 或获得,取决于您的观点和迹象

如果您正在处理粒子位置(正如您在上面的评论中指出的那样),这可能不是一件容易的事。示例是 Lennard-Jones 原子聚类问题,即使只有 150 个粒子也很难解决。这些问题是间接组合的或连续组合的。您可能会寻找 Lennard-Jones 问题的现有解决方案,也许您可​​以找到适合您应用的解决方案。一般可用的求解器无法解决此类问题。