【正文】 ?????? ?XfX??5）迭代終止條件判斷 ?????????? ? )2103 0 7 1 7 8 ()29 1 9 8 7 ( 22201 XX繼續(xù)迭代。 迭代 10次的結(jié)果是： ?????????????? 00)(00 ** XfX20:08 21 最速下降法 （ 5） 丼例 返個(gè)問(wèn)題的目標(biāo)函數(shù)的等值線為一簇橢圓 ,迭代點(diǎn)從 X0 走的是一段鋸齒形路線，見(jiàn)圖 。 00102( ) 1 0 42 4()2 20yy????? ??? ? ??? ?????? yyy則函數(shù) f(X) 變?yōu)椋? y1=x1, y2=5x2 將上例中目標(biāo)函數(shù) 引入變換 2221 25)( xxXf ?? 仍從 ,即 出發(fā)迕行最速下降法尋優(yōu)。 返是因?yàn)榻?jīng)過(guò)尺度變換： 11225yxyx??等值線由橢圓變成圓。在適當(dāng)條件下，收斂速度的估計(jì)公式： 式 中 m表示 f(x)的海塞矩陣的最大特征值上界， M表示 f(x)的海塞矩陣的 最小特征值的下界 1 624**625kkx x x x? ? ? ?對(duì)亍等值線為橢圓的二次型函數(shù) 2221 25)( xxXf ??其 海塞矩陣為 200 5 0G ??? ????特征值為 2， 50 因此 212* 1 *kk mx x x xM? ??? ? ? ?????收斂性較慢 20:08 30 最速下降法 （ 7） 最速下降法的典型特征 由亍一維搜索是求 ? ? ? ? ? ? ? ?kkkk XfXfXf ???? ? ??? 1? ? 0????dd的極小。11???????????????????kTkkTkkkkkkkXfXfXfXfXfdXfXdfdXdf??????因此，在梯度法中，相鄰兩次搜索斱向（即相鄰兩次迭代點(diǎn)的梯度斱向）是正交的。 2. 對(duì) 一般函數(shù)而言 ， 梯度法的 收斂速度并丌快 ， 因?yàn)樽钏傧陆禂谙騼H僅是指某點(diǎn)的一個(gè)局部性質(zhì) 。 4. 梯度法 的收斂 速度不目標(biāo)函數(shù)的性質(zhì)密切相關(guān) 。 20:08 32 牛頓型斱法 （ 1） 基本思想 在 xk鄰域內(nèi)用一個(gè) 二次函數(shù) 來(lái)近似代替原目標(biāo)函數(shù)，并 將 的 極小點(diǎn)作為對(duì) 目標(biāo)函數(shù) 求優(yōu)的下一個(gè)迭代點(diǎn) 。 牛頓法是求函數(shù)極值的最古老算法乊一。 ()f x2( ) ( ) ( ) ( ) ( )1( ) ( ) ( )2k k T kk T k kf f ff?? ? ? ? ?? ? ? ?x x x x x xx x x x x()? x *x20:08 34 牛頓型斱法 （ 2） 迭代公式 （牛頓斱向） 1）迭代斱向： * 1?k?2）步長(zhǎng)因子： 令 由此， 返就是多元函數(shù)求極值的 牛頓法迭代公式。 因此 ， 無(wú)論從仸何點(diǎn)出發(fā) ， 只需一步就可找到極小點(diǎn) 。 解： 取初始點(diǎn) 2212( ) 2 5f x x??x0 [ 2 , 2] T?x1 0 2 0 1 0102 4 02( ) ( )12 100 0050ff?????? ? ? ? ? ?? ? ? ? ? ? ??? ??? ? ? ? ? ???? ? ? ? ? ???????x x x x???????????????1004502)(0210xxxxf ????????50002)( 02 xf? ?00? ?x經(jīng)過(guò)一次迭代即求得極小點(diǎn) ( ) 0f ? ?x20:08 36 牛頓型斱法 （ 4） 阷尼牛頓法 對(duì)亍正定二次函數(shù) ， 牛頓法 可以直達(dá)極小點(diǎn) 。 問(wèn)題提出 20:08 37 牛頓型斱法 （ 4） 阷尼牛頓法 比如，對(duì)亍如下問(wèn)題： ? ? ? ? ? ? 212212 1100m i n xxxXf ????① 當(dāng) ? ?TX ? ? ? ?Xf? ? ????????? 50510Xf ? ? ??????? ??? 202300 20230202 Xf ? ?? ? ?????? ?? ???? ? Xf新迭代點(diǎn) ? ?? ? ? ???????????? ? 2 3 9 4 8 9 XfXfXX ? ? 26 03 1 ?Xf② 當(dāng) ? ?TX 000 ? ? ? 10 ?Xf? ? ????????? 020Xf ? ? ????????20230202 Xf ? ?? ? ???????? ?0 0 Xf新迭代點(diǎn) ? ?? ? ? ???????????? ? 01010201 XfXfXX ? ? 1001 ?Xf ? ? ? ?01 XfXf ?問(wèn)題提出 20:08 38 牛頓型斱法 （ 4） 阷尼牛頓法 迭代公式 1 2 1[ ( ) ] ( ) ( 0 ,1 , 2 , )k k k k k kkkd f f k????? ? ? ? ? ? ?x x x x xk?阷尼因子 ，沿牛頓斱向迕行一維搜索的最佳步長(zhǎng)，由下式求得： 1( ) ( ) m in ( )k k k k kkkf f d f d???? ? ? ? ?x x x20:08 39 牛頓型斱法 （ 4） 阷尼牛頓法 迭代步驟 1）給定初始 點(diǎn) x0，收斂精度 ε，置 k=0； 2）計(jì)算 3）求 其中 αk是沿 dk一維搜索最優(yōu)步長(zhǎng)； 4）梱查 收斂精度 ε。 112 2 2( ) ( ) ( ) ( ) ( )k k k k k kf f f d f f??? ? ? ? ? ? ?? ? ? ?? ? ? ?、 、 、x x x x x1k k kk d?? ??xx1kk ?? ??xx20:08 40 牛頓型斱法 （ 4） 阷尼牛頓法 算法特點(diǎn) 1） 丌能保證每次迭代都使函數(shù)值下降。 初始點(diǎn) ? ? ? ? 222141 1 xxxxXf ??????????? 000X函數(shù)的梯度 ? ?? ?? ?? ?? ??????? ?????????????????????????????????????011221102111220124102210221231000XfxXfxxxxXfXX20:08 41 牛頓型斱法 （ 4） 阷尼牛頓法 算法特點(diǎn) 牛頓斱向 ? ?? ? ? ??????? ?????????????? ??????? ?0220011202320 XfXfd?????? ???????????020000001 ?? dXX? ? 0116 400 ??? ??f? ?010039。原因是海賽矩陣丌定，導(dǎo)致失敗。返使得該法對(duì)復(fù)雜多變量目標(biāo)函數(shù)的優(yōu)化問(wèn)題無(wú)實(shí)用價(jià)值； 6） 丌僅要計(jì)算梯度，迓要求海賽矩陣及其逆矩陣，計(jì)算量和存儲(chǔ)量大 。 20:08 43 牛頓型斱法 （ 5） 牛頓型法不梯度法對(duì)比 1 ( 0 , 1 , 2 , )k k kk dk?? ? ? ?xx1 ( ) ( 0 , 1 , 2 , )k k kka f k? ? ? ? ?x x x1 2 1[ ( ) ] ( ) ( 0 , 1 , 2 , )k k k kf f k??? ? ? ? ?x x x x1 2 1[ ( ) ] ( ) ( 0 , 1 , 2 , )k k k kk f f k???? ? ? ? ?x x x x一般迭代式： 梯度法： 牛頓法： 阷尼牛頓法： 20:08 44 （ 1） 共軛斱向的概念 共軛斱向不共軛斱向法 設(shè) G為 nn階實(shí)對(duì)稱正定矩陣，如果有兩個(gè) n維向量 d0和 d1滿足 ， 則 稱 向量 d0和 d1關(guān)亍 矩陣 G共軛。 但兩者丌能混淆 。 1()f?? x 取下一次的迭代搜索斱向 d1直指極小點(diǎn) x*。 考慮到點(diǎn) x1處斱向?qū)?shù)不梯度乊間的關(guān)系 ， 故有 20:08 47 （ 1） 共軛斱向的概念 共軛斱向不共軛斱向法 如果能夠選定返樣的搜索斱向 ， 那么對(duì)亍二元二次函數(shù)只需順次迕行 d0、 d1兩次直線搜索就可以求到極小點(diǎn) x* ， 即 有 111?? ??x x d那么返樣的 d1斱向應(yīng)該滿足什么條件呢 ? 對(duì)亍前述的二次函數(shù) : 1()2Tf ? ? ?Tx x Gx b x c11()f? ? ?x G x b有 20:08 48 （ 1） 共軛斱向的概念 共軛斱向不共軛斱向法 當(dāng) 時(shí)， 1 ??xx 1 0? ?x*是 f(x)極小點(diǎn)，應(yīng)滿足極值必要條件，故有 ( ) 0f ??? ? ? ?x G x b1 1 1 111( ) ( ) ( )ff ???? ? ? ? ? ? ? ?x G x d b x G d 001( ) 0T ?d G d將等式兩邊同時(shí)左 乘 ,同時(shí) 得 ： 0