機(jī)械優(yōu)化設(shè)計(jì)第九章

1、 坐標(biāo)輪換法坐標(biāo)輪換法例題分析例題分析一、共軛方向一、共軛方向二、二、PowellPowell基本算法基本算法三、三、 改進(jìn)的改進(jìn)的PowellPowell算法算法5 53 3 鮑威爾（鮑威爾（powellpowell) )法法1 1、明確共軛方向的幾何及求優(yōu)意義、明確共軛方向的幾何及求優(yōu)意義2 2、掌握、掌握PowellPowell基本算法的求優(yōu)原理基本算法的求優(yōu)原理3 3、注意比較、注意比較PowellPowell基本算法與改進(jìn)的基本算法與改進(jìn)的PowellPowell算法算法 的異同點(diǎn)的異同點(diǎn)5 53 3 鮑威爾（鮑威爾（powellpowell) )法法Powell法法直接利用目標(biāo)函數(shù)

2、值來構(gòu)造直接利用目標(biāo)函數(shù)值來構(gòu)造“共共軛軛 方向方向“，并以，并以“共軛方向共軛方向“為搜為搜索方索方 向的一種直接搜索法向的一種直接搜索法一、共軛方向一、共軛方向 共軛性與共軛方向 共軛性定義： 設(shè)設(shè)A A為為n nn n 階實(shí)對(duì)稱正定矩陣，若在階實(shí)對(duì)稱正定矩陣，若在R Rn n 中有中有兩個(gè)非零的兩個(gè)非零的n n維矢量維矢量02121ASSSST能滿足：和則稱矢量則稱矢量2121SSASS與是共軛的，或稱對(duì)于與共軛矢量的為)(A 共軛方向 ： 指共軛矢量的方向指共軛矢量的方向 推論： 若非零的若非零的n 維矢量組：維矢量組： 且其中任兩個(gè)向量關(guān)于且其中任兩個(gè)向量關(guān)于n 階實(shí)對(duì)稱正定矩陣階實(shí)

3、對(duì)稱正定矩陣 A共軛，即滿足：共軛，即滿足： 則稱矢量組：則稱矢量組：，”、“nkRSSS21),2 . 1,;( , 0kjijiASSjTi共軛”關(guān)于、“ASSSk21 對(duì)于同一對(duì)于同一“A”A”而言，而言， 不是唯一的，即：存不是唯一的，即：存在多于一對(duì)的向量在多于一對(duì)的向量 滿足：滿足：21SS 和021ASST21SS 和例 如： 3226620 , 3121ATSS、0626 ,18623 , 22 , 60 , 321SS AT463 , 0221SST、0469 , 6463 , 22 , 63 , 021SS AT 若有兩個(gè)非零的若有兩個(gè)非零的n維矢量維矢量 ,對(duì)于單位矩對(duì)于

4、單位矩 陣陣E 共軛，由共軛定義知：共軛，由共軛定義知： ，此時(shí)，二者，此時(shí)，二者 nRSS21、0)cos(222121SSSSSS02121SSSSTTE為一對(duì)為一對(duì)正交向量正交向量 正交是共軛的特例，共軛概念是正交概念正交是共軛的特例，共軛概念是正交概念的推廣！的推廣！共軛方向的幾何意義正定二元二次函數(shù)：正定二元二次函數(shù)：CXBAXXXfTT21)(“實(shí)對(duì)稱正定矩陣”)(,211222211211aaaaaaA2121bbBxxXC常數(shù)BAXxfxfXfXXf21)()(梯度的矩陣表達(dá)式：在點(diǎn)函數(shù)1l2l) 1 (X)2(Xf(x1,x2)=Ci)() 2(XfX1S)() 1 (Xf

5、連接兩切連接兩切點(diǎn)構(gòu)成的矢量點(diǎn)構(gòu)成的矢量：) 1 () 2(2XXS任一矢量方向設(shè)：1S共軛對(duì)與則：ASS 212S證明：）（）（：式式的梯度：和在點(diǎn)函數(shù)（）（）（）（）（*)()() 1 () 2() 2()() 1 ()()(2) 1)212)22) 11)2() 1 (SAXXAXfXfBAXXfBAXXfXXXf）（）（即：正交，必與矢量和又）（）（）（）（40)(30)()()(2111121XfXfSXfXfTTSS）可得：）代入式（將式（）式（）式（）（）（*(*)0)()(:34121XfXfTS021SS AT “對(duì)于正定二元二次函數(shù)，沿共軛方向一維共軛方向一維搜索搜索就可獲

6、得最優(yōu)點(diǎn)，且只需兩步只需兩步就可得到 推論： “對(duì)于正定n元二次函數(shù)，從任意初始點(diǎn)出 發(fā)，依次沿著依次沿著n個(gè)相互共軛的方向進(jìn)行一個(gè)相互共軛的方向進(jìn)行一 維搜索維搜索就可獲得最優(yōu)點(diǎn)共軛矢量的性質(zhì) 設(shè)設(shè)A A為為n nn n 階實(shí)對(duì)稱正定矩陣，若非零的階實(shí)對(duì)稱正定矩陣，若非零的 n n 維矢維矢 量組：量組： 則，這組向量是線性無(wú)關(guān)的則，這組向量是線性無(wú)關(guān)的 ，”、“nkRSSS21是共軛的，對(duì)于A 在在n維空間中，互相共軛的非零向量的個(gè)數(shù)維空間中，互相共軛的非零向量的個(gè)數(shù)維數(shù)維數(shù) n 設(shè)有：正定設(shè)有：正定n元二次函數(shù)：元二次函數(shù)： ，若有彼此，若有彼此A共軛的共軛的 n 個(gè)個(gè) 非零矢量非零矢量

7、 則對(duì)于求則對(duì)于求 的極的極CXBAXXXfTT21)(nTnRxxxXX,21,1210”、“nSSSS)(Xf小點(diǎn)的尋優(yōu)問題，可從任一點(diǎn)小點(diǎn)的尋優(yōu)問題，可從任一點(diǎn) 出發(fā)，依次沿出發(fā)，依次沿 方向做方向做 n 次次一維搜索，即可找到極小點(diǎn)（最多一維搜索，即可找到極小點(diǎn)（最多 n 次，與次，與次序無(wú)關(guān)）次序無(wú)關(guān)）)0(X”“iS 優(yōu)化算法的二次收斂性 如果一個(gè)優(yōu)化算法，能通過有限次迭代（如果一個(gè)優(yōu)化算法，能通過有限次迭代（ 一維搜索），求出正定一維搜索），求出正定n元二次函數(shù)的理想極小元二次函數(shù)的理想極小 點(diǎn)的話，就稱此算法點(diǎn)的話，就稱此算法具有具有“二次收斂性二次收斂性 ” ”二、二、Pow

8、ell Powell 基本算法基本算法1、任選一個(gè)初始點(diǎn)、任選一個(gè)初始點(diǎn)X(0) ,再選二個(gè)線性無(wú)關(guān)的向量再選二個(gè)線性無(wú)關(guān)的向量 （如坐標(biāo)軸單位向量：（如坐標(biāo)軸單位向量：e1=1,0T， e2=0,1T ）作）作 為初始搜索方向?yàn)槌跏妓阉鞣较騉x2x1)2(S) 1 (S1e2e)1(1X)1(2X)()2(3XX)0()1(0XX)1(3)2(0XX)2(1X)2(2X2、從 出發(fā)，依次沿 做一維 搜索，分別得極小點(diǎn) 。 )()0()1(0XX21ee 、)1(2)1(1XX、第一環(huán)：”“)()2(0)1(3)1(2)1(1)1(0XXXXX基本方向組：”“21;ee新生方向：) 1 (S)

