一千萬個為什麽

搜索

如何有效地找到包含平滑函數值的數組中的最大值?

我有一個函數,它采用浮點數並返回一個浮點數。可以假設,如果你要繪制這個函數的輸出,它將是'n'形的,即。將存在單個最大點,並且在具有零斜率的函數上沒有其他點。我們還知道產生這個最大輸出的輸入值將位於兩個已知點之間,可能是0.0和1.0。

我需要有效地找到輸出值,在某種程度的近似下產生最大輸出值,而不進行窮舉搜索。

I'm looking for something similar to Newton's Method which finds the roots of a function, but since my function is opaque I can't get its derivative.

最佳答案

到目前為止,由於各種原因,我想略去所有其他答案,但我不會。

當導數不可用時,用於最小化(或最大化)平滑函數的優秀且有效的方法是拋物線插值。編寫算法是很常見的,因此當拋物線插值不像黃金分割那樣快時,它會暫時切換到黃金分割搜索(布倫特的最小化)。

我用C ++編寫了這樣一個算法。有什麽優惠?

UPDATE: There is a C version of the Brent minimizer in GSL. The archives are here: ftp://ftp.club.cc.cmu.edu/gnu/gsl/ Note that it will be covered by some flavor of GNU "copyleft."

在我寫這篇文章時,最新和最好的似乎是gsl-1.14.tar.gz。最小化器位於文件gsl-1.14/min/brent.c中。它似乎具有與我實施的類似的終止標準。我還沒有研究過它如何決定轉向黃金分割,但對於OP來說,這可能沒什麽問題。

UPDATE 2: I googled up a public domain java version, translated from FORTRAN. I cannot vouch for its quality. http://www1.fpl.fs.fed.us/Fmin.java I notice that the hard-coded machine efficiency ("machine precision" in the comments) is 1/2 the value for a typical PC today. Change the value of eps to 2.22045e-16.

轉載註明原文: 如何有效地找到包含平滑函數值的數組中的最大值?