區間消去法

當已確定了初始單谷區間之後，就可以進行一維尋優。實用的一維尋優方法一般可以分為區間消去法和函數逼近法兩種。

所謂區間消去法(又稱試探法)，就是不斷消去不存在最優點的區間，使搜索區間越來越短．最終尋得近似最優點。為了在每次迭代中縮短區間，需要在區間內插入計算點並求出其函數值。插入點的位置則因方法的不同而異，一般是按某種給定的規則來確定區間內插入點的位置，此點位置的確定僅僅按照區間縮短如何加快，而不顧及函數值的分佈關係。屬於這種方法的有裴波納契(Fibonacci)法、黃金分割法(0.618法)等。

函數逼近法(又稱插值法或近似法)，是用一個多項式來近似代替目標函數，並用這個多項式的極小點作為目標函數的近似最優點。這個多項式是根據某些點處的某些信息，如函數值、一階導數、二階導數等構造出來的。屬於這種方法的有牛頓法(切線法)、二次插值法(拋物線法)等 ^[2]  。

搜索區間

確定之後，採用區間消去法逐步縮短搜索區間，從而找到極小點的數值近似解。假定在搜索區間

內任取兩點

，並計算函數值

。於是將有下列三種可能情形 ^[2]  ：

(1)

，如圖1(a)所示。由於函數值為單谷，所以極小點必在區間

內。

(2)

，如圖1(b)所示。同理，極小點應在區間

內。

(3)

，如圖1(c)所示。這時極小點應在區間

內。

根據以上所述，只要在區間

內取兩個點，算出它們的函數值並加以比較，就可以把搜索區間

縮短成

，

或

。應當指出，對於第一種情況，我們已算出區間[

內

點的函數值，如果把搜索區間

進一步縮短，只需在其內再取一點算出函數值並與

加以比較，即可達到目的。對於第二種情況，同樣只需再計算一點的函數值就可以把搜索區間繼續縮短。第三種情形與前面兩種情形不同，因為在區間

內缺少已算出的函數值。要想把區間

進一步縮短，需在其內部取兩個點(而不是一個點)計算出相應的函數值再加以比較才行。如果經常發生這種情形，為了縮短搜索區間，需要多計算一倍數量的函數值，這就增加了計算工作量。因此，為了避免多計算函數值，我們把第三種情形合併到前面兩種情形中去。例如，可以把前面三種情形改為下列兩種情形：

(1)若

，則取

為縮短後的搜索區間。

(2)若

，則取

為縮短後的搜索區間。

在實際計算中，最常用的區間消去法是裴波納契法和黃金分割法(0.618法) ^[2]  。