【正文】 （ 3）改變初始點(diǎn)重新迭代，可避免出現(xiàn)病態(tài)。 方法特點(diǎn) 步長(zhǎng)加速法（ HookReeves算法） 一、步長(zhǎng)加速法原理 步長(zhǎng)加速法也稱之為離散步長(zhǎng)的 HookReeves算法，是一種不使用導(dǎo)數(shù)的直接搜索算法，其算法過程可分成兩個(gè)基本階段：坐標(biāo)循環(huán)試探及模矢加速搜索。見下圖，從初始探點(diǎn) Y0出發(fā)，依次沿 n個(gè)坐標(biāo)方向用固定步長(zhǎng)△進(jìn)行試探，尋找更好的點(diǎn) 。 而模矢加速搜索，就是沿模矢方向 加大步長(zhǎng)前進(jìn)，以得到第 k+1次迭代的出發(fā)點(diǎn) Y0，這樣就完成了一次迭代，然后再從新的 Y0出發(fā)，進(jìn)行下一輪坐標(biāo)循環(huán)試探，如此重復(fù)進(jìn)行，使目標(biāo)值不斷減小。 121 , ?knn XYYYY 為并記?)( 1 kk XX ??二、步長(zhǎng)加速法算法 設(shè)問題為 nEXXf ?),(m i n X0為初始點(diǎn)， 個(gè)坐標(biāo)軸的單位方向向量，初始坐標(biāo)循環(huán)試探的步長(zhǎng)為△ 0，模矢加速搜索的加速步長(zhǎng)因子為 a1（通常取 a=2），迭代終止準(zhǔn)則為 ( 為預(yù)先確定的正數(shù)）。 neee n 依次是?, 21????)。2(,1,0),(),()( 10 轉(zhuǎn)令成功步長(zhǎng)加速即若 ???? ? kkjXfYf k0,0,00 ??? jkXY（ 1） ???????????????? ?????其它情形當(dāng)當(dāng),)()(,)()(,11111jjjjjjjjjjjjYYfeYfeYYfeYfeYY（ 2） 轉(zhuǎn)令 ,1,1 ???? jjnj （ 3）若 （ 2）；否則，轉(zhuǎn)（ 4） 否則轉(zhuǎn)（ 6） )2(,1,0,10 轉(zhuǎn)???? ? kkjXY k否則，令 。),(, 計(jì)算停止即近似極小點(diǎn)輸出若 nY???（ 6） 1,0,21 0 ??????? kkjYY n令否則， ，轉(zhuǎn)（ 2） （ 5） )( 10 kkk XXaXY ??? ?令,),(),()( 10 nkn YXYfYf ?? ?令成功試探即若（ 4） 轉(zhuǎn)（ 5）； α0d0 x 0 x1 x* 1 α1d1 1()f?? x d1 ()k k kkf ? ?? ? ? ? 1d x d22()()kk kff????? 1xx1 ( 0 , 1 , 2 , )k k kk k?? ? ? ?x x d共軛梯度法： 1 ( ) ( 0 , 1 , 2 , )k k kka f k? ? ? ? ?x x x梯度法： 鮑威爾 (Powell)法 j j k k k d d dj g g k+1 x x k+1 共軛法 直接法 鮑威爾法原理， 如何構(gòu)成共軛方向？ ！ 坐標(biāo)輪換法 直接法 步長(zhǎng)加速法（ HookReeves算法） 單純形方法 一、基本思想 單純形替換法也是一種不使用導(dǎo)數(shù)的求解無約束極小化問題的直接搜索方法，與前面幾種方法不同的是，單純形替換法不是利用搜索方向從一個(gè)點(diǎn)迭代到另一個(gè)更優(yōu)的點(diǎn)，而是從一個(gè)單純形迭代到另一個(gè)更優(yōu)的單純形。 定義：?jiǎn)渭冃? n維空間中的恰好有 n+1個(gè)頂點(diǎn)（極點(diǎn)）的有界的凸多面體稱之為一個(gè)單純形。 根據(jù)定義，可知，一維空間中的單純形是線段，二維空間中的單純形是三角形，而三維空間中的單純形則是四面體。 在單純形替換算法中，從一個(gè)單純形到另一個(gè)單純形的迭代主要通過反射、擴(kuò)張、收縮和縮邊這 4個(gè)操作來實(shí)現(xiàn)。下面以二維問題為例來對(duì) 4種操作進(jìn)行說明（參見下圖）。 8 （ 1）反射 —— 設(shè)除了最劣點(diǎn) X1以外的基余頂點(diǎn)的中心為 X4，作 X1關(guān)于點(diǎn) X4的對(duì)稱點(diǎn) X5，稱 X5為 X1的反射點(diǎn)。求反射點(diǎn)的過程稱之為反射。 )()()( 321 XfXfXf ??（ 2）擴(kuò)張 —— 在得到反射點(diǎn) X5之后，如果 X5優(yōu)于原單純形的最劣點(diǎn)（即有 ），表明反射方向（ X5— X1）是有利方向，反射成功。若進(jìn)一步有 ，可沿反射方向前進(jìn)適當(dāng)?shù)木嚯x到點(diǎn) X6。 X6稱之為擴(kuò)張點(diǎn)，求擴(kuò)張點(diǎn)的過程稱之為擴(kuò)張。擴(kuò)張之后，若擴(kuò)張點(diǎn) X6優(yōu)于反射點(diǎn) X5，則擴(kuò)張成功，以 X6取代X1，得新單純形 {X6,X2,X3}；否則，擴(kuò)張失敗，舍棄擴(kuò)張點(diǎn)，以反射 X5點(diǎn)取代 X1，得新單純形 {X5,X2,X3}。 )()( 15 XfXf ?)()( 25 XfXf ?設(shè)當(dāng)前的單純形的頂點(diǎn)為 X1， X2， X3，且有 )()()( 251 XfXfXf ??如果出現(xiàn) 。表示反射完全失敗，應(yīng)退回到介于 X4與 X1之間的某個(gè)點(diǎn) X8。 )()( 15 XfXf ?（ 3）收縮 —— 在得到反射點(diǎn) X5之后，如果有 表示反射部分成功，方向（ X5— X1）雖然是有利方向，但 X5前進(jìn)過遠(yuǎn)，應(yīng)收縮到介于 X4與 X5之間的某個(gè)點(diǎn) X7。 上述兩種從反射點(diǎn)向 X1方向后退的過程都稱之為收縮。如果收縮點(diǎn)優(yōu)于原來的最劣點(diǎn) X1，稱收縮成功，并以收縮點(diǎn)取代原最劣點(diǎn)，構(gòu)成新單純形 {X7,X2,X3}或 {X8,X2,X3}；否則，稱之為收縮失敗，舍棄收縮點(diǎn)。 （ 4）縮邊 —— 若收縮失敗，則應(yīng)壓縮當(dāng)前單純形的邊長(zhǎng)：令最優(yōu)點(diǎn) X3不動(dòng)，而其余頂點(diǎn)向 X3方向壓縮，使邊長(zhǎng)縮短（通?？s短一半），以產(chǎn)生新單純形。如下圖所示，點(diǎn) X1壓縮到點(diǎn) X9，點(diǎn) X2壓縮到點(diǎn) X10，得新單純形 {X9,X10,X3}，這一過程稱之為縮邊。 二、單純形替換算法 設(shè)初始點(diǎn)為 X0，初始邊長(zhǎng) h， ei為坐標(biāo)軸方向的單位向量 ， 預(yù)定正數(shù) ,2,1 ni ?? 21,??（ 2）比較各項(xiàng)點(diǎn) Xi的函數(shù)值，挑出其中的最優(yōu)點(diǎn)，記為 XL；最劣點(diǎn)，記 XH；次差點(diǎn)，記為 Xw； （ 3）求反射中心 21 ?? nn XX 和反射點(diǎn))(1 112)(01HnnnnHiiinXXaXXXnX?????????? ?其中， a0，通常取 a=1； （ 1）令 },{,2,1,100 nii XXXniheXX ?? 構(gòu)造單純形???； 輸出 XL，為原問題近似極小點(diǎn)；否則，轉(zhuǎn)（ 2）。 構(gòu)造新單純形； ??（ 4）根據(jù)不同 情 況，分別進(jìn)行擴(kuò)張，收縮或縮邊，其中收縮因子 ? ?1121m a x )()(????????LiniLiXXXfXf（ 5）如果滿足 ? 例 46 用單純形法求目標(biāo)函數(shù) 12( ) ( ) ( )f x x x x? ? ? ?2212, 4 5 6解： 選 x0=[8,9]T, x1=[10,11]T, x2=[8,11]T為頂點(diǎn)作初始單純形 。 ( ) ( ) ??? ? ? ? ? ?????n3 i H 0 2i = 0811x x x x x10n2的最優(yōu)解。 計(jì)算各 頂點(diǎn)函數(shù)值 f0=f（ x0） =45, f1=f（ x1） =125, f2=f（ x2） =61?？梢娮詈命c(diǎn) xL=x0, 最差點(diǎn) xH=x1, 次差點(diǎn) xG=x2。 求 x0, x2的中心 x3。 ()? ? ? ? ? ?? ? ? ? ?? ? ? ? ? ?? ? ? ? ? ???4 3 1448 10 6x 2x x 210 11 9f f x 13求反射點(diǎn) x4及其函數(shù)值 f4。 ))()??? ? ? ? ? ?? ? ?? ? ? ? ? ?? ? ? ? ? ??????????5 3 4 355x x + 2( x x8 6 8 2(10 9 104 8f f x 8由于 f4 f0 ，故需擴(kuò)張，取 α=2得擴(kuò)張點(diǎn) x5 由于 f5 f4 ，故擴(kuò)張成功，以 x5代替 x1，由 x0、 x x5構(gòu)成新的單純性，進(jìn)行下一循環(huán)。 經(jīng) 32次循環(huán)，可將目標(biāo)函數(shù)值降到 1 106，接近極小值 f*=f（ x*） =f（ 5， 6） =0。 表 1 無約束優(yōu)化方法搜索方向之間的相互聯(lián)系 —— 間接法 kk??dg1[]k k k???d G g1[]k ?Gk k k??d Q g111[][]k T kkk T k???????????gdQIggk k k??d A g11k k k??? ? ?A A A1[]kk ??AG搜索方向 函數(shù)梯度的修正因子 所用目標(biāo)函數(shù)信息 梯度法 I（ 單位陣 ） 一階導(dǎo)數(shù) （ 阻尼 ） 牛頓法 二階導(dǎo)數(shù) 共軛梯度法 一階導(dǎo)數(shù) 變尺度法 一階導(dǎo)數(shù)，使 （海賽矩陣的逆陣） 無約束優(yōu)化方法 —— 間接法總結(jié) 梯度法 方向 負(fù)梯度 用到一階導(dǎo)數(shù) 適合于精度不高或用于復(fù)雜函數(shù)尋找一個(gè)好的初始點(diǎn) 牛頓法 用到一階導(dǎo)數(shù)和海色矩陣，具有二次收斂性 要求海色矩陣非奇異，且維數(shù)不宜太高 共軛梯度法 用到一階導(dǎo)數(shù)，具有二次收斂性 變尺度法 收斂快，效果好，被認(rèn)為是目前最有效的無約束優(yōu)化方法。適用于維數(shù)較高，具有一階偏導(dǎo)數(shù)的目標(biāo)函數(shù) 坐標(biāo)輪換法 計(jì)算效率較低 適合維數(shù)較低，目標(biāo)函數(shù)無導(dǎo)數(shù)或?qū)?shù)較難求得 步長(zhǎng)加速法 同坐標(biāo)輪換法，對(duì)目標(biāo)函數(shù)的性態(tài)的適應(yīng)性更好 Powell法 具有二次收斂性，收斂速度較快，可靠性高，被認(rèn)為是直接法中最有效的方法之一 單純形法 思路清楚，收斂慢 無約束優(yōu)化方法 —— 直接法總結(jié) 無約束優(yōu)化作業(yè) P93~94： 2， 4 無約束優(yōu)化上機(jī) 最速下降法優(yōu)化設(shè)計(jì)程序 題目：編程求解函數(shù) 的極小點(diǎn) x*。 221 2 1 1 2( ) 2 4 2f x x x x x? ? ? ?x初始點(diǎn) x0=[1,1]T，迭代精度 。 0. 00 1?