牛顿法与拟牛顿法

一、Newton法)(minxfnRx上二次连续可微函数是nRxf)()()(2nRCxf即1.问题局部收敛性修正牛顿法二、拟牛顿法习题。近似，用二次函数产生为了由)()(1xfxQxxkk110kkxxxx))(()(21)()()()()(2kkTkkTkkxxxfxxxxxfxfxQxf2.算法思想)()(21)()(kkTkkTkkxxGxxxxgxf。其中)(,)(2kkTkkxfGxfg0)()(kkkxxGgxQ，此时有则，正定，即矩阵若001kkkGGGHessekkkkgGxx11。迭代公式这就是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停止，若。转令，否则4,1:stepkk收敛速度快，为二阶收敛。（2）初始点的选取困难，甚至无法实施。。的存在性和计算量问题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））和（如何克服缺点（问题二：)(Newton变尺度法算法二、拟)x(fGxxNewton.kkkk111迭代公式：先考虑)x(fHxxGHNewtonkkkkkk11，则有：替代正定矩阵用迭代公式中，如果我们在)x(fHtxx.kkkkk12考虑更一般的形式：xIxxxfdIHxfHtxxTkkkkkkkk度量为最速下降方向梯度法时,)()(1xGxxxfGdNewtonGHkTkkkkk111),(度量为最速下降方向法时法为变尺度算法。称Newton）收敛速度要快（的计算量要小）（质）迭代公式具有下降性（附加某些条件使得：如何对3213kkHH.0kH)HHH(HHHkkkkkk111kkGH？如何确定和如何保证kkkkH?GHH101kkGHNewton条件拟条件拟Newton则因为记),()(),()(2kkkkxfGxfgxfxg)xx(Gggkkkkk111这样我们想到,xx)gg(Gkkkkk1111。此条件确定需满足的条件，并利用分析：kkHG1)()()()(111kTkkxxxfxfxf))(()(211121kKTkxxxfxx))(()()(1121kkkxxxfxgxg111()kkkkkHggxx。则有记,,11kkkkkkxxsggy的一般步骤；变尺度法算法、拟)(Newton400100:k,H,x.Step，精度正定矩阵给定初始点。其中令)(min)(:,.31kkkkkkkkkkdtxfdtxftdtxxstep1kkkHysNewtonNewton拟条件或拟方程。2.();kkkStepdHfx计算搜索方向Step4.判断是否满足终止准则：yes:计算stop,No:转step5。1kx1k*x:x.21:,1111stepkksyHNewtonNewtonHHHHHkkkkkkkk转，令。方程：或拟条件拟满足使得计算按照校正公式。令kkkkkkkkkkkkxxsggxfxfyxfgxfgstep11111,)()(,)(,)(.5校正法秩？如何确定22kH.算法三、DFP的一个重要工作多变量无约束优化问题）（做了改进和年）（首次提出年）（算法的提出：319632195911PowellFletcherDavidonDFP.TkkkTkkkkkkkvvuuHHHH1nkkkkRvu,R，，待定：的确定。kH，我们有条件：拟根据kkksyHNewton1kkTkkkTkkkksy)vvuuH(kkkkTkkkkTkkkyHsyvvyuu即：kkkTkkkkkTkkkyHyvvsyuu组解：，我们可以如下确定一满足上述方程的解很多。这样，我们可以取：1,,1,kTkkkkkkTkkkkyvyHvyusu。即：kkTkkkkkkTkkkkyHyyHvyssu1,,1,校正公式的校正公式：的够得到根据上述推导，我们能DFPyHyHyyHysssHHDFPHkkTkkTkkkkTkkTkkkk1。性质：000kHH算法的步骤；、DFP3步改为：将变尺度法的第5.step,k:kHyHyHyyHysssHHDFP.stepkkkTkkTkkkkTkkTkkk2151转，计算的校正公式：按照.11,4)(min.02221xxxxfDFP初始点算法求解请用例，因为算法与梯度法相同：第一步。解：取ttxftxDFPxxxfIH8121)(82)(,00210。36923.852308.0)()(,04616.126154.001010010ggxfxfyxxs。所以解得04616.073846.0,13.0)81(4)21())((min))((102200000xtttxftxfxftxf。的校正公式：按照12697.003149.003149.000380.10000000000001yHyHyyHysssHHDFPTTTT。搜索方向09340.049416.1)(111xfHd。0000.00000.049423.0111112dxdtxx是极小点。，所以因为220)(xxf