第八章 無約束多維問題的最優(yōu)化方法

1、第八章第八章 無約束多維問題的無約束多維問題的最優(yōu)化方法最優(yōu)化方法1 概述概述2 最速下降法最速下降法3 牛頓型方法牛頓型方法4 共軛方向及共軛方向法共軛方向及共軛方向法5 共軛梯度法共軛梯度法6 變尺度法變尺度法7 坐標(biāo)輪換法坐標(biāo)輪換法8 鮑威爾法鮑威爾法9 單形替換法單形替換法1 1 概概 述述 無約束優(yōu)化方法只考慮搜索的適行性，結(jié)合罰函數(shù)法，也可解約束優(yōu)化問題。目前，成熟可靠的優(yōu)化算法中，無約束優(yōu)化方法占多數(shù)，總體上無約束優(yōu)化方法的有效性及實用性都優(yōu)于約束優(yōu)化方法。 無約束優(yōu)化方法可分為兩大類：1)不求導(dǎo)數(shù)的，主要有隨機方法和直接搜索方法；2)求導(dǎo)數(shù)的，按所求導(dǎo)數(shù)的最高階數(shù)又可分為一階方

2、法和二階方法。二階方法很少采用。優(yōu)化算法的一般搜索迭代公式 xk+1= xk+xk xk+1= xk+kdk 注意，在搜索迭代中，由于一維搜索需增加大量計算，因此，并不是所有優(yōu)化方法都采用一維搜索。2 2 最速下降法最速下降法 (1)以負(fù)梯度方向作為搜索方向并作一維搜索，因此又稱為“梯度法”，屬于求導(dǎo)數(shù)的間接法。它的基本思想早在1847年就已提出。盡管它本身不再被認(rèn)為是一種有效的方法，但它是許多優(yōu)化方法尤其是二次收斂方法的基礎(chǔ)。 各點的梯度一般各不相同，因此“最速下降方向”僅對某一點附近而言，它具有局部性質(zhì)。 當(dāng)作一維搜索時，搜索方向是與目標(biāo)函數(shù)等值線相切的，而切點的梯度方向是與等值線正交的。

3、因此，相鄰兩次搜索方向相互垂直，搜索路徑呈嚴(yán)重的“之”字形，特別是目標(biāo)函數(shù)接近二次型時更為明顯。 可以利用梯度矢量在極值點為零這一重要性質(zhì)設(shè)立收斂準(zhǔn)則 f(x*) 2 2 最速下降法最速下降法 或nixfii, 2 , 1 數(shù)值微分在優(yōu)化中是一個非常重要的問題，對優(yōu)化結(jié)果影響較大。具體作法是用 代替 ，其中xfxf f = f f0式中，f0 = f(x0)，是計算偏導(dǎo)數(shù)那點 x0 處的目標(biāo)函數(shù)值； f = f(x) = f(x1, x2, , xi+xi, , xn)，是其它變量保持不變，xi 變化為 xi+xi 時的目標(biāo)函數(shù)值。 xi = 0.001(ui li) ui 和 li 分別為變

4、量 xi 的估計上限和下限。xfxf盡可能接近，xi 應(yīng)取得小一些，但過小又 為使會引起舍入誤差。一般可取2 2 最速下降法最速下降法 求 f(x1, x2) = x12+25x22 的極小點。 取初始點 x0 =2 2T，則 f(x0) =104 f(x0) =4 100T 沿負(fù)梯度即-4 -100T方向進(jìn)行一維搜索，有 x1 = x0 0 f(x0) =2 2T 04 100T = 2 40 2 1000T 在x1點 f(x1, x2) =(2 40)2+25(2 1000)2 =(0) 令(0) = 0，有 2(2 40) (-4)+50(2 1000) (-100) = -16+320

