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

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

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

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

4、量 xi 的估計上限和下限。xfxf盡可能接近，xi 應取得小一些，但過小又 為使會引起舍入誤差。一般可取2 2 最速下降法最速下降法 求 f(x1, x2) = x12+25x22 的極小點。 取初始點 x0 =2 2T，則 f(x0) =104 f(x0) =4 100T 沿負梯度即-4 -100T方向進行一維搜索，有 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 得到第一次迭代的結果： 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 牛頓型方法牛頓型方法 是用目標函數(shù)二階偏導數(shù)的間接方法，因類似于解非線性方程的牛頓法而得名，又叫“二階導數(shù)法”、“擬線性法”。 將目標函數(shù)泰勒展開，保留到二次項，原目標函數(shù)就轉變?yōu)橄铝卸涡秃瘮?shù)： f(xk)+2f(xk)(x* xk) = 0 對于二次型函數(shù)，從理論上來說，牛頓法

6、從任選初始點一步就能收斂到最優(yōu)點。但對于目標函數(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) 為求極值點，對上式求偏導數(shù)，并令xf=0，得到3 3 牛頓型方法牛頓型方法 為防止牛頓法收斂到極大點而不是極小點，可在迭代過程中作一維搜索，形成改進的牛頓法“阻尼牛頓法”。 牛頓法的最大缺點是需要計算海賽矩陣，并求其逆矩陣，計算量很大。 用牛

7、頓法求 f(x1, x2) = x12+25x22 的極小點。 取 x0 = 2 2T f(x0) = 2x10 50 x20 T = 4 100T 50100215000210202xxff3 3 牛頓型方法牛頓型方法 因為f(x1, x2)是二次型函數(shù)，用牛頓迭代公式，一步就可達到最優(yōu)點： 對照梯度法和牛頓法迭代公式，可以看出只相差一項海賽矩陣的逆矩陣。因此，牛頓法是對梯度法的進一步修正。事實上，梯度法是對目標函數(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共軛矢量)。特別地，當G為單位矩陣時，(d0)Td1=0 ，則稱d0 和d1是的。矢量正交是矢量共軛的特例。 cfTTxbGxxx214 4 共軛方向及共軛方向及共軛方向法共軛方向法x1x2 如n=2，二次函數(shù)的等值線為一同心橢圓族，它的極小點就是橢圓中心。該橢圓族有一重要性質，即兩平行線與橢圓的兩個切點的連線必過橢圓族的中心，且連線與

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

10、產(chǎn)生共軛方向的方法為格拉姆斯密特 (GramSchmidt)法。 比較有效的共軛方向法都盡量避免計算海賽矩陣。5 5 共軛梯度法共軛梯度法 gk = Gxk + b 前面已給出優(yōu)化算法的搜索迭代公式： xk+1= xk+kdk 若進行一維搜索，k 則為最優(yōu)步長因子。 xk 和xk+1 兩點負梯度方向的差為 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 共軛梯度法共軛梯度法 上式表明：。因此，利用這個性質，不必計算矩陣G 即可求出共軛梯度法的共軛方向。Xk+2xkxk+1gkgk+1gk+1 gkdkdk+15 5 共軛梯度法共軛梯度法 設從xk出發(fā)，沿dk=-gk 方向作一維搜索到 xk+1點，并算出xk+1點的梯度方向gk+1。由于gk+1 是沿等直面在該點的法線方向，而dk是沿等直面在該點的切線方向，故(dk)Tgk+1= 0，即 ，。 為了在 gk+1 和 gk 構成的正交系中確定共軛方向dk+1，令 dk+1 = -gk+1+k dk 即把共軛

12、方向dk+1看成-gk+1與 dk的線性組合，k 為待定系數(shù)。要使dk+1與dk 共軛，就應使 (dk+1)TGdk =0而 (dk+1)TGdk =(-gk+1+kdk)TGdk =(-gk+1 kgk)TG(-gk ) =gk+1TGgk+k gkTGgk =05 5 共軛梯度法共軛梯度法 因此kTkkTkkGggGgg1 前面已推導出 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)方向為一組關于G的。上述結論也可由數(shù)學歸納法證明。 最后，我們得到共軛梯度法的迭代公式為 x k+1 = x k+k dk式中 dk = -gk+k-1 dk-12121kkkgg 在迭代中第一次搜索方向 d0 取 x0 的負梯度方向-g0。5 5 共軛梯度法共軛梯度法 與梯度法相比，由于修正項kdk 改進了收斂性，使搜索方向共軛，故能以較少的迭代次數(shù)收斂到最優(yōu)點。

14、 由于計算梯度時很可能出現(xiàn)誤差，使搜索方向不能完全保持共軛，同時目標函數(shù)也可能不是正定的二次函數(shù)，因此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。轉2)繼續(xù)進行迭代。2121kkkgg則結束迭代，輸出當前點作為最優(yōu)點。否則，若k=n，dk= -gk，k0，轉2)進行新一輪迭代。若kn，dk按下式計算: dk=-gk+k-1dk-1，其中kg 3)計算當前點的梯度 gk ，若迭代收斂準則成立，5 5 共軛梯度法共軛梯度法 用共軛梯度法求f(x1, x2) = x12+2x22 4x1 2x1x2的極小點。 取 x0 = 1 1T d0 = -g0 = -2x1 2x2 4 4x2 2x1x0 = 4 -2T 沿 d0 進行一維搜索 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 進行一維搜索 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算法。 變尺度法是在牛頓法的基礎上演變發(fā)展的，但它是一階方法，不求二階偏導數(shù)，而

