Nelder Mead 的停止標準
我正在嘗試實現用於優化功能的 Nelder-Mead 算法。關於 Nelder-Mead 的維基百科頁面對整個算法非常清楚，除了它的停止標準。那裡可悲地說：
檢查收斂[需要澄清]。
我自己嘗試並測試了幾個標準：
- 停止如果在哪裡很小而且在哪裡是個-單純形的第一個頂點，從低（) 到高 () 函數值。換句話說，當單純形的最大值幾乎等於最小值時。我發現這不能正常工作，因為這不能保證函數在單純形中的作用。例如，考慮函數：
這當然是微不足道的優化，但假設我們用 NM 做這個，讓我們的兩個單純形點和. 該算法將在這裡收斂而沒有找到它的最優值。
- 第二個選項涉及評估單純形的質心：如果. 這假設如果單純形的最低點和質心具有如此相似的值，則單純形足夠小，可以稱為收斂。
這是檢查收斂的正確方法嗎？還是有一種既定的方法來檢查這個？我找不到這方面的任何資料，因為大多數搜索結果都集中在算法的複雜性上。
Numerical Recipes的原始版本中對這種“下坡單純形算法”的描述特別清晰和有幫助。因此，我將引用其中的相關部分。這是背景：
在一維最小化中，可以將最小值括起來…… 唉! 在多維空間中沒有類似的過程。…我們能做的最好的就是給我們的算法一個開始的猜測；也就是說，一個 $ N $ -vector 的自變量作為第一個嘗試點。然後，該算法應該通過難以想像的複雜性走下坡路 $ N $ 維地形，直到它遇到（至少是局部的）最小值。
下坡單純形法不僅要從一個點開始，而且要從一個點開始 $ N+1 $ 點，定義初始單純形。【你可以把這些點作為初始的起點 $ P_0 $ 隨著]$$ 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 $ 什麼時候
$$ \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/獲取最新版本。