5、 10000 +5000000 = 5000320 10016 = 0 0 = 0.020030718 得到第一次迭代的結(jié)果： x1 = 2 40 2 1000T= 1.919877 -3.0718034-2T f(x1) =3.686164 經(jīng)過十次迭代，得到最優(yōu)解： x* = 0 0T f(x* ) =03 3 牛頓型方法牛頓型方法 是用目標(biāo)函數(shù)二階偏導(dǎo)數(shù)的間接方法，因類似于解非線性方程的牛頓法而得名，又叫“二階導(dǎo)數(shù)法”、“擬線性法”。 將目標(biāo)函數(shù)泰勒展開，保留到二次項，原目標(biāo)函數(shù)就轉(zhuǎn)變?yōu)橄铝卸涡秃瘮?shù)： f(xk)+2f(xk)(x* xk) = 0 對于二次型函數(shù)，從理論上來說，牛頓法

6、從任選初始點一步就能收斂到最優(yōu)點。但對于目標(biāo)函數(shù)不是二次型，或計算機截斷誤差的影響，往往需要多次迭代才能得到最優(yōu)點。牛頓法的迭代公式為： xk+1 = xk 2f(xk)-1f(xk) (k=0, 1, 2, )2f(xk)為f(x)在xk點處的海賽矩陣。21 f(x) (x)= f(xk)+f(xk)T(x xk)+ (xxk)T2f(xk)(xxk) 為求極值點，對上式求偏導(dǎo)數(shù)，并令xf=0，得到3 3 牛頓型方法牛頓型方法 為防止牛頓法收斂到極大點而不是極小點，可在迭代過程中作一維搜索，形成改進(jìn)的牛頓法“阻尼牛頓法”。 牛頓法的最大缺點是需要計算海賽矩陣，并求其逆矩陣，計算量很大。 用牛

7、頓法求 f(x1, x2) = x12+25x22 的極小點。 取 x0 = 2 2T f(x0) = 2x10 50 x20 T = 4 100T 50100215000210202xxff3 3 牛頓型方法牛頓型方法 因為f(x1, x2)是二次型函數(shù)，用牛頓迭代公式，一步就可達(dá)到最優(yōu)點： 對照梯度法和牛頓法迭代公式，可以看出只相差一項海賽矩陣的逆矩陣。因此，牛頓法是對梯度法的進(jìn)一步修正。事實上，梯度法是對目標(biāo)函數(shù)f(x)在點xk的一階(線性)近似，而牛頓法是對f(x)在點xk 的二階(二次)近似。000100501401000421221004501002122xxfTTTTT4 4 共

8、軛方向及共軛方向法共軛方向及共軛方向法 二次正定函數(shù)的一般形式為：式中，G為 nn 階對稱正定矩陣，b=b1, b2, ,bnT 為常矢量，c為常數(shù)。 對于矩陣 G，若存在兩個 n 維非零矢量 d0 和 d1，使 (d0)TGd1=0成立，則稱d0和d1是(或G共軛矢量)。特別地，當(dāng)G為單位矩陣時，(d0)Td1=0 ，則稱d0 和d1是的。矢量正交是矢量共軛的特例。 cfTTxbGxxx214 4 共軛方向及共軛方向及共軛方向法共軛方向法x1x2 如n=2，二次函數(shù)的等值線為一同心橢圓族，它的極小點就是橢圓中心。該橢圓族有一重要性質(zhì)，即兩平行線與橢圓的兩個切點的連線必過橢圓族的中心，且連線與

9、平行線的方向是共軛的(見下圖)。4 4 共軛方向及共軛方向法共軛方向及共軛方向法 因此，從任一點出發(fā)，沿任意方向作一維搜索找到的極小點就是橢圓的切點，再沿共軛方向作一維搜索找到的極小點就是橢圓中心也就是目標(biāo)函數(shù)的極小點。這說明，對二維二次正定目標(biāo)函數(shù)只要沿共軛方向作兩次一維搜索就可得到其極小點。 推廣到n維，若采用共軛方向作為搜索方向，任何一個具有極小值的n維二次正定目標(biāo)函數(shù)，理論上最多只要n步就能達(dá)到極小點且與所用搜索方向的次序無關(guān)。這種性質(zhì)稱為“”，利用這種性質(zhì)的優(yōu)化方法稱為。4 4 共軛方向及共軛方向法共軛方向及共軛方向法 共軛方向是一大類方法，包括共軛梯度法，Powell法等。其中一種

