最優(yōu)化牛頓法

1、一、一、Newton Newton 法法 )(minxfnRx 上上二二次次連連續(xù)續(xù)可可微微函函數(shù)數(shù)是是nRxf)()()(2nRCxf 即即1. 問(wèn)題問(wèn)題。近近似似，用用二二次次函函數(shù)數(shù)產(chǎn)產(chǎn)生生為為了了由由)()(1xfxQxxkk 110kkxxxx)()(21)()()()()(2kkTkkTkkxxxfxxxxxfxfxQxf 2. 算法思想算法思想)()(21)()(kkTkkTkkxxGxxxxgxf 。其中其中)(,)(2kkTkkxfGxfg 0)()( kkkxxGgxQ，此此時(shí)時(shí)有有則則，正正定定，即即矩矩陣陣若若001 kkkGGGHessekkkkgGxx11 。迭迭代

2、代公公式式這這就就是是 Newton令令有有比比較較迭迭代代公公式式,1kkkkdtxx ,1kkkgGd 。而而1 kt0010 :k,x.step，精精度度給給定定初初始始點(diǎn)點(diǎn)103 kkkkx)xx(Gg)x(Q.step解解出出由由方方程程組組)x(fG)x(fg.stepkkkk22 和和計(jì)計(jì)算算?？煽赡婺鏁r(shí)時(shí)，當(dāng)當(dāng)kkkkkgGxxG11 3. 算法步驟算法步驟;,|)(|. 41*1 kkxxxfstep停停止止，若若 。轉(zhuǎn)令，否則2, 1:stepkk 收斂速度快，為二階收斂。（2） 初始點(diǎn)的選取困難，甚至無(wú)法實(shí)施。初始點(diǎn)的選取困難，甚至無(wú)法實(shí)施。的的存存在在性性和和計(jì)計(jì)算算量

3、量問(wèn)問(wèn)題題1(3) kG?(1)1)x(f)x(fkk 4. 算法特點(diǎn)算法特點(diǎn) 存在缺點(diǎn)及修正存在缺點(diǎn)及修正 初始點(diǎn)要選在最優(yōu)解附近。 ?1)x(f)x(fkk 如如何何使使得得問(wèn)問(wèn)題題一一：)(min)(:1kkkkkkkkkkdtxfdtxftdtxxNewton 法法稍稍作作修修正正：如如果果對(duì)對(duì)kkkkkkdxgGxx 11Newton 法法中中，有有在在,0)()(011 kkTkkkTkkTkkgGggGxfdxfG有有時(shí)時(shí)，當(dāng)當(dāng)是是下下降降方方向向。時(shí)時(shí)，當(dāng)當(dāng)kkdG0 。則則有有：)()(1kkxfxf ?32）和和（如如何何克克服服缺缺點(diǎn)點(diǎn)（問(wèn)問(wèn)題題二二：)(Newton變變

4、尺尺度度法法算算法法二二、擬擬)x(fGxxNewton.kkkk 111迭迭代代公公式式：先先考考慮慮)x(fHxxGHNewtonkkkkkk 11，則則有有：替替代代正正定定矩矩陣陣用用迭迭代代公公式式中中，如如果果我我們們?cè)谠?x(fHtxx.kkkkk 12考考慮慮更更一一般般的的形形式式：xIxxxfdIHxfHtxxTkkkkkkkk 度度量量為為最最速速下下降降方方向向梯梯度度法法時(shí)時(shí), )()(1xGxxxfGdNewtonNewtonGHkTkkkkk度量為方向法時(shí)),(11法法為為變變尺尺度度算算法法。稱(chēng)稱(chēng)Newton）收收斂斂速速度度要要快快（的的計(jì)計(jì)算算量量要要小?。?/p>

5、（質(zhì)質(zhì)）迭迭代代公公式式具具有有下下降降性性（附附加加某某些些條條件件使使得得：如如何何對(duì)對(duì)3213kkHH.0 kH)HHH(HHHkkkkkk 111 kkGH？如如何何確確定定和和如如何何保保證證kkkkH?GHH 101 kkGHNewton條條件件擬擬條條件件擬擬Newton則則因因?yàn)闉橛浻?,()(),()(2kkkkxfGxfgxfxg )xx(Gggkkkkk111 這這樣樣我我們們想想到到,xx)gg(Gkkkkk 1111。kkkkkxxggH 111)(。此此條條件件確確定定需需滿滿足足的的條條件件，并并利利用用分分析析：kkHG1 )()()()(111 kTkkxxx

6、fxfxf)()(211121 kKTkxxxfxx)()()(1121 kkkxxxfxgxg則則有有記記,11kkkkkkxxsggy 的的一一般般步步驟驟；變變尺尺度度法法算算法法、擬擬)(Newton400100 :k,H,x.Step，精精度度正正定定矩矩陣陣給給定定初初始始點(diǎn)點(diǎn); )(. 2kkkxfHdStep 計(jì)計(jì)算算搜搜索索方方向向。其其中中令令)(min)(:,. 31kkkkkkkkkkdtxfdtxftdtxxstep 。方方程程條條件件或或擬擬擬擬NewtonNewtonsyHkkk 1Step 4. Step 4. 判斷判斷 是否滿足終止準(zhǔn)則：是否滿足終止準(zhǔn)則： y

7、es: yes: 計(jì)算計(jì)算 stop, stop, No : No : 轉(zhuǎn)轉(zhuǎn)step 5 step 5 。1 kx1 k*x:x. 21:,1111stepkksyHNewtonNewtonHHHHHkkkkkkkk轉(zhuǎn)轉(zhuǎn)，令令。方方程程：或或擬擬條條件件擬擬滿滿足足使使得得計(jì)計(jì)算算按按照照校校正正公公式式 。令令kkkkkkkkkkkkxxsggxfxfyxfgxfgstep 11111,)()(, )(, )(. 5校校正正法法秩秩？如如何何確確定定1 kH）三三、對(duì)對(duì)稱(chēng)稱(chēng)秩秩一一校校正正（1SRTkkkkkkvuHHHH 1nkkRvu ，待待定定：的確定。的確定。kHkkTkkkkksy

8、vuHyH )(1由由擬擬牛牛頓頓條條件件kkkkTkkyHsyvu 上上。必必在在kkkkyHsu 已已滿滿足足擬擬牛牛頓頓條條件件）（否否則則，假假定定kkkkHyHs0 kTkTkkkkkkkTkyvvyHsHHyv)(01 則則有有kTkkkTkkkkkkkkkyyHsyHsyHsHHH)()(1 對(duì)對(duì)稱(chēng)稱(chēng)要要求求kTkkkTkkkkkkkkyyHsyHsyHsHHSR)()(11 校校正正：.11 GHnSRn步步終終止止性性質(zhì)質(zhì)而而具具有有需需要要線線搜搜索索，即即對(duì)對(duì)于于二二次次函函數(shù)數(shù)，它它不不校校正正具具有有二二次次終終止止性性，.1,1110 GHnSRsssnn步步終終止

9、止，即即方方法法至至多多校校正正函函數(shù)數(shù)，線線性性無(wú)無(wú)關(guān)關(guān)，那那么么對(duì)對(duì)二二次次設(shè)設(shè)定定理理校校正正特特點(diǎn)點(diǎn)1SR有有二二次次終終止止性性。不不需需要要做做線線搜搜索索，而而具具. 1.,. 2ijsyHjji 具具有有遺遺傳傳性性質(zhì)質(zhì)時(shí)時(shí)，才才正正定定。只只有有（不不保保證證0), 0. 3 kTkkkkyyHsH校校正正法法秩秩？如如何何確確定定22 kH.算算法法四四、DFP的的一一個(gè)個(gè)重重要要工工作作多多變變量量無(wú)無(wú)約約束束優(yōu)優(yōu)化化問(wèn)問(wèn)題題）（做做了了改改進(jìn)進(jìn)和和年年）（首首次次提提出出年年）（算算法法的的提提出出：319632195911PowellFletcherDavidonDF

