C++所有局部最大值

Question

問題

我有1D多項式，關節功能的計算公式的快速發現。我想在給定的範圍內找到該函數的所有局部最大值。

我的做法

我目前的解決方案是，我評估我的功能一定數目從點的範圍，然後我去通過這些點並記住點中的功能上升到下降改變。因爲我可以在間隔內更改樣本數量，但我想盡可能以最低的樣本數量查找所有最大值。

問題

你可以提出任何effetive算法給我嗎？

Answer 1

找到一個未知函數的所有最大值是很難的。你永遠無法確定你找到的最大值只是一個最大值，或者你沒有忽略某個最大值。

但是，如果有關該功能的信息已知，則可嘗試利用該功能。當然，最簡單的一個是，如果函數被認爲是合理的並且等級有界的話。達到五級的合理函數，可以從一個封閉公式推導出所有四個極值，詳見http://en.wikipedia.org/wiki/Quartic_equation#General_formula_for_roots。最有可能的是，你不想實現這一點，但對於線性，方形和立方根，閉合公式是可行的，並且可以用來找到四次函數的最大值。

這只是最簡單的信息，可能是已知的，其他有趣的信息是您是否可以對二階導數給出一個界限。當你發現一個強烈的斜坡時，這將允許你減少採樣密度。

您也可以利用您打算使用您找到的最大值的信息。它可以爲您提供有關您需要多少精度的線索。知道一個點接近最大值就足夠了嗎？或者說一個點是平坦的？如果將鞍點歸類爲最大值，是否真的存在問題？或者如果忽視轉折點旁邊的最大權利？多少是可允許的誤差範圍？

如果你不能利用這樣的信息，你會被拋回到抽樣功能的小步驟，希望你不會犯太多的錯誤。

---

編輯：
你提到在你的函數實際上是一個內核密度估計的意見。這給了你至少包含以下信息：

• 除非內核不限於擴展，你估計的功能將是一個分段函數：在任意一點只有通過測量點精確可計算的數量影響。

• 如果內核是基於一個有理函數，那麼得到的估計函數將是分段理性的。它將與內核的等級相同！

  • 如果內核是統一的內核，你的估計函數將是一個階梯函數。
    這種情況需要特殊處理，因爲在數學意義上不會有任何最大值。但是，這也使你的工作變得非常簡單。

  • 如果內核是三角核，那麼你的估計函數將是一個分段線性函數。

  • 如果內核是Epanechnikov內核，那麼你的估計函數將是一個分段二次函數。

  在所有這些情況下，產生分段函數和找到它們的最大值是很重要的。

• 如果內核的級別太高或超驗，您仍然知道您的估算所依據的測量結果，並且您知道內核屬性。這可以讓你推導出你的最大值可以得到多少密度的啓發式。

• 至少，你知道內核的一階和二階導數。

  • 原則上，這允許用戶在任何點計算估計函數的第一和第二導數。

  • 在局部內核的情況下，計算一階導數和估計函數在任意點的二階導數的上界可能更爲謹慎。

  有了這些信息，應該有可能將搜索約束到有最大值的區域，並避免斜率過採樣。

正如你看到的，有很多的，你可以從你的函數的知識，你可以使用你的優勢得到有用的信息。

Answer 2

局部最大值是一階導數的根源之一。爲了在工作間隔中隔離這些根，可以使用Sturm定理，然後進行二分法。理論上（使用精確的算術）它給你所有的真正的根。

一個等價的方法是在Bezier/Bernstein基礎上表達您的多項式並查找係數符號的變化（船體屬性）。通過Bezier的遞歸細分可以有效地實現二分搜索。

有多種經典算法可用於多項式，例如Laguerre，通常也會查找複數根。