【正文】 在 ? ? ? ?? ?0xfxfxL ??上滿足： ? ? ? ?( 0 )22 ,Tnf x m R x L x? ? ? ?? ? ? ? ?則在精確線搜索條件下， 阻尼牛頓法產(chǎn)生的點(diǎn)列 ? ?()kx滿足： (1) 當(dāng) ? ?()kx是有限點(diǎn)列時(shí)， 其最后一個(gè)點(diǎn)為 ? ?xf的唯一極小點(diǎn)． (2) 當(dāng) ? ?()kx是無(wú)限點(diǎn)列時(shí)， 收斂到 ? ?xf的唯一極小點(diǎn)． 阻尼牛頓法收斂定理 定理 3: 設(shè) ? ?xf二階連續(xù)可微， 又設(shè)對(duì)任意的 ( 0 ) ,nxR?存在常數(shù) ,0?m 使得 ? ?xf在 ? ? ? ?? ?( 0 )L x f x f x??上滿足： ? ? ? ?( 0 )22 ,Tnf x m R x L x? ? ? ?? ? ? ? ?則在 Wolfe不精確線搜索條件下， 阻尼牛頓法 產(chǎn)生的點(diǎn)列 ? ?()kx滿足： ? ?()l im 0kk fx?? ??且 ? ?()kx收斂到 ? ?xf的唯一極小點(diǎn)． 例 2： 用阻尼牛頓法求解： ? ? ? ? ? ?(0 )241 1 2 2m i n 1 0 , 0 Tf x x x x x x? ? ? ? ?解： ??????????????????21102000 Gg顯然 0G不是正定的， 但： ???????? ???011210G于是， ???????? ???? ?020100 gGd沿方向 0d進(jìn)行線搜索， ? ?( 0 ) 40 16 1 ,f x d??? ? ?得其極小點(diǎn) .00 ??從而迭代不能繼續(xù)下去． 帶保護(hù)的牛頓法算法 給出 ( 0 ) 12, , , : 0nx R k????Step1: kG若 為奇異的，轉(zhuǎn) Step8，否則， Step2: 令 ,1 kkk gGd ???Step3: 若 ,1 kkkTk dgdg ??為奇異的，轉(zhuǎn) ，否則，則轉(zhuǎn) Step8，否則， Step4: 若 ,1 kkkTk dgdg ??則轉(zhuǎn) Step9，否則， Step5: 沿方向 kd進(jìn)行線搜索， 求出 ,k?并令 ( 1 ) ( ) .kk kkx x d?? ??Step6: 若 ,21 ???kg 停； Step7: 令 ,1?? kk 轉(zhuǎn) Step1； Step8: 令 ,kk gd ?? 轉(zhuǎn) Step5； Step9: 令 ,kk dd ??轉(zhuǎn) Step5. 例 3： 用帶保護(hù)的牛頓法求解： ? ? ? ? ? ?( 0 )241 1 2 2m i n 1 0 , 0 Tf x x x x x x? ? ? ? ?解： ??????????????????21102000 Gg顯然 0G不是正定的， 但： ???????? ???011210G于是， ???????? ???? ?020100 gGd因?yàn)椋? ,000 ?dg T故令， ,2000 ???????????? gd沿 0d進(jìn)行線搜索得： ,210 ??? ?( 1 ) ( 1 )0 ,01x f x?????????第二次迭代： ????????????????? ??2110,0111 Gg而： ???????? ???? ?121111 gGd使 ,0211 ??dg T 故令 ?????????????????? ???12121d沿 1d進(jìn)行線搜索， 得出 ,1 ??于是 : ? ?( 2 ) ( 2 ) f x??? ? ??????此時(shí) : ???????? ???0 72g共軛梯度法 問(wèn)題 1: 如何建立有效的算法？ 從二次模型到一般模型 問(wèn)題 2: 什么樣的算法有效呢？ 二次終止性 (經(jīng)過(guò)有限次迭代必達(dá)到極小點(diǎn)的性質(zhì)） 算法特點(diǎn) （１）建立在二次模型上，具有二次終止性． （２）有效的算法，克服了最速下降法的慢 收斂性，又避免了牛頓法的計(jì)算量大和局部收 性的缺點(diǎn)． （３）算法簡(jiǎn)單，易于編程，需存儲(chǔ)空間小等 優(yōu)點(diǎn)，是求解大規(guī)模問(wèn)題的主要方法． 共軛方向及其性質(zhì) 定義 1: 設(shè) mddd , 21 ?是 nR 中任一組 非零向量， 如果： ? ?jiGdd jTi ?? ,0則稱 mddd , 21 ?是關(guān)于 G 共軛的． 注： 若 ,IG ? 則是正交的，因此共軛是 正交的推廣． 定理 1: 設(shè) G為 n 階正定陣， 非零向量組 mddd , 21 ?關(guān)于 G 共軛， 則必線性無(wú)關(guān)． 推論 1: 設(shè) G為 n階正定陣， 非零向量組 nddd , 21 ?關(guān)于 G共軛， 則向量構(gòu)成 nR的一組基． 推論 2: 設(shè) G為 n 階正定陣， 非零向量組 nddd , 21 ?關(guān)于 G 共軛， 若向量 v 與 nddd , 21 ?關(guān)于 G 共軛， 則 .0?v求 的極小點(diǎn)的方法 共軛方向法算法 ? ? ? ?( ) ( )0m i n ,kkk k kf x d f x d??? ?? ? ?Step1: 給出 ( 0 ) , 0 1 , : 0nx R k?? ? ? ? ?計(jì)算 ? ?( 0 )0g g x?和初始下降方向 .0dStep2: 如果 ,??kg 停止迭代． Step3: 計(jì)算 ( 1 ),kk x? ?使得 ( 1 ) ( ) .kk kkx x d?? ??Step4: 采用某種共軛方向法計(jì)算 1?kd使得： .,1,0,01 kjGdd jTk ????Step5: 令 ,1: ?? kk 轉(zhuǎn) Step2. 共軛方向法基本定理 定義 2: 設(shè) n 維向量組 kddd , 21 ?線性無(wú)關(guān)， ( 1 ) ,nxR?向量集合 ? ?( 1 ) 11kk i i iiH x d R???? ? ??為 (1)x 與 kddd , 21 ?生成的 k 維超平面． 引理 1: 設(shè) ? ?xf 是連續(xù)可微的嚴(yán)格凸函數(shù)， n 維向量組 kddd ?, 21線性無(wú)關(guān)， ( 1 ) ,nxR?則： ( 1 ) ( 1 )1kkiiix x d????? ?是 ? ?xf在 kH上 唯一極小點(diǎn)的充要條件是： kidg iTk ?,2,1,01 ???定理 2: 設(shè) G為 n 階正定陣， 向量組 kddd ?, 21關(guān)于 G共軛， 對(duì)正定二次函數(shù) ? ? ,21 cxbGxxxf TT ???由任意 開(kāi)始， 依次進(jìn)行 k 次精確線搜索： ( 1 ) ( ) , 1 , 2 , ,ii iix x d i k?? ? ? ?則： （１） kidgiTk ?,2,1,01 ???（２） ( 1)kx ? 是 ? ?xf在 kH上的極小點(diǎn)． 推論 : 當(dāng) nk ? 時(shí)， 為正定二次函數(shù)在 nR上的極小點(diǎn)． (1)x( 1)nx ?共軛梯度法 記： 11 ????? kkkk dgd ?左乘 ,1Gd Tk ?并使 1111???? ?kTkkTkk GddGdg?,01 ?? kTk dGd 得： （ HestenesStiefel公式） ?。? 00 gd ??—— 是一種特殊的共軛方向法 共軛梯度法基本性質(zhì) 定理 3: 對(duì)于正定二次函數(shù)， 采用精確線搜索 的共軛梯度法在 nm ? 步后終止， 且對(duì) ni ??1 成立下列關(guān)系式： ,1,1,0,0 ??? ijGdd jTi ?,1,1,0,0 ??? ijgg jTi ?,iTiiTi gggd ??,1,1,00 ??? ijdg jTi ?（共軛性） （正交性） （下降條件） 系數(shù)的其他形式 （１） FR公式 111??? ?kTkkTkk gggg?（ 1964） （ 2） PRP公式 ? ?1111??????kTkkkTkk ggggg? （ 1969） FR共軛梯度法算法 ? ?( + 1 )+1 ,kkg f x??( 0 )00 ()d g f x? ? ? ??令Step1: 給出 ( 0 ) , 0 1 , : 0nx R k?? ? ? ? ?Step2: 如果 ,??kg停． Step5: 轉(zhuǎn) Step2. 計(jì)算 Step4: 11 ,k k k kd g d???? ? ?11Tkkk Tkkgggg???? ，Step3: 由精確線搜索求 ,k?計(jì)算 1 ,kk??令( 1 ) ( ) ,kk kkx x d?? ??并 令例 4： 用 FR共軛梯度法求解： ? ? ? ?2 2 ( 0 )1 2 1 2 131mi n 2 2 , 422 Tf x x x x x x x? ? ? ? ? ?解： 化成 ? ? cxbGxxxf TT ??? 21形式 ? ? ? ? ? ? ?????????????????????????????212121 0,21113,21xxxxxxxf( 0 ) 24x???????? ( 0 )0126g Gx b???? ? ?????(1) 0126d ??? ?????17500000 ??? GdddgTT?( 1 ) ( 0 )0026173817x x d???????? ? ???????116171217g Gx b??????? ? ??????? ?g(2) 289100110 ?? ggggTT???????????????????289210289900011 dgd ?171011111 ??? GdddgTT? ( 2 ) ( 1 )1111x x d???? ? ?????02 ?g * ( 2 ) 11xx ???? ????例 5： 用 FR共軛梯度法求解： ? ? ? ? ? ?2 2 ( 0 )1 2 011mi n 1 , 1 1 , 022 TTf x x x x d? ? ? ? ?解： 化成 ? ? cxbGxxxf TT ??? 21形式 ? ? ? ? ?????????????????2121 1001,21xxxxxf(0 ) 11x??????? (0 )011g Gx b??? ? ?????(1) ???????? ??010d100000 ??? GdddgTT? ( 1 ) ( 0 ) 0001x x d???? ? ?????( 1 )101g Gx b??? ? ?????11 ?g(2) 2100110 ?? ggggTT? ??????????????1210011 dgd ?5411111 ??? GdddgTT? ( 2 ) ( 1 )112515x x d????????? ? ???????( 2 )22515g Gx b???????? ? ???????2 1 / 5g ?(3)2211115TTgggg