牛顿法讲解学习

牛顿法如前面所提到的，最速下降法在最初几步迭代中函数值下降很快外，总的说来下降的并不快，且愈接近极值点下降的愈慢。因此，应寻找使目标函数下降更快的方法。牛顿法就是一种收敛很快的方法，其基本思路是利用二次曲线来逐点近似原目标函数，以二次曲线的极小值点来近似原目标函数的极小值点并逐渐逼近改点。一维目标函数f(x)在x(k)点逼近用的二次曲线(即泰勒二次多项式)为1申(x(k))二f(x(k))+f'(x(k))(x一x(k))+f"(X(k))(X一X(k))22此二次函数的极小点可由®"(x(k))二0求得。对于n维问题，n为目标函数f(X)在X(k)点逼近用的二次曲线为：1申(X(k))二f(x(k))+[Vf(X(k))].[X-X(k)]+ [X-X(k)]t,V2f(X(k)).[X-X(k)]2令式中的HessianV2f(X(k))二H(X(k))，则上式可改写为：申(X(k))=f(x(k))+[Vf(X(k))].[X-X(k)]+丄[X-X(k)]t.H(X(k)).[X-X(k)]2沁f(X)当V申(X)二0时可求得二次曲线9(X)的极值点，且当且仅当改点处的Hessian矩阵为正定时有极小值点。由上式得：V9(X)=Vf(X(k))+H(X(k))[X-X(k)]令V9(X)=0，则Vf(X(k))+H(X(k))[X-X(k)]=0若H(X(k))为可逆矩阵，将上式等号两边左乘[H(X(k))]-1，贝y得[H(X(k))]-1Vf(X(k))+1[X-X(k)]=0整理后得X=X(k)-[H(X(k))]-1Vf(X(k))当目标函数/(X)是二次函数时，牛顿法变得极为简单、有效，这时H(X(k))是一个

