以特定分辨率查找連續函數的最大值

想象一下，函數在[0.0，n]範圍內是連續的。是否有任何算法可以比簡單迭代更快地找到給定最小步長s的函數的最大值？簡單的迭代對於編程很簡單，但是當時間複雜度增加時，n/s很大。以特定分辨率查找連續函數的最大值

double maxValue = 0; 
double maxValueX = 0; 
double s = 0.1 * n; 
for (double x = 0.0; x <= n; x += s) 
{ 
    double value = someFunction(x); 
    if(value > maxValue) { 
     maxValue = value; 
     maxValueX = x; 
    } 
}

我已經試過這種方法是要快得多，但不知道這是否會停滯在局部最大值。

double min = 0; 
double max = n; 
int steps = 10; 
increment = (max - min)/steps; 
while (increment > s) 
{ 
    double maxValue = 0; 
    double maxValueX = X; 
    for (double x= min; x <= max; x+= increment) 
    { 
     double value = someFunction(x); 
     if(value > maxValue) { 
      maxValue = value; 
      maxValueX = x; 
     } 
    } 
    min = Math.Max(maxValueX - increment, 0.0); 
    max = Math.Min(maxValueX + increment, n); 
    increment = (max - min)/steps; 
}

來源

2013-10-03 Moop

若f（x）是連續的，最大值（也是最小值）出現在d/dx f（x）= 0處。雖然沒有關於函數程度的信息並且僅通過調用它來評估函數，但這可能是唯一的方法。此外，隨着您增加步數，除非對域值（即x的可能值）有其他已知限制，否則您可能會有更「接近最大值」的值。 –

如果你想看'd/dx f（x）'，你需要'f'來區分。有許多功能是連續的但不可區分的。 – Teepeemm

如果你知道一些關於連續「f」是什麼的話，那可能會有所幫助。例如，如果'| f（x + s）-f（x）|'有界，那麼當'f'遠離它的最大值時，可以採取更大的步驟。 – Teepeemm

鑑於你正在討論的函數是代碼，那麼不，該函數可以在任何點返回任意的最大值。

如果您可以對功能進行假設（如最大變化率），那麼您可以優化。

來源

2013-10-03 03:03:40

假設有這樣一種算法，也就是說，一種算法可以在不查看每個近似點的情況下找到連續函數的近似值的最大值。

現在選擇一個正整數n，然後選擇任意n個雙打的有限序列。有無窮多個連續函數，使得f（n）等於序列中的第n個二元組，並且小於或等於其中最大的那個。選擇其中之一。

現在使用你的算法找到n個雙打的最大雙倍。通過假設，它檢查少於n個雙打。我們假設它檢查除第k個雙數之外的所有數據。

現在假設我們創建一個與第一個序列相同的新序列，除了第k個double是最大序列。算法是神奇的，當給定一個輸入，它不會讀取，它會改變它的輸出？

現在很清楚爲什麼沒有這樣的算法？如果你想在抽屜裏找到最長的字符串，你將不得不看看所有的字符串。

該功能的連續性根本無法幫到你。所有連續性給你一個保證，給定一個函數的一個點，你可以找到另一個函數的點，如你所願接近第一個點。這不會告訴你關於該函數的最大值的信息。（嗯，好吧，它會告訴你東西。在一個封閉的有界區間則意味着最大的存在，這是一件好事，但它並不能幫助你找到它。）

來源

2013-10-03 06:28:33

我認爲你的反例是有點不真誠的：改變第k個double會改變函數的「形狀」，因此在理論上可能是一個算法，它會首先消除由於特定的局部邊界條件導致的第k個值，如果第k個值是局部或全局最大值，則滿足。 – InBetween

@InBetween：我不喜歡被稱爲不誠實，特別是在公共場合。我既不誠實地回答這個問題，也不試圖假裝我比我更瞭解微積分。當我們將最好的意圖歸於其他人時，我們都會在本網站上做得更好。 –

@InBetween：爲了解決您的具體問題：除了在k-0.00000001和k + 0.0000001之間的所有點上取一個等於f（x）的新函數g（x），並在這些點之間選擇一個連續函數。 –

以特定分辨率查找連續函數的最大值

回答

相關問題