机器算法验证 - Nelder Mead 的停止标准 - 吾爱随笔录

Nelder Mead 的停止标准

机器算法验证优化算法

2022-03-14 01:50:52

我正在尝试实现用于优化功能的 Nelder-Mead 算法。关于 Nelder-Mead 的维基百科页面对整个算法非常清楚，除了它的停止标准。那里可悲地说：

检查收敛_{[需要澄清]}。

我自己尝试并测试了几个标准：

停止如果 $f(x_{N+1}) - f(x_1) < \epsilon$ 在哪里 $\epsilon$ 很小而且在哪里 $x_i$ 是个 $i$ -单纯形的第一个顶点，从低（ $f(x_1)$ ) 到高 ( $f(x_{N+1})$ ) 函数值。换句话说，当单纯形的最大值几乎等于最小值时。我发现这不能正常工作，因为这不能保证函数在单纯形中的作用。例如，考虑函数：
$f (x) = x^{2}$ $f(x) = x^2$ 这当然是微不足道的优化，但假设我们用 NM 做这个，让我们的两个单纯形点 $x_1 = -1$ 和 $x_2=1$ . 该算法将在这里收敛而没有找到它的最优值。
第二个选项涉及评估单纯形的质心：如果 $|f(x_1) - f(x_c)| < \epsilon$ . 这假设如果单纯形的最低点和质心具有如此相似的值，则单纯形足够小，可以称为收敛。

这是检查收敛的正确方法吗？还是有一种既定的方法来检查这个？我找不到这方面的任何资料，因为大多数搜索结果都集中在算法的复杂性上。

3个回答

不是一个完整的答案，但评论太长了，可能会让你走上正轨。

John C. Nash 在“计算机的紧凑数值方法”第 2 版的第 171 页上简要介绍了该主题。optim()并且恰好是在 R函数中实现的 Nelder-Mead 例程引用的参考。引用相关部分：

因此，必须解决有关最小化算法的最棘手问题：何时找到最小值？Nelder 和 Mead 建议函数值的“标准误差”：
$t e s t = {[(\sum_{i = 1}^{n + 1} [S (b_{i}) - \bar{S}]^{2}) / n]}^{1 / 2}$ $\mathrm{test} = \left[ \left( \sum_{i=1}^{n+1}[S(b_i) - \bar{S}]^2 \right) / n \right]^{1/2}$ 在哪里 $\bar{S} = \sum_{i = 1}^{n + 1} S (b_{i}) / (n + 1) .$ $\bar{S} = \sum_{i=1}^{n+1} S(b_i)/(n+1).$

我会打断以澄清这一点 $S(.)$ 是被最小化的函数， $b$ 是 $n+1$ 定义的点 $n$ -维单纯形；函数值最高的点是 $b_H$ 函数值最低的点是 $b_L$ . 纳什继续说：

当测试值低于预先指定的容差时，该过程被认为已经收敛。在 Nelder 和 Mead 感兴趣的统计应用中，这种方法是合理的。然而，作者发现，在函数表面上相当平坦的区域出现问题时，该标准会导致程序过早终止。在统计上下文中，如果遇到这样的区域，可能会想停下来，但假设寻求最小值，使用更简单的测试来检验两者之间的相等性似乎是合乎逻辑的 $S(b_L)$ 和 $S(b_H)$ ，即单纯形中所有点的高度相等的检验。

快速查看的来源optim()表明它使用最高和最低函数值（定义单纯形的点）之间的差异来确定收敛：高值和低值if (VH <= VL + convtol || VL <= abstol) break;在哪里。这附带了一个警告，即我非常快速地查看了源代码，并且可能遗漏了一些东西。VHVL

现在，您的选项 (1) 似乎是 Nash 提倡的第二种方法。他还讨论了您遇到的问题：

最后，仍然有可能收敛到一个不是最小值的点。例如，如果 $(n+1)$ 单纯形的点都在一个平面上（二维线），单纯形只能移入 $(n-1)$ 中的方向 $n$ 维空间，可能无法向最小值前进。O'Neill (1971) 在 Nelder-Mead 思想的 FORTRAN 实现中，沿每个参数轴在假定最小值的任一侧测试函数值。如果发现任何函数值低于当前假定的最小值，则重新启动该过程。

纳什在这里引用的原始参考资料是：

Nelder JA, Mead R. 1965。函数最小化的单纯形法。计算机杂志 7：308-313。

O'Neill R. 1971。算法 AS 47：使用单纯形过程的函数最小化。应用统计 20：338-345。

