無約束極值問題課件

1、非線性規(guī)劃無約束極值問題 現(xiàn)在我們來研究n元函數(shù)的無約束極值問題。這種問題的表達(dá)式為： Min f(X) XE(n) (1) 為求此問題的最優(yōu)解或近似最優(yōu)解，常使用搜索法，并要進(jìn)行若干次迭代。 當(dāng)用迭代法求解問題（1）時(shí)，常從某一近似點(diǎn)X(k)出發(fā)，接著在這一點(diǎn)選定一搜索方向P(k)，使目標(biāo)函數(shù)值沿該方向下降，然后選擇步長(zhǎng)，沿P(k)方向移動(dòng)一個(gè)步長(zhǎng)，即可得下一個(gè)近似點(diǎn)X(k1)X(k1) X(k) P(k)且滿足 f(X(k1) f(X(k)這樣即可逐步趨近極小點(diǎn)，當(dāng)滿足精度條件| f(X(k1) |21, |f(X(k1)- f(X(k) |0 這里的方向g(0)和步長(zhǎng) 0都是待定的。一、

2、梯度法（最速下降法）為了使f(x) 的函數(shù)值在x(0)沿方向g(0)移動(dòng)步長(zhǎng) 0后有所下降，我們將f(x)在x(0)上展開泰勒級(jí)數(shù) f(x(0)+ 0 g(0)= f(x(0)+ 0 f(x(0) )T g(0)+o( 0 )只要 0 f(x(0) )T g(0)0,就可以保證f(x(0)+ 0 g(0) f(x(0)若記x(1) x(0)+ 0 g(0)，則 f(x(1) ) 0 故使該二次函數(shù)沿p(0)方向取極小值的為這就是推廣后的共軛梯度法的計(jì)算公式。它與原來共軛梯度法的差異就是：步長(zhǎng)的計(jì)算公式發(fā)生了改變。在原共軛梯度法中凡是用到A的地方，都要改成當(dāng)前的海賽矩陣。牛頓法 為了尋找收斂速度

3、快的無約束最優(yōu)化方法，我們考慮在每次迭代時(shí)，用適當(dāng)?shù)亩魏瘮?shù)去近似目標(biāo)函數(shù)f，并用迭代點(diǎn)指向近似二次函數(shù)極小點(diǎn)的方向來構(gòu)造搜索方向，然后精確地求近似二次函數(shù)的極小點(diǎn)，以該極小點(diǎn)作為 f 的極小點(diǎn)的近似值。這就是牛頓法的基本思想。也是單變量牛頓法的推廣。 牛頓法是求無約束最優(yōu)解的一種古典解析算法。 牛頓法可以分為原始牛頓法和阻尼牛頓法兩種。實(shí)際中應(yīng)用較多的是阻尼牛頓法。原始牛頓法一、原始牛頓法的基本思想 在第k次迭代的迭代點(diǎn)xk鄰域內(nèi)，用一個(gè)二次函數(shù)去近似代替原目標(biāo)函數(shù)f(x)，然后求出該二次函數(shù)的極小點(diǎn)作為對(duì)原目標(biāo)函數(shù)求優(yōu)的下一個(gè)迭代點(diǎn)，依次類推，通過多次重復(fù)迭代，是迭代點(diǎn)逐步逼近原目標(biāo)函數(shù)的

4、極小點(diǎn)。如圖所示。F(x)1(x)0(x)x0 x1x2x*二、原始牛頓法的迭代公式 設(shè)目標(biāo)函數(shù)f(x)具有連續(xù)的一、二階導(dǎo)數(shù)，在xk點(diǎn)鄰域內(nèi)取f(x)的二次泰勒多項(xiàng)式作近似式，即 取逼近函數(shù)(x)為設(shè)xk+1為(x)極小點(diǎn)，根據(jù)極值的必要條件，應(yīng)有 (xk+1)=0，即 f(xk)+ H(xk)x=0 若f(x)在點(diǎn)xk處的海賽矩陣正定，則由上式解出的駐點(diǎn)就是(x)的極小點(diǎn)，所以它可以作為f的第k1次迭代的極小點(diǎn)，記為xk+1 得 xk+1 = xk- H(xk)-1 f(xk) 即牛頓法迭代公式，方向- H(xk)-1 f(xk)稱為牛頓方向我們知道，對(duì)于正定二次函數(shù)的無約束最優(yōu)化問題例：

5、用牛頓法求解這個(gè)例子說明，牛頓法要比最速下降法收斂的快，事實(shí)上例：用牛頓法求解三、原始牛頓法的特點(diǎn) 若用原始牛頓法求某二次目標(biāo)函數(shù)的最優(yōu)解，則構(gòu)造的逼近函數(shù)與原目標(biāo)函數(shù)是完全相同的二次式，其等值線完全重合，故從任一點(diǎn)出發(fā)，一定可以一次達(dá)到目標(biāo)函數(shù)的極小點(diǎn)。 因此，牛頓法是具有二次收斂性的算法。其優(yōu)點(diǎn)是：對(duì)于二次正定函數(shù)，迭代一次即可以得到最優(yōu)解，對(duì)于非二次函數(shù)，若函數(shù)二次性較強(qiáng)或迭代點(diǎn)已經(jīng)進(jìn)入最優(yōu)點(diǎn)的較小鄰域，則收斂速度也很快。 原始牛頓法的缺點(diǎn)是：由于迭代點(diǎn)的位置是按照極值條件確定的，并未沿函數(shù)值下降方向搜索，因此，對(duì)于非二次函數(shù)，有時(shí)會(huì)使函數(shù)值上升，即 f(xk+1) f(xk)，而使計(jì)算

6、失敗。阻尼牛頓法一、對(duì)原始牛頓法的改進(jìn) 為解決原始牛頓法的不足，在由xk求xk+1時(shí)，不直接用迭代公式，而是沿牛頓方向進(jìn)行最優(yōu)一維搜索，以確定最優(yōu)步長(zhǎng)k ，這就是所謂的阻尼牛頓法。 因此，迭代公式變?yōu)椋?xk+1 = xk - k H(xk)-1 f(xk) 這就是阻尼牛頓法的迭代公式，最優(yōu)步長(zhǎng)k也稱為阻尼因子，是沿牛頓方向一維搜索得到的最優(yōu)步長(zhǎng)。二、阻尼牛頓法的迭代步驟 （1）給定初始點(diǎn)和收斂精度 （2）計(jì)算 f(xk) 、 H(xk)、 H(xk)-1 （3）求xk+1 = xk - k H(xk)-1 f(xk) （4）檢查收斂精度，若| xk+1- xk | 則x*=xk+1，停止，否

7、則 k=k+1，返回（2）繼續(xù)三、阻尼牛頓法的特點(diǎn) 優(yōu)點(diǎn)：由于阻尼牛頓法每次迭代都在牛頓方向進(jìn)行一維搜索，避免了迭代后函數(shù)值上升的現(xiàn)象，從而保持了牛頓法的二次收斂性，而對(duì)初始點(diǎn)的選擇沒有苛刻的要求。 缺點(diǎn)： 1、對(duì)目標(biāo)函數(shù)要求苛刻，要求函數(shù)具有連續(xù)的一、二階導(dǎo)數(shù)；為保證函數(shù)的穩(wěn)定下降，海賽矩陣必須正定；為求逆陣要求海賽矩陣非奇異。 2、計(jì)算復(fù)雜且計(jì)算量大，存儲(chǔ)量大.例:用阻尼牛頓法解DFP變尺度法 變尺度法也稱擬牛頓法，它是基于牛頓法的思想而又作了重大改進(jìn)的一類方法。我們所介紹的變尺度法是由Davidon于1959年提出又經(jīng)Fletcher和Powell加以發(fā)展和完善的一種變尺度法，故稱為DF

8、P變尺度法。一、變尺度法的基本思想 變尺度法的基本思想與牛頓法和梯度法有密切聯(lián)系。觀察梯度法和牛頓法的迭代公式 x(k+1)=x(k)- k f(xk) 和 xk+1 = xk - k H(xk)-1 f(xk) 分析比較這兩種方法可知：梯度法的搜索方向?yàn)? f(xk) ，只需計(jì)算函數(shù)的一階偏導(dǎo)數(shù)，計(jì)算量小，當(dāng)?shù)c(diǎn)遠(yuǎn)離最優(yōu)點(diǎn)時(shí)，函數(shù)值下降很快，但當(dāng)?shù)c(diǎn)接近最優(yōu)點(diǎn)時(shí)收斂速度極慢。牛頓法的搜索方向?yàn)? H(xk)-1 f(xk) ，不僅需要計(jì)算一階偏導(dǎo)數(shù)，而且要計(jì)算二階偏導(dǎo)數(shù)及其逆陣， 計(jì)算量很大，但牛頓法具有二次收斂性，當(dāng)?shù)c(diǎn)接近最優(yōu)點(diǎn)時(shí)，收斂速度很快。 思考：若迭代過程先用梯度法，后用牛

9、頓法并避開牛頓法的海賽矩陣的逆矩陣的煩瑣計(jì)算，則可以得到一種較好的優(yōu)化方法，這就是“變尺度法”產(chǎn)生的基本構(gòu)想。 為此，綜合梯度法和牛頓法的優(yōu)點(diǎn)，提出變尺度法的基本思想。 變尺度法的基本迭代公式寫為下面的形式： xk+1 = xk - k A(k) f(xk) 式中的A(k)為構(gòu)造的n n階對(duì)稱矩陣，它是隨迭代點(diǎn)的位置的變化而變化的。若A(k) =I，上式為梯度法的迭代公式，若A(k) = H(xk)-1 ，上式為阻尼牛頓法的迭代公式。 變尺度法的搜索方向- A(k) f(xk) ，稱為擬牛頓方向。二、尺度矩陣的概念 通過坐標(biāo)變換可以改變函數(shù)的偏心程度，我們也稱之為尺度變換。尺度變換能顯著地改進(jìn)

10、幾乎所有極小化方法的收斂性質(zhì)。如用梯度法求f(x)=x12+25x22的極小值時(shí)， 需要迭代10次才能到達(dá)極小點(diǎn)x*=0 0T。若作變換 y1=x1 y2=5x2 則可以將函數(shù)的等值線由橢圓變?yōu)閳A，即(y)=y12+y22，從而消除了函數(shù)的偏心，用梯度法只需一次迭代即能求得極小點(diǎn)。對(duì)于一般二次函數(shù) 為減低函數(shù)二次項(xiàng)的偏心程度，進(jìn)行尺度變換 xQx則在新的坐標(biāo)系中，函數(shù)的二次項(xiàng)變?yōu)?若矩陣G是正定的，則總存在矩陣Q使 QTGQ=I將函數(shù)的偏心變?yōu)榱恪?用Q-1右乘等式兩邊，得 QTG=Q-1再用Q左乘等式兩邊，得 QQTG=I 所以 QQT=G-1 這說明二次函數(shù)矩陣G的逆陣，可以通過尺度變換矩

