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

1、第四章第四章無約束問題的最優(yōu)化方法無約束問題的最優(yōu)化方法4.1 4.1 引言引言4.2 4.2 單變量優(yōu)化計(jì)算方法單變量優(yōu)化計(jì)算方法4.3 4.3 多變量優(yōu)化計(jì)算方法多變量優(yōu)化計(jì)算方法4.4 4.4 多變量優(yōu)化計(jì)算的梯度方法多變量優(yōu)化計(jì)算的梯度方法4.5 4.5 多變量多變量無約束優(yōu)化設(shè)計(jì)方法小結(jié)無約束優(yōu)化設(shè)計(jì)方法小結(jié)4.1 4.1 引言引言一一. . 目的：目的：求一組求一組 n n 維設(shè)計(jì)變量維設(shè)計(jì)變量 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)點(diǎn)即求目標(biāo)函數(shù)的最優(yōu)解：最優(yōu)點(diǎn) x x* * 和最優(yōu)值和最優(yōu)值 f(xf(x* *) ) 。二二.意義意義：l 為有約束優(yōu)化方法的研究提供了策略思想、概念基礎(chǔ)和基本方為有約束優(yōu)化方法的研究提供了策略思想、概念基礎(chǔ)和基本方法；法；l 為有約束優(yōu)化問題的間接解法提供了有效而方便的方法；為有約束優(yōu)化問題的間接解法提供了有效而方便的方法；l 對(duì)于某些工程問題，進(jìn)行分析后，便于提供解決的有效方法；對(duì)于某些工程問題，進(jìn)行分析后，便于提供解決的有效方法；l 不可避免地還存在無約束優(yōu)化的設(shè)計(jì)問題。不可避免地還存在無約束優(yōu)化的設(shè)計(jì)問題。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次迭代時(shí)，從已知點(diǎn)次迭代時(shí)，從已知點(diǎn) 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) 臺(tái)勞展開；臺(tái)勞展開； 取二次近似：取二次近似： )()()(2)()()()()()(21)()(kkTkkTkkkkSxHSSxfxfSxf 4.2.1 4.2.1 搜索區(qū)間的確定：搜索區(qū)間的確定： 4.2 4.2 單變量優(yōu)化計(jì)算方法單變量優(yōu)化計(jì)算方法：0)()()(kkSxfdd對(duì)對(duì)求導(dǎo)，令其為零。求導(dǎo)，令其為零。 0)()()()()()()(kkTkkTkSxHSSxf)()()()()(

5、)()()(kkTkkTkkSxHSSxf2. 2. 數(shù)值迭代法：數(shù)值迭代法：直接法直接法應(yīng)用序列消去原理：應(yīng)用序列消去原理： 分?jǐn)?shù)法、分?jǐn)?shù)法、黃金分割法黃金分割法近似法近似法利用多項(xiàng)式函數(shù)逼近（曲線擬合）原理：利用多項(xiàng)式函數(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ù)只有一個(gè)峰值，則此區(qū)間為單峰區(qū)間。單峰個(gè)峰值，則此區(qū)間為單峰區(qū)間。單峰區(qū)間內(nèi)，一

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

7、區(qū)間的確定：給定初始點(diǎn)給定初始點(diǎn)(0)(0)、初始步長、初始步長h,h,求初始搜索區(qū)間的步驟求初始搜索區(qū)間的步驟: :(0)(0) 可任取，最好接近最小點(diǎn)，可取可任取，最好接近最小點(diǎn)，可取(0)(0)=0=0，h0,h0,(2)(2)令令(0)(0)(1)(1) ， (1)(1)+h+h(2)(2) ,得兩個(gè)試點(diǎn)得兩個(gè)試點(diǎn)(1)(1)(2)(2) 計(jì)算計(jì)算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）為起點(diǎn)，步