10、產(chǎn)生共軛方向的方法為格拉姆斯密特 (GramSchmidt)法。 比較有效的共軛方向法都盡量避免計算海賽矩陣。5 5 共軛梯度法共軛梯度法 gk = Gxk + b 前面已給出優(yōu)化算法的搜索迭代公式： xk+1= xk+kdk 若進(jìn)行一維搜索，k 則為最優(yōu)步長因子。 xk 和xk+1 兩點負(fù)梯度方向的差為 gk+1 gk = G(xk+1 xk) = G(xk+kdk xk)=k Gdk 若dk+1 和 dk 是G 共軛方向，則 (dk+1)TG dk = 0 用(dk+1)T前乘 (gk+1 gk)，有 (dk+1)T(gk+1 gk) = k(dk+1)TGdk = 0 即 dk+1與(g

11、k+1 gk)正交。 二次正定函數(shù) cfTTxbGxxx21在 xk 點的梯度為 5 5 共軛梯度法共軛梯度法 上式表明：。因此，利用這個性質(zhì)，不必計算矩陣G 即可求出共軛梯度法的共軛方向。Xk+2xkxk+1gkgk+1gk+1 gkdkdk+15 5 共軛梯度法共軛梯度法 設(shè)從xk出發(fā)，沿dk=-gk 方向作一維搜索到 xk+1點，并算出xk+1點的梯度方向gk+1。由于gk+1 是沿等直面在該點的法線方向，而dk是沿等直面在該點的切線方向，故(dk)Tgk+1= 0，即 ，。 為了在 gk+1 和 gk 構(gòu)成的正交系中確定共軛方向dk+1，令 dk+1 = -gk+1+k dk 即把共軛

12、方向dk+1看成-gk+1與 dk的線性組合，k 為待定系數(shù)。要使dk+1與dk 共軛，就應(yīng)使 (dk+1)TGdk =0而 (dk+1)TGdk =(-gk+1+kdk)TGdk =(-gk+1 kgk)TG(-gk ) =gk+1TGgk+k gkTGgk =05 5 共軛梯度法共軛梯度法 因此kTkkTkkGggGgg1 前面已推導(dǎo)出 gk+1 gk = k Gdk，即 gk+1 gk = -kGgk或代入上式得kkkkggGg122111111111111100kkkTkkTkkTkkTkkTkkTkkTkkTkkkTkkkTkkTkkTkkgggggggggggggggggggggg

13、ggGggGgg5 5 共軛梯度法共軛梯度法 因此,下一個搜索方向確定為kkkkkkkkdgggdgd221111 同樣,可以證明按上述公式確定的 dk+2與dk+1為共軛方向，依此類推而確定的 n個dk (k=0,1,2,n-1)方向為一組關(guān)于G的。上述結(jié)論也可由數(shù)學(xué)歸納法證明。 最后，我們得到共軛梯度法的迭代公式為 x k+1 = x k+k dk式中 dk = -gk+k-1 dk-12121kkkgg 在迭代中第一次搜索方向 d0 取 x0 的負(fù)梯度方向-g0。5 5 共軛梯度法共軛梯度法 與梯度法相比，由于修正項kdk 改進(jìn)了收斂性，使搜索方向共軛，故能以較少的迭代次數(shù)收斂到最優(yōu)點。

14、 由于計算梯度時很可能出現(xiàn)誤差，使搜索方向不能完全保持共軛，同時目標(biāo)函數(shù)也可能不是正定的二次函數(shù)，因此n次迭代后一般都不會達(dá)到精確的極小點。可在每n次迭代后令 d0 = dn = -gn作為下一輪迭代的第一次搜索方向，重新開始新一輪迭代。 上述共軛梯度法又稱。而PRP(Polak-Ribiere-Poiyak)共軛梯度法按下式計算k-1：1111kTkkTkkkggggg5 5 共軛梯度法共軛梯度法 1)給定變量個數(shù)n，選取收斂精度和初始點x0，計算x0點的梯度 g0，取第一次搜索方向d0 = -g0 ，令k = 0。 2)沿dk方向作一維搜索，得到 xk+1點，xk+1= xk+k dk 。

