機(jī)械優(yōu)化設(shè)計(jì)之無約束優(yōu)化辦法課件

1、機(jī)械優(yōu)化設(shè)計(jì)何軍良2016年9月2208:19Shanghai Maritime University190919121958200408:19Q優(yōu)化設(shè)計(jì)概述0優(yōu)化設(shè)計(jì)的數(shù)學(xué)基礎(chǔ)働一維搜索方法ME無約束優(yōu)化方法CONTENTS働線性規(guī)劃約束優(yōu)化方法機(jī)械優(yōu)化設(shè)計(jì)中的幾個(gè)問題第四章 無約束優(yōu)化方法坐標(biāo)輪換法共覘梯度法071變尺度法08鮑威爾方法091單形替換法08:194.7變尺度法（1）問題提出1)梯度法 XXjgk)*簡(jiǎn)單,開始時(shí)目標(biāo)函數(shù)值下降較快,但趣來趣慢。2)阻尼牛頓法Xk+1 = Xk-aky2f(Xk)Yl7f(Xk)*目標(biāo)函數(shù)值在最優(yōu)點(diǎn)附近時(shí)收斂快”但要用到二階導(dǎo)數(shù)和矩陣求逆。能否

2、克服各自的缺點(diǎn),綜合發(fā)揮其優(yōu)點(diǎn)?變尺度法也稱擬牛頓法,它是基于牛頓法的思想而又作了重大改進(jìn)的一 類方法。我們所介紹的變尺度法是由Davidon于1959年提出又經(jīng) Fletcher和Powell加以發(fā)展和主善的一種變尺度法,故稱為DFP變尺 度法。08:194.7變尺度法梯度法：x=x-agk牛頓法：嚴(yán)）"約-/戲九變量的尺度變換是放大或縮小各個(gè)坐標(biāo)。通過尺度變換可以把函數(shù)的 偏心程度降到最低限度。這種算法僅用到梯度，不必計(jì)算海賽陣及其逆矩陣，但又能使搜索方 向逐漸逼近牛頓方向,具有較快的收斂速度。尺度變換技巧能顯著地改進(jìn)幾乎所有極小化方法的收斂性質(zhì)。例如在用最速下降法求/（%，%）

3、 =北了 +25上：極小值時(shí)，需要進(jìn)行10 次迭代才能達(dá)到極小點(diǎn)。(2 )基本思想對(duì)于二次函數(shù)：/(x)二xTGx+bTx+c進(jìn)行尺度變換“ 5目的：減少二次項(xiàng)的偏心在新的坐標(biāo)系中，函數(shù)/仗)的二次項(xiàng)變?yōu)?-xrGx-xrQrGQx2 2如G是正定,則總存在矩陣0 ,使得:QtGQ = I1108:194.7變尺度法用矩陣O'右乘等式兩邊,得：QTG = Q1用矩陣0左乘等式兩邊,得：QQTG = I所以 Q0 =G-'上式說明：二次函數(shù)矩陣G的逆陣,可以通過尺度變換 矩陣4 = QQT來求得。1108:194.7變尺度法x(k+i) =xw -a(k)Akgk去為構(gòu)造的&qu

4、ot;階對(duì)稱矩陣,它隨迭代點(diǎn)的位置變化而變化,對(duì)梯 度起到改變尺度的作用,又稱為變尺度矩陣。 Ak =1,上式為梯度法的迭代公式若念=Hk i ,上式為阻尼牛頓法的迭代公式(2)當(dāng)矩陣去不斷地迭代而能很好地逼近V7(x)-*時(shí),就可以不再需要計(jì)算二階導(dǎo)數(shù)。(3)變尺度法的搜索方向:S= -Akgk ,稱為擬牛頓方向。 變尺度法的關(guān)鍵在于尺度矩陣綣的產(chǎn)生。(4)變尺度矩陣的產(chǎn)生擬牛頓方向S二血必須具有下降性、收斂性和 計(jì)算的簡(jiǎn)便性。下降性一妾求變尺度矩陣為對(duì)陣正定矩陣；收斂性-華求變尺度矩陣逐漸逼近砒,滿足擬牛頓條件；簡(jiǎn)便性r望變尺度矩陣有如下遞推形式: Ar+1 =k +k1108:194.7