9、1(0)1(2)1(XXS再沿 做“n+1”次一維搜索得到極小點(diǎn))1(S)1(3X 新方向 ：)1(S3、從 出發(fā)，依次沿 做一 維搜索，分別得極小點(diǎn) 。 )()1(3)2(0XX)1(2Se 、)1(2)1(1XX、)2(0)2(2)2(XXS再沿 做“n+1”次一維搜索得到極小點(diǎn))2(S)2(3X 新方向 ：)2(S第二環(huán)：”“)2(3)2(2)2(1)2(0XXXX基本方向組：”、“)1(2Se新生方向：)2(S XXASS)2(321: 共軛，故一輪的終點(diǎn)對(duì)與由于n維問題維問題“Powell算法算法”的要點(diǎn)：的要點(diǎn)： 在每一環(huán)迭代中，總有一個(gè)始點(diǎn)（第一環(huán)為任 選）和n 個(gè)線性獨(dú)立的搜索

10、方向作為基本方向 組，從始點(diǎn)出發(fā)，依次沿基本方向組的n個(gè)方 向做一維搜索，得一終點(diǎn) 由始點(diǎn)和終點(diǎn)的連線構(gòu)成一個(gè)新生方向，再沿 新生方向一維搜索，就完成了一環(huán)的迭代 二維目標(biāo)函數(shù)完成二維目標(biāo)函數(shù)完成“二環(huán)二環(huán)”的迭代過程稱為一輪的迭代過程稱為一輪 用新生方向替換基本方向組的一個(gè)方向，替換原 則是：去掉基本方向組第一個(gè)方向而將新方向排 在基本方向組的最后。每一環(huán)的始點(diǎn)均是上一環(huán) 的終點(diǎn) n 維目標(biāo)函數(shù)完成n環(huán)迭代的過程稱為“一輪”,對(duì) 于n 維的正定二次函數(shù)，一輪的終點(diǎn)即為“最優(yōu) 點(diǎn)” X 對(duì)于非二次函數(shù)，則仿上轉(zhuǎn)入第二輪迭代（重置 單位坐標(biāo)矢量系）直到某輪中的某環(huán)的始點(diǎn)和 終點(diǎn)之距滿足精度要求為

11、止Powell基本算法的缺陷舉例基本算法的缺陷舉例 ： （三維問題）小點(diǎn)”“三個(gè)相應(yīng)方向上的極（一維搜索）方向組”）”（線性無(wú)關(guān)的“基本“（初始點(diǎn)）)2()1()0()2()1()0()0(XXXSSSX)()()() !(KKKKSXX根據(jù)迭代公式：)2()2()1()1()0()0()0()2()2()1()1()1()2()2()2()3(SSSXSSXSXX) 2() 2() 1 () 1 () 0() 0() 0() 3() 3(SSSXXS新生方向：Ox1x2x3Ox1x2x3)0(S)1(S)2(S)3(S) 1 () 1 (S) 2(2)S)3(S)0(X)1 (X)2(X)3

