[科普中國]-鮑威爾法

簡介

鮑威爾法，嚴(yán)格來說是鮑威爾共軛方向法，是邁克爾J.D.鮑威爾提出的一種求解函數(shù)局部最小值的算法。該函數(shù)不能是可微分的，并且不會導(dǎo)出衍生函數(shù)。

該函數(shù)必須是固定數(shù)量的實值輸入的實值函數(shù)。通過傳入一組初始搜索向量，通常會傳入N個搜索向量（譬如{s1,,,,,sn}）這是與每個軸對齊的法線。12

鮑威爾法是在無約束優(yōu)化共扼方向，從某個初始點(diǎn)出發(fā)，求目標(biāo)函數(shù)在這些方向上的極小值點(diǎn)，然后以該點(diǎn)為新的出發(fā)點(diǎn)，取復(fù)這一過程直到獲得滿意解，其優(yōu)點(diǎn)是不必計算目標(biāo)函數(shù)的 梯度就可以在有限步內(nèi)找到極值點(diǎn)。

計算過程鮑威爾法依次通過沿著每個搜索向量的雙向搜索使功能最小化。沿著每個搜索向量的雙向線搜索可以通過黃金分割搜索或黑雁的方法來完成。讓每個雙向線搜索中找到的最小值為

其中x0是起始點(diǎn)，αi是沿著si的雙向搜索確定的標(biāo)量。然后可以將新位置（x1）表示為搜索向量的線性組合，即

新的位移矢量

成為新的搜索向量，并被添加到搜索向量列表的末尾。

同時，對新方向貢獻(xiàn)最大的搜索向量，即最成功的搜索向量（）搜索向量列表。新的N個搜索向量集合是

該算法迭代任意次數(shù)，直到?jīng)]有明顯的改善。

該方法對于計算連續(xù)但復(fù)雜函數(shù)的局部最小值是有用的，特別是沒有基礎(chǔ)數(shù)學(xué)定義的函數(shù)，因為不需要導(dǎo)數(shù)?；舅惴ê唵?復(fù)雜度在沿著搜索向量的線性搜索中，這可以通過布倫特法來實現(xiàn)。3

布倫特法定義布倫特方法(the method of Brent)是在二分法或試位法的基礎(chǔ)上，借助二次插值方法進(jìn)行加速，有利用反插值方法來簡化計算而形成的一種方法。

內(nèi)容假如知道f(x)的零點(diǎn)x’在一個不太大的區(qū)間[x0,x1]內(nèi)，而且已知f(x)在區(qū)間的端點(diǎn)處的函數(shù)值

以及f（x）=0在（x0,x1）內(nèi)的近似解x=x2和f(x2)，接下來利用這已知的三個點(diǎn)以及它們所對應(yīng)的函數(shù)值作插值拋物線。與Muller方法不同的是，把x0 ，x1 ，x2 與f(x0), f(x1), f(x2)的對應(yīng)關(guān)系反過來用，相當(dāng)于用y0 ，y1 ，y2 替代方程組

f(x0)= a(x0-x2) ^2+b(x0-x2)+c **************** (1)

f(x1)= a(x1-x2) ^2+b(x1-x2)+c **************** (2)

f(x2)= a(x2-x2) ^2+b(x2-x2)+c **************** (3)

中的x0 ，x1 ，x2 ，而方程組的常數(shù)項f(x0), f(x1), f(x2) 則用這里的x0 ，x1 ，x2替換。所以對應(yīng)的插值拋物線的一般形式為

x= a(y-y2) ^2+b(y-y2)+c **************** (4)

x0= a(y0-y2) ^2+b(y0-y2)+c **************** (5)

x1= a(y1-y2) ^2+b(y1-y2)+c **************** (6)

x2= a(y2-y2) ^2+b(y2-y2)+c **************** (7)

由（5）（6）（7）式可以得c=x2,利用Muller方法，可以寫成a,b 的表達(dá)式。

在（4）中令y=0,可以得到下一個近似點(diǎn)為

X=x2+(ay2 ^2+by2) **************** (8)

其中ay2 ^2+by2相當(dāng)于校正項。

Brent方法的下一個規(guī)則是，如果得到的x仍然在區(qū)間[x0,x1]內(nèi)，則用x2根據(jù)f(x2)

的符號替換x0或x1 ，用x替換x2；如果所得到的x不在區(qū)間[x0,x1]內(nèi)，則暫時放棄反拋物線插值法，繼續(xù)用二分法或試位法。

實際上，我們可以利用二分法所得到函數(shù)順便采用反插值方法試探一下。