常数矩阵，式确表达式，而利用式X=X(k)-[H(X(k))]-1Vf(X(k))作一次迭代计算所得的X就是最优9(X(9(X(k))=f(x(k))+.[X-X(k)]+1[X-X(k)]t.H(X(k)).[X-X(k)]变成精点X*。在一般情况下/(X)不一定是二次函数，则不能一步就能求出极小值，即极小值点不在-[H(X(k))]-1Vf(X(k))方向上，但由于在X(k)点附近函数9(X)与/(X)是近似的，所以这个方向可以作为近似方向，可以用式X=X(k)H(X(k))-1Vf(X(k))求出点X作为一个逼近点X(k+i)。这时式X=X(k)-[H(X(k))]-1Vf(X(k))可改成牛顿法的一般迭代公式：X(k+1)=X(k)-[H(X(k))]-1Vf(X(k))式中-[H(X(k))]-1Vf(X(k))称为牛顿方向，通过这种迭代，逐次向极小值点X*逼近。例：试用牛顿法求目标函数f(X)=x2+25x2的极小值点12解：设取X(k)=[22卜，贝y则，Vf(X(k))=dx

f

则，Vf(X(k))=dx

f

dx2Id2fIdx2H(X(k))=V2f(X(k))=I 1Id2fIdxdx212x150x24100d2fIdxdxIdfIdx2I2X=X(k)X(k+1)=X(k)-IIH(X(k))II-1Vf(X(k))I2I1I500II4II0II2II100II02IIII100IIII0IIf(X(k+1))=0，I0I故X(k+1)=I0II为极小点050例：试用牛顿法求目标函数f(X)=x2+x2-xx-10x-4x+60的极小点。121212解：取X(k)=[0ob，贝yVf(Vf(X(k))=dx1

f

dx22x-x-10II-10I12=2x-x-4III-4I211— —1TOC\o"1-5"\h\zI df d2fI2-1-12I dx2 d2-1-12H(X伙))=V2f(X(k))=|i i2 :I d2fd2f IIdxdx dx2 I2 1 2 x=x(k)X(k+1)=X(k)H(X(k)) Vf(X(k))I0I1I21II-10II8III0I一3II12III-4III6II8IX（k+1）=即为最小点X*，只迭代一次就达到了X*。I6I由上述可见，牛顿法无一维探索而直接代入公式计算，当初始点选得合适且当/（X）为二次函数时收敛很快。即使目标函数/（X）不是二次函数，当初始点选得好时，例如满足初始误差IIX（0）-X*||<1时，也会很快收敛。但是这种方法对初始点的选择要求较高，如不满足||x（0）-X*||<1就不能保证有比较好的收敛性。初始点的选择有时甚至会影响到是否收敛。如果选择不当使初始点离较大点近时，计算结果就可能收敛于极大点。初始点选择不当有时也会导致收敛到鞍点或不收敛，基于这种原因，对古典的牛顿法要做些修改，于是便出现了修正牛顿法。其修正方法是：X（k）求X（k+1）时不是直接用原来的迭代公式，而且沿着X(k)点处的牛顿方向进行一维搜索，将该方向上的最优点最为X(k+1)。这样就会避免收敛于极大点或鞍点。于是式X(k+1)=X(k)-|H(X(k))_1Vf(X(k))改写成：X(k+1)=X(k)-a(k)IH(X(k))I-1Vf(X(k))令S(k)=-[H(X(k))I-1Vf(X(k))则X(k+1)=X(k)+a(k)S(k)式中的探索步长a（k）为minf(X(k)+aS(k))二f(X(k)+a(k)S(k))O>0这种修正牛顿法虽然计算工作量多一些，但是具有收敛快的优点，并且，即使初始点选择不当，用这种探索方法也会成功。牛顿法算法原理牛顿法是基于多元函数的泰勒展开而来的，它将-[H(X(k))『Vf(X(k))作为探索方向，因此它的迭代公式可直接写出来：X(k+1)=X(k)-[H(X(k))]-1Vf(X(k))牛顿法算法步骤给定初始点X(0)，及精度£>0，令k=0；若||Vf(X(k))|G,停止，极小点为x(k)，否则转步骤(3)；计算[V2f(X(k))]-1，令s(k)=-[H(X(k))]-1Vf(X(k))；令x(k+1)=x(k)+s(k)，k=k+1，转步骤(2)。3.牛顿法算法的MATLAB程序调用格式：[x,minf]=minNT(f,x0,var,eps)其中，f：目标函数x0：初始点var：自变量向量eps：精度x：目标函数取最小值时的自变量值minf：目标函数的最小值牛顿法的MATLAB程序代码如下：function[x,minf]=minNT(f,x0,var,eps)%目标函数：f;%初始点:x0;%自变量向量:var;%目标函数取最小值时的自变量值:x;%目标函数的最小值:minf;formatlong;ifnargin==3eps=1.0e-6;endtol=1;x0=transpose(x0);whiletol>epsgradf=jacobian(f,var); %梯度方向jacf=jacobian(gradf,var);%雅克比矩阵v=Funval(gradf,var,x0);tol=norm(v);pv=Funval(jacf,var,x0);p=-inv(pv)*transpose(v);x1=x0+p;x0=x1;endx=x1;minf=Funval(f,var,x);formatshort;修正牛顿法算法原理如果V2f(X(k))不正定，则牛顿法有可能不收敛，为了解决这个问题，引进修正牛顿法。此方法与牛顿法不同的是在于引进了搜索步长，而搜索步长的大小通过一维搜索算法确定。修正牛顿法算法步骤给定初始点x(o)，及精度£>0，令k=0；若||Vf(X(k))|G,停止，极小点为x(k)，否则转步骤(3)；计算[V2f(X(k))『，令s(k)=-[H(X(k))『Vf(X(k))；用一维搜索法求a，使得f(X(k)+a(k)S(k))二minf(X閃+aS(k)),令O>0X(k+1)=X(k)+a(k)S(k)，k=k+1，转步骤(2)。修正牛顿法算法的MATLAB程序调用格式：[x,minf]=minMNT(f,x0,var,eps)其中，f：目标函数x0：初始点var：自变量向量eps：精度x：目标函数取最小值时的自变量值minf：目标函数的最小值修正牛顿法的MATLAB程序代码如下：function[x,minf]=minMNT(f,x0,var,eps)%目标函数：f；%初始点:x0;%自变量向量:var;%目标函数取最小值时的自变量值:x;%目标函数的最小值:minf;formatlong;ifnargin==3eps=1.0e-6;endtol=1;x0=transpose(x0);symsl;whiletol>epsgradf=jacobian(f,var); %梯度方向jacf=jacobian(gradf,var); %