11、陣Q求得。 QQT實(shí)際上是在空間內(nèi)測(cè)量距離大小的一種度量，稱為尺度矩陣，記作A，即 A= QQT 例如向量x的長(zhǎng)度為 |x|=(xTx)1/2 尺度變換后，向量x對(duì)于尺度下的長(zhǎng)度為 |x|A = (Qx)T(Qx)1/2=xT(QQT)x1/2=(xTAx)1/2三、尺度變換矩陣的建立 根據(jù)變尺度法的基本原理，需要構(gòu)造一個(gè)變尺度矩陣序列Ak來逼近海賽逆矩陣序列Hk-1，每迭代一次，尺度改變一次。 為了建立變尺度矩陣Ak ，必須對(duì)其附加某些條件。 1、為保證迭代公式的下降性質(zhì)，要求Ak中的每一個(gè)矩陣都是對(duì)稱正定的。因?yàn)槿粢笏阉鞣较騍k= - Ak f(xk) 為下降方向，即要求 f(xk) T

12、 Sk 0，也就是 - f(xk) T Ak f(xk) 0 ，即Ak應(yīng)為對(duì)稱正定。 2、要求Ak之間的迭代具有簡(jiǎn)單的形式，顯然Ak+1= Ak+Ek為最簡(jiǎn)單的形式，其中Ek為校正矩陣。 3、要求必須滿足擬牛頓條件。 所謂擬牛頓條件，可以如下推導(dǎo)。 設(shè)迭代已經(jīng)進(jìn)行到k+1步，xk+1、 f(xk+1)均已經(jīng)求得，當(dāng)f(x)為具有正定矩陣G的二次函數(shù)時(shí)，根據(jù)泰勒展開得 f(xk+1) = f(xk) +H(xk)(xk+1-xK)即 H-1 (xk)( f(xk+1) - f(xk)=xk+1-xk令A(yù)k+1滿足類似上式的關(guān)系，也就是用Ak+1逼近H-1 (xk) 即 Ak+1( f(xk+1)

13、 - f(xk)=xk+1-xk 則Ak+1可以近似于H-1 (xk) ，因此把上式稱為擬牛頓條件，為簡(jiǎn)便起見，記 Gk= f(xk+1) - f(xk) xk= xk+1-xk 則擬牛頓條件變?yōu)?Ak+1 Gk = xk 四、變尺度法的一般步驟 1、選定初始點(diǎn)和收斂精度 2、計(jì)算初始點(diǎn)處的梯度，選取初始對(duì)稱正定矩陣A0，置k=0。 3、計(jì)算搜索方向Sk = - Ak f(xk) 4、沿Sk方向一維搜索，計(jì)算 f(xk+1) 、xk 、Gk 。 5、判斷是否滿足終止準(zhǔn)則，若滿足輸出最優(yōu)解，否則轉(zhuǎn)6。 6、當(dāng)?shù)鷑次還未找到極小點(diǎn)，重置Ak為單位矩陣，并以當(dāng)前點(diǎn)為初始點(diǎn)返回2，否則轉(zhuǎn)7。 7、計(jì)

