在最少的計算次數中查找全局最大值

假設我在間隔[0,1]上定義了一個函數f，該函數是平滑的，並且在某些點開始減少之後增加到某個點a。我在此間隔上有一個網格x[i]，例如與步長爲dx = 0.01，我想通過在最壞的情況下做最小數量的評估f，我想找到哪些點具有最高的價值。我認爲我可以做得比窮舉搜索更好，應用漸變式方法啓發靈感。有任何想法嗎？我正在考慮像二元搜索或拋物線方法。在最少的計算次數中查找全局最大值

這是一個二分樣法我編碼：

def optimize(f, a, b, fa, fb, dx): 
    if b - a <= dx: 
     return a if fa > fb else b 
    else: 
     m1 = 0.5*(a + b) 
     m1 = _round(m1, a, dx) 
     fm1 = fa if m1 == a else f(m1) 
     m2 = m1 + dx 
     fm2 = fb if m2 == b else f(m2) 
     if fm2 >= fm1: 
      return optimize(f, m2, b, fm2, fb, dx) 
     else: 
      return optimize(f, a, m1, fa, fm1, dx) 

def _round(x, a, dx, right = False): 
    return a + dx*(floor((x - a)/dx) + right)

的理念是：找到區間的中間，計算m1和m2 - 點到右側和它的左側。如果方向正在增加，請按照正確的時間間隔進行操作，否則繼續向左。每當間隔太小時，只需比較兩端的數字。然而，這個算法仍然不使用我計算的點處的導數的強度。

來源

2016-04-14 Ilya

你可能想看看nelder蜂蜜酒或模擬退火 – iedoc

@iedoc：不，這將是一個可怕的矯枉過正，因爲這個函數被認爲是單峯的。 –

有多少個網格點？ –

免責聲明：未測試代碼。以此爲「靈感」。

比方說，你有以下11點

x,f(x) = (0,3),(1,7),(2,9),(3,11),(4,13),(5,14),(6,16),(7,5),(8,3)(9,1)(1,-1)

從這裏你可以做這樣的事情的啓發，以二分法

a = 0 ,f(a) = 3 | b=10,f(b)=-1 | c=(0+10/2) f(5)=14

你可以看到，越來越多區間爲[A，C [並且沒有必要這麼做，因爲我們知道在那個區間內功能在增加。最大值必須在區間[c，b]中。因此，在下一次迭代中，您將更改s.t.的值。一個= C

a = 5 ,f(a) = 14 | b=10,f(b)=-1 | c=(5+10/2) f(6)=16

再次[a,c]增加使a移動右邊

你可以重複這個過程，直到a=b=c。

這裏實現這個想法的代碼。更多信息here：

int main(){ 
#define STEP (0.01) 
#define SIZE (1/STEP) 
    double vals[(int)SIZE]; 
    for (int i = 0; i < SIZE; ++i) { 
     double x = i*STEP; 
     vals[i] = -(x*x*x*x - (0.6)*(x*x)); 
    } 
    for (int i = 0; i < SIZE; ++i) { 
     printf("%f ",vals[i]); 
    } 
    printf("\n"); 

    int a=0,b=SIZE-1,c; 
    double fa=vals[a],fb=vals[b] ,fc; 
    c=(a+b)/2; 
    fc = vals[c]; 

    while(a!=b && b!=c && a!=c){ 

     printf("%i %i %i - %f %f %f\n",a,c,b, vals[a], vals[c],vals[b]); 


     if(fc - vals[c-1] > 0){ //is the function increasing in [a,c] 
      a = c; 
     }else{ 
      b=c; 
     } 
     c=(a+b)/2; 
     fa=vals[a]; 
     fb=vals[b]; 
     fc = vals[c]; 
    } 
    printf("The maximum is %i=%f with %f\n", c,(c*STEP),vals[a]); 


}

來源

2016-04-14 11:55:03

關於增加間隔：如果f（c）> f（a）'，最大值仍可能位於它們之間。 – Ilya

@伊利亞是的，修好了。您應該只能找到哪個區間正在增加或減少。現在應該工作。 –

我不知道我可以按照你的算法，當然你在描述*中仍然存在這個問題*從這裏你可以看到增加的區間是[a，c [並且沒有必要那麼做，因爲我們知道在那段時間內，功能正在增加* – Ilya

找點哪裏衍生物（F（x）的）=（DF/DX）= 0

衍生，你可以使用五點模板或類似算法。
- 應爲O（n）
然後符合這些多個點（其中，d = 0）上的多項式迴歸/最小二乘迴歸。
- 應該也是O（N）。假設所有的數字都是鄰居。
然後找到曲線
- 的頂部不得超過O（M），其中M是合適的，功能試驗的分辨率也比較多。

同時採取衍生物，可以由k-長度步驟飛躍直到衍生物改變符號。

當微分改變符號時，取k的平方根並繼續反向。

當再次導數變化時，再次取新k的平方根，改變方向。

示例：跳過100個元素，找到符號更改，跳躍= 10，反向，下一次更改==>跳躍= 3 ...然後它可以固定爲每步1個元素以查找確切位置。

來源

2016-04-14 14:14:04

這樣的函數被稱爲單峯。

在不計算所述衍生物，可以通過

工作發現其中增量X [I + 1] -x [I]改變符號，通過二分法（三角洲是正則最大後負）;這需要Log2（n）比較;這種方法與你所描述的非常接近;
將Golden section方法適用於離散情況;它需要Logφ（n）比較（φ〜1.618）。

顯然，金部分是更昂貴的，因爲φ< 2，但實際上二分搜索需要兩個函數求值的時間，因此2Log2（N）=Log√2（N）。

可以證明這是最優的，即對於任意的單峯函數，你不能比O（Log（n））快。

如果你的函數非常規則，那麼delta值將會平滑變化。你可以想到interpolation search，它試圖通過線性插值來更好地預測搜索到的位置，而不是簡單的減半。在有利條件下，它可以達到O（Log（Log（n））的性能。我不知道這個原理是否適用於Golden搜索。

實際上，deltas上的線性插值非常接近拋物線在函數值插值。後一種方法可能是最適合你的，但你必須要小心的極端案例。

如果衍生品是允許的，你可以使用任何root solving方法上的一階導數，知道在給定的時間間隔內有一個孤立的零點

如果只有一階導數是可用，使用regula falsi。如果二階導數也是可能的，你可以考慮牛頓，但更喜歡安全的包圍方法。

我想這些方法的好處（超線性和二次收斂）由於您正在使用網格而變得無用。

來源

2016-04-14 19:07:28

我假設功能評估是非常昂貴的。

在特殊情況下，您的函數可以近似擬合一個多項式，您可以輕鬆計算功能評估最少數量的極值。而且由於您知道只有一個最大值，因此2（二次）的多項式可能是理想的。

例如：如果f(x)可以通過一些已知的多項式表示，說2，那麼，你可以在任何3點評估您的功能和使用牛頓差或拉格朗日插值法計算多項式係數。

然後它簡單地求解這個多項式的最大值。對於程度2，您可以輕鬆獲得最大封閉表單表達式。

爲了得到最終答案，您可以在解決方案的附近進行搜索。

來源

2016-04-14 22:51:57

在最少的計算次數中查找全局最大值

回答

相關問題