最优化牛顿法

一、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停止，若。转令，否则2,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度量为最速下降方向梯度法时,)()(1xGxxxfGdNewtonNewtonGHkTkkkkk度量为方向法时),(11法为变尺度算法。称Newton）收敛速度要快（的计算量要小）（质）迭代公式具有下降性（附加某些条件使得：如何对3213kkHH.0kH)HHH(HHHkkkkkk111kkGH？如何确定和如何保证kkkkH?GHH101kkGHNewton条件拟条件拟Newton则因为记),()(),()(2kkkkxfGxfgxfxg)xx(Gggkkkkk111这样我们想到,xx)gg(Gkkkkk1111。kkkkkxxggH111)(。此条件确定需满足的条件，并利用分析：kkHG1)()()()(111kTkkxxxfxfxf))(()(211121kKTkxxxfxx))(()()(1121kkkxxxfxgxg则有记,,11kkkkkkxxsggy的一般步骤；变尺度法算法、拟)(Newton400100:k,H,x.Step，精度正定矩阵给定初始点;)(.2kkkxfHdStep计算搜索方向。其中令)(min)(:,.31kkkkkkkkkkdtxfdtxftdtxxstep。方程条件或拟拟NewtonNewtonsyHkkk1Step4.判断是否满足终止准则：yes:计算stop,No:转step5。1kx1k*x:x.21:,1111stepkksyHNewtonNewtonHHHHHkkkkkkkk转，令。方程：或拟条件拟满足使得计算按照校正公式。令kkkkkkkkkkkkxxsggxfxfyxfgxfgstep11111,)()(,)(,)(.5校正法秩？如何确定1kH）三、对称秩一校正（1SRTkkkkkkvuHHHH1nkkRvu，待定：的确定。kHkkTkkkkksyvuHyH)(1由拟牛顿条件kkkkTkkyHsyvu上。必在kkkkyHsu已满足拟牛顿条件）（否则，假定kkkkHyHs0kTkTkkkkkkkTkyvvyHsHHyv)(01则有kTkkkTkkkkkkkkkyyHsyHsyHsHHH)())((1对称要求kTkkkTkkkkkkkkyyHsyHsyHsHHSR)())((11校正：.11GHnSRn步终止性质而具有需要线搜索，即对于二次函数，它不校正具有二次终止性，.1,,,1110GHnSRsssnn步终止，即方法至多校正函数，线性无关，那么对二次设定理校正特点1SR有二次终止性。不需要做线搜索，而具.1.,.2ijsyHjji具有遗传性质时，才正定。只有（不保证0),0.3kTkkkkyyHsH校正法秩？如何确定22kH.算法四、DFP的一个重要工作多变量无约束优化问题）（做了改进和年）（首次提出年）（算法的提出：319632195911PowellFletcherDavidonDFP.TkkkTkkkkkkkvvuuHHHH1nkkkkRvu,R，，待定：的确定。kH，我们有条件：拟根据kkksyHNewton1kkTkkkTkkkksy)vvuuH(kkkkTkkkkTkkkyHsyvvyuu即：kkkTkkkkkTkkkyHyvvsyuu组解：，我们可以如下确定一满足上述方程的解很多。这样，我们可以取：1,,1,kTkkkkkkTkkkkyvyHvyusu。即：kkTkkkkkkTkkkkyHyyHvyssu1,,1,校正公式的校正公式：的够得到根据上述推导，我们能DFPyHyHyyHysssHHDFPHkkTkkTkkkkTkkTkkkk1。校正可以保证则定理：0,000kkTHDFPysHk算法的步骤；、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)1970,(ShannoGoldfardFletcherBroydenBFGS校正五、kkkkkkysBsyH11由拟牛顿条件TkkkTkkkkkvvbuuaBB1kkkkTkkkkTkkksBysvvbsuua;1,;1,kkTkkkkkkTkkkksBsbsBvysayukkTkTkkkkkTkTkkkksBssBsBysyyBB)(1uAvAuvAAuvAMorrisonShermenTTT111111)(:kTkTkkkkTkkkTkTkkkTkTkkTkkkyssyHHysysssysyHyHH)1(1)1970,(ShannoGoldfardFletcherBroydenBFGS校正五、kTkTkkkkTkkkTkTkkkTkTkkTkkkyssyHHysysssysyHyHH)1(1。校正可以保证则定理：0,000kkTHBFGSysHk校正特点BFGS搜索方法结合使用。线，尤其是常能与低精度也优于在数值计算中，还未能证明。敛性。这个性质对于时，具有总体收索此外，当采用不精确搜校正的各种性质。公式，具有迄今为止最好的拟牛顿DFPBFGSDFPPowellWolfeDFP)(.,11,4)(min.02221选用精确线搜索初始点算法求解请用例xxxxfBFGS