14、算Ak+1= Ak+Ek ，置k=k+1返回3。五、DFP變尺度法 在變尺度法中，校正矩陣Ek取不同形式，就形成不同的變尺度法， DFP算法中的校正矩陣Ek取下列形式： Ek=k xk T+ Ak Gk vkT其中， k 、vk是待定向量。根據(jù)擬牛頓條件 Ak+1 Gk = xk 從而得到DFP算法中的校正公式例：用DFP法計(jì)算BFGS變尺度法 因?yàn)镈FP算法是用Ak逼近H-1 ，但在計(jì)算時(shí)由于舍入誤差和一維搜索的不精確，有可能導(dǎo)致Ak奇異，而使數(shù)值穩(wěn)定性方面不夠理想。所以1970年提出更穩(wěn)定的算法，稱為BFGS算法，它是用Bk逼近H，相應(yīng)的擬牛頓條件為 Gk = Bkxk其校正公式為例：用B

15、FGS法計(jì)算坐標(biāo)輪換法 坐標(biāo)輪換法屬于直接法，既可以用于無約束優(yōu)化問題的求解，又可以經(jīng)過適當(dāng)處理用于約束優(yōu)化問題求解。 坐標(biāo)輪換法是每次搜索只允許一個(gè)變量變化，其余變量保持不變，即沿坐標(biāo)方向輪流進(jìn)行搜索的尋優(yōu)方法。它把多變量的優(yōu)化問題輪流地轉(zhuǎn)化成單變量（其余變量視為常量）的優(yōu)化問題，因此又稱這種方法為變量輪換法。此種方法只需目標(biāo)函數(shù)的數(shù)值信息而不需要目標(biāo)函數(shù)的導(dǎo)數(shù)。一、坐標(biāo)輪換法的迭代過程 任取一初始點(diǎn)x0作為第一輪的始點(diǎn)x01,先沿第一坐標(biāo)軸的方向e1作一維搜索，用一維優(yōu)化方法確定最優(yōu)步長(zhǎng)11，得第一輪的第一個(gè)迭代點(diǎn)x11=x01+ 11 e1，然后以x11為新起點(diǎn)，沿第二坐標(biāo)軸的方向e2作

