最优化牛顿法

1、一、一、Newton Newton 法法 )(minxfnRx 上上二二次次连连续续可可微微函函数数是是nRxf)()()(2nRCxf 即即1. 问题问题。近似近似，用二次函数，用二次函数产生产生为了由为了由)()(1xfxQxxkk 110kkxxxx)()(21)()()()()(2kkTkkTkkxxxfxxxxxfxfxQxf 2. 算法思想算法思想)()(21)()(kkTkkTkkxxGxxxxgxf 。其中其中)(,)(2kkTkkxfGxfg 0)()( kkkxxGgxQ，此此时时有有则则，正正定定，即即矩矩阵阵若若001 kkkGGGHessekkkkgGxx11 。迭迭

2、代代公公式式这这就就是是Newton令令有有比较迭代公式比较迭代公式,1kkkkdtxx ,1kkkgGd 。而而1 kt0010 :k,x.step，精精度度给给定定初初始始点点103 kkkkx)xx(Gg)x(Q.step解解出出由由方方程程组组)x(fG)x(fg.stepkkkk22 和和计计算算。可可逆逆时时，当当kkkkkgGxxG11 3. 算法步骤算法步骤;,|)(|. 41*1 kkxxxfstep停止，停止，若若 。转令，否则2, 1:stepkk 收敛速度快，为二阶收敛。（2） 初始点的选取困难，甚至无法实施。初始点的选取困难，甚至无法实施。的的存存在在性性和和计计算算

3、量量问问题题1(3) kG?(1)1)x(f)x(fkk 4. 算法特点算法特点5. 存在缺点及修正存在缺点及修正 初始点要选在最优解附近。 ?1)x(f)x(fkk 如如何何使使得得问问题题一一：)(min)(:1kkkkkkkkkkdtxfdtxftdtxxNewton 法法稍稍作作修修正正：如如果果对对kkkkkkdxgGxx 11Newton 法法中中，有有在在,0)()(011 kkTkkkTkkTkkgGggGxfdxfG有有时时，当当是是下下降降方方向向。时时，当当kkdG0 。则则有有：)()(1kkxfxf ?32）和和（如如何何克克服服缺缺点点（问问题题二二：)(Newto

4、n变变尺尺度度法法算算法法二二、拟拟)x(fGxxNewton.kkkk 111迭迭代代公公式式：先先考考虑虑)x(fHxxGHNewtonkkkkkk 11，则则有有：替替代代正正定定矩矩阵阵用用迭迭代代公公式式中中，如如果果我我们们在在)x(fHtxx.kkkkk 12考考虑虑更更一一般般的的形形式式：xIxxxfdIHxfHtxxTkkkkkkkk 度度量量为为最最速速下下降降方方向向梯梯度度法法时时, )()(1xGxxxfGdNewtonNewtonGHkTkkkkk度量为方向法时),(11法法为为变变尺尺度度算算法法。称称Newton）收收敛敛速速度度要要快快（的的计计算算量量要要

5、小小）（质质）迭迭代代公公式式具具有有下下降降性性（附附加加某某些些条条件件使使得得：如如何何对对3213kkHH.0 kH)HHH(HHHkkkkkk 111 kkGH？如如何何确确定定和和如如何何保保证证kkkkH?GHH 101 kkGHNewton条条件件拟拟条条件件拟拟Newton则则因因为为记记),()(),()(2kkkkxfGxfgxfxg )xx(Gggkkkkk111 这这样样我我们们想想到到,xx)gg(Gkkkkk 1111。kkkkkxxggH 111)(。此条件确定此条件确定需满足的条件，并利用需满足的条件，并利用分析：分析：kkHG1 )()()()(111 kT

6、kkxxxfxfxf)()(211121 kKTkxxxfxx)()()(1121 kkkxxxfxgxg则则有有记记,11kkkkkkxxsggy 的的一一般般步步骤骤；变变尺尺度度法法算算法法、拟拟)(Newton400100 :k,H,x.Step，精精度度正正定定矩矩阵阵给给定定初初始始点点; )(. 2kkkxfHdStep 计计算算搜搜索索方方向向。其其中中令令)(min)(:,. 31kkkkkkkkkkdtxfdtxftdtxxstep 。方方程程条条件件或或拟拟拟拟NewtonNewtonsyHkkk 1Step 4. Step 4. 判断判断 是否满足终止准则：是否满足终止

7、准则： yes: yes: 计算计算 stop, stop, No : No : 转转step 5 step 5 。1 kx1 k*x:x. 21:,1111stepkksyHNewtonNewtonHHHHHkkkkkkkk转转，令令。方方程程：或或拟拟条条件件拟拟满满足足使使得得计计算算按按照照校校正正公公式式 。令令kkkkkkkkkkkkxxsggxfxfyxfgxfgstep 11111,)()(, )(, )(. 5校校正正法法秩秩？如如何何确确定定1 kH）三三、对对称称秩秩一一校校正正（1SRTkkkkkkvuHHHH 1nkkRvu ，待待定定：的确定。的确定。kHkkTkk

8、kkksyvuHyH )(1由由拟拟牛牛顿顿条条件件kkkkTkkyHsyvu 上上。必必在在kkkkyHsu 已已满满足足拟拟牛牛顿顿条条件件）（否否则则，假假定定kkkkHyHs0 kTkTkkkkkkkTkyvvyHsHHyv)(01 则则有有kTkkkTkkkkkkkkkyyHsyHsyHsHHH)()(1 对对称称要要求求kTkkkTkkkkkkkkyyHsyHsyHsHHSR)()(11 校校正正：.11 GHnSRn步步终终止止性性质质而而具具有有需需要要线线搜搜索索，即即对对于于二二次次函函数数，它它不不校校正正具具有有二二次次终终止止性性，.1,1110 GHnSRsssnn

9、步步终终止止，即即方方法法至至多多校校正正函函数数，线线性性无无关关，那那么么对对二二次次设设定定理理校校正正特特点点1SR有有二二次次终终止止性性。不不需需要要做做线线搜搜索索，而而具具. 1.,. 2ijsyHjji 具具有有遗遗传传性性质质时时，才才正正定定。只只有有（不不保保证证0), 0. 3 kTkkkkyyHsH校校正正法法秩秩？如如何何确确定定22 kH.算算法法四四、DFP的的一一个个重重要要工工作作多多变变量量无无约约束束优优化化问问题题）（做做了了改改进进和和年年）（首首次次提提出出年年）（算算法法的的提提出出：319632195911PowellFletcherDavi