5、變尺度法下降性:要求S與濟(jì)之間的夾角小于90。f即：S伙)TgQO將擬牛頓方向帶入上式,得：4S切Tg廠AkgkVgk=妝弘皿 > 0所以只要為對(duì)陣正定矩陣,S就是下降方向。(4)變尺度矩陣的產(chǎn)生簡(jiǎn)便性:變尺度矩陣是隨迭代過程的推進(jìn)而逐次改變的,因而它是一種矩陣序列念, k=l, 2,選取初始矩陣4。,并以梯度方向快速收斂,通常取單位矩陣E作為 初始矩陣,BPA0=Eo而后的矩陣均是在前一構(gòu)造矩陣的基礎(chǔ)上校正 得到,令勺訛+心。(.矩陣序列的推廣到一般的反+1次構(gòu)造矩陣/J基本迭代式J Ak稱為校正矩陣1108:194.7變尺度法構(gòu)造矩陣仏+1應(yīng)該滿足一個(gè)重要條件一J以牛頓條 件變尺度法

6、采用構(gòu)造矩陣來代替牛頓法中海賽矩陣的逆陣 主要目的之一就是為了避免計(jì)算二階偏導(dǎo)數(shù)和逆矩陣 力圖僅用梯度和其他一些易于獲得的信息來確定迭代方向 因此 擬牛頓條件是關(guān)于海賽矩陣和梯度之間的關(guān)系。(5 )擬牛頓條件設(shè)F3)為一般形式"階的目標(biāo)函數(shù)，并具有連續(xù)的一、二階偏導(dǎo)。在點(diǎn) 工處的二次泰勒近似展開F(x)心 F(f) +心該近似二次函數(shù)的梯度為:VF(x) « gk +Hkx式中=，若令x = x('+i),則有k+igkHk(x(k+l)嚴(yán))H k' (g k+ g Q(5 )擬牛頓條件上式中 ，無仗+1)X 稱之為位移矢量,并簡(jiǎn)化書寫:ak =x(k+l)

7、-x(k)而gk+1 - gk是前后迭代點(diǎn)的梯度矢量差 > 簡(jiǎn)化書寫:兒=g 5 g k自以上三式得:bkHk海賽矩陣與梯度間的關(guān)系式1108:194.7變尺度法(5 )擬牛頓條件按照變尺度法產(chǎn)生構(gòu)造矩陣的遞推思想,期望能夠借助前一次迭代的某些結(jié)果來計(jì)算下一個(gè)構(gòu)造矩陣,因此可以根據(jù)上式,用第k+l次構(gòu)造矩陣Ak+i近似代替<則上式即產(chǎn)生構(gòu)造矩陣Ak+i應(yīng)滿足的一個(gè)重要條件 > 通常稱為擬牛頓 條件或擬牛頓方程2108:194.7變尺度法(6)變尺度矩陣的構(gòu)造擬牛頓條件% = Aui九 可寫成(4 + AAJ %二空或4兒DFP算法中的校正矩陣 取為下列形式:將代入：yk +兒

8、=6 &幾兩邊對(duì)比得：&川申；幾=6， 0嚴(yán)":幾=4取 uk =(Jkvk= A yk回代到(2)得：厶4 S 人幾幾4 A E兒丈4兒則：aFA=-1乂4兒DFP變尺度法的迭代式為：k+l =Xk -akAkVf(Xk)由上式可以看出，構(gòu)造矩陣如+1的確定取決于第k次迭代中的下列 信息：上次的構(gòu)造矩陣：Ak迭代點(diǎn)的位移矢量:6 = *2) _兀迭代點(diǎn)的梯度增量：兒因此 不必作二階導(dǎo)數(shù)矩陣及其求逆的計(jì)算S兒兒4兒1708:194.7變尺度法(7) DFP變尺購法的特點(diǎn) DFP算法的收斂速度介于梯度法和牛頓法之間。 DFP法具有二次收斂性(搜索方向的共覘性)。對(duì)于二次

9、函數(shù)F(x) , DFP法所構(gòu)成的搜索方向序列S®, S，S(2)，為一組關(guān)于海賽矩陣H共轆的矢量，即DFP法屬于共轆方向法f具有二次收斂性。在任何情況下f這種方法對(duì)于二次目標(biāo)函數(shù)都將在步內(nèi)搜索到目標(biāo)函數(shù)的最優(yōu)點(diǎn) 而且最后的構(gòu)造矩陣A必等于海賽矩陣H。1.關(guān)于算法的穩(wěn)定性 數(shù)值計(jì)算穩(wěn)定性較差。算法的穩(wěn)定性是指算法的每次迭代都能使目標(biāo)函數(shù)值單調(diào)下降。2.構(gòu)造矩陣正定性從理論上肯定了DFP法的穩(wěn)定性，但實(shí)際上f 由于每次迭代的一維搜索只能具有一定的精確度,且存在機(jī)器 運(yùn)算的舍入誤差，構(gòu)造矩陣的正定性仍然有可能遭到破壞；3為了提高實(shí)際計(jì)算中的穩(wěn)定性,_方面應(yīng)對(duì)一維搜索提出較高 的精度要求,

10、另一方面,當(dāng)發(fā)生破壞正定性時(shí),將構(gòu)造矩陣重 置為單位矩陣E重新開始,通常采用的簡(jiǎn)單辦法是在«次迭代 后重置單位矩陣1908:194.7變尺度法（8） DFP變尺度算法的計(jì)算步驟1.任取初始點(diǎn)卅）給出迭代精度£計(jì)算初始點(diǎn)精度g。商（八）及其 模Iloilo若血卜礙專步驟（7），否則進(jìn)行下一步2.置氐0 ,取 Ak-E3計(jì)算迭代方向S=-AkgklQS方向做一維搜索求優(yōu)化步長 a,使Fx（k）+a（k）S伙）= min F（x +&S伙）確定下一個(gè)迭代點(diǎn)嚴(yán)）=F）+/）s 2108:194.7變尺度法（8） DFP變尺度算法的計(jì)算步驟4計(jì)算泌+】）的梯度+1及其模ll+

11、i|，若I以+§ £則轉(zhuǎn)步驟, 否則轉(zhuǎn)下一步5計(jì)算位移矢量6和梯度矢量兒6 =兀（2）?；铮﹥?孤+1一孤按DFP公式計(jì)算構(gòu)造矩陣4+14.Ak yk yTk AAk *rTyk $k A 兒6.豊k-Z 若k<n （n為優(yōu)化問題的維數(shù)）返步驟 >否則返步驟7輸出最優(yōu)解（兀*，”*），終止計(jì)算22n8:1923n8:19D F p算法流程圖輸入:k jO A計(jì)算：g(0)(O)JI I.F (x(o)A")yy% A“+i) a(«)+ m _ N伙+1)S伙+】）x(0) J x(ul)(+1)(斤+1)X*F* J F(x*)Sj_f)g

12、min F(x(/:) + a(k)S(k) > ak)嚴(yán))Sg 伙+1）jVF（?；?1）<?出口2308:194.7變尺度法(9) DFP算例例：用DFP算法求下列問題的極值：/(x“2)= 4jT - lxxx2解：1 )取初始點(diǎn)X0 = 1 1；為了按DFP法構(gòu)造第一次搜 尋方向別,需計(jì)算初始點(diǎn)處的梯度Vf(x°) =4x2 2兀-423108:194.7變尺度法3108:194.7變尺度法取初始變尺度矩陣為單位矩陣4。訂f則第一次搜尋方向?yàn)閞f0=-A0Vf(x°) = -0_-41_ 4_12-210(9) DFP算例沿別方向逬行一維搜索,得11x1