12、(X)0(X0) 0 () 2() 2() 1 () 1 () 0() 3() 3() 0(0SSXXS ，若：上式表明：在下一環(huán)的基本方向組 中，就和 線性相關(guān)或接近線性相關(guān)（共面）”“)3()2()1(SSS)3(S）（、2)1(SSPowell基本算法的缺陷基本算法的缺陷 基本方向組中的 n個(gè)搜索方向有可能出現(xiàn)線性 相關(guān)或近似線性相關(guān)的情況,一旦出現(xiàn)這種情況 以后的搜索將在維數(shù)下降的空間內(nèi)進(jìn)行，使算 法收斂不到真正的最優(yōu)點(diǎn)上，此即“退化現(xiàn)象”三、改進(jìn)后的三、改進(jìn)后的PowellPowell算法算法其基本特點(diǎn)1、與基本算法的相同之處： 在第一環(huán)中，從初始點(diǎn) 出發(fā)，沿 n維空間的 各個(gè)坐標(biāo)方

13、向來進(jìn)行一維搜索可得點(diǎn) ，則 由 到 連線方向就構(gòu)成了“新生方向”)1(0X)1(nX)1(nX)1(0X2、不同之處：在獲取了新的方向后，Powell法則要在本環(huán)中已取 得的“n+1”個(gè)方向中，選取n個(gè)線性無(wú)關(guān)的、且共軛 程度盡可能高的方向作為下一環(huán)的“基本方向組”， 以避免“退化現(xiàn)象”出現(xiàn)同時(shí)成立和若：23122132113)(21)(2(fffffffffmm則下一環(huán)迭代采用這個(gè)新方向，并淘汰原來基本方向組中的第 個(gè)方向，而將新方向放在新的基本方向組中的最后)(kmS)(,)()1()1()1(2)1(1)()()(1)(1)(2)(1)()()(2)(1kknknkkkknkmkmkk

14、knkmkkSSSSSSSSSSSSSSS，新方向組：原方向組：否則：否則： 仍用原來的n個(gè)搜索方向作為下一環(huán)的“基本方向組”( )( )( )( )10230( )( )( )11()()(2)()()maxkkkknnkkkmiii nff Xff XffXXf Xf X )(1)()()()()1kmkmkmkmkmkmXXSnmSK（相對(duì)應(yīng)的方向與最大下降量中，相鄰兩點(diǎn)函數(shù)值的向的一維搜索環(huán)中沿基本方向組各方 改進(jìn)后的Powell法只是在第一輪的第一環(huán)內(nèi)采用單 位坐標(biāo)矢量系 作為基本方向組， 以后每輪開始時(shí)，就不必重置單位坐標(biāo)矢量系， 只按上述產(chǎn)生新基本方向組的方式一環(huán)接一環(huán)的 繼續(xù)進(jìn)

15、行即可，隨著逐環(huán)迭代的繼續(xù)各環(huán)的基本 方向組將漸趨共軛)2 .1(niei“ Pwell 算法的迭代步驟和程序框圖（自學(xué)）例：用Powell基本算法求：1 . 0,0 , 060104)(min)0(212212221精度：的最優(yōu)解。始點(diǎn)：TXRXxxxxxxXf解：1、選初始點(diǎn)、確定首輪第一環(huán)的基本方向組10010 , 02) 1 (2) 1 (1)0() 1 (0ee1SSXXT2、沿 進(jìn)行一維搜索得到極小點(diǎn)1e)1(1X0500100) 1 (1) 1 (1) 1 (1) 1 (1) 1 (0) 1 (1SXX35)(56010)(min)1(1)1(1)1(12)1(1)1(1XfXf

16、：采用一維優(yōu)化方法求解) 1 (2) 1 (2) 1 (2) 1 (2) 1 (1) 1 (251005SXX3、再由 沿 進(jìn)行一維搜索得到該方向上 的極小點(diǎn)) 1 (1X2) 1 (2eS) 1 (2X75.14)(5 . 4359)(min)1(2)1(2)1(22)1(2)1(2XfXf：采用一維優(yōu)化方法求解5 . 45005 . 45)1(0)1(2)1(XXS7253.64725.7154155 .455 .451313)1(3)1()1(3)1(2)1(3)1(3)1(2)1(3)(.)(SXSXX)()(4、沿新方向 一維搜索得到極小點(diǎn))1(S)1(3X1863.9)()1(3Xf5、再進(jìn)行首輪第二環(huán)的迭代8.6.80367.8)(0026.60028.80367.8)(1277.69075.72087.8)(7326.54725.7