《牛顿法讲解学习》由会员分享，可在线阅读，更多相关《牛顿法讲解学习（6页珍藏版）》请在金锄头文库上搜索。
1、牛顿法如前面所提到的，最速下降法在最初几步迭代中函数值下降很快外，总的说来下降的并 不快，且愈接近极值点下降的愈慢。因此，应寻找使目标函数下降更快的方法。牛顿法就是 一种收敛很快的方法，其基本思路是利用二次曲线来逐点近似原目标函数，以二次曲线的极 小值点来近似原目标函数的极小值点并逐渐逼近改点。一维目标函数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)点
2、逼近用的二次曲线为：1申(X(k)二 f (x(k) + Vf (X(k).X - X(k) +X -X(k)t,V2f (X(k).X -X(k)2令式中的Hessian V2f (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)
3、+ H(X(k)X - X(k) = 0若H (X (k)为可逆矩阵，将上式等号两边左乘H (X (k) -1，贝y得H(X(k)-1 Vf (X(k) +1 X - X(k) = 0整理后得X = X (k)- H (X (k) -1 Vf (X (k)当目标函数/ (X)是二次函数时，牛顿法变得极为简单、有效，这时H (X (k)是一个常数矩阵，式 确表达式，而利用式X = X(k)-H(X(k)-1 Vf (X(k)作一次迭代计算所得的X就是最优9 ( X (k) = f ( x (k) +.X -X(k) +1X -X(k)t.H(X(k).X -X(k)变成精点X*。在一般情况下/(
4、X)不一定是二次函数，则不能一步就能求出极小值，即极小值点 不在-H(X(k)-1 Vf (X(k)方向上，但由于在X(k)点附近函数9 (X)与/(X)是近似的， 所以这个方向可以作为近似方向，可以用式X = X(k) H(X(k) -1 Vf (X(k)求出点X作 为一个逼近点X(k+i)。这时式X = X(k) -H(X(k)-1 Vf (X(k)可改成牛顿法的一般迭代 公式：X (k+1)= X (k) - H(X (k)-1 Vf (X (k)式中-H (X(k)-1 Vf (X (k)称为牛顿方向，通过这种迭代，逐次向极小值点X *逼近。例：试用牛顿法求目标函数f (X) = x2
5、 + 25x2的极小值点12解：设取X (k) =2 2卜，贝y则，Vf(X(k)=dx1 fdx2I d 2 fI dx 2H (X (k) = V 2 f (X (k) = I1I d2 fI dx dx212 x150 x24100d 2 f I dx dx I df I dx 2 I2 X =X(k)X(k+1) = X(k) -IIH(X(k)II-1Vf (X(k)I2I1I500II4 II0II2II100II 02IIII100IIII0IIf (X(k+1) =0，I0I故 X (k+1) = I0II 为极小点050例：试用牛顿法求目标函数 f(X)= x2+x2-xx
6、-10x -4x +60的极小点。1 2 1 2 1 2解：取 X(k) =0 ob，贝yVf (X( k)=dx1fdx22 x - x - 10II-10I12=2 x - x - 4 III-4 I2111Idfd2f I2-1-12Idx 2dx dxIH (X 伙)=V 2 f (X( k) = | ii 2:Id2 f d 2fII dx dxdx 2I212x=x(k)X( k+1)= X( k)H (X( k)Vf (X( k)I0I1I21II-10II8III0I一3II12III-4 III6II8IX（k+1）= 即为最小点X*，只迭代一次就达到了 X*。I6I由上述可
7、见，牛顿法无一维探索而直接代入公式计算，当初始点选得合适且当/（X）为 二次函数时收敛很快。即使目标函数/（X）不是二次函数，当初始点选得好时，例如满足初 始误差IIX（0） -X*| 1时，也会很快收敛。但是这种方法对初始点的选择要求较高，如不满 足|x（0）-X*|0这种修正牛顿法虽然计算工作量多一些，但是具有收敛快的优点，并且，即使初始点选 择不当，用这种探索方法也会成功。1. 牛顿法算法原理牛顿法是基于多元函数的泰勒展开而来的，它将-H(X(k)Vf (X(k)作为探索方向，因此它的迭代公式可直接写出来：X(k+1) = X(k) - H(X(k)-1 Vf (X(k)2. 牛顿法算法
8、步骤(1) 给定初始点X(0)，及精度 0，令k = 0 ；(2) 若|Vf (X(k)| G ,停止，极小点为x(k)，否则转步骤(3)；(3) 计算V 2f (X (k) -1，令 s (k) =- H (X (k) -1 Vf (X (k)；(4) 令 x(k+1) = x(k) + s(k)， k = k + 1，转步骤(2)。3.牛顿法算法的MATLAB程序调用格式：x,min f = min NT(f, x0, var, eps)其中， f ：目标函数x0 ：初始点var ：自变量向量eps ：精度x ：目标函数取最小值时的自变量值min f ：目标函数的最小值牛顿法的MATLAB
9、程序代码如下：function x,minf=minNT(f,x0,var,eps)%目标函数：f;%初始点:x0;%自变量向量:var;%目标函数取最小值时的自变量值:x;%目标函数的最小值:minf;format long;if nargin=3eps=1.0e-6;endtol=1;x0=transpose(x0);while tolepsgradf=jacobian(f,var);%梯度方向jacf=jacobian(gradf,var); %雅克比矩阵 v=Funval(gradf,var,x0);tol=norm(v);pv=Funval(jacf,var,x0); p=-inv(
10、pv)*transpose(v);x1=x0+p;x0=x1;endx=x1;minf=Funval(f,var,x);format short;4. 修正牛顿法算法原理如果V 2 f ( X (k)不正定，则牛顿法有可能不收敛，为了解决这个问题，引进修正牛顿法。此方法与牛顿法不同的是在于引进了搜索步长，而搜索步长的大小通过一维搜索算法确 定。5. 修正牛顿法算法步骤(1) 给定初始点x(o)，及精度 0，令k = 0 ；(2) 若|Vf (X(k)| G ,停止，极小点为x(k)，否则转步骤(3)；(3) 计算V2f (X(k)，令s(k)=-H(X(k)Vf (X(k)；(4) 用一维搜索
11、法求 a ，使得 f(X(k) +a(k)S(k)二minf(X閃 +aS(k),令O0X(k+1) = X(k) +a (k)S(k)， k = k +1，转步骤(2)。6. 修正牛顿法算法的MATLAB程序调用格式：x,min f = min MNT (f, x0, var, eps)其中， f ：目标函数x0 ：初始点var ：自变量向量eps ：精度x ：目标函数取最小值时的自变量值min f ：目标函数的最小值修正牛顿法的MATLAB程序代码如下：function x,minf=minMNT(f,x0,var,eps)%目标函数：f；%初始点:x0;%自变量向量:var;%目标函数取
12、最小值时的自变量值:x;%目标函数的最小值:minf;format long;if nargin=3eps=1.0e-6;endtol=1;x0=transpose(x0);syms l;while tolepsgradf=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);y=x0+l*pyf=Funval(f,var,y); a,b=minJT(yf,0,0.1);xm=minHJ(yf,a,b);x1=x0+xm*p; x0=x1;endx=x1;minf=Funval(f,var,x);format short;