15、 k k +1。轉(zhuǎn)2)繼續(xù)進(jìn)行迭代。2121kkkgg則結(jié)束迭代，輸出當(dāng)前點作為最優(yōu)點。否則，若k=n，dk= -gk，k0，轉(zhuǎn)2)進(jìn)行新一輪迭代。若kn，dk按下式計算: dk=-gk+k-1dk-1，其中kg 3)計算當(dāng)前點的梯度 gk ，若迭代收斂準(zhǔn)則成立，5 5 共軛梯度法共軛梯度法 用共軛梯度法求f(x1, x2) = x12+2x22 4x1 2x1x2的極小點。 取 x0 = 1 1T d0 = -g0 = -2x1 2x2 4 4x2 2x1x0 = 4 -2T 沿 d0 進(jìn)行一維搜索 x1 = x0+0 d0 =1 1T+04 -2T = 1+40 1 20T 在x1點 f(

16、x1, x2) =(1+40)2+2(1-20)2 4(1+40) 2(1+40)(1 20) 令df/d0 = 0，有 8(1+40) 8(1 20) 16 2(2 160) = 8+320 8+160 16 4+320 = 800 20 = 0 0 = 0.25 x1 = 2 0.5T g1 = 2x1 2x2 4 4x2 2x1x1 = -1 -2T 25. 020500110ggggTT5 5 共軛梯度法共軛梯度法 d1 = -g1+0 d0 = 2 1.5T 沿d1 進(jìn)行一維搜索 x2 = x1+1d1=2 0.5T+12 1.5T = 2+21 0.5+1.51T 在 x2點 f(

17、x1, x2) =(2+21)2+2(0.5+1.51)2 4(2+21) 2(2+21)(0.5+1.51)令 df/d1 = 0，有 4(2+21)+6(0.5+1.51) 8 2(4+61) = 8+81+3+91 8 8 121 = 51 5 = 0 1 = 1 x2 = 4 2T 因為 g2 = 0 0T，且在 x2 點處海賽矩陣正定，故 x2 為極小點。 x* = x2 = 4 2T f(x*) = -86 6 變尺度法變尺度法 又被稱為“擬牛頓法”、“大步梯度法”、“共軛方向法”，其中最有名的是DFP算法。 變尺度法是在牛頓法的基礎(chǔ)上演變發(fā)展的，但它是一階方法，不求二階偏導(dǎo)數(shù)，而

18、是用一個矩陣近似表示海賽矩陣的逆矩陣，然后在搜索迭代過程中不斷修正這個矩陣，使它逐步逼近海賽矩陣的逆矩陣。 通過可改進(jìn)收斂性。對于一般二次函數(shù) cfTTxbGxxx21 進(jìn)行尺度變換 xQx，則二次項GQxQxGxxTTT2121若G正定，則總存在矩陣Q使 QTGQ = II 為單位矩陣。6 6 變尺度法變尺度法 用Q-1左乘等式兩邊，再用Q左乘等式兩邊，得到 QQTG = I即 QQT = G-1令 H = QQTH 稱為，要求H 正定。則牛頓法迭代公式變?yōu)?xk+1 = xk kHf(xk) (k=0, 1, 2, ) 用尺度矩陣逼近海賽矩陣的逆矩陣G -1，則構(gòu)成一個尺度矩陣序列Hk。因

19、此，尺度在不斷變化，迭代公式為 xk+1 = xk k Hk gk (k=0, 1, 2, ) gk f(xk)6 6 變尺度法變尺度法 對Hk的要求：1) Hk應(yīng)對稱正定。2) Hk之間的迭代應(yīng)具有下列簡單的形式： H k+1 = H k+ Ek Ek為nn 階矩陣，稱為。3) Hk必須滿足擬牛頓條件 H k+1 yk = sk yk gk+1 gk sk xk+1 xk6 6 變尺度法變尺度法 根據(jù)校正公式中Ek選取的不同，形成不同的變尺度法，其中最著名的為DFP算法。DFP算法中Ek取下列形式： Ek = k uk ukT+k vk vkT式中k、k 為待定常數(shù)，uk、vk 是n維待定向

