algorithm - 快速查找 C++ 中的所有局部最大值

Question

问题

我有一个计算一维多项式联合函数的公式。我想在给定范围内找到该函数的所有局部最大值。

我的方法

我目前的解决方案是，我在范围内的一定数量的点上评估我的函数，然后我遍历这些点并记住函数从上升到下降的点。因为我可以在间隔内更改样本数，但我想找到样本数尽可能少的所有最大值。

问题

你能给我推荐一些有效的算法吗？

Answer 1

找到未知函数的所有最大值很困难。您永远无法确定您找到的最大值真的只是一个最大值，或者您没有在某处忽略最大值。

但是，如果对该函数有一些了解，您可以尝试利用它。当然，最简单的一个是，如果已知该函数是有理数且等级有界。直到五级有理函数，才有可能从封闭公式中推导出所有四个极值，参见 http://en.wikipedia.org/wiki/Quartic_equation#General_formula_for_roots了解详情。很可能，您不想实现它，但对于线性、平方和立方根，封闭公式是可行的，可用于查找四次函数的最大值。

这只是可能知道的最简单的信息，其他有趣的信息是您是否可以给二阶导数一个界限。这将允许您在发现强斜率时降低采样密度。

您还可以利用您打算如何使用找到的最大值的信息。它可以为您提供有关所需精度的线索。知道一个点接近最大值就足够了吗？或者说一个点是平的？如果鞍点被归类为最大值真的是个问题吗？或者，如果忽略了转折点旁边的最大值？允许的误差范围是多少？

如果您不能利用这样的信息，您将退回到小步对您的函数进行采样，并希望您不会犯太多错误。

---

编辑:
您在评论中提到您的函数实际上是核密度估计。这至少为您提供了以下信息:

• 除非内核不受扩展限制，否则您的估计函数将是一个分段函数:其上的任何点只会受到可精确计算的测量点数量的影响。

• 如果内核基于有理函数，则生成的估计函数将是分段有理函数。而且会和内核同级!

  • 如果内核是统一内核，您的估计函数将是阶跃函数。
    这种情况需要特殊处理，因为在数学意义上不会有任何最大值。但是，它也让您的工作变得非常轻松。

  • 如果内核是三角内核，您的估计函数将是分段线性函数。

  • 如果内核是 Epanechnikov 内核，您的估计函数将是分段二次函数。

  在所有这些情况下，生成分段函数并找到它们的最大值几乎是微不足道的。

• 如果内核等级太高或超越，您仍然知道您的估计所基于的测量，并且您知道内核属性。这使您可以启发式地了解最大值的密度。

• 至少，您知道内核的一阶和二阶导数。

  • 原则上，这允许您在任何点计算估计函数的一阶和二阶导数。

  • 在局部内核的情况下，计算任何点的估计函数的一阶导数和二阶导数的上限可能更为谨慎。

  有了这些信息，应该可以将搜索限制在存在最大值的区域，并避免对斜率进行过度采样。

如您所见，您可以从对函数的了解中获得很多有用的信息，并且可以利用这些信息发挥自己的优势。