快速算法的基準，其任務是功能最小化

是否有一組測試函數來衡量給定算法的性能（就速度而言，可能會折衷交易），其任務是查找/全局最小值一個給定時間間隔內的實值函數？最終：這個問題是一個開放的問題還是存在一個理論上最好的算法來完成這樣的任務？快速算法的基準，其任務是功能最小化

編輯：沒有限制的功能，其他應該是有界的。

2016-02-16 marco trevi

「功能沒有限制」：這是不現實的說法。在這種情況下，唯一的方法是徹底搜索。準備2^64功能評估。 –

除了有界性之外，對函數沒有任何限制，似乎不可能總是找到它的全局最小值，更不用說在合理的時間內。

考慮對[0..1]中定義實值函數的家族：

f (x0) = y0 
f (x) = 0 for all other x in [0..1]

對於任何固定x0 in [0..1]和y0 < 0，最小值是在x0。但是，任何不知道x0的算法都很難找到它。

來源

2016-02-16 16:36:15 Gassa

是的。如果我收緊約束條件，我的問題是否有合理的答案？（即考慮幾乎在任何地方平等的功能類別，所以甚至病理性病例） –

@marcotrevi是：也許是連續的，平滑的或[Lipschitz]（https://en.wikipedia.org/wiki/Lipschitz_continuity）函數，問題是有道理的。 – Gassa

@marcotrevi您可能必須定義域，例如[0..1]中的實際值。 – Gassa

在你評估f（x）的每個點上取一個0的函數，對於你不評估f（x）的每一個點c取一個未知的c> 0。如果你想要它是連續的，那麼如果x在a和b之間，其中a和b是你評估f（a）和f（b）的相鄰點，則f從f（a）= 0到f （a + b）/ 2）= c，回到f（b）= 0。由於你從不評估其他任何東西，所以你的算法不能得出結論：全局最大值不是零，而是錯誤的。

來源

2016-02-16 16:36:12 gnasher729

我懷疑這個函數在數學上是不明確的，因爲它取決於算法... –

@marcotrevi我們可以用這種方式來重新修飾它。 1.採取任何算法。 2.等到它完成執行。 3. * Then *，在算法的輸出錯誤的地方存在一個函數（在答案中定義了一個這樣的函數）。因此，不存在「正確」的算法。 – Gassa

快速算法的基準，其任務是功能最小化

回答

相關問題