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

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

2、標(biāo)搜索法對等高線近似于圓的函數(shù)比較有效，對等高線為扁橢圓的函數(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一些改進方法nRosenbrock算法（旋轉(zhuǎn)方向法）nHooke-Jeeves算法（步長加速法）多維無約束最優(yōu)化：共軛方向法n基本思想：沿著某些方向依次進行精確的一維搜索，確定最佳的步長。n共軛方向1.

3、定義：設(shè) Ann 對稱正定，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(單位矩陣)時， d(1)TAd(2)= d(1)Td(2)=0，即正交關(guān)系。共軛方向正交方向n當(dāng)d(1),d(2), ,d(m) 關(guān)于正定矩陣A兩兩共軛時， 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一個算法用于解正定二次函數(shù)的無約束極小時，若有限步迭代可達最優(yōu)解，則稱該算法具有二次終結(jié)性。n共軛方向 + 精確一維搜索 二次終結(jié) 設(shè) z1, z2, zm 關(guān)于正定陣A 共軛。則從任意初始點出發(fā)，二次型目標(biāo)函數(shù) 的極小點可通過沿每個共軛方向搜索一次得到1( ),2TTmf xx Axb xc xR例n有理由相信具有二次終結(jié)性的算法對極小化具有連續(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 從而極小點Powell共軛方向法 從初始點t0開始，沿任意一組線性無關(guān)的方向d1, d2, dn依次進行一維搜索，得到t1，令典范方向dn+1=t1 t0，沿典范方向再作一次搜索，得到一個新的起始點，同時用典范方向替換調(diào)d1。這個過程稱為一個循環(huán)，只要新得到的n個方向線性無關(guān)，就可以進行下一次循環(huán)。已經(jīng)證明

6、，如果這樣的循環(huán)可以進行n次，則n次循環(huán)后得到的那組向量關(guān)于A共軛。因此，再循環(huán)一次，就得到了二次型函數(shù)的極小點。Powell法(I)Powell法流程框圖：初始步驟k=1,初始點xB0=t01及d11, d21, dn1線性無關(guān)*111, 2 , .,()m in()jjkkkkjjjjjjjnftdftd對求使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：在每一步的過程中，搜索方向線性獨立是非常重要的，否則可能不收斂。例2： Rosenbrock函數(shù)的極小值例3：221212131( )()()222f xxxx xx222123123123123( ,)()()()f x x xxxxxxxxxx 避免線性相關(guān)的搜索方向在算法的第 k 步，所有計算同前。如果則停止，否則找下標(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