13、 = x° + a odQ4-2+仏。2%3108:194.7變尺度法3108:194.7變尺度法得：勺=0.25 疋2 ）再按DFP法構(gòu)造點(diǎn)0處的搜尋方向/ ,需計(jì)算_維搜索最佳步長應(yīng)滿足/(x1) = min/(x° + cif0J0) = min(40cif()2 20a()-3)aa2 10.53108:194.7變尺度法3108:194.7變尺度法巧（丄）=3108:194.7變尺度法(9) DFP算例Ag°=gl-g°Ax° = x1 -x°代入校正公式0 _ Ax°Ax° r A0Ag0Ag°

14、;rA0 "Ax°rAg° Ag°rA°Ag01-0.51 -0.5丁-43 -41 -0.5'3 '-43 -4_ 3 _-4(9) DFP算例3108:194.7變尺度法3108:194.7變尺度法9-12A110-1216第二次搜尋方向?yàn)閐l=-Algl =866521251950195041Too3108:194.7變尺度法3108:194.7變尺度法2 + a.5 1n c 60.5 H of5 1再沿 1進(jìn)行一維搜索"得x2 = X1 + axd1 =3108:194.7變尺度法(9) DFP算例匕為一維搜

15、索最佳步長,應(yīng)滿足/(x2) = min/Cx1 +a/T) = min(-4al)52a得52伶 a= x14梯度：Vf(x2) =海賽矩陣:V2/(x2) =2兀一 2兀44x2 2xx2 -2-24X23 )判斷妒是否為極值點(diǎn)因此為極小點(diǎn)。2808:194.7變尺度法K'S梯度為零向量，海賽矩陣正定。可見滿足極值充要條件因此為極小點(diǎn)。2808:194.7變尺度法(9) DFP算例例:用DFP變尺度法求目標(biāo)函數(shù)F(x) = 4(“ 5嚴(yán) +(£ -6)2的最優(yōu)解。已知初始點(diǎn)嚴(yán)=89丁 ,迭代精度滬0.01_24_8_24列) -6 |_9 6cif(0)解:第一次迭代:g

16、o = VF(x(0)=8(%| 5)2(x2 6)(8,9)'24_6g°| =24.3>gs(°)=A)go =-24_-6MM(1)JO)Q+ 9 *-8.21538gl=VF(x(1) =-0.107844.43076(9) DFP算例式中最優(yōu)步長應(yīng)用一維搜索方法在計(jì)算機(jī)上求解。為了說明問題,又因?yàn)榇死繕?biāo)函數(shù)簡(jiǎn)單,所以用解析法來求:F(x(1) = f(a) = 4(8 - 24a) - 5+ (9 -6a- 6)2得：a(0) =0.13077為求極小 > 將上式對(duì)疣求導(dǎo) < 并令廠盤）=0于是：%(1)4.861521g =4.567

17、16£(9) DFP算例第二次迭代: 確趕點(diǎn)的擬牛頓方向Scr0 = xx(0)=-3.13848-0.78462y()= gigo =- 25.10784-1.56924按DFP公式計(jì)算構(gòu)造矩陣芻F+寧聖產(chǎn)5)X) y0 A)X)316U808寸Z8寸寸 -2n<IHr ZJO8ZOf-111N<urla)sss匡mCHa (6) ss卜寸4.7 ss(9) DFPW0U2IIX2II一4.9999才6.00014_-0.00016'0.00028H 0.00032 A m4.999900!600014908:194.7變尺度法(9) DFP算例討論:o按DFP

