無約束優(yōu)化計算方法

1、第四章第四章無約束問題的最優(yōu)化方法無約束問題的最優(yōu)化方法4.1 4.1 引言引言4.2 4.2 單變量優(yōu)化計算方法單變量優(yōu)化計算方法4.3 4.3 多變量優(yōu)化計算方法多變量優(yōu)化計算方法4.4 4.4 多變量優(yōu)化計算的梯度方法多變量優(yōu)化計算的梯度方法4.5 4.5 多變量多變量無約束優(yōu)化設(shè)計方法小結(jié)無約束優(yōu)化設(shè)計方法小結(jié)4.1 4.1 引言引言一一. . 目的：目的：求一組求一組 n n 維設(shè)計變量維設(shè)計變量 X= xX= x1 1, x, x2 2 , ,x ,x n n T T, , 使目標(biāo)函數(shù)達(dá)到使目標(biāo)函數(shù)達(dá)到 min. f(x) XRmin. f(x) XRn n即求目標(biāo)函數(shù)的最優(yōu)解：最

2、優(yōu)點即求目標(biāo)函數(shù)的最優(yōu)解：最優(yōu)點 x x* * 和最優(yōu)值和最優(yōu)值 f(xf(x* *) ) 。二二.意義意義：l 為有約束優(yōu)化方法的研究提供了策略思想、概念基礎(chǔ)和基本方為有約束優(yōu)化方法的研究提供了策略思想、概念基礎(chǔ)和基本方法；法；l 為有約束優(yōu)化問題的間接解法提供了有效而方便的方法；為有約束優(yōu)化問題的間接解法提供了有效而方便的方法；l 對于某些工程問題，進(jìn)行分析后，便于提供解決的有效方法；對于某些工程問題，進(jìn)行分析后，便于提供解決的有效方法；l 不可避免地還存在無約束優(yōu)化的設(shè)計問題。不可避免地還存在無約束優(yōu)化的設(shè)計問題。4.1 4.1 引言引言三三. . 內(nèi)容：內(nèi)容：一維搜索：一維搜索： 求最

3、優(yōu)步長因子求最優(yōu)步長因子(k)(k)多維（變量）優(yōu)化：確定搜索方向多維（變量）優(yōu)化：確定搜索方向 S (k)S (k)黃金分割黃金分割插值法插值法坐標(biāo)輪換法坐標(biāo)輪換法共軛方向法共軛方向法梯度法梯度法共軛梯度法共軛梯度法牛頓法牛頓法DFPDFP變尺度法變尺度法 定義定義:在第在第K K次迭代時，從已知點次迭代時，從已知點 X X(k)(k)出發(fā)，出發(fā)，沿給定方向求最優(yōu)步長因子沿給定方向求最優(yōu)步長因子(k)(k)，使，使 f f (X(X(k)(k) + + S S(k) (k) ) )達(dá)到最小值的過程，稱達(dá)到最小值的過程，稱為一維搜索。為一維搜索。方法：方法：1.解析法：解析法： f(x(k+1

4、)=min.f(x(k)+S(k)=f(x(k)+(k)S(k) 步驟步驟: : f(X f(X(k)(k) + S + S(k) (k) ) ) 沿沿S S(k)(k) 方向方向x x(k)(k) 臺勞展開；臺勞展開； 取二次近似：取二次近似： )()()(2)()()()()()(21)()(kkTkkTkkkkSxHSSxfxfSxf 4.2.1 4.2.1 搜索區(qū)間的確定：搜索區(qū)間的確定： 4.2 4.2 單變量優(yōu)化計算方法單變量優(yōu)化計算方法：0)()()(kkSxfdd對對求導(dǎo)，令其為零。求導(dǎo)，令其為零。 0)()()()()()()(kkTkkTkSxHSSxf)()()()()(

5、)()()(kkTkkTkkSxHSSxf2. 2. 數(shù)值迭代法：數(shù)值迭代法：直接法直接法應(yīng)用序列消去原理：應(yīng)用序列消去原理： 分?jǐn)?shù)法、分?jǐn)?shù)法、黃金分割法黃金分割法近似法近似法利用多項式函數(shù)逼近（曲線擬合）原理：利用多項式函數(shù)逼近（曲線擬合）原理： 二次插值法二次插值法、 三次插值法三次插值法 求得最優(yōu)步長因子求得最優(yōu)步長因子： 4.2.1 4.2.1 搜索區(qū)間的確定：搜索區(qū)間的確定： 4.2.1 4.2.1 搜索區(qū)間的確定：搜索區(qū)間的確定：單峰區(qū)間：單峰區(qū)間： 在區(qū)間在區(qū)間 1 1，3 3 內(nèi)，函數(shù)只有一內(nèi)，函數(shù)只有一個峰值，則此區(qū)間為單峰區(qū)間。單峰個峰值，則此區(qū)間為單峰區(qū)間。單峰區(qū)間內(nèi)，一

6、定存在一點區(qū)間內(nèi)，一定存在一點* *，當(dāng)任意一，當(dāng)任意一點點2 2* *時，時，f(f(2 2) )f(f(* *) )，說明：說明：l 單峰區(qū)間內(nèi)，函數(shù)可單峰區(qū)間內(nèi)，函數(shù)可以有不可微點，也可以以有不可微點，也可以是不連續(xù)函數(shù)；是不連續(xù)函數(shù)；f(x)0130f(x)31f()32*10當(dāng)當(dāng)2 2* *時，仍有時，仍有f (f (2 2 ) ) f(f(* *) ) ，則，則* *是最優(yōu)點，也即為最優(yōu)是最優(yōu)點，也即為最優(yōu)步長因子步長因子(k)(k)。2l確定的搜索區(qū)間必定確定的搜索區(qū)間必定是一個含有最優(yōu)點是一個含有最優(yōu)點* *的的單峰區(qū)間。單峰區(qū)間。 4.2.1 4.2.1 搜索區(qū)間的確定：搜索

