第三講多維無約束最優(yōu)化共軛方向法

1、多維無約束最優(yōu)化：直接法n網(wǎng)格法每個(gè)格子中，取中點(diǎn)計(jì)算目標(biāo)值進(jìn)行比較，收縮到“最優(yōu)”的格子再繼續(xù)剖分。多維無約束最優(yōu)化：?jiǎn)渭冃畏╪單純形n維空間中由n+1個(gè)點(diǎn)所構(gòu)成的體積不為0的形狀。n單純形法從給定單純形出發(fā)，通過變換產(chǎn)生一系列單純形，逐步逼近最優(yōu)點(diǎn)。多維無約束最優(yōu)化：爬山法n輪流坐標(biāo)搜索法輪流坐標(biāo)搜索法從任意初始點(diǎn) 出發(fā)，沿坐標(biāo)軸 ，求解一維極值問題：記最優(yōu)的 為 ，令 ，從該點(diǎn)出發(fā)，沿坐標(biāo)軸 繼續(xù)搜索，直到n個(gè)方向搜索完一遍，得到 ，以之為新的 重復(fù)上述搜索過程，直到沿n個(gè)方向搜索的結(jié)果都無明顯改善。0 x101()m in()Rfxfxe1e*10* 1xxe2enx0 x例子n輪流坐

2、標(biāo)搜索法對(duì)等高線近似于圓的函數(shù)比較有效，對(duì)等高線為扁橢圓的函數(shù)效果不好。n例求Rosenbrock函數(shù)的極小值n輪流搜索結(jié)果為(0, 0)-(0.16, 0)-(0.16, 0.026)-(0.21, 0.026)-(0.21, 0.045)-(0.25, 0.045)-(0.25, 0.06)-(0.27, 0.06)-nAlternative.c222211( )100()(1)f xxxx一些改進(jìn)方法nRosenbrock算法（旋轉(zhuǎn)方向法）nHooke-Jeeves算法（步長(zhǎng)加速法）多維無約束最優(yōu)化：共軛方向法n基本思想：沿著某些方向依次進(jìn)行精確的一維搜索，確定最佳的步長(zhǎng)。n共軛方向1.

3、定義：設(shè) Ann 對(duì)稱正定，d (1),d (2) Rn , d (1) 0，d(2) 0，滿足d(1)TAd(2)=0, 稱d(1),d(2) 關(guān)于矩陣A共軛。2.共軛向量組：d(1),d(2), ,d(m) Rn 均非零，滿足d(i)TAd(j)=0,(ij) .共軛方向n當(dāng)A=I(單位矩陣)時(shí)， d(1)TAd(2)= d(1)Td(2)=0，即正交關(guān)系。共軛方向正交方向n當(dāng)d(1),d(2), ,d(m) 關(guān)于正定矩陣A兩兩共軛時(shí)， d(1),d(2), ,d(m) 線性無關(guān)。構(gòu)造共軛方向的Schmidt過程設(shè)d(1),d(2), ,d(m) 線性無關(guān)。令則 z1, z2, zm 關(guān)于

4、A 共軛。11(),1,2,.()jTijjjii TiidAzzdzjmzAz二次終結(jié)性n一個(gè)算法用于解正定二次函數(shù)的無約束極小時(shí)，若有限步迭代可達(dá)最優(yōu)解，則稱該算法具有二次終結(jié)性。n共軛方向 + 精確一維搜索 二次終結(jié) 設(shè) z1, z2, zm 關(guān)于正定陣A 共軛。則從任意初始點(diǎn)出發(fā)，二次型目標(biāo)函數(shù) 的極小點(diǎn)可通過沿每個(gè)共軛方向搜索一次得到1( ),2TTmf xx Axb xc xR例n有理由相信具有二次終結(jié)性的算法對(duì)極小化具有連續(xù)二階導(dǎo)數(shù)的一般函數(shù)也是有效的。n例子：22121 212( )2( )6()2233f xxxx xxx例解 1221122111101 11*2122422

5、,3212310,011011/2()1,0101()2min(),1/2,min(),TTAbadddAzzzdzzAzzf xzzf xz 0T取則由正交化過程，現(xiàn)從x =(0,0)出發(fā)，沿 方向極小化得再沿 方向極小化得2*01*12*22/11,( 9/22, 2/11)Txxzz 從而極小點(diǎn)Powell共軛方向法 從初始點(diǎn)t0開始，沿任意一組線性無關(guān)的方向d1, d2, dn依次進(jìn)行一維搜索，得到t1，令典范方向dn+1=t1 t0，沿典范方向再作一次搜索，得到一個(gè)新的起始點(diǎn)，同時(shí)用典范方向替換調(diào)d1。這個(gè)過程稱為一個(gè)循環(huán)，只要新得到的n個(gè)方向線性無關(guān)，就可以進(jìn)行下一次循環(huán)。已經(jīng)證明

6、，如果這樣的循環(huán)可以進(jìn)行n次，則n次循環(huán)后得到的那組向量關(guān)于A共軛。因此，再循環(huán)一次，就得到了二次型函數(shù)的極小點(diǎn)。Powell法(I)Powell法流程框圖：初始步驟k=1,初始點(diǎn)xB0=t01及d11, d21, dn1線性無關(guān)*111, 2 , .,()m in()jjkkkkjjjjjjjnftdftd對(duì)求使Powell法(II) *1111010,1,.,1,kkkjjjjkkjjkkkkkknnnttdddjndtttt原d 被代替1*1*1010()min()nnkkkkkknnnnnnf tttf ttt找使Powell法(III) *10()kkkkBnnnxttt1|kkBB

7、xxy輸出結(jié)果，停止nK=k+1,轉(zhuǎn)下一步13d11d11t12d10t12t20t21t22t21d22d例子(powell.c)例1：在每一步的過程中，搜索方向線性獨(dú)立是非常重要的，否則可能不收斂。例2： Rosenbrock函數(shù)的極小值例3：221212131( )()()222f xxxx xx222123123123123( ,)()()()f x x xxxxxxxxxx 避免線性相關(guān)的搜索方向在算法的第 k 步，所有計(jì)算同前。如果則停止，否則找下標(biāo) m 使和*n+1使 111,.()()max ()( )kkkkmmjjjnf tf tf tf t1*1/20011( )()| ()()kknkkmmf tf tf tf t1*011011()min()nkkkknnnnf tdf td1|k