18、搜索方向?yàn)楣厕A的性該題的理論最優(yōu)點(diǎn)是質(zhì),本題為二元二次函數(shù)在兩次迭代后即達(dá)到最優(yōu)點(diǎn),本題計(jì)算 結(jié)果稍有誤差，這是由于一維搜索的不精確性產(chǎn)生的。若在已知A】的基礎(chǔ)上f再用DFP公式遞推下一次的構(gòu)造矩陣f可計(jì)算得0.12500A =200.5000而計(jì)算目標(biāo)函數(shù)海賽矩陣的逆陣有J.804.7變尺度法(9) BFGS變尺度法DFP算法由于舍入誤差和_維搜索的不精確,有可能導(dǎo)致奇異,而使數(shù)值穩(wěn)定性方面不夠理想。所以1970年,Broyden、Fletcher、Goldstein、Sharnio等人提出一種更穩(wěn)定的算法,稱為BFGS算法。其校正公式為:4.8鮑威爾方法（1）概述I基本思想：基于坐標(biāo)輪換法

19、,不用求導(dǎo)數(shù),在迭代中逐次 產(chǎn)生共轆搜索方向。收斂效果：對(duì)于正定（有極小值）二次函數(shù),經(jīng)過兀輪迭代 后求得極小點(diǎn)；對(duì)于非二次函數(shù),一般也具有較高的收斂 速度。Powell法是求解無約束優(yōu)化問題的最好方法。將其與懲罰 函數(shù)法結(jié)合,可以處理有約束優(yōu)化問題。3408:194.8鮑威爾方法（2 ）共轆方向的生成xxk+i為兩個(gè)極小點(diǎn)根據(jù)梯度與等值面之間關(guān)系可知（刃）1 =0（刃丁（氣1一緞）=°（/） gk+ o(2 )共轆方向的生成384.8鮑威爾方法(2 )共覘方向的生成（刃X+i-gQ = （結(jié)論：從不同的點(diǎn)出 發(fā)沿某一方向分別對(duì)9k函數(shù)作兩次一維搜索,得到兩個(gè)極小點(diǎn) 那么這兩個(gè)極小點(diǎn)

20、的 連線方向與該方向?qū)共覘08:193908:19TG(xk+l-xk) = OdJ9k+idk3908:194.8鮑威爾方法4008:194.8鮑威爾方法（3 ）基本算法鮑威爾基本算法的搜索過程（二維）X）任選一初始點(diǎn)0 再 選兩個(gè)線性無關(guān)的向量 如坐標(biāo)軸單位向量 匂二1,0卩和乞二0，1卩作為 初始搜索方向。（3 ）基本算法鮑威爾基本算法的搜索過程（二維）2）從0出發(fā)，順次沿珀乞 作一維搜索f得城，扃點(diǎn)， 兩點(diǎn)連線得一新方向加4008:194.8鮑威爾方法（3 ）基本算法鮑威爾基本算法的搜索過程（二維）用/代替匂形成兩個(gè)線性無關(guān)向量/島作為下一輪迭代的 搜索方向。再從城出發(fā)沿/作一維搜索

21、得點(diǎn)兀罷作為下一輪迭代的初始點(diǎn)。3 ）從球?qū)绨l(fā),» e2?> d1作一維搜索,得到 點(diǎn)x；, 兩點(diǎn)連線得一新 方向：d = x2 xo從現(xiàn)沿/作一維搜索得點(diǎn)X2 O即是二維問題的極小點(diǎn)疋(3 )基本算法鮑威爾基本算法的搜索過程(二維)方法的基本迭代格式包括共轆方向產(chǎn)生和方向替換兩主要步驟。° 4308:194.8鮑威爾方法(3 )基本算法鮑威爾基本算法的搜索過程(三維)1.第一輪基本方向組取單位坐標(biāo)矢量系 % g e“ ,沿這些方向依次作一維 搜索,然后將始末兩點(diǎn)相連 作為新生方向。輪的基本方向組是將上輪的第一個(gè)方向淘汰,上輪的新生方向補(bǔ)入本輪的最后而構(gòu)成：d2k,

22、d3k, dk2.再沿新生方向作一維搜索， 完成第一輪的迭代。以后每4908:194.8鮑威爾方法4908:194.8鮑威爾方法(4)基本算法示例4908:194.8鮑威爾方法4908:194.8鮑威爾方法例 用Powell方法求解下列問題;min/(x) (Xi +> +(4 1)*解 取初始點(diǎn)和初始搜索方向分別為4908:194.8鮑威爾方法4908:194.8鮑威爾方法4908:194.8鮑威爾方法(4 )基本算法示例第1輪迭代置<1>0)下面用解析法求*x)沿直線的極小點(diǎn).先沿邊°作一維搜索，min yXF®基本算法示例令卩(入)=兀*5+加小“)