20、量，ukukT 和 vkvkT 都是對稱、秩為1的n n 階矩陣。 取k 、k 、uk、vk，使它們滿足： kuk ukTyk = sk k vk vkTyk =-Hk yk注意到uyk和vyk均為1 1階矩陣即常量，可取 uk = sk vk = Hk yk定出 kkTkkkkTkyHyys116 6 變尺度法變尺度法 因此，DFP算法校正公式為 用DFP法求f(x1, x2) = x12+2x22 4x1 2x1x2的最優(yōu)解。 1)取x0 = 1 1T k=0 g0 = -4 2T H0 = I d0 = - H0 g0 = 4 -2T 沿d0進(jìn)行一維搜索 x1 = x0+0 d0 = 1

21、+40 1 20T 令df/d0 = 0, 得到 0 = 0.25， x1 = 2 0.5T 2) k = 1 g1 = -1 -2T y0 = g1 g0 = 3 -4T s0 = x1 x0 = 1 -0.5T kkTkkTkkkKTkTkKKKyHyHyyHysssHH16 6 變尺度法變尺度法 d1 = - H1 g1 = 0.84+0.76 0.38+0.82T= 1.6 1.2T x2 = x1+1 d1 = 2+1.61 0.5+1.21T 令df/d1 = 0, 得到 1 = 1.25， x2 = 4 2T 3) g2 = 0 0T41. 038. 038. 084. 0161

22、212925125. 05 . 05 . 0151100143434343435 . 015 . 015 . 0110010000000000100yHyHyyHysssHHTTTT (x2)T2f(x2)x2 = 4 0 4 2T =16 0 2f(x2) 正定 x* = x2 = 4 2T f(x*) = -8422222xf7 7 坐標(biāo)輪換法坐標(biāo)輪換法 坐標(biāo)輪換法屬于不求導(dǎo)數(shù)的直接搜索法。它的基本思想是取x的n個坐標(biāo)方向作為搜索方向，即從x0出發(fā)，第一次搜索沿x1坐標(biāo)方向，第二次搜索沿x2坐標(biāo)方向，第n次搜索沿xn坐標(biāo)方向，第n+1次搜索沿x1坐標(biāo)方向，依次類推。搜索不斷沿坐標(biāo)方向輪換進(jìn)

23、行，直到收斂條件被滿足。坐標(biāo)輪換法一般不作一維搜索。 坐標(biāo)輪換法的算法如下： 1)選取初始點x0(x0又稱為)，初始步長xi，收斂精度i。一般初始步長可取為變量估計變動范圍(uili) 的1/100，收斂精度i可取為初始步長xi的1/100。令k=0。 2) k k+1。進(jìn)行一輪依次沿坐標(biāo)方向的。先給x1 一個增量x1，其它變量保持不變，得到一個試驗點Tknkksxxxx112111,x7 7 坐標(biāo)輪換法坐標(biāo)輪換法 檢驗 xs 的適行性。若f(xs) f(xk-1)，則xs 就作為下一個坐標(biāo)方向搜索的起點；否則，從xk-1點沿反方向搜索Tknkksxxxx112111,x 若兩個方向的搜索都失

24、敗了，則停在原來的點不動。 接著，以步長x2沿x2坐標(biāo)方向搜索，直到 xn為止。此輪探查搜索的終點稱為xBk。 3)作 (Pattern Move) 到點xMk。模式移動的方向是從前一個基點xBk-1到當(dāng)前基點xBk，移動量是兩基點之間的距離，即 檢驗?zāi)Ｊ揭苿拥倪m行性。若f(xMk)f(xBk)，則xMk就作為下一輪搜索的起點；否則，取消此次模式移動，xBk作為下一輪搜索的起點。1kBkBkBkMxxxx7 7 坐標(biāo)輪換法坐標(biāo)輪換法 4)重復(fù)2)、3)的搜索模式移動的循環(huán)，直到各個坐標(biāo)方向探查搜索都失敗，仍停留在原基點不動為止。檢驗收斂準(zhǔn)則 xiI 是否滿足。若不滿足，則將各變量步長xi (i

25、 =1, 2, n) 都減少一半，重新開始新一輪探查搜索；若滿足，則輸出最優(yōu)點x*= xBk。 用坐標(biāo)輪換法解 f(x) = x12+x226(x1 + x2) + x3min. 求經(jīng)過一輪探查搜索和模式移動后的終點xM(1)。 1)選取變量估計下限xl = 0 0 0T，變量估計上限xu = 10 10 10T，初始點x0 = xB(0)=5 5 5T，初始步長x1=x2= x3= 0.1，收斂精度1= 2= 3= 0.001 。求出 f0 =f(x0) = -5 2)進(jìn)行探查搜索。 向正向搜索：xs = 5.1 5 5T，f(xs) = -4.59 （不適行） 向反向搜索：xs = 4.9