7、區(qū)間的確定：給定初始點給定初始點(0)(0)、初始步長、初始步長h,h,求初始搜索區(qū)間的步驟求初始搜索區(qū)間的步驟: :(0)(0) 可任取，最好接近最小點，可取可任取，最好接近最小點，可取(0)(0)=0=0，h0,h0,(2)(2)令令(0)(0)(1)(1) ， (1)(1)+h+h(2)(2) ,得兩個試點得兩個試點(1)(1)(2)(2) 計算計算f(f(1)(1), f(), f(2)(2),),令令f(f(1(1）)f)f1 1, f(, f(2(2）)f)f2 2, ,(3)(3)比較比較f f1 1與與f f2,2,若若f f2 2fff3 3, ,則則以以（3 3）為起點，步

8、長加倍，直至兩端大中間小，為起點，步長加倍，直至兩端大中間小，（4 4）f f2 2ff1,1, 則后退則后退 運算。運算。 （如圖）（如圖） 4.2.1搜索區(qū)間的確定：搜索區(qū)間的確定： 4.2.1 4.2.1 搜索區(qū)間的確定：搜索區(qū)間的確定：定步長搜索法定步長搜索法: : 。it3，若不是若是，轉(zhuǎn)第步；：1ifif判斷)；if(tif,t1it1,ii ,0tit令。2t3，2t1，若不是若是，轉(zhuǎn)第步；：1f2f判斷)；2f(t2f,0t12t ,0t0t2,i令若不是，轉(zhuǎn)第步；若是，轉(zhuǎn)第步；：1f2f判斷)；2f(t2f,0t12t2,i令)；1f(t1，f0)、初始步長t1(t1選初始點

9、 3. 3. 加速步長搜索法加速步長搜索法：.0t2i或t0t1i2t0tit 4. 4. 外推法：外推法：2111ittf 2 =f (1+t0 ) 1f1 。*,)f()若f(；*,)f()若f(則收斂，,）（中，,第m次在區(qū)間收斂條件：；,舍去，,)則*f()此例中f(,)和f(f(比較）；（）（）（，,）內(nèi)取兩點,（此例中在,第二次在區(qū)間；,舍去，,)則*f()若f(；,和,舍去，,)則*f()若f(；,舍去，,)則*f()若f(),)和f(f(比較）（），（，,內(nèi)取兩點,第一次在區(qū)間1）；（0定公比(m)1(m)3(m)1(m)3(m)3(m)1(1)1(1)31m(m)1(m)3(

10、m)3(m)1(2)32222(2)122212221(1)1(1)3(2)122(1)1(1)32(1)3(2)1(2)3(2)3212221(1)311(2)3(2)111(1)1(1)3111211(1)31211(1)112111211(1)31212(1)112111211(1)1(1)3(1)112(1)1(1)3(1)3111211(1)3(1)14.2.2 4.2.2 黃金分割法黃金分割法 (0.618(0.618法法) )1. 1. 序列消去原理：序列消去原理：f()3(1)12*1(1)03(2)1121221(2)1(3)3(3)4.2.2 4.2.2 黃金分割法黃金分割

11、法 (0.618)(0.618)在搜素區(qū)間在搜素區(qū)間a,ba,b內(nèi)內(nèi), ,任取兩點任取兩點(1(1）與與(2(2），且，且aa(1) (1) (2) (2) bb計算計算f(f(1)(1),),與與f(f(2)(2),),并進(jìn)行比較。有三種情況：并進(jìn)行比較。有三種情況：（1 1） f(f(1)(1), f(), f() f(2)(2),), （圖（圖c c、d)d) 丟掉丟掉a,a,(1)(1) )， * *必在必在 (1)(1),b,b內(nèi)內(nèi)（3 3） f(f(1)(1)=f()=f(2)(2),),（圖（圖e e） 這時，不論丟掉這時，不論丟掉a,a,(1)(1) ) 還是還是(2)(2),

12、b, ,b, * *必在留必在留 下的部分內(nèi)下的部分內(nèi)對于第對于第(1)(1)、(2)(2)種情況，只要種情況，只要再取一個點再取一個點(3)(3) 就可進(jìn)行比較、就可進(jìn)行比較、消去。但對于第三種情況，就要消去。但對于第三種情況，就要補(bǔ)充兩個點。因此第三種合并為補(bǔ)充兩個點。因此第三種合并為前兩種前兩種: :(1)(1) f( f(1)(1)f()f(2)(2) )、 (2) f(2) f(1)(1)f()f(2)(2) )4.2.2 4.2.2 黃金分割法黃金分割法 (0.618)(0.618)2. 2. 黃金分割與黃金分割與0.6180.618：bd 古希臘建筑師認(rèn)為：邊長為古希臘建筑師認(rèn)為

13、：邊長為 b b，d d 的矩形建筑的矩形建筑物，若邊長能符合以下條件，則最美觀：物，若邊長能符合以下條件，則最美觀：618. 001,2解得，則dbddb歐幾里德幾何稱這種邊長分割為黃金分割。歐幾里德幾何稱這種邊長分割為黃金分割。 序列消去法中，為提高效率，減少計算量和存序列消去法中，為提高效率，減少計算量和存儲量，儲量，希望在每一次縮短搜索區(qū)間迭代過程中希望在每一次縮短搜索區(qū)間迭代過程中兩計算點兩計算點(1)(1)、(2)(2)，在區(qū)間中的位置相對于邊，在區(qū)間中的位置相對于邊界來說應(yīng)是對稱的，而且還要求丟去一段后保留界來說應(yīng)是對稱的，而且還要求丟去一段后保留點在新區(qū)間中的位置與丟去點再原區(qū)

14、間中的位置點在新區(qū)間中的位置與丟去點再原區(qū)間中的位置相當(dāng)。相當(dāng)。令令a,ba,b長為長為L, L, 并令并令l/L=l/L= 2 2+ +-1=0 -1=0 =0.6180339887=0.6180339887 llLLl0.618法計算程序框圖3.4 3.4 二次插值法（拋物線法）二次插值法（拋物線法）1. 1. 基本原理：基本原理： 。的最優(yōu)點近似的極小值，以擬合曲線即用拋物線逼近擬用一元二次多項式的一元函數(shù)，是*,)(21fpfpfcbapSxfxfpkkk步驟：步驟： 133221321213132133221322212212312322323332222212111321231,f

15、ffcfffbfcbapfcbapfcbappfff：解得，得：，代入，已知函數(shù)值，及中間任意一點，選目標(biāo)函數(shù)值的點。三個已知確定二項式系數(shù)，需選3.4 3.4 二次插值法（拋物線法）二次插值法（拋物線法）2. 2. 步驟步驟 ( (續(xù)續(xù)) )： 32112122131312121,)(212*02cffcffccccbcbddpp其中得令3. 3. 結(jié)果分析：結(jié)果分析：。，重取插值點，再擬合若不滿足，則縮小區(qū)間。則且。則且，若滿足判斷是否滿足精度：代替校核以若外，結(jié)論：重新處理。在其中若。：軸的直線上，結(jié)論位于一條平行與則若4422422423414314341423212*,*,*,0,*

16、,0*,0fffffffcpp問題：若不滿足精度，如何縮小區(qū)間，再擬合（分四種情況分析）問題：若不滿足精度，如何縮小區(qū)間，再擬合（分四種情況分析） ？ p*=44.2.3 4.2.3 二次插值法（拋物線法）二次插值法（拋物線法）(1)確定初始插值點確定初始插值點(1)(1)=a,=a,(3)(3)=b=b， (2)(2)=0.5(=0.5(1)(1)+ + (3)(3) )計算計算f f1 1,f,f2 2,f,f3 3, ,構(gòu)成構(gòu)成p p1 1,p,p2 2,p,p3 3(2)(2)計算計算p p* *= =(4)(4)、f f4 4(3)(3)縮短搜索區(qū)間縮短搜索區(qū)間 取取f f2 2,f

17、,f4 4小者的點為小者的點為(2)(2) 兩側(cè)鄰點為兩側(cè)鄰點為(1)(1)、(3)(3) 根據(jù)原區(qū)間中根據(jù)原區(qū)間中(4)(4)，(2) (2) 的相對位置及的相對位置及f f2 2,f,f4 4的比的比較，有四種情況（如圖）較，有四種情況（如圖）, ,陰影線部分為丟去的，再對陰影線部分為丟去的，再對新區(qū)間三個新店代號一次作新區(qū)間三個新店代號一次作(1)(1)、(2)(2)、(3)(3)處理。計處理。計算算f f1 1,f,f2 2,f,f3 34.2.3 4.2.3 二次插值法（拋物線法）二次插值法（拋物線法）算法框圖算法框圖4.2.3 4.2.3 二次插值法（拋物線法）二次插值法（拋物線法

18、） 與黃金分割法相比，二次插值法充分利用函數(shù)值的信息；與黃金分割法相比，二次插值法充分利用函數(shù)值的信息；收斂快；調(diào)用函數(shù)次數(shù)少。收斂快；調(diào)用函數(shù)次數(shù)少。4.4.方法評價方法評價: :4.2 4.2 坐標(biāo)輪換法和坐標(biāo)輪換法和 Poweel Poweel 法法一一. . 坐標(biāo)輪換法：坐標(biāo)輪換法：1. 1. 基本思想：基本思想：2. 2. 搜索方向與步長：搜索方向與步長： 每次以一個變量坐標(biāo)軸作為搜索方向，將每次以一個變量坐標(biāo)軸作為搜索方向，將 n n維的優(yōu)化問題轉(zhuǎn)化為一維搜索問題。例，第維的優(yōu)化問題轉(zhuǎn)化為一維搜索問題。例，第 k k輪迭代的第輪迭代的第 i i 次搜索，是固定除次搜索，是固定除 x

19、 xi i外的外的 n-n-1 1 個變量，沿個變量，沿 x xi i 變量坐標(biāo)軸作一維搜索，求變量坐標(biāo)軸作一維搜索，求得極值點得極值點 x xi i(k)(k) n n 次搜索后獲得極值點序列次搜索后獲得極值點序列 x x1 1(k)(k), x, x2 2(k(k）, , x, xn n(k)(k)，若未收斂，則開始第，若未收斂，則開始第 k+1 k+1 次迭代，直至收斂到最優(yōu)點次迭代，直至收斂到最優(yōu)點 x x* *。 。：次搜索的收斂條件輪第第；：次搜索的迭代公式輪第第；：次搜索的步長輪第第向；個設(shè)計變量的坐標(biāo)軸方為第次搜索的方向：輪第第)()()()()(1)()()()(,.,2 ,

20、 1,kikikikikikikikikiSikniSxxikSikiSik4.3.1 4.3.1 坐標(biāo)輪換法坐標(biāo)輪換法算法框圖算法框圖4.3.1 4.3.1 坐標(biāo)輪換法坐標(biāo)輪換法加速步長法：加速步長法：( )( )134()(),2iiikkiitf xf xi(k)(k)ii-11ii1、先規(guī)定初始步長 ，探測下降方向2、取初始步長的若干倍作為搜索步長t、以計算新點 x=x+ e、若取繼續(xù)向前， 直到目標(biāo)函數(shù)值增大，取前一點為本次新點5、不滿足精度時取t =(0.10.5)4.3.1 4.3.1 坐標(biāo)輪換法坐標(biāo)輪換法例例4-1 4-1 設(shè)目標(biāo)函數(shù)設(shè)目標(biāo)函數(shù)求其無約束的最優(yōu)點（求其無約束的最

21、優(yōu)點（x x1 1* *,x,x2 2* *）。）。解：目標(biāo)函數(shù)的等值線及加速步解：目標(biāo)函數(shù)的等值線及加速步長的搜索路線如圖所示。長的搜索路線如圖所示。22141212221212922244)(xxxxxxxxxxf2 . 425. 20125. 02 . 45 . 225. 0,25. 00625. 042),(76.20)(2 . 425. 20125. 02 . 45 . 20625. 0042.25)(,2 . 4 5 . 21 10)1(101101100sxxttxfxfsxxxxfxT）取取試試驗驗步步長長應(yīng)應(yīng)正正值值。軸軸的的移移動動方方向向：沿沿。先先判判斷斷。試試驗驗步步

22、長長取取，）取取初初始始點點053. 1)(,025. 1 ,053. 1)(08. 7)(2 . 20 . 21025. 082 . 40 . 2),(2 . 7)(95. 30 . 21025. 02 . 40 . 23 68.16)(,2 . 40 . 2 )(74.16)(2 . 45 . 10125. 042 . 45 . 225. 044)(68.16)(2 . 40 . 20125. 022 . 45 . 25 . 025. 022)(4125.19)(*)1(2)1(2)1(2)1(1)1(22)1(1)1(22)1(1)1(11)1(1)1(1)1(1)1(1)1(1)1(1

23、)1(1)1(1xfxxfxfxxfxfsxxxxfxxxfxfxxfxfxxfxfT最最優(yōu)優(yōu)化化值值為為求求得得最最優(yōu)優(yōu)化化點點為為依依次次繼繼續(xù)續(xù)下下去去，最最后后可可試試驗驗步步長長應(yīng)應(yīng)取取負(fù)負(fù)值值。方方向向搜搜索索：）沿沿方方向向得得到到的的好好點點為為故故沿沿再再加加大大步步長長取取加加大大步步長長取取4.3.1 4.3.1 坐標(biāo)輪換法坐標(biāo)輪換法)(ki4.4.最優(yōu)步長法：最優(yōu)步長法： 最優(yōu)步長法就是利用一維優(yōu)化搜索方法(如0.618方法或二次插值方法)，求出每維搜索計算的 值，如圖所示。在這種情況下，每一次沿坐標(biāo)方向進(jìn)行搜索計算，都使目標(biāo)函數(shù)值降至最小，如此反復(fù)迭代計算，直至達(dá)到收

24、斂條件 為止。)( kis4.3.1 4.3.1 坐標(biāo)輪換法坐標(biāo)輪換法3. 3. 方法評價：方法評價：方法簡單，容易實現(xiàn)。方法簡單，容易實現(xiàn)。當(dāng)維數(shù)增加時，效率明顯下降。當(dāng)維數(shù)增加時，效率明顯下降。收斂慢，以振蕩方式逼近最優(yōu)點收斂慢，以振蕩方式逼近最優(yōu)點。 受目標(biāo)函數(shù)的性態(tài)影響很大。受目標(biāo)函數(shù)的性態(tài)影響很大。 如圖如圖 a) a) 所示，二次就收斂到極值點；所示，二次就收斂到極值點； 如圖如圖 b) b) 所示，多次迭代后逼近極值點；所示，多次迭代后逼近極值點； 如圖如圖 c) c) 所示，目標(biāo)函數(shù)等值線出現(xiàn)山脊（或所示，目標(biāo)函數(shù)等值線出現(xiàn)山脊（或稱陡谷），若搜索到稱陡谷），若搜索到 A A