10、donDFP.TkkkTkkkkkkkvvuuHHHH 1nkkkkRvu,R ，待待定定：的确定。的确定。kH，我我们们有有条条件件：拟拟根根据据kkksyHNewton 1kkTkkkTkkkksy)vvuuH( kkkkTkkkkTkkkyHsyvvyuu 即即：kkkTkkkkkTkkkyHyvvsyuu 组组解解：，我我们们可可以以如如下下确确定定一一满满足足上上述述方方程程的的解解很很多多。这这样样，我我们们可可以以取取：1,1, kTkkkkkkTkkkkyvyHvyusu 。即即：kkTkkkkkkTkkkkyHyyHvyssu1,1, 校校正正公公式式的的校校正正公公式式：的

11、的够够得得到到根根据据上上述述推推导导，我我们们能能DFPyHyHyyHysssHHDFPHkkTkkTkkkkTkkTkkkk 1。校校正正可可以以保保证证则则定定理理：0, 000 kkTHDFPysHk算算法法的的步步骤骤；、DFP3步改为：步改为：将变尺度法的第将变尺度法的第 5.step,k:kHyHyHyyHysssHHDFP.stepkkkTkkTkkkkTkkTkkk2151转转，计计算算的的校校正正公公式式：按按照照 .11,4)(min.02221 xxxxfDFP初始点初始点算法求解算法求解请用请用例例，因为因为算法与梯度法相同：算法与梯度法相同：第一步第一步。解：取解：

12、取 ttxftxDFPxxxfIH8121)(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

13、. 0111112dxdtxx是极小点。是极小点。，所以，所以因为因为220)(xxf )1970,(ShannoGoldfardFletcherBroydenBFGS 校校正正五五、kkkkkkysBsyH 11由由拟拟牛牛顿顿条条件件TkkkTkkkkkvvbuuaBB 1kkkkTkkkkTkkksBysvvbsuua ;1,;1,kkTkkkkkkTkkkksBsbsBvysayu kkTkTkkkkkTkTkkkksBssBsBysyyBB)(1 uAvAuvAAuvAMorrisonShermenTTT111111)(: kTkTkkkkTkkkTkTkkkTkTkkTkkkyssyHHysysssysyHyHH )1(1)1970,(ShannoGoldfardFletcherBroydenBFGS 校校正正五五、kTkTkkkkTkkkTkTkkkTkTkkTkkkyssyHHysysssysyHyHH )1(1。校校正正可可以以保保证证则则定定理理：0, 000 kkTHBFGSysHk校校正正特特点点BFGS搜搜索索方方法法结结合合使使用用。线线，尤尤其其是是常常能能与与低低精