23、=(3+A)2 +<1+A)S 如=2C3+A) +2(1+入)=0, dA得到 Ai = -2,x<1*n = (0,1)T再從出發(fā)，沿出m作一維搜索:4908:194.8鮑威爾方法4908:194.8鮑威爾方法min /(xGU,十疋J, X4908:194.8鮑威爾方法4908:194.8鮑威爾方法令爭(zhēng) GO = /(xu-n + 人護(hù) 2) = (1+A)2 + 1, 學(xué)=2( 1 + A) 0,dA47得到九=U" =(0,0)T.(4 )基本算法示例令方向 就“=x(1,2> x(K<>> = *.作一維tn搜索:min 彳(算門+屈&

24、quot;3八A令甲=y(x<K2) + W約)=(3A)2 + ( 2A I)2. 霑=1%-4(-24 1) = 0,得到山=_邑4908:194.8鮑威爾方法(4 )基本算法示例經(jīng)第1輪迭代，得到最好點(diǎn)4908:194.8鮑威爾方法4908:194.8鮑威爾方法- 2人-A13213=一卸494.8鮑威爾方法(lf2>(2+2)(4 )基本算法示例第2輪迭代+第2輪的搜索方向?yàn)?2.1>初始點(diǎn)為斗=兀08:194132135008:194.8鮑威爾方法(4 )基本算法示例下面仍用解析方法求八工)在直線上的極小點(diǎn).先沿占?小搜索:min 心“ +加)，A5108:194.

25、8鮑威爾方法5108:194.8鮑威爾方法得到Ai =魯及點(diǎn)算仁.1)= x(2,0> + 入if 門"4 "r4 _13_ 6'O'13213 1.413OX!_13 J5108:194.8鮑威爾方法5108:194.8鮑威爾方法(4 )基本算法示例再沿搜索:min /(x<2a)+加3亠A5108:194.8鮑威爾方法5108:194.8鮑威爾方法得到a2 = -18169及點(diǎn)x(2> =工宀小十&"> =13r 88 -169_ 34廠而一5108:194.8鮑威爾方法(4 )基本算法示例5108:194.8鮑

26、威爾方法_兀(20)4-'361316926013_一 169-8816934169r 8曠-361699169l n+ V344,60-1 -169MB169A最后，從屮岀發(fā)，沿出門作一維搜索: min /(x(2'2) +Arf(2>).AQ得到入嚴(yán)才及極小點(diǎn)文=±22> +和肝)514.8鮑威爾方法(4 )基本算法示例I08:190町2#08:194.8鮑威爾方法(5)基本算法缺陷況。如第k輪中f產(chǎn)生新的方向:可能在某一輪迭代中出現(xiàn)基本方向組為線性相關(guān)的矢量系的情Jk=xnk-xok=a1kJ1k+ a2kJ2k + + anMnk式中 £

27、叱砒.心*為第k輪基本方向組矢量，5508:194.8鮑威爾方法(5)a2 禺*為各方向的最優(yōu)步長。若在第k輪的優(yōu)化搜索過程中出現(xiàn),則方向小表示為姑. d3 血啲線性組合，以后的各次搜索將在降維的空間 逬行,無法得到維空間的函數(shù)極小值,計(jì)算將失敗。#08:194.8鮑威爾方法(5)基本算法缺陷56鮑威爾基本算法的退化如圖所示為一個(gè) 三維優(yōu)化問題的 示例,設(shè)第一輪 中咕0 ,則新 生方向與巧、e3 共面,隨后的各 環(huán)方向組中,各 矢量必在該平面 內(nèi),使搜索局限 于二維空間,不 能得到最優(yōu)解。08:194.8鮑威爾方法(5)（5 ）基本算法缺陷例用Powell方法求解卜列問題：min （4 + 工

28、3）+（ Hi 十 + 並）'+（Q + 孔一工3）2 +取初始點(diǎn)才' = （*",*），搜索方向基本算法缺陷解用Powell方法求解.首先置丘“），從0】小出發(fā)，沿川“搜索: min /（x（1-0> +洌?。?，"in211AJ+A1丄護(hù)（入）=y）十=（i-a）2+a2 +（i+a>5908:194.8鮑威爾方法(5)基本算法缺陷令 /(A)=0,即 一 2(1人)+2入+ 2( 1+4) = 0.由此得到Ai =0,因此有#08:194.8鮑威爾方法(5)#08:194.8鮑威爾方法(5)LTJ#08:194.8鮑威爾方法(5)#08:19