10、P.TkkkTkkkkkkkvvuuHHHH 1nkkkkRvu,R ，待待定定：的確定。的確定。kH，我我們們有有條條件件：擬擬根根據(jù)據(jù)kkksyHNewton 1kkTkkkTkkkksy)vvuuH( kkkkTkkkkTkkkyHsyvvyuu 即即：kkkTkkkkkTkkkyHyvvsyuu 組組解解：，我我們們可可以以如如下下確確定定一一滿滿足足上上述述方方程程的的解解很很多多。這這樣樣，我我們們可可以以取?。?,1, kTkkkkkkTkkkkyvyHvyusu 。即即：kkTkkkkkkTkkkkyHyyHvyssu1,1, 校校正正公公式式的的校校正正公公式式：的的夠夠得得

11、到到根根據(jù)據(jù)上上述述推推導(dǎo)導(dǎo)，我我們們能能DFPyHyHyyHysssHHDFPHkkTkkTkkkkTkkTkkkk 1。校校正正可可以以保保證證則則定定理理：0, 000 kkTHDFPysHk算算法法的的步步驟驟；、DFP3步步改改為為：將將變變尺尺度度法法的的第第5.step,k:kHyHyHyyHysssHHDFP.stepkkkTkkTkkkkTkkTkkk2151轉(zhuǎn)轉(zhuǎn)，計(jì)計(jì)算算的的校校正正公公式式：按按照照 .11,4)(min.02221 xxxxfDFP初初始始點(diǎn)點(diǎn)算算法法求求解解請(qǐng)請(qǐng)用用例例，因?yàn)橐驗(yàn)樗惴ㄅc梯度法相同：算法與梯度法相同：第一步第一步。解：取解：取 ttxft

12、xDFPxxxfIH8121)(82)(,00210。 36923. 852308. 0)()(,04616. 126154. 001010010ggxfxfyxxs。所所以以解解得得 04616. 073846. 0,13. 0)81(4)21()(min)(102200000 xtttxftxfxftxf。的的校校正正公公式式：按按照照 12697. 003149. 003149. 000380. 10000000000001yHyHyyHysssHHDFPTTTT。搜搜索索方方向向 09340. 049416. 1)(111xfHd。 0000. 00000. 049423. 01111

13、12dxdtxx是是極極小小點(diǎn)點(diǎn)。，所所以以因因?yàn)闉?20)(xxf )1970,(ShannoGoldfardFletcherBroydenBFGS 校校正正五五、kkkkkkysBsyH 11由由擬擬牛牛頓頓條條件件TkkkTkkkkkvvbuuaBB 1kkkkTkkkkTkkksBysvvbsuua ;1,;1,kkTkkkkkkTkkkksBsbsBvysayu kkTkTkkkkkTkTkkkksBssBsBysyyBB)(1 uAvAuvAAuvAMorrisonShermenTTT111111)(: kTkTkkkkTkkkTkTkkkTkTkkTkkkyssyHHysysssysyHyHH )1(1)1970,(ShannoGoldfardFletcherBroydenBFGS 校校正正五五、kTkTkkkkTkkkTkTkkkTkTkkTkkkyssyHHysysssysyHyHH )1(1。校校正正可可以以保保證證則則定定理理：0, 000 kkTHBFGSysHk校校正正特特點(diǎn)點(diǎn)BFGS搜搜索索方方法法結(jié)結(jié)合合使使用用。線線，尤尤其其是是常常能能與與低低精精