16、一維搜索，確定步長(zhǎng)21 ，得第一輪的第二個(gè)迭代點(diǎn)x21=x11+ 11 e2 第二輪迭代，需要 x1x21 x12 x21+ 12 e1 x22=x12+ 22 e2 依次類推，不斷迭代，目標(biāo)函數(shù)值不斷下降，最后逼近該目標(biāo)函數(shù)的最優(yōu)點(diǎn)。 二、終止準(zhǔn)則 可以采用點(diǎn)距準(zhǔn)則或者其它準(zhǔn)則。 注意： 若采用點(diǎn)距準(zhǔn)則或函數(shù)值準(zhǔn)則，其中采用的點(diǎn)應(yīng)該是一輪迭代的始點(diǎn)和終點(diǎn)，而不是某搜索方向的前后迭代點(diǎn)。 三、坐標(biāo)輪換法的流程圖給定：x0，K=1i=1X0k=x0沿ei方向一維搜索求xik=xi-1k+ ikeix=xk f=f(x)i=n?|xnk-x0k|?x*=xf*=f(x*)i=i+1x0=xnkk=

17、k+1NYNY四、小結(jié) 坐標(biāo)輪換法程序簡(jiǎn)單，易于掌握。但是計(jì)算效率比較低，尤其是當(dāng)優(yōu)化問題的維數(shù)較高時(shí)更為嚴(yán)重。一般把此種方法應(yīng)用于維數(shù)小于10的低維優(yōu)化問題。 對(duì)于目標(biāo)函數(shù)存在“脊線”的情況，在脊線的尖點(diǎn)處沒有一個(gè)坐標(biāo)方向可以使函數(shù)值下降，只有在銳角所包含的范圍搜索才可以達(dá)到函數(shù)值下降的目的，故坐標(biāo)輪換法對(duì)此類函數(shù)會(huì)失效。例：利用坐標(biāo)輪換法計(jì)算單純形法單純形法所謂單純形就是n維歐氏空間R n中具有n+1個(gè)頂點(diǎn)的凸多面體。例如一維空間中的線段；二維空間中的三角形；三維空間中的四面體。1、單純形法基本思路： 設(shè) x(0),x(1), x(n)是R n中n+1個(gè)點(diǎn)構(gòu)成的一個(gè)當(dāng)前的單純形。 假設(shè)求函