26、 5 5T，f(xs) = -5.39 （適行）7 7 坐標(biāo)輪換法坐標(biāo)輪換法 向正向搜索：xs = 4.9 5.1 5T，f(xs) = -4.98 （不適行） 向反向搜索：xs = 4.9 4.9 5T，f(xs) = -5.78 （適行） 向正向搜索：xs = 4.9 4.9 5.1T，f(xs) = -5.68 （不適行） 向反向搜索：xs = 4.9 4.9 4.9T，f(xs) = -5.88 （適行） 因此，xB(1)= 4.9 4.9 4.9T，f(xB(1) = -5.88。 3)作模式移動 xM(1)= xB(1)+(xB(1) xB(0) ) =4.9 4.9 4.9T+(

27、4.9 4.9 4.9T 5 5 5T) =4.9 4.9 4.9T+-0.1 -0.1 -0.1T =4.8 4.8 4.8T 由于f(xM(1)=-6.72 f(xB(1)，因此模式移動滿足適行性，點4.8 4.8 4.8T 作為下一輪探查搜索的起點。 7 7 坐標(biāo)輪換法坐標(biāo)輪換法 坐標(biāo)輪換法被認(rèn)為是目前最成功的優(yōu)化算法之一，至今仍被廣泛應(yīng)用著。國外有些專家曾以工程實際中實際提出的優(yōu)化設(shè)計問題作為考題，對各種優(yōu)化方法進(jìn)行專門研究對比，坐標(biāo)輪換法是名列前茅的算法之一。坐標(biāo)輪換法的缺點是有時收斂較慢。由于其搜索方向是固定的，如果恰好遇到某些約束曲面的走向?qū)λ乃阉魈貏e不利時，往往會在接近最優(yōu)點

28、之前，“粘”在約束邊界上中止收斂而得到一個假最優(yōu)點。針對這個缺點，已提出了一些改進(jìn)措施。如:；8 8 鮑威爾法鮑威爾法 (Powell)法的搜索方向是共軛的，但不需要計算目標(biāo)函數(shù)的導(dǎo)數(shù)，這是它的一大優(yōu)點。 二次正定函數(shù) cfTTxbGxxx21在xk 和xk+1點的梯度為 gk = Gxk + b gk+1 = Gxk+1 + b gk+1 gk = G(xk+1 xk ) = Gdk 設(shè)xk、xk+1為沿同一方向dj進(jìn)行一維搜索得到的兩個極小點，因此dj和梯度方向正交(圖4-15)，有 (dj)T gk = 0 (dj)T gk+1 = 0 根據(jù)共軛方向的定義(式4-11)，有 (dj)T

29、(gk+1 gk ) = (dj)TG dk = 0 因此，dj和dk是G共軛方向。8 8 鮑威爾法鮑威爾法 圖4-17為 Powell 法搜索過程。 1) 任選一初始點x0，確定收斂精度，選擇坐標(biāo)軸方向ei (i= 1,2, . ,n)為第一輪搜索方向，令k = 0, xB(0) = x0。 2) k k+1。從xB(k-1)出發(fā)，分別沿ei (i= 1,2, . ,n)作一維搜索，此輪搜索的終點為xB(k) 。 3) 作模式移動。沿dk = xB(k) xB(k-1)作一維搜索，得到xk，作為下一輪搜索的起點。 4) 檢驗收斂準(zhǔn)則。如滿足則輸出當(dāng)前點xk作為最優(yōu)點。 5) 若未收斂，則重復(fù)

