BFGS优化算法及应用实例.doc

《BFGS优化算法及应用实例.doc》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、目录1、引言12、BFGS算法综述12.1拟牛顿法及其性质12.2BFGS算法33、数值实验63.1代码实现63.2算法测试73.3结果分析84、总结84.1总结概括85、参考文献：91、引言在最优化的问题中，线性最优化至少可以使用单纯形法求解，但对于非线性优化问题，牛顿法提供了一种求解的办法。牛顿法的优点是具有二次收敛速度，但是当Hesse矩阵不正定时，不能保证所产生的方向是目标函数在处的下降方向。特别地，当奇异时，算法就无法继续进行下去，尽管修正的牛顿法可以克服这一缺点，但修正参数的选取很难把握，

2、过大或过小都会影响到收敛速度，此外，牛顿法的每一迭代步都需要目标函数的二阶导数，即Hesse矩阵，对于大规模问题，其计算量是惊人的。由此引出了一种新的求解非线性优化问题的方法——拟牛顿法。拟牛顿法(Quasi-NewtonMethods)是求解非线性优化问题最有效的方法之一，于20世纪50年代由美国Argonne国家实验室的物理学家W.C.Davidon所提出来。Davidon设计的这种算法在当时看来是非线性优化领域最具创造性的发明之一。不久R.Fletcher和M.J.D.Powell证实了这种新的

3、算法远比其他方法快速和可靠，使得非线性优化这门学科在一夜之间突飞猛进。在之后的20年里，拟牛顿方法得到了蓬勃发展，出现了大量的变形公式以及数以百计的相关论文。其中BFGS就是拟牛顿法中的一种方法。2、BFGS算法的综述2.1拟牛顿法及其性质拟牛顿法的基本思想是在牛顿法的第二步中用Hesse矩阵的某个近似矩阵取代。通常，应具有以下三个特点：（1）在某种意义下有，使得相应的算法产生的方向近似于牛顿方向，以确保算法具有较快的收敛速度；（2）对所有的，是对称正定的，从而使得算法所产生的方向是函数在处下降方向；

4、（3）矩阵更新规则相对比较简单，即通常采用秩1或秩2矩阵进行校正。下面介绍满足这三个特点的矩阵的构造，设在开集上二次连续可微，那么在处二次近似模型为（2.1）对上式求导得（2.2）令，位移，梯度差，则有（2.3）注意到对于二次函数，上式是精确成立的。现在，要求在拟牛顿法中构造Hesse矩阵的近似矩阵满足这种关系式，即（2.4）式（2.4）通常称为拟牛顿方程或拟牛顿条件。令，则得到拟牛顿方程的另一种形式：（2.5）其中为Hesse矩阵逆的近似。搜索方向由或确定。根据（或）的第三个特点，可令，（2.6）其

5、中，为秩1或秩2矩阵，通常将拟牛顿方程（2.4）（或（2.5））和校正规则（2.6）所确立的方法称为拟牛顿法。下面介绍一对称秩1校正公式。在（2.6）中取（秩1矩阵），其中.由拟牛顿方程（2.4）得（2.7）即有（2.8）式（2.8）表明向量平行，即存在常数使得.因此有（2.9）于是，由（2.8）得（2.10）由此，若，则可取，即（2.11）故得对称秩1的校正公式如下：（2.12）类似地，利用拟牛顿方程（2.1.5），对称秩1的修正可得（2.13）有了对称秩1校正公式后，利用它可以构造求解一个无约束优

6、化问题的一个拟牛顿算法，步骤如下：算法2.1（对称秩1算法）步0给定初始点，终止误差，初始对称正定矩阵（通常取单位矩阵），令.步1若，停止运算，输出作为近似极小点。步2计算搜索方向.步3用线性搜索技术求步长.步4令，由对称秩1校正公式（2.13）确定.步5令，转步1.2.2BFGS算法BFGS校正是目前最流行，也是最有效的牛顿校正，它是由Broyden，Fletcher，Goldfarb和Shanno在1970年各自独立提出的拟牛顿法，故称BFGS算法，其基本思想是：在（2.6）中去修正矩阵为秩2矩阵

7、（2.14）其中为待定向量为待定实数，于是拟牛顿方程（2.4）可得（2.15）或者等价地（2.16）不难发现，满足（2.16）的向量和不唯一，可取和分别平行于和，即令，其中为待定的参数，于是有（2.17）将的表达式代入（2.16）得（2.18）整理得（2.19）故可令及，即（2.20）从而得到BFGS秩2修正公式如下：（2.21）显然，由（2.21）可知，若对称，则校正后的也对称，并且可以证明BFGS校正公式的如下性质：引理2.1设对称正定，由BFGS校正公式（2.21）确定，那么的对称正定的充要条件

8、是.证必要性是显然的。因，故若正定，则显然有.下面证明充分性.设，且正定，由校正公式（2.21），对任意的有（2.22）因对称正定，故存在对称正定矩阵，使得，从而利用Cauchy-Schwarz不等式得（2.23）不难发现，式（2.23）中等号成立的充要条件是存在实数，使得，即故若不等式（2.23）严格成立，则由（2.22）得（2.24）否则，若（2.23）中等号成立，即存在，使得，则由（2.22）（2.23）得（2.25）故对任意的，总有.证毕。引理2