Numerical Recipes的原始版本中对这种“下坡单纯形算法”的描述特别清晰和有帮助。因此，我将引用其中的相关部分。这是背景：

在一维最小化中，可以将最小值括起来...... 唉! 在多维空间中没有类似的过程。...我们能做的最好的就是给我们的算法一个开始的猜测；也就是说，一个 $N$ -vector 的自变量作为第一个尝试点。然后，该算法应该通过难以想象的复杂性走下坡路 $N$ 维地形，直到它遇到（至少是局部的）最小值。

下坡单纯形法不仅要从一个点开始，而且要从一个点开始 $N+1$ 点，定义初始单纯形。【你可以把这些点作为初始的起点 $P_0$ 随着]
$\begin{matrix} (10.4.1) & P_{i} = P_{0} + λ e_{i} \end{matrix}$ $P_i = P_0 + \lambda e_i\tag{10.4.1}$ 在哪里 $e_i$ 是 $N$ 单位向量和哪里 $\lambda$ 是一个常数，它是您对问题特征长度尺度的猜测。...

大多数步骤只是将单纯形的函数最大的点（“最高点”）通过单纯形的相对面[移动]到较低的点。...

现在解决手头的问题，终止算法。 请注意该帐户的一般性：作者为终止任何多维优化器提供了直观且有用的建议，然后具体说明了它如何应用于此特定算法。第一段回答了我们面前的问题：

终止标准可能很微妙...... 我们通常可以识别多维算法的一个“循环”或“步骤”。然后，当在该步骤中移动的矢量距离在幅度上比某个容差小一点时，就有可能终止TOL。或者，我们可以要求终止步骤中函数值的减少比某个容差小一点FTOL。...

请注意，上述任何一个标准都可能被一个异常步骤所愚弄，由于某种原因，该步骤未能到达任何地方。因此，在声称已找到最小值的点重新启动多维最小化例程通常是一个好主意。对于此重新启动，您应该重新初始化任何辅助输入量。例如，在下坡单纯形法中，您应该重新初始化 $N$ 的 $N+1$ 单纯形的顶点再次由方程 $(10.4.1)$ ，和 $P_0$ 是要求的最小值的顶点之一。

重新启动永远不应该非常昂贵；毕竟，您的算法确实收敛到重新启动点一次，现在您已经在那里启动了算法。

[第 290-292 页。]

Numerical Recipes中此文本随附的代码阐明了“分数更小”的含义：值之间的差异 $x$ 和 $y$ （参数的值或函数的值）“略小于”阈值 $T\gt 0$ 什么时候

\begin{matrix} (1) & \frac{| x | - | y |}{f (x, y)} = 2 \frac{| x | - | y |}{| x | + | y |} < T \end{matrix}

$\frac{|x| - |y|}{f(x,y)} = 2\frac{|x|-|y|}{|x| + |y|} \lt T\tag{1}$

和 $f(x,y) = (|x|+|y|)/2$ .

的左侧 $(1)$ 有时称为“相对绝对差”。在某些领域，它以百分比表示，称为“相对百分比误差”。有关更多选项和术语，请参阅有关相对变化和差异的 Wikipedia 文章。

参考

威廉 H. Press等人。，数字食谱：科学计算的艺术。 剑桥大学出版社（1986 年）。访问http://numerical.recipes/获取最新版本。

稻草人：只追踪最低的角落

f_{min} (t) \equiv {min}_{all corners} f (X_{i}, t)

$f_{\text{min}}(t) \equiv \text{min}_{\text{all corners}} \ f(X_i, t)$ 使用“耐心”停止规则：

# stop when you run out of patience, no improvement for say 10 iterations in a row:
if t > tbest + patience:
    message = "iter %d: f %g >= fbest %g" ...
    return message, fbest, xbest

监控所有 $n+1$ corners 在检查合理的坐标缩放、约束、NM 初始单纯形时绝对有用。跟踪所有角落是否可以提高组合

问题：崎岖的地形，可能有不良的缩放比例或愚蠢的限制
算法，平衡探索和移动（和软件复杂性）
正确的停止规则

还有待观察——欢迎真正的测试用例。

Stopiter（除了patience; 最简单的是挂钟时间之外，真正的课程还有许多停止条件。）

另请参阅：
NLopt：许多算法，包括 Nelder-Mead，易于比较。尤其是关于比较算法
 下坡的注释：耐心停止min_improvement

其它你可能感兴趣的问题

上一篇基于事后分析的出版工作有问题吗？下一篇联合概率中的分号表示法是什么？