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

2、標搜索法對等高線近似于圓的函數比較有效，對等高線為扁橢圓的函數效果不好。n例求Rosenbrock函數的極小值n輪流搜索結果為(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算法（旋轉方向法）nHooke-Jeeves算法（步長加速法）多維無約束最優化：共軛方向法n基本思想：沿著某些方向依次進行精確的一維搜索，確定最佳的步長。n共軛方向1.

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

4、A 共軛。11(),1,2,.()jTijjjii TiidAzzdzjmzAz二次終結性n一個算法用于解正定二次函數的無約束極小時，若有限步迭代可達最優解，則稱該算法具有二次終結性。n共軛方向 + 精確一維搜索 二次終結 設 z1, z2, zm 關于正定陣A 共軛。則從任意初始點出發，二次型目標函數 的極小點可通過沿每個共軛方向搜索一次得到1( ),2TTmf xx Axb xc xR例n有理由相信具有二次終結性的算法對極小化具有連續二階導數的一般函數也是有效的。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取則由正交化過程，現從x =(0,0)出發，沿 方向極小化得再沿 方向極小化得2*01*12*22/11,( 9/22, 2/11)Txxzz 從而極小點Powell共軛方向法 從初始點t0開始，沿任意一組線性無關的方向d1, d2, dn依次進行一維搜索，得到t1，令典范方向dn+1=t1 t0，沿典范方向再作一次搜索，得到一個新的起始點，同時用典范方向替換調d1。這個過程稱為一個循環，只要新得到的n個方向線性無關，就可以進行下一次循環。已經證明

6、，如果這樣的循環可以進行n次，則n次循環后得到的那組向量關于A共軛。因此，再循環一次，就得到了二次型函數的極小點。Powell法(I)Powell法流程框圖：初始步驟k=1,初始點xB0=t01及d11, d21, dn1線性無關*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輸出結果，停止nK=k+1,轉下一步13d11d11t12d10t12t20t21t22t21d22d例子(powell.c)例1：在每一步的過程中，搜索方向線性獨立是非常重要的，否則可能不收斂。例2： Rosenbrock函數的極小值例3：221212131( )()()222f xxxx xx222123123123123( ,)()()()f x x xxxxxxxxxx 避免線性相關的搜索方向在算法的第 k 步，所有計算同前。如果則停止，否則找下標 m 使和*n+1使 111,.()()max ()( )kkkkmmjjjnf tf tf tf t1*1/20011( )()| ()()kknkkmmf tf tf tf t1*011011()min()nkkkknnnnf tdf td1|k