最优化理论方法

1、牛顿法牛顿法作为求解非线性方程的一种经典的迭代方法，它的收敛速度快，有内在 函数可以直接使用。结合着 matlab可以对其进行应用，求解方程。牛顿迭代法(Newton' method)又称为牛顿-拉夫逊方法(Newton-Raphson method)，它是牛顿在17世纪提出的一种在实数域和复数域上近似求解方程的方法 ， 其基本思想是利用目标函数的二次 Taylor展开，并将其极小化。牛顿法使用函数f x的泰勒级数的前面几项来寻找方程 f x =0的根。牛顿法是求方程根的重要方法之一，其最大优点是在方程 f x =0的单根附近具有平方收敛，而且该法还 可以用来求方程的重根、复根，此时非

2、线性收敛，但是可通过一些方法变成线性 收敛。牛顿法的几何解释: 方程f x =0的根x*可解释为曲线y = f x与x轴的焦点的横坐标。如下图:设Xk是根x*的某个近似值，过曲线y二f x上横坐标为兀的点Pk引切线，并 将该切线与x轴的交点 的横坐标Xk 1作为x*的新的近似值。鉴于这种几何背景， 牛顿法亦称为切线法。2牛顿迭代公式:(1)最速下降法:以负梯度方向作为极小化算法的下降方向，也称为梯度法。设函数f x在Xk附近连续可微，且gkXk =0。由泰勒展开式：f X= f kXX kX ' f k X：Xk X (*)可知，若记为xXk =dk，则满足d：gk ：0的方向dk是下

3、降方向。当:-取定后， d：gk的值越小，即-d：gk的值越大，函数下降的越快。由 Cauchy-Schwartz不等 式：dT g| d| 0k，故当且仅当dk=-gk时，d：gk最小，从而称-gk是最速下降 方向。最速下降法的迭代格式为：兀-二 Xk-kg。(2)牛顿法：设f x是二次可微实函数，xk Rn，Hesse矩阵2 f xk正定。在兀附近用二次Taylor展开近似f，f 仇 +sq叫s )= f (Xk )丁 s"f 仏)丁 s+*sTN2f g )ss=x-xk， qf s)为f(x)的二次近似。将上式右边极小化，便得：Xk仃Xk - |2 f Xk f Xk，这就是

4、牛顿法的迭代公式。在这个公式里，步长因子:k =1。令Gk八2 fx,gk八fxk，贝U上式也可写成：1Xk i 二 Xk - Gk gk显然，牛顿法也可以看成在椭球范数|人下的最速下降法。事实上，对于f Xk S、f Xk - g：s，TSk是极小化冋题当采取12范gk s的解。该极小化问题依赖于所取的范数,S数时，s -gk，所得方法为最速下降法。当采用椭球范数G时,Sk = -Ggk，所得方法即为牛顿法。对于正定二次函数，牛顿法一步即可达到最优解。 而对于非二次函数，牛顿法并 不能保证有限次迭代求得最优解，但由于目标函数在极小点附近近似于二次函 数，故当初始点靠近极小点时，牛顿法的收敛速

5、度一般是快的。牛顿法收敛定理：设f C 2，兀充分靠近X*,，f x* = 0 ,如果12 f x*正定，且Hesse矩阵G x满足Lipschitz条件，即存在一：.0，使得对所有i,j，有：Gj(x)Gj (yy，其中Gij x是Hesse矩阵G x的i,j元素，则对一切k，牛顿迭代公式有意义，且所得序列兀？收敛到x*，并且具有二阶收敛速度。在实际求解中，当初始点远离最优解时，Hesse矩阵Gk不一定正定。牛顿方向不一定是下降方向，其收敛性不能保证。这说明恒取步长因子为1的牛顿法是 不合适的，应该在牛顿法中采用某种一维搜索来确定步长因子。但是应该强调， 仅当步长因子:收敛到1时，牛顿法才是

6、二阶收敛的。这时牛顿法的迭代公式 为：Xkkd其中:k是一维搜索产生的步长因子。带步长因子的牛顿法步1选取初始数据，取初始点xd，终止误差； 0，令k: = 0。 步2计算gk。若|gk| £芯，停止迭代，输出Xk，否则进行步3.步3解方程组构造牛顿方向，即解 Gkd二-gk，求出dk。步4进行一维搜索，求 亠使得f x k dk = mi nf x， a令Xk 1 二Xk dk,k : = k 1 转步 2牛顿法的计算步骤:步骤1准备选定初始近似值X），计算fo =f ( Xo )，fo=f (Xo )。步骤2迭代按公式：Xifo=xof0迭代一次，得新的近似值Xi，fi=f (X

7、i )，1 1f1 = f(X-1 )。步骤3控制女口果X1满足卩£坷，或t S，则终止迭代，以X1作为所求的根；否则转步骤4.此处，；1, ；2是允许误差，而: Xo ,当刈cC时；°F二,当卜存c时，其中C是取绝对误差或相对误差的控制常数，一般可取 c = 10步骤4 修改 如果迭代次数达到预先制定的次数 N，或者f；=0 ,则方法失败;否则以 心办"'代替Xo, fo, fo，转步骤2继续迭代。4牛顿法的改进在优化问题的计算中，牛顿迭代法是非线性方程求根中一种很实用的方法，它具有简单的迭代格式和较快的收敛速度，它二次收敛到单根，线性收敛到重根。 数值

8、计算中的经典牛顿法面临的主要问题是 Hesse矩阵Gk不正定，这时候二次模型不一定有极 小点，甚至没有平稳点。当Gk不定时，二次模型函数是无界的。Goldstein和Price（ 1967）提出当Gk非正定时，采用最速下降方向-gk。Goldfeld 等人（1966年）提出了一种修正方法，即使牛顿方向偏向最速下降方向 -gk。更 明确的说，就是将模型的Hesse矩阵Gk改变成Gk vkI，其中vk - 0 ,使得Gk vkI 正定。该算法的框架如下：给出初始点X。 Rn。第k步迭代为：(1 令 Gk =Gk vkI，其中：Vk = 0 ,如果Gk正定；Vk 0,否则。(2) 计算 Gk 的 C

9、holesky 分解，Gk 二 LkD：。(3) 解 Gk d = -gk 得 dk。(4) 令 Xk 1 二 Xk dk牛顿法的优点是收敛快，缺点一是每步迭代要计算f Xk及f' Xk ,计算量较大且有时f' Xk计算较困难，二是初始近似值 X0只在根X*附近才能保证收敛， 如X0给的不合适可能不收敛。为克服这两个缺点，通常可以下述两个方法：(1) 简化牛顿法，也称平行弦法。其迭代公式为，Xk 1 二Xk -Cf Xk ,C =0,1川|迭代函数Xjux-Cf X。(2) 牛顿下山法：牛顿法的收敛性依赖于初始值 X0的选取。如果X0偏离所求根 X*较远，则牛顿法可能发散。为防止迭代发散， 对迭代过程再附加一项要求，即 具有单调性：f (Xk+ p f (xj满足这项要求的算法称下山法。将牛顿法与下山法结合