?主页
?专栏作家
?量化基础理论?软件使用经验?量化软件
?资源导航
?资料下载
?量化论坛
?创建新帐号?重设密码
首页
拟牛顿法及相关讨论
星期三, 2009-06-17 00:24 —satchel1979
使用导数的最优化算法中，拟牛顿法是目前为止最为行之有效的一种算法，具有收敛速度快、算法稳定性强、编写程序容易等优点。在现今的大型计算程序中有着广泛的应用。本文试图介绍拟牛顿法的基础理论和若干进展。
牛顿法(Newton Method)
牛顿法的基本思想是在极小点附近通过对目标函数做二阶Taylor展开，进而找到的极小点
的估计值[1]。一维情况下，也即令函数为
则其导数满足
因此
(1)
将作为极小点的一个进一步的估计值。重复上述过程，可以产生一系列的极小点估值集合
。一定条件下，这个极小点序列收敛于的极值点。
将上述讨论扩展到维空间，类似的，对于维函数有
其中和分别是目标函数的的一阶和二阶导数，表现为维向量和矩阵，而后
者又称为目标函数在处的Hesse矩阵。设可逆，则可得与方程(1)类似的迭代公式：
(2)
这就是原始牛顿法的迭代公式。
原始牛顿法虽然具有二次终止性（即用于二次凸函数时，经有限次迭代必达极小点），但是要求初始点需要尽量靠近极小点，否则有可能不收敛。因此人们又提出了阻尼牛顿法[1]。这种方法在算法形式上等同于所有流行的优化方法，即确定搜索方向，再沿此方向进行一维搜索，找出该方向上的极小点，然后在该点处重新确定搜索方向，重复上述过程，直至函数梯度小于预设判据。具体步骤列为算法1。
算法1：
(1) 给定初始点，设定收敛判据，.
(2) 计算和.
(3) 若< ，则停止迭代，否则确定搜索方向.
(4) 从出发，沿做一维搜索，
令.
(5) 设，转步骤(2).
在一定程度上，阻尼牛顿法具有更强的稳定性。
拟牛顿法(Quasi-Newton Method)
如同上一节指出，牛顿法虽然收敛速度快，但是计算过程中需要计算目标函数的二阶偏导数，难度较大。更为复杂的是目标函数的Hesse矩阵无法保持正定，从而令牛顿法失效。为了解决这两个问题，人们提出了拟牛顿法。这个方法的基本思想是不用二阶偏导数而构造出可以近似Hesse矩阵的逆的正定对称阵，从而在"拟牛顿"的条件下优化目标函数。构造方法的不同决定了不同的拟牛顿法。
首先分析如何构造矩阵可以近似Hesse矩阵的逆：
设第k次迭代之后得到点，将目标函数在处展成Taylor级数，取二阶近似，得到
因此
令，则
(3)
记
同时设Hesse矩阵可逆，则方程(3)可以表示为
(4)
因此，只需计算目标函数的一阶导数，就可以依据方程(4)估计该处的Hesse矩阵的逆。也即，为了
用不包含二阶导数的矩阵近似牛顿法中的Hesse矩阵的逆矩阵，必须满足
(5)
方程(5)也称为拟牛顿条件。不加证明的，下面给出两个最常用的构造公式
DFP公式
设初始的矩阵为单位矩阵，然后通过修正给出，即
DFP算法中定义校正矩阵为
因此
(6)
可以验证，这样产生的对于二次凸函数而言可以保证正定，且满足拟牛顿条件。
BFGS公式
BFGS公式有时也称为DFP公式的对偶公式。这是因为其推导过程与方程(6)完全一样，只需要用矩
阵取代，同时将和互换，最后可以得到
(7)
这个公式要优于DFP公式，因此目前得到了最为广泛的应用。
利用方程(6)或(7)的拟牛顿法计算步骤列为算法2。
算法2：
(1) 给定初始点，设定收敛判据，.
(2) 设，计算出目标函数在处的梯度.
(3) 确定搜索方向：
.
(4) 从出发，沿做一维搜索，满足
令.
(5) 若，则停止迭代，得到最优解，否则进行步骤(6).
(6) 若，则令，回到步骤(2)，否则进行步骤(7).
(7) 令，，，利用方程(6)或(7)计算，设，回到步骤(3)。
限域拟牛顿法(Limited Storage Quasi-Newton Method)
算法2的步骤(3)中，为了确定第次搜索方向，需要知道对称正定矩阵，因此对于维的问题，
存储空间至少是，对于大型计算而言，这显然是一个极大的缺点。作为比较，共轭梯度
法只需要存储3个维向量。为了解决这个问题，Nocedal首次提出了基于BFGS公式的限域拟牛顿法(L-BFGS)[2]。
L-BFGS的基本思想是存储有限次数（如次）的更新矩阵，如果> 的话就舍弃次以前
的，也即L-BFGS的记忆只有次。如果，则L- BFGS等价于标准的BFGS公式。
首先将方程(7)写为乘法形式：
(8)
其中，是的矩阵。乘法形式下"舍弃"等价于置，。容易得出，给定后，BFGS的矩阵更新可以写为
若，则
(9)
若> ，则
(10)
方程(9)和(10)称为狭义BFGS矩阵(special BFGS matrices)。仔细分析这两个方程以及和的
定义，可以发现L-BFGS方法中构造只需要保留个维向量：个、个以及（对角阵）。
快速计算
L-BFGS算法中确定搜索方向需要计算，下列算法可以高效地完成计算任务：
算法3:
IF Then
= 0; =
ELSE
= ; =
ENDIF
;
DO = (-1),0,-1
;
;
储存;
;
ENDDO
;
DO = 0, (-1)
;
;
;
ENDDO
完整的程序包可从下列网址下载：
https://www.doczj.com/doc/f911711340.html,/~nocedal/software.html
针对二次非凸函数的若干变形
对于二次凸函数，BFGS算法具有良好的全局收敛性。但是对于二次非凸函数，也即目标函数Hesse 矩阵非正定的情况，无法保证按照BFGS算法构造的拟牛顿方向必为下降方向。为了推广BFGS公式的应用范围，很多工作提出了对BFGS公式稍作修改或变形的办法。下面举两个例子。
Li-Fukushima方法[3]
Li和Fukushima提出新的构造矩阵的方法：
(11)
其中
的定义见算法2中步骤(7)，而
除此之外，算法2中步骤(3)的一维搜索采用如下方式：
给定两个参数和，找出最小的非负整数j，满足
取，步长。
Xiao-Wei-Wang方法[4]
Xiao、Wei和Wang提出了计入目标函数值的另一种的构造方法：设，其中
的构造方法与方程(7)和(11)形式相同：
(12)
相应的
而一维搜索则采用弱Wolfe-Powell准则：
给定两个参数和，找出步长，满足
(13)
(14)
如果= 满足方程(13)、(14)，则取= 。
可以看出，这两种方法只是改变了的定义方式，其他则与标准的BFGS方法完全一样。因此将二者推广到限域形式是非常直接的，这里不再给出算法。对于二次非凸函数的拟牛顿方法还在进一步发展当中，上述的两个例子并不一定是最佳算法。
一维搜索
使用导数的优化算法都涉及到沿优化方向的一维搜索。事实上一维搜索算法本身就一个非常重要的课题，分为精确一维搜索以及非精确一维搜索。标准的拟牛顿法或L-BFGS均采用精确一维搜索。与前者相比，非精确一维搜索虽然牺牲了部分精度，但是效率更高，调用函数的次数更少。因此
Li-Fukushima方法和Xiao-Wei-Wang方法中均采用了这类算法。不加证明的，本节分别给出两类范畴中各自的一个应用最为广泛的例子，分别是二点三次插值方法和Wolfe-Powell准则。
二点三次插值方法
在精确一维搜索各种算法中，这种方法得到的评价最高。其基本思想是选取两个初始点和，满足
< ; < ; > 。这样的初始条件保证了在区间中存在极小点。利用这
两点处的函数值、（记为、）和导数值、（记为、）构造一个三
次多项式，使得在和处与目标函数有相同的函数值和导数值，则设
，那么通过4个边界条件可以完全确定、、、4个参数。之后找出的零点，作为极小点的一个进一步的估计。可以证明，由出发，最佳估计值的计算公式为
(15)
为了避免每次都要求解4维线性方程组的麻烦，整个搜索过程可以采用算法4：
算法4：
(1) 给定初始点和，满足< ，计算函数值、和导数值、，并且< ，> ，
给定允许误差。
(2) 计算如下方程，得到最佳估计值：
(16)
(17)
(3) 若，则停止计算，得到点；否则进行步骤(4)。
(4) 计算和。若，则停止计算，得到点,
若< ，则令，转步骤(2)；
若> ，则令，转步骤(2)。
利用三次函数插值，方程(16)、(17)并不是唯一的方法，也可以利用下式计算、、三个参数：
(18)
然后利用(15)式寻找最佳点[5]。此外，即使< ，一般而言也可以用(15)式外推寻找（参见[5]）。
Wolfe-Powell准则
不等式(13)、(14)给出了这种非精确一维搜索算法。如果我们将不等式(14)用下式替换：
(19)
也即
则不等式(13)、(19)称为强Wolfe-Powell准则。其重要性在于当时，该方法过渡为精确一维搜索算法[6]。算法如下[5]
算法5：
(1) 给定两个参数和，为初始点（相应于），为猜想点（可设为
1）。计算两点处的函数值、和导数值、。给定最大循环次数，设；
(2) 若和违反不等式(13)或者不等式(19)的右半段，则缩小搜索范围的上限，否则
转步骤(5)；
(3) 若> ，利用二次插值方法寻找最佳点：
设，计算和；设，若转步骤(2)，否则转步骤(5);
若，转步骤(4)；
(4) 利用式(16)、(17)（或者式(15)、(18)）寻找最佳点。令，计算和；设
= ，若，转步骤(2)，否则转步骤(5)；
(5) 若满足不等式(19)的左半段，则停止计算，得到最佳点；否则转步骤(6)；
(6) 利用式(16)、(17)（或者式(15)、(18)）寻找最佳点，并计算以及；设，
若转步骤(2)，否则转步骤(7)；
(7) 停止计算得到目前最佳估计值。
需要补充说明的是步骤(4)可以有不同的估算方法，例如
(20)
此外，点处的导数值，因为在一维搜索中，相当于待求步长。在大多数情况下，= 以及= 可以取得很好的效果。Wolfe-Powell准则的几何意义可以参考文献[5][6]。
拟牛顿法（变尺度法）DFP算法的c/c++源码 #include "iostream.h" #include "math.h" void comput_grad(double (*pf)(double *x), int n, double *point, double *grad); //计算梯度 double line_search1(double (*pf)(double *x), int n, double *start, double *direction); //0.618法线搜索 double line_search(double (*pf)(double *x), int n, double *start, double *direction); //解析法线搜索 double DFP(double (*pf)(double *x), int n, double *min_point); //无约束变尺度法 //梯度计算模块 //参数：指向目标函数的指针，变量个数，求梯度的点，结果 void comput_grad(double (*pf)(double *x), int n, double *point, double *grad) { double h=1E-3; int i; double *temp; temp = new double[n]; for(i=1;i<=n;i++) { temp[i-1]=point[i-1]; } for(i=1;i<=n;i++) { temp[i-1]+=0.5*h; grad[i-1]=4*pf(temp)/(3*h); temp[i-1]-=h; grad[i-1]-=4*pf(temp)/(3*h); temp[i-1]+=(3*h/2); grad[i-1]-=(pf(temp)/(6*h)); temp[i-1]-=(2*h); grad[i-1]+=(pf(temp)/(6*h)); temp[i-1]=point[i-1]; } delete[] temp; }
几种拟牛顿算法综述 摘要: 拟牛顿方法是求解无约束优化问题有效而著名的算法。在拟牛顿法中，有根据矫正公式的不同分为几类方法。本文主要针对SR1、SR1的一种修改、BFGS、MBFGS、非单调的CBFGS、LBFGS这几种矫正公式产生方法进行理论阐述，包括其收敛性，收敛速度的证明并检验其在正定二次问题上的等价性。最后通过C#编程语言检验上述方法在收敛速度上的差异性。 关键字：拟牛顿法、矫正公式、收敛性、非线性方程 引言： 考虑无约束问优化题minf(x)（0.1）f是连续可微的函数。牛顿法利用 Newton方法最突出的优点是其收敛速度快，凡是目标函数的Hessian矩阵 较简单的问题都可以采用Newton方法,1- 。对于那些Hessian矩阵复杂的问题而 言，求解Hessian矩阵无疑是一项艰巨的工程，这是很多学者选择采用拟牛顿的方法来解决现实中较复杂的问题的原因所在。拟牛顿法和Newton法的主要区别于求解迭代方向。拟牛顿法的主要思路是通过构造一个矩阵序列*H（k）+去逼近 原问题迭代方向中的Hessian矩阵*G(k)?1+，这很好的避免了复杂矩阵求逆的问题。在算法上很好的降低了计算量，从而提高计算速度。为了寻找与G有某种近似的，我们需要来考察的各种相关关系。为此目的，我们将f(x)的梯度在处作Taylor 展开， (δ)()δ(x) f(x) 当δ充分小时，可得到近似关 δ()δ(δ)() 或δγ，γ 1 1(δ)（0.2） 关系式（1）对二次函数f(x)恒成立，但对于不一定成立。现在我们研究与寻找，使它满足关系式（1）。为讨论与计算上的方便，当得到 1 δ时，δ，γ已知，我们求得 1，它满足关系: 1 δγ （0.3）为了叙述方便，我们引入=?1那么有以下式子成立
Newton迭代法求解非 线性方程
一、 Newton 迭代法概述 构造迭代函数的一条重要途径是用近似方程来代替原方程去求根。因此，如果能将非线性方程f (x )=0用线性方程去代替，那么，求近似根问题就很容易解决，而且十分方便。牛顿(Newton)法就是一种将非线性方程线化的一种方法。 设k x 是方程f (x )=0的一个近似根，把如果)(x f 在k x 处作一阶Taylor 展开，即： )x x )(x ('f )x (f )x (f k k k -+≈ (1-1) 于是我们得到如下近似方程： 0)x x )(x ('f )x (f k k k =-+ (1-2) 设0)('≠k x f ，则方程的解为： x ?=x k +f (x k ) f (x k )? (1-3) 取x ~作为原方程的新近似根1+k x ，即令： ) x ('f ) x (f x x k k k 1k -=+, k=0,1,2,… (1-4) 上式称为牛顿迭代格式。用牛顿迭代格式求方程的根的方法就称为牛顿迭代法，简称牛顿法。 牛顿法具有明显的几何意义。方程： )x x )(x ('f )x (f y k k k -+= (1-5) 是曲线)x (f y =上点))x (f ,x (k k 处的切线方程。迭代格式(1-4)就是用切线式(1-5)的零点来代替曲线的零点。正因为如此，牛顿法也称为切线法。 牛顿迭代法对单根至少是二阶局部收敛的，而对于重根是一阶局部收敛的。一般来说，牛顿法对初值0x 的要求较高，初值足够靠近*x 时才能保证收敛。若
要保证初值在较大范围内收敛，则需对)x (f 加一些条件。如果所加的条件不满足，而导致牛顿法不收敛时，则需对牛顿法作一些改时，即可以采用下面的迭代格式： ) x ('f ) x (f x x k k k 1k λ -=+, ?=,2,1,0k (1-6) 上式中，10<λ<，称为下山因子。因此，用这种方法求方程的根，也称为牛顿下山法。 牛顿法对单根收敛速度快，但每迭代一次，除需计算)x (f k 之外，还要计算 )x ('f k 的值。如果)x (f 比较复杂，计算)x ('f k 的工作量就可能比较大。为了避免计算导数值，我们可用差商来代替导数。通常用如下几种方法： 1. 割线法 如果用 1 k k 1k k x x ) x (f )x (f ----代替)x ('f k ，则得到割线法的迭代格式为： )x (f ) x (f )x (f x x x x k 1k k 1 k k k 1k --+---= (1-7) 2. 拟牛顿法 如果用 ) x (f )) x (f x (f )x (f k 1k k k ---代替)x ('f k ，则得到拟牛顿法的迭代格式为： )) x (f x (f )x (f ) x (f x x 1k k k k 2k 1k -+--- = (1-8) 3. Steffenson 法 如果用 ) x (f ) x (f ))x (f x (f k k k k -+代替)x ('f k ，则得到拟牛顿法的迭代格式为： ) x (f ))x (f x (f ) x (f x x k k k k 2k 1 k -+- =+
拟牛顿法的研究现状 文献综述 姓名:孟媛媛 学号：112111215 指导老师：肖伟 前言 求解非线性方程组 0)(=x F 的方法有很多，最速下降法具有结构简单，计算量小的优点，但是它的收敛速度较慢；牛顿法及其改进牛顿法，虽然收敛速度快，但在迭代过程中的每一步构造搜索方向时，首先要计算目标函数的Hessian 矩阵，然后需要解一个线性方程组，计算工作量很大，这就抵消了牛顿法收敛速度快的优点。为了克服牛顿法的缺点，人们提出了拟牛顿法，拟牛顿法在构造搜索方向时，只需要利用目标函数及其一阶导数的信息，避免了Hessian 矩阵的计算，减少了计算量，并且具有超线性收敛的优点，经理论证明和实践检验，拟牛顿法已经成为一类公认的比较有效的算法. 拟牛顿法 一、求解非线性方程组的拟牛顿法 设R R n n F →：是连续可微映射．考虑下面的非线性方程组： 0)(=x F )1.1( 牛顿法是求解方程组)1.1(的经典的方法之一，其迭代格式为： d x x k k k +=+1，)()(1 x x d k k k F F -'-=， 其中)(x k F '是F 在x k 处的Jacobian 阵.牛顿法的一个显著优点就是具有局部的超线性甚至二阶收敛速度，由于牛顿法这一优点，使其成为颇受欢迎的算法之一， 然而，当Jacobian 矩阵)(x k F '奇异时，牛顿方向可能不存在．克服牛顿法的这一缺陷的一个主要途径就是采用拟牛顿法，其基本思想是利用某个矩阵B k 作为 )(x k F '的近似取代)(x k F '.拟牛顿法的一般格式为： d x x k k k k α+ =+1， )2.1(
拟牛顿法 牛顿法的收敛速度虽然较快，但要求海森矩阵要可逆，要计算二阶导数和逆矩阵，就加大了就算机计算量。为了克服牛顿法的缺点，同时保持较快收敛速度的优点，就产生了拟牛顿法。拟牛顿法是牛顿法的直接推广，通过在试探点附近的二次逼近引进牛顿条件来确定线搜索方向，它主要有DFP 和BFGS 两种形式，拟牛顿法的一般步骤为： （1） 给定初始点(0)x ，初始对称正定矩阵0H ，(0) 0()g g x =及精度0ε>； （2） 计算搜索方向() k k k p H g =-； （3） 作直线搜索(1) ()()(,)k k k x F x p +=，计算(1)(1)11(),()k k k k f f x g g x ++++==， (1)()1,k k k k k k S x x y g g ++=-=- （4） 判断终止准则是否满足； （5） 令1k k k H H E +=+置1k k =+，转步骤（2）； 不同的拟牛顿法对应不同的k E ，主要介绍DFP 和BFGS 两种拟牛顿法。 1. DFP 法 （1） 算法原理 DFP 算法中的校正公式为： 1k k k k T T k k k k k k T T k k k S S H y y H H H S y y H y +=+ - 为了保证k H 的正定性，在下面的算法中迭代一定次数后，重置初始点和迭代矩阵再进行迭代。 （2） 算法步骤 1） 给定初始点(0)x ，初始矩阵0n H I =及精度0ε>； 2） 若() (0) f x ε?≤，停止，极小点为(0)x ；否则转步骤3）； 3） 取() (0)(0)0p H f x =-?，且令0k =； 4） 用一维搜索法求k t ，使得() ()()()0 ()min ()k k k k k k t f X t p f X tp α≥+=+，令 (1)()()k k k x x tp +=+，转步骤5）； 5） ( ) (1) k f x ε+?≤，停止，极小值点为(1)k x +；否则转步骤6）； 6） 若1k n +=，令(0) ()n x x =，转步骤3）；否则转步骤7）；
本文链接：https://www.doczj.com/doc/f911711340.html,/miaowei/52925.html 最近在看条件随机场中的优化算法。其中就设计到了无约束化的最优化方法，也就是牛顿法。在CRF （conditional random field）中，使用的是L-BFGS法。费了好大的劲把算法的原理及推导算是看明白了，可是到了具体实现上，又碰到问题了，比如在求搜索方向的时候，使用 但是程序中如何实现呢？ 现在转载一篇文章，看过之后，会非常受益。 使用导数的最优化算法中，拟牛顿法是目前为止最为行之有效的一种算法，具有收敛速度快、算法稳定性强、编写程序容易等优点。在现今的大型计算程序中有着广泛的应用。本文试图介绍拟牛顿法的基础理论和若干进展。 牛顿法(Newton Method) 牛顿法的基本思想是在极小点附近通过对目标函数做二阶Taylor展开，进而找到的极小点的估计值[1]。一维情况下，也即令函数为 则其导数满足 因此 (1) 将作为极小点的一个进一步的估计值。重复上述过程，可以产生一系列的极小点估值集合。一定条件下，这个极小点序列收敛于的极值点。 将上述讨论扩展到维空间，类似的，对于维函数有 其中和分别是目标函数的的一阶和二阶导数，表现为维向量和矩阵，而后者又称为目标函数在处的Hesse矩阵。设可逆，则可得与方程(1)类似的迭代公式： (2) 这就是原始牛顿法的迭代公式。 原始牛顿法虽然具有二次终止性（即用于二次凸函数时，经有限次迭代必达极小点），但是要求初始点需要尽量靠近极小点，否则有可能不收敛。因此人们又提出了阻尼牛顿法[1]。这种方法在算法形式上等同于所有流行的优化方法，即确定搜索方向，再沿此方向进行一维搜索，找出该方向上的极小点，然后在该点处重新确定搜索方向，重复上述过程，直至函数梯度小于预设判据。具体步骤列为算法1。
拟牛顿法 牛顿法有很好的收敛性，特别是当初始点x0选择在最终解x*附近时，收敛速度叫梯度法更快，但是当初始迭代点远离x*，收敛速度慢且不能保证收敛，当其Hession <0，迭代算法不会像函数值减小的方向前进。针对newton法的这些弱点，提出了改进方法：拟牛顿方法，包括rank one，DFP和BFGS三种算法。 （1）Rank one 选用aster书《An Introduction to Optimization》中实例验证 目标函数：f(x1,x2)=x1^2+0.5*x2^2+3，是一个二次型函数。初始值x0=[1,2]’；，精度 1.0e-5控制迭代终止，当norm(G)<=1.0e-5时，迭代终止；取H0=I2，Q=[2,0;0,1]; ①迭代结果：经过两次迭代之后，迭代停止，得值x=【0,0】’。 ②改变初始值为远离x= [0,0]’的值x0=[1000,2]’，和x0=[1000,1000]’，算法经过两步迭代后都收敛到x=【0,0】’。 算法的结果验证了书中结论：不论初始值X0如何选取，稚一算法在n步迭代之内收敛到终解。 稚一算法对于恒定hess矩阵的情况非常好，也就是对二次型问题问题非常有效，但是对于非二次型问题，H（k）可能是非正定的，这样函数不能向下降的方向前进，这就引出下面的稚二算法。 （2）DFP 目标函数：f(x1,x2)=2*(x1^2)+x2^2+2*x1*x2+x1-x2； 即：f(x1,x2)=1/2*[x1,x2]*[4,2;2,2]* [x1,x2]’-[x1,x2]*[-1,1]’; 初始点x0=[0,0]’，取H0=I2，Q=[4,2;2,2]。H0是一个实对称正定矩阵，第一次迭代后，H1=[0.5,-0.5;-0.5,1.5]是一个非对称正定矩阵，此时就体现出稚二算法的优势，第二次迭代后，满足norm(G)<=1.0e-5条件，迭代终止，的解x=【-1.0,1.5】’。同样，改变初值x0=[100,4]及x0=[100,100]都在迭代两步后收敛到x=[-1.0,1.5]’; 结果证明了DFP算法较稚一算法的优越之处：在Hess矩阵不是对称正定矩阵是，依然可以收敛。 （3）BFGS DFP算法较稚一算法有很好的优越性，但是对于较强的非二次型反问题，DFP算法也会“噎住”，因为H（k）几乎变得奇异，针对这个问题，提出了改进的算法BFGS算法。 目标函数：f(x1,x2)=1/2* x’*Q* x- x’*b+log（π）; 其中Q=[5,-3;-3,2];b=[0;1];取H0=I2，x0=[0;0]。
拟牛顿法(Quasi-Newton Methods)是求解非线性优化问题最有效的方法之一，于20世纪50年代由美国Argonne国家实验室的物理学家W. C. Davidon所提出来。Davidon 设计的这种算法在当时看来是非线性优化领域最具创造性的发明之一。不久R. Fletcher和M. J. D. Powell证实了这种新的算法远比其他方法快速和可靠，使得非线性优化这门学科在一夜之间突飞猛进。在之后的20年里，拟牛顿方法得到了蓬勃发展，出现了大量的变形公式以及数以百计的相关论文。 拟牛顿法和最速下降法(Steepest Descent Methods)一样只要求每一步迭代时知道目标函数的梯度。通过测量梯度的变化，构造一个目标函数的模型使之足以产生超线性收敛性。这类方法大大优于最速下降法，尤其对于困难的问题。另外，因为拟牛顿法不需要二阶导数的信息，所以有时比牛顿法(Newton's Method)更为有效。如今，优化软件中包含了大量的拟牛顿算法用来解决无约束，约束，和大规模的优化问题。 拟牛顿法的基本思想如下。首先构造目标函数在当前迭代$x_k$的二次模型：m_k(p)=f_k+g_k^T p+p^T B_k p/2，这里f_k=f(x_k)，g_k=▽f(x_k)，B_k是一个对称正定矩阵。于是我们取这个二次模型的最优解p_k=-B_k^{-1} g_k作为搜索方向，并且得到新的迭代点x_{k+1}=x_k+a_k p_k，其中我们要求步长a_k满足Wolfe条件。这样的迭代类似与牛顿法，区别就在于用近似的Hesse矩阵B_k代替真实的Hesse矩阵。所以拟牛顿法最关键的地方就是每一步迭代中矩阵B_k的更新。现在假设得到一个新的迭代x_{k+1}，并得到一个新的二次模型：m_{k+1}(p)=f_{k+1}+g_{k+1}^T p + p^T B_{k+1} p/2。我们尽可能地利用上一步的信息来选取B_{k+1}。具体地，我们要求g_{k+1}-g_k=a_k B_{k+1} p_k，从而得到B_{k+1}s_k=y_k，其中s_k=x_{k+1}-x_k，y_k=g_{k+1}-g_k。这个公式被称为割线方程。下面主要介绍这几种方法：DFP方法，BFGS方法，SR1方法，Broyden族方法。 纯形法，求解线性规划问题的通用方法。单纯形是美国数学家G.B.丹齐克于1947年首先提出来的。它的理论根据是：线性规划问题的可行域是n维向量空间Rn中的多面凸集，其最优值如果存在必在该凸集的某顶点处达到。顶点所对应的可行解称为基本可行解。单纯形法的基本思想是：先找出一个基本可行解，对它进行鉴别，看是否是最优解；若不是，则按照一定法则转换到另一改进的基本可行解,再鉴别；若仍不是，则再转换,按此重复进行。因基本可行解的个数有限，故经有限次转换必能得出问题的最优解。如果问题无最优解也可用此法判别。根据单纯形法的原理，在线性规划问题中，决策变量（控制变量）x1，x2， (x) n的值称为一个解,满足所有的约束条件的解称为可行解。使目标函数达到最大值（或最小值）的可行解称为最优解。这样，一个最优解能在整个由约束条件所确定的可行区域内使目标函数达到最大值（或最小值）。求解线性规划问题的目的就是要找出最优解。 最优解可能出现下列情况之一：①存在着一个最优解；②存在着无穷多个最优解； ③不存在最优解，这只在两种情况下发生，即没有可行解或各项约束条件不阻止目标函数的值无限增大（或向负的方向无限增大）。 单纯形法的一般解题步骤可归纳如下：①把线性规划问题的约束方程组表达成典范型方程组，找出基本可行解作为初始基本可行解。②若基本可行解不存在，即约束条件有矛盾，则问题无解。③若基本可行解存在，从初始基本可行解作为起点，根据最优性条件和可行性条件，引入非基变量取代某一基变量，找出目标函数值更优的另一基本可行解。④按步骤3进行迭代,直到对应检验数满足最优性条件（这时目标函数值不能再改善），即得到问题的最优解。⑤若迭代过程中发现问题的目标函数值无界，则终止迭代。 用单纯形法求解线性规划问题所需的迭代次数主要取决于约束条件的个数。
拟牛顿法的matlab实现（转） 2011-03-16 15:07:04| 分类：matlab | 标签：|字号大中小订阅 牛顿法成功的关键是利用了Hesse矩阵提供的曲率信息，但计算Hesse矩阵工作量大，并且有的目标函数的Hesse矩阵很难计算，甚至不好求出。针对这一问题，拟牛顿法比牛顿法更为有效。这类算法仅利用目标函数值和一阶导数的信息，构造出目标函数的曲率近似，使方法具有类似牛顿法的收敛速度快的优点。函数名：quasi_Newton(f,x0,error), 参数：f:待求梯度函数x0:初始点error：允许误差 主程序： function A=quasi_Newton(f,x0,error) [a,b]=size(x0); G0=eye(b); initial_gradient=gradient_my(f,x0,b); norm0=0; norm0=initial_gradient*initial_gradient'; syms step_zzh; A=[x0]; search_direction=-initial_gradient; x=x0+step_zzh*search_direction; f_step=subs(f,findsym(f),x); best_step=golden_search(f_step,-15,15); x_1=x0+best_step*search_direction; A=[A;x_1]; k=1; while norm0>error ox=x_1-x0; og=gradient_my(f,x_1,b)-initial_gradient; G1=G0+(ox'*ox)/(ox*og')-(G0*og'*og*G0)/(og*G0*og'); if k+1==b new_direction=-gradient_my(f,x_1,b); else new_direction=-(G1*(gradient_my(f,x_1,b))')'; end x=x_1+step_zzh*new_direction; f_step=subs(f,findsym(f),x); best_step=golden_search(f_step,-15,15) x_2=x_1+best_step*new_direction A=[A;x_2]; initial_gradient=gradient_my(f,x_1,b); norm0=initial_gradient*initial_gradient'; x0=x_1;x_1=x_2; G0=G1;
机械设计优化大作业 摘要：拟牛顿法是求解优化问题的一种重要方法，本文在Matlab平台上，运用拟牛顿法对最小值问题进行了无约束优化求解。计算结果表明，拟牛顿法能够比较精确地计算函数的极小值。 关键词：拟牛顿法，最小值 1 概述 随着计算机技术的飞速发展和数值计算方法的广泛应用，工程设计领域在设计方法和技术创新方面有了巨大发展和进步，这也大大推动了现代工程领域的技术进步和创新。优化设计就是其中发展最快的设计方法之一。 优化设计是20世纪60年代初发展起来的一门新兴学科，他将数学中的最优化理论与工程设计领域相结合，使人们在解决工程设计问题时，可以从无数设计方案中找到最优或尽可能完善的设计方案，大大提高了工程的设计效率和设计质量。目前，优化设计是工程设计中的一种重要方法，已经广泛应用于各个工程领域——航空航天、机械、船舶、交通、电子、通讯、建筑、纺织、冶金、是有、管理等，并产生了巨大的经济效益和社会效益。特别是由于现代国家、地区和企业之间的激烈竞争，各种原材料、能源的短缺，优化设计越来越受到人们广泛的重视，并成为21世纪工程设计人员必须掌握的的一种设计方法。 优化设计工作中，针对具体设计问题是否选择了合适的优化方法，相应的计算程序是否有效．数学模型构造是否合理，能否充分反映实际问题且尽量简化，这些都直接关系到优化设计进程和机械设计结果。目前，常用的机械优化设计过程：①分析设计变量，提出目标函数，确定约束条件，建立优化设计的数学模型； ②选择适当的优化方法，编写优化程序；③准备必须的初始数据并上机计算，对计算机求得的结果进行必要的分析。 2 拟牛顿法简介 拟牛顿法(Quasi-Newton Methods)是求解非线性优化问题最有效的方法之一，于20世纪50年代由美国Argonne国家实验室的物理学家W. C. Davidon 所提出来。Davidon设计的这种算法在当时看来是非线性优化领域最具创造性的发明之一。不久R. Fletcher和M. J. D. Powell证实了这种新的算法远比其他方法快速和可靠，使得非线性优化这门学科在一夜之间突飞猛进。在之后的20年里，拟牛顿方法得到了蓬勃发展，出现了大量的变形公式以及数以百计的相关论文。 拟牛顿法和最速下降法(Steepest Descent Methods)一样只要求每一步迭代时知道目标函数的梯度。通过测量梯度的变化，构造一个目标函数的模型使之足以产生超线性收敛性。这类方法大大优于最速下降法，尤其对于困难的问题。另外，因为拟牛顿法不需要二阶导数的信息，所以有时比牛顿法(Newton's Method)更为有效。如今，优化软件中包含了大量的拟牛顿算法用来解决无约束，约束，和大规模的优化问题。
文献综述 数学与应用数学 解非线性规划问题的拟牛顿法究 非线性规划是具有非线性约束条件或目标函数的数学规划,是运筹学的一个重要分支.非线性规划研究一个n 元实函数在一组等式或不等式的约束条件下的极值问题，且目标函数和约束条件至少有一个是未知量的非线性函数.非线性规划问题也就是在多种决策中挑选最好决策的问题，它被广泛应用于农业、国防、交通、金融、能源、通信等许多领域，在资源利用、结构优化、调度管理、后勤供应等许多问题中产生了巨大的经济效益和社会效应.例如：如何在现有人力、物力、财力条件下合理安排产品生产，以取得最高的利润；如何设计某种产品，在满足规格、性能要求的前提下，达到最低的成本；如何确定一个自动控制系统的某些参数，使系统的工作状态最佳；如何分配一个动力系统中各电站的负荷，在保证一定指标要求的前提下，使总耗费最小；如何安排库存储量，既能保证供应，又使储存费用最低；如 何组织货源，既能满足顾客需要，又使资金周转最快等. 非线性规划问题是在二十世纪50年代发展起来的，主要讨论非线性决策问题的最佳选择之特性，构造寻求最优解的计算方法，研究这些计算方法的理论性质及实际计算表现.随着电子计算机的发展和应用，非线性最优化理论和方法有了很大发展，目前，已成为一门十分活跃的学科.许多急需解决的、对国民经济有重大影响的大规模复杂科学和工程问题本质上都是优化问题.它们有的规模十分巨大（维数达上百万，如大气科学中的四维同化问题）.因此，研究高效的优化计算方法不仅具有重要的科学意义，而且具有广泛的应用前景，将对促进优化方法在国民生产等方面的因公起到重大作用. 对于无约束优化问题 （P ） )(min x f ，n T n R x x x x ∈=）K ,,(21 众所周知，牛顿法是非常好的方法，因为牛顿法具有二次收敛性，但当)()(2k x f ?不正定时，不能保证算法产生的方向是f 在)(k x 处的下降方向.特别，当)()(2k x f ?奇异时，子问题0)()()()(2=?+?k k x f d x f 可能无解，即牛顿方向可能不存在.修正牛顿法可克服牛顿法的上诉困难，但在修正牛顿法中，参数0>k v 的选取十分重要.若k v 参数国小，则相应的修正牛顿
?主页 ?专栏作家 ?量化基础理论?软件使用经验?量化软件 ?资源导航 ?资料下载 ?量化论坛 ?创建新帐号?重设密码 首页
拟牛顿法及相关讨论 星期三, 2009-06-17 00:24 —satchel1979 使用导数的最优化算法中，拟牛顿法是目前为止最为行之有效的一种算法，具有收敛速度快、算法稳定性强、编写程序容易等优点。在现今的大型计算程序中有着广泛的应用。本文试图介绍拟牛顿法的基础理论和若干进展。 牛顿法(Newton Method) 牛顿法的基本思想是在极小点附近通过对目标函数做二阶Taylor展开，进而找到的极小点 的估计值[1]。一维情况下，也即令函数为 则其导数满足 因此 (1) 将作为极小点的一个进一步的估计值。重复上述过程，可以产生一系列的极小点估值集合 。一定条件下，这个极小点序列收敛于的极值点。 将上述讨论扩展到维空间，类似的，对于维函数有 其中和分别是目标函数的的一阶和二阶导数，表现为维向量和矩阵，而后 者又称为目标函数在处的Hesse矩阵。设可逆，则可得与方程(1)类似的迭代公式：
(2) 这就是原始牛顿法的迭代公式。 原始牛顿法虽然具有二次终止性（即用于二次凸函数时，经有限次迭代必达极小点），但是要求初始点需要尽量靠近极小点，否则有可能不收敛。因此人们又提出了阻尼牛顿法[1]。这种方法在算法形式上等同于所有流行的优化方法，即确定搜索方向，再沿此方向进行一维搜索，找出该方向上的极小点，然后在该点处重新确定搜索方向，重复上述过程，直至函数梯度小于预设判据。具体步骤列为算法1。 算法1： (1) 给定初始点，设定收敛判据，. (2) 计算和. (3) 若< ，则停止迭代，否则确定搜索方向. (4) 从出发，沿做一维搜索， 令. (5) 设，转步骤(2). 在一定程度上，阻尼牛顿法具有更强的稳定性。
SR1校正的拟牛顿法 !!!本程序适用于求解形如f(x)=1/2*x'Ax+bx+c二次函数的稳定点；!!!输入函数信息，输出函数的稳定点及迭代次数； !!!iter整型变量，存放迭代次数； !!!x为n维变量，初始值由用户输入；gradt实型变量，存放函数梯度; !!!dir实型变量，存放搜索方向； program main real,dimension(:),allocatable::x,gradt,dir,b ,s,y,p ,gradt1,x1 real,dimension(:,:),allocatable::hessin ,H ,G real::x0,tol integer::n ,iter,i,j print*,'请输入变量的维数' read*,n allocate(x(n),gradt(n),dir(n),b(n),s(n),y(n),p(n),gradt1(n),x1(n)) allocate(hessin(n,n),H(n,n),G(n,n)) print*,'请输入初始向量x' read*,x print*,'请输入hessin矩阵' read*,hessin print*,'请输入矩阵b' read*,b iter=0 tol=0.000001 do i=1,n do j=1,n if (i==j)then H(i,j)=1 else H(i,j)=0 endif enddo enddo 100 gradt=matmul(hessin,x)+b if(sqrt(dot_product(gradt,gradt))
相关主题
文本预览