29、4.8鮑威爾方法(5)從0Z岀發(fā)沿肝搜索:T 1 -TVT1+ A11 +入101石己小+ W)=616U80無曲5!吳羈鮒 ou(K+I)z+Q+s 戢6"(0*令 (K + I) + 人YI) + = K+ I) " ( £二PK+ =【>)、=:Q)38G08:194.8鮑威爾方法（5 ）基本算法缺陷再從Qg出發(fā)，沿於心搜索:6108:194.8鮑威爾方法#08:194.8鮑威爾方法x(r23 +=O'0丄T丄T_i+A令屛（入=0號(hào)即2（扌+入）+2（* +入）一2廠入=0,#08:194.8鮑威爾方法6308:194.8鮑威爾方法(5)基本

30、算法缺陷#08:194.8鮑威爾方法#08:194.8鮑威爾方法得到入產(chǎn)_壬及點(diǎn)#08:194.8鮑威爾方法#08:194.8鮑威爾方法xu,3> = x<ls2> 十 Aid丄2"1T_18.#08:194.8鮑威爾方法(5 )基本算法缺陷第1階段迭代的最后一步是從疋z出發(fā)，沿方向丄181T1丄T0一2_2_9作一維搜索:min+0Z 人(5 )基本算法缺陷min /（x<n3?6508:194.8鮑威爾方法#08:194.8鮑威爾方法丄T518O'3L184a6708:194.8鮑威爾方法#08:194.8鮑威爾方法爭(zhēng)（入）=/（x（n3>

31、+0"）#08:194.8鮑威爾方法(5)基本算法缺陷令“)= 0.即5)-由此得到局=寺及點(diǎn)8丄X*1® +姑曠X)=丄1#08:194.8鮑威爾方法(6 )修正算法#08:194.8鮑威爾方法(6 )修正算法(5)基本算法缺陷#08:194.8鮑威爾方法(6 )修正算法#08:194.8鮑威爾方法(6 )修正算法由第1輪搜索結(jié)果可知.在第2輪搜索時(shí)，前3個(gè)方向占1線性相關(guān),#08:194.8鮑威爾方法(6 )修正算法#08:194.8鮑威爾方法(6 )修正算法繼續(xù)作下去，所得點(diǎn)的第一個(gè)分量恒為此永遠(yuǎn)達(dá)不到極小點(diǎn)x=(0,0,0>T,#08:194.8鮑威爾方法(6

32、 )修正算法#08:194.8鮑威爾方法(6 )修正算法可見：如果在某輪迭代中,#08:194.8鮑威爾方法(6 )修正算法#08:194.8鮑威爾方法(6 )修正算法個(gè)搜索方向線性相關(guān)或近似線性相關(guān),#08:194.8鮑威爾方法(6 )修正算法#08:194.8鮑威爾方法(6 )修正算法會(huì)給Powell方法的收斂性帶來嚴(yán) 重后果口選取個(gè)線性無關(guān)且盡可能共轆的方向作為下一輪搜索的方向組。做法：形成新的搜索方向組時(shí),不是定的去掉前一次搜索方向組中的第一個(gè)方向 < 而是首先根據(jù)Powell條件f判斷原方向組是否需要替換f 若需要,則進(jìn)一步判斷原方向組中哪個(gè)方向最壞 <并以前一輪新生成的

33、 搜索方向替換本輪中的這個(gè)最壞方向。*根據(jù)Powell條件判定是否需換方向；如需換向,則換掉函數(shù)值下降量最大的方向。方向組的構(gòu)造在第吃輪的搜索中 < 祁為初始點(diǎn) > 搜索方向?yàn)樯?兮 心J產(chǎn) 生的新方向?yàn)楸?> 此方向的極小點(diǎn)為兀b沿冰方向移動(dòng)得到點(diǎn)上2旺上 X0k <稱之為k對(duì)的反射點(diǎn)。計(jì)Xj . Xn水各點(diǎn)的函數(shù)值f記作:F0=F(x/)F2=F(x/)F3=F(Xn+lk)企Am = max Az = Fm_x<i<n/是第花昶方向組中,依次沿各方向搜索函數(shù)下降值7108:194.8鮑威爾方法鮑威爾算法的方向淘汰7308:19為了構(gòu)造第加J輪基本方向組

34、 < 采用如下判別式:F3 < F。9 A9（F0-2F2+F3XF0-F2-AJ2 V（化耳）2按照以下兩種情況處理:1)上式中至少一個(gè)不等式不成立 < 則第疋+1輪的基本方向仍用老 方向組人d2 心k。疋+7輪的初始點(diǎn)取xok+1=xnkF2<F3#08:19f2>f37508:194.8鮑威爾方法(6 )修正算法2 )兩式均成立,則淘汰函數(shù)值下降最大的方向,并用第花輪的新生方向補(bǔ) 入氐+7輪基本方向組的最后,即反+7輪的方向組為上J2k 血J、盅、護(hù)。吃+7輪的初始點(diǎn)取:兀嚴(yán)$ 卅是第吃輪沿'方向搜(F0)#08:194.8鮑威爾方法(7 )修正算法

