最优化理论与方法牛顿法.doc

牛顿法简介摘要：牛顿法作为求解非线性方程的一种经典的迭代方法，它的收敛速度快，有内在函数可以直接使用。结合着matlab可以对其进行应用，求解方程。关键词：牛顿法，Goldfeld等人修正牛顿法, matlab实现1 介绍： 迭代法也称辗转法，是一种不断用变量的旧值递推新值的过程，跟迭代法相对应的是直接法，即一次性解决问题。但多数方程不存在求根公式，因此求解根非常困难，甚至不可能，从而寻找方程的近似根就显得特别重要。 迭代算法是用计算机解决问题的一种基本方法。它利用计算机运算速度快、适合做重复性操作的特点，让计算机对一组指令（或一定步骤）进行重复执行，在每次执行这组指令（或这些步骤）时，都从变量的原值推出它的一个新值。 利用迭代算法解决问题，需要做好以下3个方面的工作： 1，确定迭代变量。在可以用迭代算法解决的问题中，至少存在一个直接或间接地不断由旧值递推出新值的变量，这个变量就是迭代变量。 2，建立迭代关系式。所谓迭代关系式，是指如何从变量的前一个值推出下一个值的公式（或关系）。迭代关系式的建立是解决迭代问题的关键，通常可以使用递推或倒推的方法来完成。 3，对迭代过程进行控制。在什么时候结束迭代过程？这是编写迭代程序必须考虑的问题。不能让迭代过程无休止地重复下去。迭代过程的控制通常可分为两种情况：一种是所需的迭代次数是个确定的值，可以计算出来；另一种是所需的迭代次数无法确定。对于前一种情况，可以构建一个固定次数的循环来实现对迭代过程的控制；对于后一种情况，需要进一步分析出用来结束迭代过程的条件。 牛顿迭代法（Newtons method）又称为牛顿-拉夫逊方法（Newton-Raphson method）,它是牛顿在17世纪提出的一种在实数域和复数域上近似求解方程的方法,其基本思想是利用目标函数的二次Taylor展开，并将其极小化。牛顿法使用函数的泰勒级数的前面几项来寻找方程的根。牛顿法是求方程根的重要方法之一，其最大优点是在方程的单根附近具有平方收敛，而且该法还可以用来求方程的重根、复根，此时非线性收敛，但是可通过一些方法变成线性收敛。 牛顿法的几何解释：方程的根可解释为曲线与轴的焦点的横坐标。如下图： 设是根的某个近似值，过曲线上横坐标为的点引切线，并将该切线与轴的交点 的横坐标作为的新的近似值。鉴于这种几何背景，牛顿法亦称为切线法。2 牛顿迭代公式： （1）最速下降法： 以负梯度方向作为极小化算法的下降方向，也称为梯度法。 设函数在附近连续可微，且。由泰勒展开式： （*）可知，若记为，则满足的方向是下降方向。当取定后，的值越小，即的值越大，函数下降的越快。由Cauchy-Schwartz不等式： ，故当且仅当时，最小，从而称是最速下降方向。 最速下降法的迭代格式为： 。（2）牛顿法： 设是二次可微实函数，Hesse矩阵正定。在附近用二次Taylor展开近似，为的二次近似。将上式右边极小化，便得：， 这就是牛顿法的迭代公式。在这个公式里，步长因子。令，则上式也可写成：显然，牛顿法也可以看成在椭球范数下的最速下降法。 事实上，对于，是极小化问题 的解。该极小化问题依赖于所取的范数，当采取范数时，所得方法为最速下降法。当采用椭球范数时，所得方法即为牛顿法。对于正定二次函数，牛顿法一步即可达到最优解。而对于非二次函数，牛顿法并不能保证有限次迭代求得最优解，但由于目标函数在极小点附近近似于二次函数，故当初始点靠近极小点时，牛顿法的收敛速度一般是快的。牛顿法收敛定理： 设，充分靠近，如果正定，且Hesse矩阵满足Lipschitz条件，即存在，使得对所有i,j，有：，其中是Hesse矩阵的元素，则对一切k，牛顿迭代公式有意义，且所得序列收敛到，并且具有二阶收敛速度。在实际求解中，当初始点远离最优解时，Hesse矩阵不一定正定。牛顿方向不一定是下降方向，其收敛性不能保证。这说明恒取步长因子为1的牛顿法是不合适的，应该在牛顿法中采用某种一维搜索来确定步长因子。但是应该强调，仅当步长因子收敛到1时，牛顿法才是二阶收敛的。这时牛顿法的迭代公式为：，其中是一维搜索产生的步长因子。带步长因子的牛顿法步1 选取初始数据，取初始点，终止误差，令。步2 计算。若，停止迭代，输出，否则进行步3.步3 解方程组构造牛顿方向，即解，求出。步4 进行一维搜索，求使得 ， 令 转步23 事例 牛顿法是非先线性方程求根中一种很实用的方法，它具有简单的迭代格式和较快的收敛速度，它二次收敛到单根，线性收敛到重根。数值计算中的经典迭代算法（SN）： 使用牛顿法求解。 这里牛顿公式为，取迭代初值，迭代结果列于下表：本例所给方程实际上等价于。若使用不动点迭代到同一精度要迭代17次，可见牛顿法的收敛速度很快。 牛顿法的计算步骤：步骤1 准备 选定初始近似值，计算，。步骤2 迭代 按公式： 迭代一次，得新的近似值，。步骤3 控制 如果满足，或，则终止迭代，以作为所求的根；否则转步骤4. 此处，是允许误差，而：其中C是取绝对误差或相对误差的控制常数，一般可取。步骤4 修改 如果迭代次数达到预先制定的次数N，或者，则方法失败；否则以代替，转步骤2继续迭代。4 牛顿法的改进在优化问题的计算中，牛顿迭代法是非线性方程求根中一种很实用的方法，它具有简单的迭代格式和较快的收敛速度，它二次收敛到单根，线性收敛到重根。数值计算中的经典牛顿法面临的主要问题是Hesse矩阵不正定，这时候二次模型不一定有极小点，甚至没有平稳点。当不定时，二次模型函数是无界的。 Goldstein和Price（1967）提出当非正定时，采用最速下降方向。Goldfeld等人（1966年）提出了一种修正方法，即使牛顿方向偏向最速下降方向。更明确的说，就是将模型的Hesse矩阵改变成，其中，使得正定。 该算法的框架如下：给出初始点。第k步迭代为：（1）令，其中：，如果正定；否则。（2）计算的Cholesky分解，。（3）解得。（4）令 牛顿法的优点是收敛快，缺点一是每步迭代要计算，计算量较大且有时计算较困难，二是初始近似值只在根附近才能保证收敛，如给的不合适可能不收敛。 为克服这两个缺点，通常可以下述两个方法：（1）简化牛顿法，也称平行弦法。其迭代公式为， 迭代函数。（2）牛顿下山法：牛顿法的收敛性依赖于初始值的选取。如果偏离所求根较远，则牛顿法可能发散。为防止迭代发散，对迭代过程再附加一项要求，即具有单调性： 满足这项要求的算法称下山法。将牛顿法与下山法结合起来使用，即在下山法保证函数值稳定下降的前提下，用牛顿法加快收敛速度。 公式如下：与前一步的近似值，适当加权平均作为新的改进值 ，其中称为下山因子，上式即为： ，称为牛顿下山法5.MTALAB牛顿法实现：MTALAB程序：R=2 1; 1 3;P=6;4;W=3;2;u=0.1;ww=zeros(2,201);ww(:,1)=W;for i=1:200 deta=R*W-P; W=W-u*eye(2,2)/R*deta; ww(:,i+1)=W;endW0,W1 = meshgrid(0:0.05:4,-1:0.05:2);Z=2*W0.2+2*W0.*W1+3*W1.2-12*W0-8*W1+36;X,Y = contour(W0,W1,Z,20,LineWidth,2);xlabel(W0);ylabel(W1);zlabel(Z);clabel(X,Y,manual); hold on;plot(ww(1,:),ww(2,:),LineWidth,2);参考文献：1，袁亚湘，孙文瑜. 最优化理论与方法M.北京：科学出版社 2，张光澄. 非线性最优化计算方法M.北京：高等教育出版社，2005.3，邓乃扬，无约束最优化计算方法，科学出版社，北京，1982.4，胡毓达，非线性规划，高等教育出版社，北京，1990.5，席少霖，赵风治，最优化计算方法，上海科学技术出版社，上海，1983.6，EWCheney and A.A.Goldstein, “Newtons method for convex program-ming and Chebyshev approximation”, Numerische Mathematik, 11 (1959),253-268.7, R. Bryd and J. Nocedal, “An analysis of reduced Hessian methods for constrain