牛顿法与修正牛顿法

牛顿法与修正牛顿法6、评价4、优缺点5、修正牛顿法3、迭代步骤1、思想来源2、基本思想牛顿法和修正牛顿法1、思想来源梯度法相邻两次搜索方向总是相互正交，搜索路线呈锯齿形，使得其在极小点附近，收敛速度越来越慢。人们试图找到这样一种方向：它直接指向最优点，使得从任意选定的初始点出发，沿此方向迭代一次就能达到极小点。2、基本思想在求目标函数的极小值时，先将它在点附近展开成泰勒级数的二次函数式，然后求出函数的极小值点，并以此点作为欲求目标函数的极小值点的一次近似值。设目标函数是连续二阶可微的，将函数在点按泰勒级数展开，并取到二次项：)(kx))(()(21)()]([)()()()()()()()()()(kkTkkTkkkxxxHxxxxxfxfxxf)(xf)(kx*x对x求导，其极值点必满足一阶导数为零，所以，得到式中，为Hessian矩阵的逆矩阵。0)()()()()()()(kkkxHxxxfxxfx)()()(1)()(minkkkxfxHxx1)()(kxH]1[在一般情况下，不一定是二次函数，因而也不可能是的极值点。但是在点附近，函数和是近似的，所以可以用点作为下一次迭代，即得如果目标函数是正定二次函数，那么是个常矩阵，逼近式[1]是准确的。因此由点出发只要迭代一次既可以求的极小点。()fx(1)()()1()[()]()kkKkxxHxfxminx()fx(fx）)kx（()x(1)kx()fx()Hx()kx()fx[2]式与一维搜索公式比较，则有搜索方向，步长因子)()()()1(kkkksxx)()()(1)()(kTkkxfxHs1)(k]2[)()()1()(1)()()()(kkkkkksxxxfxHs牛顿法的迭代算式其中称为牛顿方向。)(kS3、迭代步骤一给定初始点，计算精度ε，令k=0；二计算点的梯度、及其逆矩阵。三构造搜索方向)0(x)(kx)()(kxf)()(kxH1)()(kxH)()()(1)()(kkkxfxHs四沿方向进行一维搜索，得迭代点五收敛判断：若，则为近似最优点，迭代停止，输出最优解和终止计算。若不满足，令k=k+1，转第二步继续迭代。)(ks)()()1(kkksxx)()1(kxf)1(kx)1(minkxx)()()1(minkxfxf)()1(kxf)1(minkxx)()1(kxf)()()1(minkxfxf)1(minkxx)()1(kxf例：用牛顿法求函数的极小值。60410)(21212221xxxxxxxf解：(1)取初始点(2)计算牛顿方向00)0(x41042102)()0(1221xxxxxxxf2112)(222122212212)0(xfxxfxxfxfxH211231)(1)0(xH68182431410211231)()()0(1)0()0(xfxHs故(3)极小值8)(min6868*100)0()0()0(1xfsxx4、优缺点数学分析表明，牛顿法具有很好的局部收敛性质，对二次函数来说，仅一步就达到优化点，但对一般函数来说，在一定条件下，当初始点的选取充分接近目标函数的极小点时，有很快的收敛速度，但若初始点选取离最小点比较远，就难保证收敛；牛顿法必须求一阶、二阶导数及求逆阵，这对较复杂的目标函数来说，是较困难的。5、修正牛顿法当目标函数为非二次函数时，目标函数在点展开所得的二次函数是该点附近的一种近似表达式，所求的极小点，当然也是近似的，需要继续迭代。但是当目标函数严重非线性时，用式进行迭代则不能保证一定收敛，即在迭代中可能会出现，所得到的下一点不如原来的好。这和初始点的选择是否恰当有很大的关系。)()()()1(kkxfxfkx]2[为了克服牛顿法的上述缺陷，可以通过在迭代中引入步长因子和一维搜索加以解决，即令式中，------一维搜索所得的最优步长因子。因而将称为牛顿方向。经过这种修改后的算法称为修正牛顿法。也称牛顿方向法or阻尼牛顿法。3)()]([)(1)()()()1(kkkkkxfxHxx)(k)()()(1)()(kkkxfxHs举例：用修正牛顿法求解下列无约束优化问题，已知解：因为所以22122210422)(.1.0,)1,1(xxxxxxfxT]13[]24][2121211[)()]([]2121211[)]([];24[)(]4222[)(];42422[)()0(1)0()0(1)0()0()0(2121xfxHsxHxfxHxxxxxf由修正牛顿法，得带入原函数对求导解得代入因为故迭代终止；所以最优解为1012)31(2)1(6)1(4)31(6)()()31(4)1)(31(2)1(2)31()(]131[]13[]11['22)1()0()0()1(xfsxx8)(]24[]131[]13[]11[)1()0()0()1(xfsxx1.00||)(||],00[)()1()1(xfxf8)(],24[min)1(minxfxx6、牛顿法的评价由于采用了目标函数的二阶导数信息，收敛速度比梯度法快。牛顿法迭代公式与一般迭代公式的区别在于，没有最优步长因子。这使得在接近最优点时，由于步长不能调节，可能会错过最优点，造成算法的稳定性欠佳，甚至造成不能收敛而导致计算失败。为了克服这一点，提出了修正牛顿法，它既保持了牛顿法收敛快的特性，有放宽了对初始点选择的要求，保证每次迭代的结果都是目标函数值下降。需要计算Hessian矩阵及其逆矩阵，内存占用、计算量大；此外二阶导数不存在，或者逆矩阵不存在的情况不能应用。知识回顾KnowledgeReview祝您成功！