35、步驟Powell算法的步驟如下：任選初始迭代點(diǎn)軸選定迭代精度S取初始基本方向組為單位坐標(biāo)矢量系di =勺其中,i=l, 2n然后令氐=1 (輪數(shù))開始迭代沿d：諸方向依次逬行次一維搜索,確定各步長F + oc： d： ) = min F)得到點(diǎn)陣X- -d. i=l , 2 n構(gòu)成新生方向dk=xkn-x沿dk方向逬行一維搜索求得優(yōu)化步長/k k .k jkx =xn+a d(3)計(jì)算各迭代點(diǎn)的函數(shù)值F(燈找岀相鄰點(diǎn)函數(shù)值差最大者A/n = maxtFC) - F(x：) = Fm_x - Fm ( l<m<n )及與之相對(duì)應(yīng)的兩個(gè)點(diǎn)4-iin 4,并以 必表示兩點(diǎn) 的連線方向。7

36、908:194.8鮑威爾方法(7 )修正算法步驟(4 )反射點(diǎn)函數(shù)值尤+i二2疋-點(diǎn)F嚴(yán) F%F2=Fx）耳"（監(jiān)）(5 )判斷是否滿足迭代終止條件。 Xq W £則可結(jié)束迭代,最優(yōu)解為 兀* = 尸=F(x*) 停止計(jì)算。否則,繼續(xù)逬行下步。8108:194.8鮑威爾方法（7 ）修正算法步驟檢驗(yàn)鮑威爾判別條件是否成立（化2耳+九）（化篤AJ2 V（化耳尸若至少其中之一不成立轉(zhuǎn)下步f否則轉(zhuǎn)步驟確定k+1輪的基本方向組和起始點(diǎn)盜1 J古（即取老方向組）08:194.8鮑威爾方法（7 ）修正算法步驟08:194.8鮑威爾方法（7 ）修正算法步驟步驟< I 當(dāng) F2VF3&

37、lt; I 當(dāng)F2NF3令k<-k+l f7508:194.8鮑威爾方法（7 ）修正算法步驟（7）確定k+1輪的方向組和起始點(diǎn)#08:194.8鮑威爾方法（7 ）修正算法步驟#08:194.8鮑威爾方法（7 ）修正算法步驟+1 <9，返回ik必”久）7708:194.8鮑威爾方法(8)算例丨的極小值例 用鮑威爾法求函數(shù)/ W *2 ) = Eg +兀2 - 5)2 + g “2 F解：選取初始點(diǎn)X冷0 of ,初始搜索方向亦"1 = 1 0r d、e2 = 0 1T 初始點(diǎn)處的函數(shù)值% = f0 = /(x；)= 250第一輪迭代:1)沿岸 方向進(jìn)行一維搜索,得：苗 &#