18、是用一個矩陣近似表示海賽矩陣的逆矩陣，然后在搜索迭代過程中不斷修正這個矩陣，使它逐步逼近海賽矩陣的逆矩陣。 通過可改進收斂性。對于一般二次函數(shù) cfTTxbGxxx21 進行尺度變換 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，則構成一個尺度矩陣序列Hk。因

19、此，尺度在不斷變化，迭代公式為 xk+1 = xk k Hk gk (k=0, 1, 2, ) gk f(xk)6 6 變尺度法變尺度法 對Hk的要求：1) Hk應對稱正定。2) Hk之間的迭代應具有下列簡單的形式： 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進行一維搜索 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 坐標輪換法坐標輪換法 坐標輪換法屬于不求導數(shù)的直接搜索法。它的基本思想是取x的n個坐標方向作為搜索方向，即從x0出發(fā)，第一次搜索沿x1坐標方向，第二次搜索沿x2坐標方向，第n次搜索沿xn坐標方向，第n+1次搜索沿x1坐標方向，依次類推。搜索不斷沿坐標方向輪換進

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

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

25、 =1, 2, n) 都減少一半，重新開始新一輪探查搜索；若滿足，則輸出最優(yōu)點x*= xBk。 用坐標輪換法解 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)進行探查搜索。 向正向搜索：xs = 5.1 5 5T，f(xs) = -4.59 （不適行） 向反向搜索：xs = 4.9

26、 5 5T，f(xs) = -5.39 （適行）7 7 坐標輪換法坐標輪換法 向正向搜索：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 坐標輪換法坐標輪換法 坐標輪換法被認為是目前最成功的優(yōu)化算法之一，至今仍被廣泛應用著。國外有些專家曾以工程實際中實際提出的優(yōu)化設計問題作為考題，對各種優(yōu)化方法進行專門研究對比，坐標輪換法是名列前茅的算法之一。坐標輪換法的缺點是有時收斂較慢。由于其搜索方向是固定的，如果恰好遇到某些約束曲面的走向對它的搜索特別不利時，往往會在接近最優(yōu)點

28、之前，“粘”在約束邊界上中止收斂而得到一個假最優(yōu)點。針對這個缺點，已提出了一些改進措施。如:；8 8 鮑威爾法鮑威爾法 (Powell)法的搜索方向是共軛的，但不需要計算目標函數(shù)的導數(shù)，這是它的一大優(yōu)點。 二次正定函數(shù) cfTTxbGxxx21在xk 和xk+1點的梯度為 gk = Gxk + b gk+1 = Gxk+1 + b gk+1 gk = G(xk+1 xk ) = Gdk 設xk、xk+1為沿同一方向dj進行一維搜索得到的兩個極小點，因此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，確定收斂精度，選擇坐標軸方向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) 檢驗收斂準則。如滿足則輸出當前點xk作為最優(yōu)點。 5) 若未收斂，則重復

30、2)、3) 的一維搜索和模式移動，但每一輪一維搜索中都用上一輪模式移動方向代替原有的一個坐標軸方向。如第二輪搜索方向為e2, e3, en, d1，依次類推。8 8 鮑威爾法鮑威爾法 框圖見圖4-18。在每一輪搜索后，模式移動與坐標輪換法的相同而不作一維搜索。另外增加了Powell 判別條件，若滿足判別式，則用模式移動方向替換目標函數(shù)值下降量最大的一個方向，以保證下一輪搜索方向組線性無關。 用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 若不滿足收斂準則，則再進行第三輪搜索。9 9 單形替換單形替換法法 又稱Simplex)法，屬于直接搜索方法。 就是在n維空間中由n+1個頂點構成的形體。在優(yōu)化搜索過程中要滿足適行性，就要對目標函數(shù)的變化趨勢有大概

34、的估計，避免盲目選擇搜索方向?？梢愿鶕?jù)若干點的目標函數(shù)值大小的變化推測這種趨勢，這些點可取為單純形的頂點。單純形的基本思想是利用單純形的頂點構造有利的搜索方向和步長，用新的較好點取代原來較差的點，構成新的單純形，不斷向最優(yōu)點逼近。 假定在一個二維問題中，已求得不在一條直線上的三個點H、S、L，及它們的目標函數(shù)值fH、fS、fL，且fH fS fL。這三點構成一個單純形三角形。如有更好點，則在最差點H的反對稱方向可能性最大。9 9 單形替換單形替換法法 因此，取S和L兩點的中點M，從H出發(fā)沿H和M的連線作模式移動到A點。然后舍棄H點，剩下的S、L和A又構成一個單純形。推廣到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