30、2)、3) 的一維搜索和模式移動，但每一輪一維搜索中都用上一輪模式移動方向代替原有的一個坐標(biāo)軸方向。如第二輪搜索方向為e2, e3, en, d1，依次類推。8 8 鮑威爾法鮑威爾法 框圖見圖4-18。在每一輪搜索后，模式移動與坐標(biāo)輪換法的相同而不作一維搜索。另外增加了Powell 判別條件，若滿足判別式，則用模式移動方向替換目標(biāo)函數(shù)值下降量最大的一個方向，以保證下一輪搜索方向組線性無關(guān)。 用Powell法求f(x1, x2) =10(x1+x2 5) 2+(x1 x2)2 的極小值。 選取x0(0) = 0 0T，F(xiàn)0 = f0 = 250。第一輪搜索：第一輪搜索： 1) 沿e1 = 1 0

31、T方向作一維搜索，得到 x1(0) =4.5455 0T, f1=22.727, 1= f0 f1 =227.273。 2) 沿e2 = 0 1T方向作一維搜索，得到x2(0) = 4.5455 0.8264T, F2 = f2=15.214, 2= f1 f2 =7.513, m = 1= 227.273。 3) 模式移動: x3(0) =2 x2(0) x0(0) = 9.091 1.6528T F3 = f(x3(0) = 385.248 8 鮑威爾法鮑威爾法 4) 檢驗Powell 判別條件。因為 F3 F0，因此下一輪搜索方向仍用e1 、e2方向。因為 F2 F3，因此x2(0)作為

32、下一輪搜索的起點。第二輪搜索：第二輪搜索： 起點x0(1) = x2(0) = 4.5455 0.8264T, F0 = f0=15.214。 1) 沿e1=1 0T方向作一維搜索，得到x1(1) = 3.8693 0.8264T, F1= f1=10.185, 1= f0 f1 =5.029。 2) 沿e2 = 0 1T方向作一維搜索，得到x2(1) = 3.8693 1.3797T, F2 = f2=6.818, 2= f1 f2 =3.367, m = 1= 5.029。 3) 模式移動: x3(1) =2 x2(1) x0(1) = 3.1931 1.9330T F3 = f(x3(1

33、) = 1.747 4) 檢驗Powell 判別條件。因為 F3 F0 且(F0 2F2+F3 ) (F0 F2 m)2 0.5m (F0 F3)2，故用模式移動方向 d3(1) = x2(1) x0(1) = -0.6762 0.5533T代替e1。沿d3(1)方向作一維搜索，得到下一輪搜索的起點： x0(2) = 2.49995 2.5091T F0 = f0 = 0.0008 若不滿足收斂準(zhǔn)則，則再進(jìn)行第三輪搜索。9 9 單形替換單形替換法法 又稱Simplex)法，屬于直接搜索方法。 就是在n維空間中由n+1個頂點構(gòu)成的形體。在優(yōu)化搜索過程中要滿足適行性，就要對目標(biāo)函數(shù)的變化趨勢有大概

34、的估計，避免盲目選擇搜索方向。可以根據(jù)若干點的目標(biāo)函數(shù)值大小的變化推測這種趨勢，這些點可取為單純形的頂點。單純形的基本思想是利用單純形的頂點構(gòu)造有利的搜索方向和步長，用新的較好點取代原來較差的點，構(gòu)成新的單純形，不斷向最優(yōu)點逼近。 假定在一個二維問題中，已求得不在一條直線上的三個點H、S、L，及它們的目標(biāo)函數(shù)值fH、fS、fL，且fH fS fL。這三點構(gòu)成一個單純形三角形。如有更好點，則在最差點H的反對稱方向可能性最大。9 9 單形替換單形替換法法 因此，取S和L兩點的中點M，從H出發(fā)沿H和M的連線作模式移動到A點。然后舍棄H點，剩下的S、L和A又構(gòu)成一個單純形。推廣到n維的情況，仍在單純形的n+1個頂點中取三個點。H為最差點，S為次差點、L為最好點，M為除H點外其它各點的中點(或稱“重心”)，模式移動的方向仍在過H和M的連線上。 1) 建立初始單純形。選擇一個初始點x0，再依次改變其中一個變量的值，給變量一個事先確定的步長xj，得到另外n個點xi (i = 1, 2, . , n)。每個點由下兩式確定： xj (1) = xj (0) +xj ( j = i ) xj