8、長加倍，直至兩端大中間小，為起點(diǎn)，步長加倍，直至兩端大中間小，（4 4）f f2 2ff1,1, 則后退則后退 運(yùn)算。運(yùn)算。 （如圖）（如圖） 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選初始點(diǎn)

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)取兩點(diǎn),（此例中在,第二次在區(qū)間；,舍去，,)則*f()若f(；,和,舍去，,)則*f()若f(；,舍去，,)則*f()若f(),)和f(f(比較）（），（，,內(nèi)取兩點(diǎn),第一次在區(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), ,任取兩點(diǎn)任取兩點(diǎn)(1(1）與與(2(2），且，且aa(1) (1) (2) (2) bb計(jì)算計(jì)算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） 這時(shí)，不論丟掉這時(shí)，不論丟掉a,a,(1)(1) ) 還是還是(2)(2),

12、b, ,b, * *必在留必在留 下的部分內(nèi)下的部分內(nèi)對(duì)于第對(duì)于第(1)(1)、(2)(2)種情況，只要種情況，只要再取一個(gè)點(diǎn)再取一個(gè)點(diǎn)(3)(3) 就可進(jìn)行比較、就可進(jìn)行比較、消去。但對(duì)于第三種情況，就要消去。但對(duì)于第三種情況，就要補(bǔ)充兩個(gè)點(diǎn)。因此第三種合并為補(bǔ)充兩個(gè)點(diǎn)。因此第三種合并為前兩種前兩種: :(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歐幾里德幾何稱這種邊長分割為黃金分割。歐幾里德幾何稱這種邊長分割為黃金分割。 序列消去法中，為提高效率，減少計(jì)算量和存序列消去法中，為提高效率，減少計(jì)算量和存儲(chǔ)量，儲(chǔ)量，希望在每一次縮短搜索區(qū)間迭代過程中希望在每一次縮短搜索區(qū)間迭代過程中兩計(jì)算點(diǎn)兩計(jì)算點(diǎn)(1)(1)、(2)(2)，在區(qū)間中的位置相對(duì)于邊，在區(qū)間中的位置相對(duì)于邊界來說應(yīng)是對(duì)稱的，而且還要求丟去一段后保留界來說應(yīng)是對(duì)稱的，而且還要求丟去一段后保留點(diǎn)在新區(qū)間中的位置與丟去點(diǎn)再原區(qū)

14、間中的位置點(diǎn)在新區(qū)間中的位置與丟去點(diǎn)再原區(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法計(jì)算程序框圖3.4 3.4 二次插值法（拋物線法）二次插值法（拋物線法）1. 1. 基本原理：基本原理： 。的最優(yōu)點(diǎn)近似的極小值，以擬合曲線即用拋物線逼近擬用一元二次多項(xiàng)式的一元函數(shù)，是*,)(21fpfpfcbapSxfxfpkkk步驟：步驟： 133221321213132133221322212212312322323332222212111321231,f

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

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

17、,f4 4小者的點(diǎn)為小者的點(diǎn)為(2)(2) 兩側(cè)鄰點(diǎn)為兩側(cè)鄰點(diǎn)為(1)(1)、(3)(3) 根據(jù)原區(qū)間中根據(jù)原區(qū)間中(4)(4)，(2) (2) 的相對(duì)位置及的相對(duì)位置及f f2 2,f,f4 4的比的比較，有四種情況（如圖）較，有四種情況（如圖）, ,陰影線部分為丟去的，再對(duì)陰影線部分為丟去的，再對(duì)新區(qū)間三個(gè)新店代號(hào)一次作新區(qū)間三個(gè)新店代號(hào)一次作(1)(1)、(2)(2)、(3)(3)處理。計(jì)處理。計(jì)算算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.方法評(píng)價(jià)方法評(píng)價(jià): :4.2 4.2 坐標(biāo)輪換法和坐標(biāo)輪換法和 Poweel Poweel 法法一一. . 坐標(biāo)輪換法：坐標(biāo)輪換法：1. 1. 基本思想：基本思想：2. 2. 搜索方向與步長：搜索方向與步長： 每次以一個(gè)變量坐標(biāo)軸作為搜索方向，將每次以一個(gè)變量坐標(biāo)軸作為搜索方向，將 n n維的優(yōu)化問題轉(zhuǎn)化為一維搜索問題。例，第維的優(yōu)化問題轉(zhuǎn)化為一維搜索問題。例，第 k k輪迭代的第輪迭代的第 i i 次搜索，是固定除次搜索，是固定除 x

19、 xi i外的外的 n-n-1 1 個(gè)變量，沿個(gè)變量，沿 x xi i 變量坐標(biāo)軸作一維搜索，求變量坐標(biāo)軸作一維搜索，求得極值點(diǎn)得極值點(diǎn) x xi i(k)(k) n n 次搜索后獲得極值點(diǎn)序列次搜索后獲得極值點(diǎn)序列 x x1 1(k)(k), x, x2 2(k(k）, , x, xn n(k)(k)，若未收斂，則開始第，若未收斂，則開始第 k+1 k+1 次迭代，直至收斂到最優(yōu)點(diǎn)次迭代，直至收斂到最優(yōu)點(diǎn) x x* *。 。：次搜索的收斂條件輪第第；：次搜索的迭代公式輪第第；：次搜索的步長輪第第向；個(gè)設(shè)計(jì)變量的坐標(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、以計(jì)算新點(diǎn) x=x+ e、若取繼續(xù)向前， 直到目標(biāo)函數(shù)值增大，取前一點(diǎn)為本次新點(diǎn)5、不滿足精度時(shí)取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)點(diǎn)（求其無約束的最

21、優(yōu)點(diǎn)（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àn)驗(yàn)步步長長應(yīng)應(yīng)正正值值。軸軸的的移移動(dòng)動(dòng)方方向向：沿沿。先先判判斷斷。試試驗(yàn)驗(yàn)步步

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

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

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

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

27、l Poweel 法法（共軛方向法、方向加速法）：（共軛方向法、方向加速法）：3. 3. 共軛方向的性質(zhì)：共軛方向的性質(zhì)：二次收斂性。為步可收斂至極值點(diǎn)，稱多方向進(jìn)行一維搜索，至出發(fā)，依次沿從任意初始點(diǎn)，次函數(shù)個(gè)非零向量，則對(duì)于二矩陣共軛的是關(guān)于設(shè)矩陣共軛。中每一個(gè)向量關(guān)于，也是與向量組，向量和搜索，分別得到最優(yōu)點(diǎn)方向進(jìn)行一維出發(fā)，沿和分別從兩個(gè)初始點(diǎn)個(gè)非零向量，對(duì)于函數(shù)矩陣共軛的是關(guān)于設(shè)。滿足，個(gè)向量則可以構(gòu)造出是線性無關(guān)的向量組，若是線性無關(guān)的。個(gè)非零向量矩陣共軛的這組關(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. 步驟：步驟： 。的極值點(diǎn)xx作第三次搜索，求得f，沿此方向xx構(gòu)筑共軛方向：S。x,的極值點(diǎn)xx分別求得f作兩次一維搜索，S,兩個(gè)坐標(biāo)軸方向S，依次沿xx，令選初始點(diǎn)x第一輪迭代：131012112111211(0)10(0)4.3.2 4.3.2 Poweel Poweel 法法4. 4. 步驟：步驟：

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

30、說明：說明：l 若是正定二次函數(shù)，若是正定二次函數(shù)，n n 輪迭代后收斂于最優(yōu)點(diǎn)輪迭代后收斂于最優(yōu)點(diǎn) x x* * 。 若是非正定二次函數(shù)，則迭代次數(shù)增加。若是非正定二次函數(shù)，則迭代次數(shù)增加。l若是若是 n n 維問題，步驟相同。維問題，步驟相同。 搜索方向：第一輪迭代，沿初始方向組搜索方向：第一輪迭代，沿初始方向組 S Si i(1)(1) (i=1,2, (i=1,2,n) ,n) 的的 n n 個(gè)方向和共軛方向個(gè)方向和共軛方向 S S(1)(1)，搜索，搜索 n+1 n+1 次得極值點(diǎn)次得極值點(diǎn) 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 個(gè)方向和共個(gè)方向和共軛方向軛方向 S S(1)(1)，構(gòu)筑共軛方向，構(gòu)筑共軛方向 S S(2) (2) 搜索搜索 n+1n+1次得極值點(diǎn)次得極值點(diǎn) 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)，需要去除前一輪中的某個(gè)方向要去除前一輪中的某個(gè)方向 S Sm m(k)(k)。去除的原則請(qǐng)

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

33、從 方向進(jìn)行一維最優(yōu)搜索，計(jì)算出最方向進(jìn)行一維最優(yōu)搜索，計(jì)算出最優(yōu)步長優(yōu)步長 由此得最優(yōu)點(diǎn)由此得最優(yōu)點(diǎn))1(0 x)1(1s。 5)1(12122212141060)(xxxxxxxf10 012)1(21)1(1eses和和0501500)1(1x方方向向上上的的極極小小點(diǎn)點(diǎn)。，并并求求替替換換成成立立，故故應(yīng)應(yīng)以以檢檢驗(yàn)驗(yàn)判判別別條條件件下下降降量量計(jì)計(jì)算算相相鄰鄰二二點(diǎn)點(diǎn)函函數(shù)數(shù)值值的的方方向向上上的的反反射射點(diǎn)點(diǎn)計(jì)計(jì)算算個(gè)個(gè)方方向向計(jì)計(jì)算算第第優(yōu)優(yōu)點(diǎn)點(diǎn)方方向向進(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其其中中時(shí)時(shí)當(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)行，故停止運(yù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è)計(jì)空間中的幾何圖形不斷向好點(diǎn)移維設(shè)計(jì)空間中的幾何圖形不斷向好點(diǎn)移動(dòng)迭代的一種算法。動(dòng)迭代的一種算法。 單純形法是在單純形法是在n n維設(shè)計(jì)空間內(nèi)由維設(shè)計(jì)空間內(nèi)由n+1n+1個(gè)頂點(diǎn)組成的幾何形體，如在個(gè)頂點(diǎn)組成的幾何形體，如在二維空間，單純形為三角形，在三維空間內(nèi)為四面體等。若各頂二維空間，單純形為三角形，在三維空間內(nèi)為四面體等。若各頂點(diǎn)間的距離相等，則稱為正單純形。點(diǎn)間的距離相等，則稱為正單純形。(a) 二維空間三角形的反射(b) 三維空間四面體的收縮4.3.34.3.3單純形法單純形法單純形法迭代的單純形法迭代的基本要點(diǎn)基本要點(diǎn)是是如何保證單

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

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

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

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

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

44、(min)(rhcxfxfxf) 1, 2 , 1;, 2 , 1( 2/ )(njnixxxlijiji4.3.3單純形法單純形法如圖所示，在迭代計(jì)算中，由于單純形不斷向最好點(diǎn)移動(dòng)和縮小，因此當(dāng)單純形的n+1頂點(diǎn)的目標(biāo)函數(shù)值的均方差很小，即 就認(rèn)為算法收斂，終止計(jì)算，并令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è)計(jì)的梯度方法多變量優(yōu)化設(shè)計(jì)的梯度方法4.4.14.4.1梯度法（最速下降法）梯度法（最速下降法）：1. 1. 基本思想：基本思想：2. 2. 搜索方向：搜索方向： 目標(biāo)函數(shù)負(fù)梯度向量方向代表最速目標(biāo)函數(shù)負(fù)梯度向量方向代表最速下降方向，因此選擇負(fù)梯度向量方向作下降方向，因此選擇負(fù)梯度向量方向作為搜索方向，期望很快找到最優(yōu)點(diǎn)。為搜索方向，期望很快找到最優(yōu)點(diǎn)。)()()()(kkxfxf4.4.1 4.4.1 梯度法梯度法4. 4. 梯度法的計(jì)算框圖：梯度法的計(jì)算框圖：4.4.1 4.4.1 梯度法梯度法5. 5. 方法評(píng)價(jià)：方法評(píng)價(jià)：l 迭代過程簡單，對(duì)初始點(diǎn)的選迭代

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

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

48、x則令，n若k，檢查搜索次數(shù)步；若不滿足，則進(jìn)行第；xx*，若滿足，則迭代結(jié)束,)f(x是否判斷；Sxx方向作一維搜索，求得沿S)；f(xS計(jì)算，0k令；和計(jì)算精度選取初始點(diǎn)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是是是是否否否否計(jì)算計(jì)算(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. 方法評(píng)價(jià)：方法評(píng)價(jià)：l迭代程序簡單，容易實(shí)現(xiàn)編程，存儲(chǔ)量較小。迭代程序簡單，容易實(shí)現(xiàn)編程，存儲(chǔ)量較小。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ù)為 ，起始，起始點(diǎn)為點(diǎn)為x x(0)(0)00，00T T，試用共軛梯度法求其極小點(diǎn)。，試用共軛梯度法求其極小點(diǎn)。2122212141060)(

50、xxxxxxxf(1)(1)12,( )Txxf x將代入得4.4.2 4.4.2 共軛梯度法共軛梯度法解解：第一次迭代的方向?yàn)椋旱谝淮蔚姆较驗(yàn)椋核运缘诙蔚较虻诙蔚较驗(yàn)闉?53.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á)極小點(diǎn)故經(jīng)兩次搜索即達(dá)極小點(diǎn)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) 點(diǎn)作臺(tái)勞展開，取二次函數(shù)式點(diǎn)作臺(tái)勞展開，取二次函數(shù)式(x) (x) 作為近作為近似函數(shù)似函數(shù), ,以以(x) (x) 的極小值點(diǎn)作為的極小值點(diǎn)作為 f(x) f(x) 的近似極小值點(diǎn)。的近似極小值點(diǎn)。( )( )( )( )( )( )( )( )( )( )( )( )1( )minmin( )( )1()()() ()()()2( )()()(),( )0,()(),*k

53、kkTkkTkkkkkkkkf xxxf xf xxxxxH xxxxf xH xxxxxxH xf xxx (k)(k+1)(k)(令得。由于在x 點(diǎn)附近，函數(shù) (x)和f(x)是近似的，所以 x=x -H(xk) -1(k)f(x )說明：說明：lf(x) f(x) 若是正定二次函數(shù)，一般迭代一次即可；若是嚴(yán)重非若是正定二次函數(shù)，一般迭代一次即可；若是嚴(yán)重非線性函數(shù)，則可能不收斂，或收斂到鞍點(diǎn)。線性函數(shù)，則可能不收斂，或收斂到鞍點(diǎn)。)為牛頓步長。(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ù)為，試用牛頓法求其極小點(diǎn)。初始點(diǎn)取x(0)=0,0T解：先計(jì)算所以得由此可見（與例4-3比較），對(duì)于任何正定二次函數(shù)，只需迭代一次，即求出其極小點(diǎn)?？梢宰C明，當(dāng)目標(biāo)函數(shù)滿足一定條件，且初始點(diǎn)選得較好時(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 使用牛頓法時(shí)，若目標(biāo)函數(shù)是嚴(yán)重非線性函數(shù)，則是否收斂將使用牛頓法時(shí)，若目標(biāo)函數(shù)是嚴(yán)重非線性函數(shù)，則是否收斂將與初始點(diǎn)有很大關(guān)系；而使用修正牛頓法，能保證每次迭代目標(biāo)與初始點(diǎn)有很大關(guān)系；而使用修正牛頓法，能保證每次迭代目標(biāo)函數(shù)值下降，從而放寬了對(duì)初始點(diǎn)的要求。函數(shù)值下降，從而放寬了對(duì)初始點(diǎn)的要求。l 若初始點(diǎn)選得合適，牛頓法的收斂速度相當(dāng)快。若初始點(diǎn)選得合適，牛頓法的收斂速度相當(dāng)快。

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