區間消去法

區間消去法(interval elimination method)是求單變數函式無約束極值的較實用的一類直接搜尋方法，其特點是在搜尋過程中，不斷縮小最優點所在的區間，即通過搜尋區間的逐步縮小來確定最優點。

基本介紹

• 中文名：區間消去法
• 外文名：interval elimination method
• 所屬學科：數學（非線性規劃）
• 簡介：通過區間的逐步縮小確定最優點

基本介紹

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

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

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

區間消去法原理

搜尋區間確定之後，採用區間消去法逐步縮短搜尋區間，從而找到極小點的數值近似解。假定在搜尋區間內任取兩點，並計算函式值。於是將有下列三種可能情形：

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

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

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

圖1（a）

圖1（b）

圖1（c）

根據以上所述，只要在區間內取兩個點，算出它們的函式值並加以比較，就可以把搜尋區間縮短成，或。應當指出，對於第一種情況，我們已算出區間[內點的函式值，如果把搜尋區間進一步縮短，只需在其內再取一點算出函式值並與加以比較，即可達到目的。對於第二種情況，同樣只需再計算一點的函式值就可以把搜尋區間繼續縮短。第三種情形與前面兩種情形不同，因為在區間內缺少已算出的函式值。要想把區間進一步縮短，需在其內部取兩個點(而不是一個點)計算出相應的函式值再加以比較才行。如果經常發生這種情形，為了縮短搜尋區間，需要多計算一倍數量的函式值，這就增加了計算工作量。因此，為了避免多計算函式值，我們把第三種情形合併到前面兩種情形中去。例如，可以把前面三種情形改為下列兩種情形：

(1)若，則取為縮短後的搜尋區間。

(2)若，則取為縮短後的搜尋區間。

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