38、163;卜彳: 其中務(wù)為一維搜索最佳步長,應(yīng)滿足fl = /(X°)= min + axd= min(l laj 100«)250)4.54550得：=50/11=4.5455 X；=所以，/I = /(云°)= 22.727A, =/0-f1 = 250-22.727 =227.2737908:194.8鮑威爾方法(8)算例4.54550+ a24.5455a22)再沿 此方向逬行一維環(huán)索，得：X? =X :+也？=其中為一維搜索最佳步長，應(yīng)滿足：得:所以，f2 = /(X； ) = min f(x + a2d= min(l la22 200a2/11 + 25

39、0/11n 4.5455a。= 0.8264X。=220.8264F2=f2 = f(x)= 15.214 A2 = /1-/2 = 22.727 -15.214 = 7.513=227.273“=/(X?)=385.24取沿曲搜索的函數(shù)值増量的最大者=max人1亠=人1 終點(diǎn)理的反射點(diǎn)和函數(shù)值為:9.09 r1.6528所以 f /I = /（X；）= 10.185$ =/0-/1 = 15.21410.185 =5.0298108:194.8鮑威爾方法（8）算例3 ） Powell條件判斷：F3>F0 ,不滿足判別條件”因而下輪迭代應(yīng)繼續(xù)使用原來的搜索方向說#2 因?yàn)榍?lt; ”所

40、以取卍為下輪迭代起始點(diǎn)X；.4.5455化=/0 =心）=15.214第二輪迭代:+ a4.54550.82644.5455 +Q0.82640.82641 ）沿d方向進(jìn)行一維搜索，得：X； =其中為一維搜索最佳步長，應(yīng)滿足/1 = /（X；）二 min /曲+訛）二 01山（1站+14.8762少+15.2148倚. = 0.6762 X；=3.8693_0.8264所以 f /I = /（X；）= 10.185$ =/0-/1 = 15.21410.185 =5.0298308:194.8鮑威爾方法(8)算例_3.8693_0.8264+ OC-,'O' 3.8693 _0

41、.8264+ c（212 )再沿d；方向逬行一維搜索,得:其中a2為一維搜索最佳步長,應(yīng)滿足：/2 = /（X；） = min /（X； + a.d）= min（l la22 -12.1718a2 +10.18523.8693'1.3797X = X + oc2d =X；得：oc2 = 0.5533所以 > 耳= /2 = /（X；）=6.818 A2 =/1-/2 = 10.185 -6.818 =3.367取沿 幾鷗搜索的函數(shù)值増量的最大者=吋終點(diǎn)罔的反射點(diǎn)和函數(shù)值為:3.19311.9330X： = 2X； - X；耳=/區(qū)）=1747A】A2 = A! =5.029所以

42、f /I = /（X；）= 10.185$ =/0-/1 = 15.21410.185 =5.0298508:194.8鮑威爾方法pl(8)算例滿足3 ) Powell條件判斷：-0.67620.5533(從2巧+血X佗一耳, J < 0.5，” (九一血尸用新方向必替換d = e ,下輪搜索方向?yàn)閑2,d 冷X；-X冷下輪起始點(diǎn)X為從X；出發(fā)f沿百搜索的極小點(diǎn):3.8693 06762勺13797 + 05533勺-0.67620.5533其中«3為一維搜索最佳步長，應(yīng)滿足/0 = /（X： ） = min f（x + a3d） = min（1.6627«32 67

43、34勺 +6.81812.49952.5059X j = X； + otd 3.86931.3797+ °3得：如=2.0257x j =化=/0 = /（X；）= 0.000808:194.8鮑威爾方法08:194.8鮑威爾方法81已足夠接近極值點(diǎn)2.5 25卩。08:204.9單型替換法（1）基本原理單形替換法是利用對(duì)簡(jiǎn)單幾何圖形各頂點(diǎn)的目標(biāo)函數(shù)值作相互比較,在 連續(xù)改變幾何圖形的過程中,逐步以目標(biāo)函數(shù)值較小的頂點(diǎn)取代目標(biāo)函 數(shù)值最大的頂點(diǎn),從而進(jìn)行求優(yōu)的一種方法,屬于直接法之一。現(xiàn)以求二元函數(shù)的極小點(diǎn)為例,說明單形替換法形成原理.設(shè)二元函數(shù)/（X） = /（"X2）在

44、習(xí)-兀郢面上取不在同一條直線上的三個(gè)點(diǎn)X| ,x2和忑，并以它們?yōu)轫旤c(diǎn)構(gòu)成一單純?nèi)切?。算出各頂點(diǎn)的函數(shù)值&2）（冷），比較其大小，現(xiàn)假定比較后有/(X1)>/(X2)>/(X3)這說明點(diǎn)/最差,點(diǎn)心最好,點(diǎn)心次差。為了尋找極小點(diǎn),一般來說應(yīng)向最差點(diǎn)的反對(duì)稱方向進(jìn)行搜索(1)基本原理以X4記為X2X3的中點(diǎn)(如圖所示),在XX4的延長線上取 點(diǎn)X®使x5 -X4+(X4-X1)-2X4-X1算岀的函數(shù)值TUG)，可能出現(xiàn)以下幾種情形:稱為X 5是X(1)基本原理(1)f(x5)<f(x3)這說明搜索方向正確,可逬一步擴(kuò)大效果,繼續(xù)沿X1X5向前搜索,也就是向

45、前擴(kuò)張。這時(shí)取x6 =X4+g(X4X)其中oc為擴(kuò)張因子,般取a = 1.2 2.00如果/(X6) < /(X5),說明擴(kuò)張有利,就可以點(diǎn)X6代替 點(diǎn)X構(gòu)成新的單純形X2,X36o如果f(X6) > /(X5),說明擴(kuò)張不利,舍去點(diǎn)X6,仍以點(diǎn)X5代替X1構(gòu)成新的單純形X?, X3, X5 。(1)基本原理(2) /(X3)</(X5)</(X2)這說明搜索方向正確，但無須擴(kuò)張,以X5代替X構(gòu)成新的單純 形X2, X3,X5。(3) /(X2)</(X5)</(X1)這表示X 5點(diǎn)走得太遠(yuǎn)，應(yīng)縮回一些。若以0表示壓縮因子,則有X7 =X4 +0(X5 X4)P常取為05。以X7代替x 1 構(gòu)成新的單純形X2, X3, X?(1)基本原理 f(X5)>f(Xi)這時(shí)應(yīng)壓縮更多一些,將新點(diǎn)壓縮至X X4之間，令X8 = X4 _0(%4 _XJ = X4 +0(X1 _乙) 如果/(X8)</(X1)則以X*代替X構(gòu)成新的單純形 X2,X3,X8否則認(rèn)為X1X4方向上的所有點(diǎn)的函數(shù)弩(X)都大于/(XJ,不能沿此方向搜索。這時(shí),可以以X巾中心逬行縮邊,使頂點(diǎn)X和X2向X3移近一半距 離,得新單純形X3, x9, X10.以此單純形為基礎(chǔ)再逬行尋優(yōu)。(2 )計(jì)算步驟(1)令X產(chǎn)X°+辰丿= 1,2,”構(gòu)造單純形X