25、點，再沿兩個坐標(biāo)軸，以點，再沿兩個坐標(biāo)軸，以t t0 0步長測試，目標(biāo)函數(shù)值均上升，計算機(jī)判斷步長測試，目標(biāo)函數(shù)值均上升，計算機(jī)判斷 A A 點為最優(yōu)點。事實上發(fā)生錯誤。點為最優(yōu)點。事實上發(fā)生錯誤。4.3.2 4.3.2 Poweel Poweel 法法（共軛方向法、方向加速法）：（共軛方向法、方向加速法）：1. 1. 基本思想：基本思想：2. 2. 共軛方向的定義：共軛方向的定義：若沿連接相鄰兩輪搜索末端的向量若沿連接相鄰兩輪搜索末端的向量 S S 方向搜索，收方向搜索，收斂速度加快。斂速度加快。(1)2x(2)2xS其中： 因為兩條平行線因為兩條平行線 S S1 1, S, S1 1與同心

26、橢圓族相切，兩個切與同心橢圓族相切，兩個切點的連線點的連線 S S 直指中心。稱直指中心。稱 S S1 1, S, S1 1 與與 S S 為共軛方向。為共軛方向。 目的目的：以共軛方向打破振蕩，加速收斂。：以共軛方向打破振蕩，加速收斂。陣A共軛。則稱這組向量是關(guān)于矩j),(i0jASTiS能滿足,nS,.,2S ,1若有一組非零向量S，設(shè)A為正定實對稱矩陣正交。2和S1S則0,2ST1S即，0時2IST1S則，若A為單位矩陣I的方向是共軛方向。2和S1S是關(guān)于矩陣共軛，2和S1S則稱向量,02AST1S滿足，2和S1S若有兩個n維向量，設(shè)A為實對稱正定矩陣 4.3.2 4.3.2 Powee

27、l Poweel 法法（共軛方向法、方向加速法）：（共軛方向法、方向加速法）：3. 3. 共軛方向的性質(zhì)：共軛方向的性質(zhì)：二次收斂性。為步可收斂至極值點，稱多方向進(jìn)行一維搜索，至出發(fā)，依次沿從任意初始點，次函數(shù)個非零向量，則對于二矩陣共軛的是關(guān)于設(shè)矩陣共軛。中每一個向量關(guān)于，也是與向量組，向量和搜索，分別得到最優(yōu)點方向進(jìn)行一維出發(fā)，沿和分別從兩個初始點個非零向量，對于函數(shù)矩陣共軛的是關(guān)于設(shè)。滿足，個向量則可以構(gòu)造出是線性無關(guān)的向量組，若是線性無關(guān)的。個非零向量矩陣共軛的這組關(guān)于）（）（）（）（）（）（nniSxAXXXBCxfnASSSAniSxxSxxniSxxxfnASSSjiSASSSS

28、nSSSSSSnAiTTniinjTinnn),.,2 , 1(21)(,.,),.,2 , 1(),.,2 , 1()(,.,)(,0,.,.,.,)0(211221)2(0)1(021)2()2(2222111211214.3.2 4.3.2 Poweel Poweel 法法4. 4. 步驟：步驟： 。的極值點xx作第三次搜索，求得f，沿此方向xx構(gòu)筑共軛方向：S。x,的極值點xx分別求得f作兩次一維搜索，S,兩個坐標(biāo)軸方向S，依次沿xx，令選初始點x第一輪迭代：131012112111211(0)10(0)4.3.2 4.3.2 Poweel Poweel 法法4. 4. 步驟：步驟：

29、迭代。若不滿足，則作下一輪。xx*則,若滿足。fff或,xx是否滿足收斂條件：每輪迭代結(jié)束時，檢驗。的極值點xx作第三次搜索，求得f，沿此方向xx構(gòu)筑共軛方向：S。x,的極值點xx一維搜索，分別求得f方向作兩次S,，分別沿Sxx令第二輪迭代：1)(k321k0k01k01k01k023202222221112(1)3204.3.2 4.3.2 Poweel Poweel 法法6. 6. 方法評價：方法評價：l 計算步驟復(fù)雜計算步驟復(fù)雜; ;l 是二次收斂方法，收斂快。對非正定函數(shù)，也很有效是二次收斂方法，收斂快。對非正定函數(shù)，也很有效; ;l 是比較穩(wěn)定的方法。是比較穩(wěn)定的方法。 5. 5.

30、說明：說明：l 若是正定二次函數(shù)，若是正定二次函數(shù)，n n 輪迭代后收斂于最優(yōu)點輪迭代后收斂于最優(yōu)點 x x* * 。 若是非正定二次函數(shù)，則迭代次數(shù)增加。若是非正定二次函數(shù)，則迭代次數(shù)增加。l若是若是 n n 維問題，步驟相同。維問題，步驟相同。 搜索方向：第一輪迭代，沿初始方向組搜索方向：第一輪迭代，沿初始方向組 S Si i(1)(1) (i=1,2, (i=1,2,n) ,n) 的的 n n 個方向和共軛方向個方向和共軛方向 S S(1)(1)，搜索，搜索 n+1 n+1 次得極值點次得極值點 x xn+1n+1(1)(1) ；第二輪；第二輪迭代，沿方向組迭代，沿方向組 S Si i(

31、2)(2) ( i=1,2, ( i=1,2,n,n；im ) im ) 的的 n-1 n-1 個方向和共個方向和共軛方向軛方向 S S(1)(1)，構(gòu)筑共軛方向，構(gòu)筑共軛方向 S S(2) (2) 搜索搜索 n+1n+1次得極值點次得極值點 x xn+1n+1(2)(2) 。其。其中，為保證搜索方向的線性無關(guān)，去除了中，為保證搜索方向的線性無關(guān)，去除了 S Sm m(2) (2) 方向方向 。l 在第在第 k k 輪迭代中，為避免產(chǎn)生線性相關(guān)或近似線性相關(guān)，需輪迭代中，為避免產(chǎn)生線性相關(guān)或近似線性相關(guān)，需要去除前一輪中的某個方向要去除前一輪中的某個方向 S Sm m(k)(k)。去除的原則請

32、自學(xué)。去除的原則請自學(xué)。4.3.2 4.3.2 Poweel Poweel 法法4.3.2 4.3.2 Poweel Poweel 法法Poweel法計算框圖例例4-2 4-2 用用PowellPowell法求函數(shù)法求函數(shù)4.3.2 4.3.2 Poweel Poweel 法法的最優(yōu)點的最優(yōu)點x x* *=x=x1 1* *，x x2 2* * T T。計算精度要求。計算精度要求0.00010.0001解：取初始點解：取初始點 x x0 0（1 1）x x(0)(0)=0=0，00T T，第一輪，第一輪迭代的搜迭代的搜索方向取兩個坐標(biāo)的單索方向取兩個坐標(biāo)的單位向量位向量從從 出發(fā)，先從出發(fā)，先

33、從 方向進(jìn)行一維最優(yōu)搜索，計算出最方向進(jìn)行一維最優(yōu)搜索，計算出最優(yōu)步長優(yōu)步長 由此得最優(yōu)點由此得最優(yōu)點)1(0 x)1(1s。 5)1(12122212141060)(xxxxxxxf10 012)1(21)1(1eses和和0501500)1(1x方方向向上上的的極極小小點點。，并并求求替替換換成成立立，故故應(yīng)應(yīng)以以檢檢驗驗判判別別條條件件下下降降量量計計算算相相鄰鄰二二點點函函數(shù)數(shù)值值的的方方向向上上的的反反射射點點計計算算個個方方向向計計算算第第優(yōu)優(yōu)點點方方向向進(jìn)進(jìn)行行一一維維搜搜索索得得最最同同理理，沿沿)1(3)1()1(3231)1(2)1(2132113)1(33)1(22)1(

34、011)1(1)1()1(1)2(2)1(1)1()1(2)1(1)1(2)1(1)1(0)1(1)1(2)1(1)1(0023)1(302)1(3)1(2)1(2)5 .253128 .18657( ,)(5 . 0)(2()6015( ,15)(,75.14)(,60)(,25,max25.20)()(,25)()(75.14)(,35)(,60)( 9102 5 . 45005 . 45 15 . 45105 . 405sssfffffffffxffxffxffessxfxfxfxfxfxfxfxxxsxxsnxsmmmmm08695. 07362. 54725. 710)9891. 0

35、(7253. 64725. 75 . 45,107253. 64725. 7* 22753. 64725. 75 . 454945. 05 . 45*4945. 05 . 4521125 . 4,55 . 450,912. 7)()2(2)2(2)2(2)2(1)2(2)2(1)2(1)2(0)2(1)1(3)2(22)1(2)2(1)2(0)1(33125 . 4521125 . 4,55 . 450,5 . 4)(33)2(2)2(2)2(2)2(113)1(3)1(3)1(2HsssxfHsssxfTTTTsxxsxxssessxxksxx其其中中時時當(dāng)當(dāng)為為優(yōu)優(yōu)化化步步長長)2(3)2

36、(3)2(2)2(3231)1(2)2(2132113)2(1)2()2(2)2(1)2(2)2(1)2(0)2(1)2(3)2(2)2(1)2(0)2(0)2(2)2(3)2(0)2(2)2(3)2(2*)2313. 00477. 0( ,)(5 . 0)(2)1869. 94991. 8( ,9782. 01720. 0)()(9782. 02087. 81869. 9)()(4991. 8)(,0367. 8)(,2087. 8)(,1869. 9)(5297. 53421. 825978. 04348. 07253. 64725. 71275. 69073. 71275. 69073.

37、 75 . 4508695. 07362. 54725. 7sxxsfffffffffxfxfxfxfxfxfxfxfxxxxxsxmmm一維搜索一維搜索成立，故沿成立，故沿（判別條件判別條件次一維搜索?？偣策M(jìn)行，故停止運算。，誤差已小于精確解其中：60001. 068*0001. 69999. 75978. 04348. 0213. 01275. 69073. 7*213. 05978. 04348. 021125978. 0,4348. 05978. 04348. 03477. 0,3129. 0)()2(3)2(3)2(3)2(3)2(2xxHsssxfTT4.3.3單純形法單純形法單純

38、形法單純形法是一種利用單純形法是一種利用n n維設(shè)計空間中的幾何圖形不斷向好點移維設(shè)計空間中的幾何圖形不斷向好點移動迭代的一種算法。動迭代的一種算法。 單純形法是在單純形法是在n n維設(shè)計空間內(nèi)由維設(shè)計空間內(nèi)由n+1n+1個頂點組成的幾何形體，如在個頂點組成的幾何形體，如在二維空間，單純形為三角形，在三維空間內(nèi)為四面體等。若各頂二維空間，單純形為三角形，在三維空間內(nèi)為四面體等。若各頂點間的距離相等，則稱為正單純形。點間的距離相等，則稱為正單純形。(a) 二維空間三角形的反射(b) 三維空間四面體的收縮4.3.34.3.3單純形法單純形法單純形法迭代的單純形法迭代的基本要點基本要點是是如何保證單

39、純形不斷地向優(yōu)點如何保證單純形不斷地向優(yōu)點移動并使單純形縮小直到趨于一點。移動并使單純形縮小直到趨于一點。這個過程是通過所謂反射，這個過程是通過所謂反射，收縮和擴(kuò)展三種運算實現(xiàn)的。收縮和擴(kuò)展三種運算實現(xiàn)的。1, 2 , 1),(max)( 1, 2 , 1),(min)( 11njxfxfxnjxfxfxjhhj設(shè)單純形的設(shè)單純形的n+1n+1個頂點為個頂點為x xj j(j=1(j=1，2 2，n+1)n+1)計算出它的目標(biāo)函數(shù)值計算出它的目標(biāo)函數(shù)值f(xf(xj j) )，并從中確定出目標(biāo)函數(shù)值最小的點，并從中確定出目標(biāo)函數(shù)值最小的點x xl l 和最大點和最大點x xh h , ,即即并

40、計算出除并計算出除x xh h點外的其余所有點的形心點外的其余所有點的形心x x0 0 。即。即然后可以進(jìn)行單純行的移動運算然后可以進(jìn)行單純行的移動運算：), 2 , 1(1)(10nixxnhjijjini如果如果 x xh h為單純形頂點中目標(biāo)函數(shù)值最大的頂點，如圖為單純形頂點中目標(biāo)函數(shù)值最大的頂點，如圖(a)(a)所示，所示，則應(yīng)以形心為鏡面像其對面反射可能獲得目標(biāo)函數(shù)值小于它的點則應(yīng)以形心為鏡面像其對面反射可能獲得目標(biāo)函數(shù)值小于它的點x xr r，即稱即稱反射點反射點，即，即 其中其中 為為反射系數(shù)反射系數(shù)。這樣。這樣x xr r 點將位于點將位于x xh h 和和x x0 0的連線上

41、，它與的連線上，它與x x0 0點的距離為點的距離為4.3.3單純形法單純形法如果 f(xr) 的值小于f(xh) ，則xr 為一個新的單純形，如圖中的三角形x1x2xr。如果反射點xr的目標(biāo)函數(shù)值，剛好等于xh的目標(biāo)函數(shù)，則這兩點剛好是目標(biāo)函數(shù)脊線為鏡面的對稱點，這時將使搜索過程陷入死循環(huán)，對此可以利用目標(biāo)函數(shù)值次最大值點xg，用它進(jìn)行反射得新的xr 或是用xr替換xg點形成一個新的單純形。0)1 (xxxhr(1) 反射：000 xxxxhr4.3.3單純形法單純形法如果反射點xr的f(xr) f(x1) 則xr 為一個新的目標(biāo)函數(shù)值最小點。此時沿x0和xr方向可以進(jìn)一步移動，有可能獲得更

42、小目標(biāo)函數(shù)值的點。因此，擴(kuò)展點擴(kuò)展點x xe e為其中 為擴(kuò)展系數(shù)擴(kuò)展系數(shù)，它與x0點的距離為 如果f(xe) f(x1) ，則用xe代替xh，構(gòu)成新單純形，進(jìn)入下次的運算過程。若f(xe) f(x1) ，則表示擴(kuò)展不成功，仍用xr代替xh構(gòu)成新單純形，再進(jìn)入下一次運算過程。 0)1 (xxxre（2）擴(kuò)展100 xxxxre4.3.3單純形法單純形法如果反射點如果反射點x xr r的函數(shù)值的函數(shù)值f(xf(xr r) )雖小于雖小于f(xf(xh h) ) ，但它大于所有其余，但它大于所有其余各點的值，則可用各點的值，則可用x xr r代替代替x xh h，這時，在新單純形中的，這時，在新單

43、純形中的x xh h為原來的為原來的x xr r，并縮小這個單純形，其收縮點為并縮小這個單純形，其收縮點為x xc c 其中其中為收縮系數(shù)為收縮系數(shù)(0(01)1)。它與。它與x x0 0點的距離為點的距離為 如果如果 ，則用，則用x xc c代替代替x xh h點，再進(jìn)行下點，再進(jìn)行下一次運算過程，反之，這個收縮過程失敗，此時可將所有單純形的一次運算過程，反之，這個收縮過程失敗，此時可將所有單純形的頂點向最好點頂點向最好點x x1 1收縮收縮1/21/2，則用，則用 代替所有的頂點，然后再進(jìn)行運算過程。代替所有的頂點，然后再進(jìn)行運算過程。0)1(xxxhc（3）收縮00 xxxxhc)(),

44、(min)(rhcxfxfxf) 1, 2 , 1;, 2 , 1( 2/ )(njnixxxlijiji4.3.3單純形法單純形法如圖所示，在迭代計算中，由于單純形不斷向最好點移動和縮小，因此當(dāng)單純形的n+1頂點的目標(biāo)函數(shù)值的均方差很小，即 就認(rèn)為算法收斂，終止計算，并令x*x1。2/1111)()(20njnxfxfjQ3 3、迭代格式：、迭代格式：X X(k+1)(k+1)=X=X(k)(k)- -(k)(k) f(X f(X(k)(k) )X X(k+1)(k+1)=X=X(k)(k)- -(k)(k)量。量。是負(fù)梯度方向的單位向是負(fù)梯度方向的單位向,)()()()()(kkkxfxf

45、S4.4 4.4 多變量優(yōu)化設(shè)計的梯度方法多變量優(yōu)化設(shè)計的梯度方法4.4.14.4.1梯度法（最速下降法）梯度法（最速下降法）：1. 1. 基本思想：基本思想：2. 2. 搜索方向：搜索方向： 目標(biāo)函數(shù)負(fù)梯度向量方向代表最速目標(biāo)函數(shù)負(fù)梯度向量方向代表最速下降方向，因此選擇負(fù)梯度向量方向作下降方向，因此選擇負(fù)梯度向量方向作為搜索方向，期望很快找到最優(yōu)點。為搜索方向，期望很快找到最優(yōu)點。)()()()(kkxfxf4.4.1 4.4.1 梯度法梯度法4. 4. 梯度法的計算框圖：梯度法的計算框圖：4.4.1 4.4.1 梯度法梯度法5. 5. 方法評價：方法評價：l 迭代過程簡單，對初始點的選迭代

46、過程簡單，對初始點的選擇，要求不高。擇，要求不高。l 梯度方向目標(biāo)函數(shù)值下降迅速梯度方向目標(biāo)函數(shù)值下降迅速只是個局部性質(zhì)，從整體來看，只是個局部性質(zhì)，從整體來看，不一定是收斂最快的方向。不一定是收斂最快的方向。l 以二維二次函數(shù)為例，相鄰兩以二維二次函數(shù)為例，相鄰兩次的搜索方向是正交的，所以搜次的搜索方向是正交的，所以搜索路徑是曲折的鋸齒形的；對于索路徑是曲折的鋸齒形的；對于高維的非線性函數(shù)，接近極值點高維的非線性函數(shù)，接近極值點處，容易陷入穩(wěn)定的鋸齒形搜索處，容易陷入穩(wěn)定的鋸齒形搜索路徑。路徑。4.4.2 4.4.2 共軛梯度法共軛梯度法1. 1. 基本思想基本思想：2. 2. 共軛方向：共

47、軛方向：對梯度法作一個修正，將搜索方向?qū)μ荻确ㄗ饕粋€修正，將搜索方向由負(fù)梯度方向旋轉(zhuǎn)一個角度，使相鄰由負(fù)梯度方向旋轉(zhuǎn)一個角度，使相鄰的兩次搜索方向由正交變?yōu)楣曹棧傻膬纱嗡阉鞣较蛴烧蛔優(yōu)楣曹?，成為二次收斂。為二次收斂。為共軛系?shù)。(k)：其中,(k)S(k)1)(kf(x1)(kS1次搜索的方向為第k),(k)f(x(k)S第k次搜索的方向為3. 3. 共軛系數(shù)：共軛系數(shù)：2)(2)1()()()(kkkxfxf推導(dǎo)過程請參考書本。(k) S(k)4.4.2 4.4.2 共軛梯度法共軛梯度法步驟：步驟：轉(zhuǎn)第步。,1kk令,S)f(xS：，構(gòu)造新的共軛方向計算則進(jìn)行下一步；，n若k轉(zhuǎn)第步；，x

48、x則令，n若k，檢查搜索次數(shù)步；若不滿足，則進(jìn)行第；xx*，若滿足，則迭代結(jié)束,)f(x是否判斷；Sxx方向作一維搜索，求得沿S)；f(xS計算，0k令；和計算精度選取初始點x(k)(k)1)(k(k)(k)1)(k(0)1)(k1)(k(k)(k)(k)1)(k(k)(k)(k)(0)Kn給定給定X0,n,K=1,X(K)=X0S(K)=-f(X(K)從從X(K)始始，沿沿S(K)進(jìn)行一維搜索得進(jìn)行一維搜索得X(K+1)K=K+1是是是是否否否否計算計算(1)(1)(),()KKfXfX(1)()Kf X結(jié)結(jié) 束束(1)(1)()KKXXff X) 1(0KXX(1)2( )(1)(1)(

49、)()()()()KKKKKKKf Xf XSf XS重置負(fù)梯度方向重置負(fù)梯度方向5.5.迭代框圖迭代框圖6. 6. 方法評價：方法評價：l迭代程序簡單，容易實現(xiàn)編程，存儲量較小。迭代程序簡單，容易實現(xiàn)編程，存儲量較小。l 需用到一階導(dǎo)數(shù)需用到一階導(dǎo)數(shù)l 開始采用梯度方向，目標(biāo)函數(shù)值下降快，后又為旋轉(zhuǎn)梯度方開始采用梯度方向，目標(biāo)函數(shù)值下降快，后又為旋轉(zhuǎn)梯度方 向，具有二次收斂性，收斂快。向，具有二次收斂性，收斂快。例例4-34-3設(shè)目標(biāo)函數(shù)為設(shè)目標(biāo)函數(shù)為 ，起始，起始點為點為x x(0)(0)00，00T T，試用共軛梯度法求其極小點。，試用共軛梯度法求其極小點。2122212141060)(

50、xxxxxxxf(1)(1)12,( )Txxf x將代入得4.4.2 4.4.2 共軛梯度法共軛梯度法解解：第一次迭代的方向為：第一次迭代的方向為：所以所以第二次迭代方向第二次迭代方向為為053.3631.7410 7631.0,0)()(7611660)(41041041042102)()0()0()1(0)*d)(d)0(2)0()0()1(2)1(1)0()0()0()0()1()0,0(1221)0()0()0()0(xfxfxxxxxxxxxfsf得得3054.0526.5210.242102)()()(2222222)0(2)1()410()526.5(210.2()()()0(

51、)1(1)1(2)1(2)1(1)1()0()0()1()1(xfxfxxxxxfxfxfs4.4.2 4.4.2 共軛梯度法共軛梯度法故經(jīng)兩次搜索即達(dá)極小點故經(jīng)兩次搜索即達(dá)極小點x x* *=8,6=8,6T T 。99999. 599999. 77479. 68434. 04367. 0052. 3631. 74367. 0 7479. 68434. 04103054. 0526. 5210. 2)1()1()1()2(7479. 68434. 021127479. 6,8434. 07479. 68434. 0521. 5,210. 2)(*(1)1()1()()()()(sxxsTTk

52、TkkrkHsssxf所所以以用用一一維維搜搜索索解解析析法法求求所所以以4.4.3 4.4.3 牛頓法和修正牛頓法牛頓法和修正牛頓法 1. 1. 基本思想：基本思想： 將將 f(x) f(x) 在在 x x(k)(k) 點作臺勞展開，取二次函數(shù)式點作臺勞展開，取二次函數(shù)式(x) (x) 作為近作為近似函數(shù)似函數(shù), ,以以(x) (x) 的極小值點作為的極小值點作為 f(x) f(x) 的近似極小值點。的近似極小值點。( )( )( )( )( )( )( )( )( )( )( )( )1( )minmin( )( )1()()() ()()()2( )()()(),( )0,()(),*k

53、kkTkkTkkkkkkkkf xxxf xf xxxxxH xxxxf xH xxxxxxH xf xxx (k)(k+1)(k)(令得。由于在x 點附近，函數(shù) (x)和f(x)是近似的，所以 x=x -H(xk) -1(k)f(x )說明：說明：lf(x) f(x) 若是正定二次函數(shù)，一般迭代一次即可；若是嚴(yán)重非若是正定二次函數(shù)，一般迭代一次即可；若是嚴(yán)重非線性函數(shù)，則可能不收斂，或收斂到鞍點。線性函數(shù)，則可能不收斂，或收斂到鞍點。)為牛頓步長。(K)f(x1)(k)H(x矩陣。為Hesse矩陣的逆1 )(k)H(x 4.4.3 4.4.3 牛頓法和修正牛頓法牛頓法和修正牛頓法212221

54、2141060)(xxxxxxxf21122112)(2112)(41024210)(31211211)0()0()0(1)0(2)0(2)0(1)0(xHxHxxxxxf例4-4 設(shè)目標(biāo)函數(shù)為，試用牛頓法求其極小點。初始點取x(0)=0,0T解：先計算所以得由此可見（與例4-3比較），對于任何正定二次函數(shù)，只需迭代一次，即求出其極小點。可以證明，當(dāng)目標(biāo)函數(shù)滿足一定條件，且初始點選得較好時，牛頓法的收斂速度是非?？斓?。68410211200)()(31)0(1)0()0()1(xfxHxx4.4.3 4.4.3 牛頓法和修正牛頓法牛頓法和修正牛頓法2. 2. 修正牛頓法：修正牛頓法：為最優(yōu)步長

55、因子。(k)其中, )(k)f(x1)(k)H(x(k)(k)x1)(kx則稱為牛頓方向，)(k)f(x1)(k)H(x(k)S令 算法框圖：算法框圖：4.4.3 4.4.3 牛頓法和修正牛頓法牛頓法和修正牛頓法l 使用牛頓法時，若目標(biāo)函數(shù)是嚴(yán)重非線性函數(shù)，則是否收斂將使用牛頓法時，若目標(biāo)函數(shù)是嚴(yán)重非線性函數(shù)，則是否收斂將與初始點有很大關(guān)系；而使用修正牛頓法，能保證每次迭代目標(biāo)與初始點有很大關(guān)系；而使用修正牛頓法，能保證每次迭代目標(biāo)函數(shù)值下降，從而放寬了對初始點的要求。函數(shù)值下降，從而放寬了對初始點的要求。l 若初始點選得合適，牛頓法的收斂速度相當(dāng)快。若初始點選得合適，牛頓法的收斂速度相當(dāng)快。

56、l 牛頓法求逆矩陣的工作量大，計算量與存儲量均隨牛頓法求逆矩陣的工作量大，計算量與存儲量均隨 n n2 2上升。上升。4. 4. 方法評價：方法評價：梯度法和牛頓法的比較：梯度法和牛頓法的比較：1 1、迭代格式、迭代格式)()()()(1)()()()1()()()()1(kkkkkkkkkxfxHxxxfxx2 2、梯度法只需計算一階偏導(dǎo)數(shù)，計算工作量小，遠(yuǎn)離最優(yōu)點時函、梯度法只需計算一階偏導(dǎo)數(shù)，計算工作量小，遠(yuǎn)離最優(yōu)點時函 數(shù)下降快，接近最優(yōu)點時收斂速度慢。數(shù)下降快，接近最優(yōu)點時收斂速度慢。3 3、牛頓法不僅需要計算一階偏導(dǎo)數(shù)，還需計算二階偏導(dǎo)數(shù)矩陣及其、牛頓法不僅需要計算一階偏導(dǎo)數(shù)，還需計算二階偏導(dǎo)數(shù)矩陣及其 逆矩陣，計算工作量大。但牛頓法具有二階收斂性，接近最優(yōu)點逆矩陣，計算工作量大。但牛頓法具有二階收斂性，接近最優(yōu)點 時收斂速度很快。時收斂速度很快。梯度法和牛頓法的比較梯度法和牛頓法的比較4.4.4 4.4.4 變尺度法變尺度法1. 1. 變尺度的定義：變尺度的定義：每確定一次搜索方向，調(diào)整一次模（尺度）的大小，稱為變尺度。每確定