牛顿法讲解学习

牛顿法

如前面所提到的，最速下降法在最初几步迭代中函数值下降很快外，总的说来下降的并不快，且愈接近极值点下降的愈慢。因此，应寻找使目标函数下降更快的方法。牛顿法就是一种收敛很快的方法，其基本思路是利用二次曲线来逐点近似原目标函数，以二次曲线的极小值点来近似原目标函数的极小值点并逐渐逼近改点。

一维目标函数f(x) 在x(k)点逼近用的二次曲线（即泰勒二次多项式）为

(x(k))f(x(k))f(x(k))(xx(k))此二次函数的极小点可由(x(k)1f(x(k))(xx(k))2 2)0求得。

(k)对于n维问题，n为目标函数f(X)在X点逼近用的二次曲线为：

(k)(k)(k)T2(k)(k)(X(k))f(x(k))f(X).[XX][XX].f(X).[XX]

12令式中的Hessianf(X2(k))H(X(k))，则上式可改写为：

(k)(k)(k)T(k)(k)(X(k))f(x(k))f(X).[XX][XX].H(X).[XX]12

f(X)当(X)0时可求得二次曲线(X)的极值点，且当且仅当改点处的Hessian矩阵为正定时有极小值点。

由上式得：

(X)f(X(k))H(X(k))[XX(k)]

令(X)0，则f(X若H(X(k)(k))H(X(k))[XX(k)]0

1(k))为可逆矩阵，将上式等号两边左乘H(X)，则得

(k)(k)(k)H(X)f(X)I[XX]0 n1整理后得

XX(k)(k)(k)H(X)f(X)

(k)1当目标函数f(X)是二次函数时，牛顿法变得极为简单、有效，这时H(X常数矩阵，式

)是一个

(k)(k)(k)T(k)(k)(X(k))f(x(k))f(X).[XX][XX].H(X).[XX]12变成精

f(X)精品文档

精品文档

(k)(k)(k)H(X)f(X)作一次迭代计算所得的X就是最优1确表达式，而利用式XX点X*。在一般情况下f(X)不一定是二次函数，则不能一步就能求出极小值，即极小值点不在H(X(k)(k)(k)方向上，但由于在点附近函数(X)与f(X)是近似的，)f(X)X(k)(k)(k)H(X)f(X)求出点X作111所以这个方向可以作为近似方向，可以用式XX为一个逼近点X公式：

(k1)。这时式XX(k)(k)(k)H(X)f(X)可改成牛顿法的一般迭代

(k)(k)X(k1)X(k)H(X)f(X) 1式中H(X(k)(k)*称为牛顿方向，通过这种迭代，逐次向极小值点逼近。 )f(X)X122例：试用牛顿法求目标函数f(X)x125x2的极小值点

解：设取X(k)22，则

Tfx2x41(k)1 f(X)f50x2100x22fx21H(X(k))2f(X(k))2fx2x1则，

2fx1x220 2f0502x2XX(k)1(k)(k)X(k1)X(k)H(X)f(X)2150040

02100021000f(X(k1))0，故X(k1)为极小点

022例：试用牛顿法求目标函数f(X)x1x2x1x210x14x260的极小点。

解：取X(k)00，则

T精品文档

精品文档

fx2xx10101(k)12f(X) f2x2x144x22fx21(k)2(k)H(X)f(X)2fx2x12fx1x22112 2f2x2XX(k)1(k)(k)X(k1)X(k)H(X)f(X)0121108

4601238X(k1)即为最小点X*，只迭代一次就达到了X*。

6由上述可见，牛顿法无一维探索而直接代入公式计算，当初始点选得合适且当f(X)为二次函数时收敛很快。即使目标函数f(X)不是二次函数，当初始点选得好时，例如满足初始误差X(0)X*1时，也会很快收敛。但是这种方法对初始点的选择要求较高，如不满足X(0)X*1就不能保证有比较好的收敛性。初始点的选择有时甚至会影响到是否收敛。如果选择不当使初始点离较大点近时，计算结果就可能收敛于极大点。初始点选择不当有时也会导致收敛到鞍点或不收敛，基于这种原因，对古典的牛顿法要做些修改，于是便出现了修正牛顿法。其修正方法是：X(k)求X(k1)时不是直接用原来的迭代公式，而且沿着

X(k)点处的牛顿方向进行一维搜索，将该方向上的最优点最为X(k1)。这样就会避免收敛

于极大点或鞍点。于是式X(k1)(k)(k)X(k)H(X)f(X)改写成： 11(k)(k)X(k1)X(k)(k)H(X)f(X) 令

(k)(k)S(k)H(X)f(X) 1则

X(k1)X(k)(k)S(k)

式中的探索步长(k)为

精品文档

精品文档

minf(X(k)S(k))f(X(k)(k)S(k))

0这种修正牛顿法虽然计算工作量多一些，但是具有收敛快的优点，并且，即使初始点选择不当，用这种探索方法也会成功。

1. 牛顿法算法原理

牛顿法是基于多元函数的泰勒展开而来的，它将H(X向，因此它的迭代公式可直接写出来：

1(k)(k))f(X)作为探索方1X(k1)X(k)(k)(k)H(X)f(X) 2. 牛顿法算法步骤

（1） 给定初始点x(0)，及精度0，令k0；

（2） 若f(X(k))，停止，极小点为x(k)，否则转步骤（3）； （3） 计算f(X2(k)(k)(k)(k)，令)sH(X)f(X)； 11（4） 令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; format long; if nargin==3 eps=1.0e-6; end 精品文档

精品文档

tol=1;

x0=transpose(x0); while tol>eps

gradf=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; end x=x1;

minf=Funval(f,var,x); format short;

4. 修正牛顿法算法原理

如果f(X2(k))不正定，则牛顿法有可能不收敛，为了解决这个问题，引进修正牛顿

法。此方法与牛顿法不同的是在于引进了搜索步长，而搜索步长的大小通过一维搜索算法确定。

5. 修正牛顿法算法步骤

（1） 给定初始点x(0)，及精度0，令k0；

（2） 若f(X(k))，停止，极小点为x(k)，否则转步骤（3）；

2(k)(k)(k)(k)（3） 计算f(X)，令sH(X)f(X)；

11(k)(k)(k)(k)(k)（4） 用一维搜索法求，使得f(XS)minf(XS)，令

0X(k1)X(k)(k)S(k)，kk1，转步骤（2）。

6. 修正牛顿法算法的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; format long; if nargin==3 eps=1.0e-6; end tol=1;

x0=transpose(x0); syms l;

while tol>eps

gradf=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*p

yf=Funval(f,var,y); [a,b]=minJT(yf,0,0.1); xm=minHJ(yf,a,b); x1=x0+xm*p; x0=x1; end x=x1;

minf=Funval(f,var,x); format short;

精品文档

%梯度方向 %雅克比矩阵