18、數(shù)的極小值。去掉x max，加入x(n+1)得到新的單純形。重復(fù)上述過程。設(shè) x(0),x(1), x(n)是R n中n+1個(gè)點(diǎn)構(gòu)成的一個(gè)當(dāng)前的單純形。比較各點(diǎn)的函數(shù)值得到：x max,x min使 f( x max)=maxf(x(0),f(x(1), ,f(x(n) f( x min)=minf(x(0),f(x(1), ,f(x(n) 取單純形中除去x max點(diǎn)外，其他各點(diǎn)的形心：幾點(diǎn)注意： 當(dāng)x(n+1)又是新單純形的最大值點(diǎn)時(shí)，取次大值點(diǎn)進(jìn)行反射； 若某一個(gè)點(diǎn)x出現(xiàn)在連續(xù)m個(gè)單純形中的時(shí)候，取各點(diǎn)與x連線的中點(diǎn)（n個(gè)）與x點(diǎn)構(gòu)成新的單純形，繼續(xù)進(jìn)行。 經(jīng)驗(yàn)上取 m 1.65n+0.0

19、5n2 例如：n=2時(shí)，可取m 1.65 2+0.05 4 =3.5 可取 m=4.12345789106111213優(yōu)點(diǎn)：不需求導(dǎo)數(shù)，不需要一維搜索。 缺點(diǎn)：無法加速，收斂慢，效果差。 2、改進(jìn)單純形法： （可變多面體算法） 設(shè)第k步迭代得到n+1個(gè)點(diǎn)： x(0),x(1), x(n) ，得到x max,x min及 通過下列4步操作選新迭代點(diǎn)： 1 反射： 取反射系數(shù) 0,(單純形法中 =1) 2 擴(kuò)展：給定擴(kuò)展系數(shù) 1,計(jì)算。（加速）若f(y(1) f(y(2), 那么y(2)取代x max; 否則， y(1)取代x max 。若maxf(x(i)| x(i) x max f(y(1)

20、f(x min), y(1)取代x max 。 3 收縮：若f(x max ) f(y(1) f(x(i), x(i) x max ,計(jì)算 以y(3)取代x max 。4 減半：若f(y(1) f(x max ), 重新取各點(diǎn)，使 x(i)= x min +1 2(x(i) - x min ) 得到新單純形。經(jīng)驗(yàn)上：=1,0.40.6, 2.33.0 . 有人建議:=1, =0.5， =2 。算法停機(jī)準(zhǔn)則?。豪豪脝渭冃畏ㄇ蠼狻ＤＪ剿阉鞣?模式搜索法是胡克 和基夫斯（Hooke & Jeeves ）1961年提出的?；舅枷肱c主要過程： 利用兩類移動(dòng)（探測(cè)性移動(dòng)和模式性移動(dòng)）進(jìn)行一步迭代：

21、探測(cè)性移動(dòng)的目的：探求一個(gè)沿各坐標(biāo)方向的新點(diǎn)并得到 一 個(gè)“有前途”的方向（下降的有利方向）； 模式性移動(dòng)的目的：沿上述“有前途”方向加速移動(dòng)。 考慮無約束最優(yōu)問題 min f(X) X Rn 主要過程：第k步迭代，設(shè)已得到x(k) 1探測(cè)性移動(dòng)： 給定步長(zhǎng)k ，設(shè)通過模式性移動(dòng)得到y(tǒng)(0), 依次沿各坐標(biāo)方向e(i)=(0, ,1,0, ,0)T i 移動(dòng)k步長(zhǎng)：i=0,1, ,n-1 , =y(i)+ke(i+1) 若f()f(y(i), 則 y(i+1) = ； 否則取 =y(i) -ke(i+1) 若f()f(y(i), 則 y(i+1) = ； 否則 y(i+1) = y(i) 最后

22、得到y(tǒng)(n) 。 若f(y(n) )f(x(k), 令x(k+1)=y(n). 將每一次探測(cè)性移動(dòng)后得到的點(diǎn)，作為下一次探測(cè)性移動(dòng)的開始點(diǎn)，經(jīng)過n次探測(cè)性移動(dòng)，一般地可以得到使f下降的點(diǎn)，這就完成了一次探測(cè)性移動(dòng)。每次探測(cè)性移動(dòng)的開始點(diǎn)稱為參考點(diǎn)。 設(shè)x(k+1)是以點(diǎn)x(k)為參考點(diǎn)進(jìn)行一次探測(cè)性移動(dòng)所得到的點(diǎn)。 若f(x(k+1) )f(x(k), 則從點(diǎn)x(k+1)出發(fā)作模式性移動(dòng)。 2模式性移動(dòng)： x(k+1) - x(k)為一個(gè)有前途的方向，取 y(0)= x(k+1) +(x(k+1) - x(k)=2 x(k+1) - x(k) 3 幾點(diǎn)措施： 若探測(cè)性移動(dòng)得到y(tǒng)(n)使f(y(

23、n) )f(x(k), 則跳過模式性移動(dòng)而令y(0)=x(k) 重新進(jìn)行探測(cè)性移動(dòng)，初始y(0)=x(1) ； 若y(n)= y(0) （即每一個(gè)坐標(biāo)方向的移動(dòng)都失?。瑴p小k ，重復(fù)上述過程。 當(dāng)進(jìn)行到k充分小（ k 0計(jì)算f=f(x) f1=f(y(0),i=1y(i)=y(i-1)+ e(i)計(jì)算f2=f(y(i)f2f1?f1=f2in?yesyes1Noi=i+12Noy(i)=y(i-1)+ (-)e(i)計(jì)算f2=f(y(i)f2f1?y(i)=y(i-1)yesNo2、算法： (續(xù))1f1f ?NoyesX=y(n), y(0)=2X -xx=X ,f=f(x)y(n)=x?N

24、oy(0)=xYes ?YesNo=0.1 2停；x為解例：用模式搜索法求解鮑威爾方法 鮑威爾方法是直接搜索法中一個(gè)十分有效的算法。該算法是沿著逐步產(chǎn)生的共軛方向進(jìn)行搜索的，它是以正定二次型為背景的共軛方向?yàn)榛A(chǔ)的一種方法，因此該方法本質(zhì)上是一種共軛方向法。是鮑威爾1964年提出的。一、原始鮑威爾基本算法 如圖所示，是二維二次目標(biāo)函數(shù)的無約束優(yōu)化問題。如圖所示，是三維二次目標(biāo)函數(shù)的無約束優(yōu)化問題。 原始鮑威爾基本算法的步驟： 第一環(huán)基本方向組取單位坐標(biāo)矢量系e1、 e2、 e3 、 en，沿這些方向依次作一維搜索，然后將始末兩點(diǎn)相連作為新生方向，再沿新生方向作一維搜索，完成第一環(huán)的迭代。以后每

25、環(huán)的基本方向組是將上環(huán)的第一個(gè)方向淘汰，上環(huán)的新生方向補(bǔ)入本環(huán)后而構(gòu)成。n維目標(biāo)函數(shù)完成n環(huán)的迭代過程稱為一輪。從這一輪的終點(diǎn)出發(fā)沿新生方向搜索所得到的極小點(diǎn)，作為下一輪迭代的始點(diǎn)。這樣就形成了算法的循環(huán)。 原始鮑威爾基本算法的缺陷： 可能在某一環(huán)迭代中出現(xiàn)基本方向組為線性相關(guān)的矢量系的情況。如第k環(huán)中，產(chǎn)生新的方向： pk=xnk-x0k= 1kp1k+ 2kp2k + + nkpnk 式中， p1k、p2k 、 、pnk為第k環(huán)基本方向組矢量,1k 、 2k 、 、nk為第k個(gè)基本方向的最優(yōu)步長(zhǎng)。 若在第k環(huán)的優(yōu)化搜索過程中出現(xiàn)1k =0，則方向pk表示為p2k 、 p3k 、 、pnk的

26、線性組合，以后的各次搜索將在降維的空間中進(jìn)行，無法得到n維空間的函數(shù)極小值，計(jì)算將失敗。 如圖所示為一個(gè)三維優(yōu)化問題的示例，設(shè)第一環(huán)中1 =0 ，則新生方向與e2 、e3共面，隨后的各環(huán)方向組中，各矢量必在該平面內(nèi)，使搜索局限于二維空間，不能得到最優(yōu)解。 原始鮑威爾基本算法的退化x1x2x31=01e23e3S1例：用原始powell法求解。二、鮑威爾修正算法 在某環(huán)已經(jīng)取得的n+1個(gè)方向中，選取n個(gè)線性無關(guān)的并且共軛程度盡可能高的方向作為下一環(huán)的基本方向組。 鮑威爾修正算法的搜索方向的構(gòu)造： 在第k環(huán)的搜索中， x0k 為初始點(diǎn)，搜索方向?yàn)閜1k、p2k 、 、 pnk，產(chǎn)生的新方向?yàn)閜k ，此方向的極小點(diǎn)為xk。點(diǎn) xn+1k=2xnk-x0k 為x0k對(duì)xnk的映射點(diǎn)。 計(jì)算x0k 、 x1k 、 、 xnk 、 xk、 x n+1k 各點(diǎn)的函數(shù)值，記作： F1=F(x0k) F2=F(xnk) F3=F(xn+1k) = F(xmk) -F(xm-1k) 是第k環(huán)方向組中，依次沿各方向搜索函數(shù)值下降最大值，即pmk方向函數(shù)下降最大。 為了構(gòu)造第k+1環(huán)基本方向組，采用如下判別式：