BFGS优化算法及应用实例

目录1、引言........................................................................................................................12、BFGS算法综述.................................................................................................12.1拟牛顿法及其性质...........................................................................................12.2BFGS算法.........................................................................................................33、数值实验..............................................................................................................63.1代码实现...........................................................................................................63.2算法测试...........................................................................................................73.3结果分析...........................................................................................................84、总结.......................................................................................................................84.1总结概括...........................................................................................................85、参考文献：.........................................................................................................9最优化方法课程设计11、引言在最优化的问题中，线性最优化至少可以使用单纯形法求解，但对于非线性优化问题，牛顿法提供了一种求解的办法。牛顿法的优点是具有二次收敛速度，但是当Hesse矩阵2=)kkGfx（不正定时，不能保证所产生的方向是目标函数在kx处的下降方向。特别地，当kG奇异时，算法就无法继续进行下去，尽管修正的牛顿法可以克服这一缺点，但修正参数的选取很难把握，过大或过小都会影响到收敛速度，此外，牛顿法的每一迭代步都需要目标函数的二阶导数，即Hesse矩阵，对于大规模问题，其计算量是惊人的。由此引出了一种新的求解非线性优化问题的方法——拟牛顿法。拟牛顿法(Quasi-NewtonMethods)是求解非线性优化问题最有效的方法之一，于20世纪50年代由美国Argonne国家实验室的物理学家W.C.Davidon所提出来。Davidon设计的这种算法在当时看来是非线性优化领域最具创造性的发明之一。不久R.Fletcher和M.J.D.Powell证实了这种新的算法远比其他方法快速和可靠，使得非线性优化这门学科在一夜之间突飞猛进。在之后的20年里，拟牛顿方法得到了蓬勃发展，出现了大量的变形公式以及数以百计的相关论文。其中BFGS就是拟牛顿法中的一种方法。2、BFGS算法的综述2.1拟牛顿法及其性质拟牛顿法的基本思想是在牛顿法的第二步中用Hesse矩阵2=)kkGfx（的某个近似矩阵kB取代kG。通常，kB应具有以下三个特点：（1）在某种意义下有kkBG，使得相应的算法产生的方向近似于牛顿方向，以确保算法具有较快的收敛速度；（2）对所有的k，kB是对称正定的，从而使得算法所产生的方向是函数f在kx处下降方向；（3）矩阵kB更新规则相对比较简单，即通常采用秩1或秩2矩阵进行校正。下面介绍满足这三个特点的矩阵kB的构造，设:nf在开集nD上二次连续可微，那么f在1kx处二次近似模型为最优化方法课程设计21111111()()(()()()2kkTkkTkkfxfxgxxxxGxx）（2.1）对上式求导得111()()kkkgxgGxx（2.2）令kxx，位移1kkksxx，梯度差1kkkygg，则有1kkkGsy（2.3）注意到对于二次函数f，上式是精确成立的。现在，要求在拟牛顿法中构造Hesse矩阵的近似矩阵kB满足这种关系式，即1kkkBsy（2.4）式（2.4）通常称为拟牛顿方程或拟牛顿条件。令111kkHB，则得到拟牛顿方程的另一种形式：1kkkHys（2.5）其中1kH为Hesse矩阵逆的近似。搜索方向由kkkdHg或kkkBdg确定。根据kB（或kH）的第三个特点，可令1kkkBBE，1kkkHHD（2.6）其中kE，kD为秩1或秩2矩阵，通常将拟牛顿方程（2.4）（或（2.5））和校正规则（2.6）所确立的方法称为拟牛顿法。下面介绍一对称秩1校正公式。在（2.6）中取()kkTkEuu（秩1矩阵），其中,knu.由拟牛顿方程（2.4）得[()]kkTkkkBuusy（2.7）即有[()]kTkkkkkusuyBs（2.8）式（2.8）表明向量ku平行kkkyBs，即存在常数使得()kkkkuyBs.因此有2()()kkkkTkkkEyBsyBs（2.9）于是，由（2.8）得最优化方法课程设计32[()]()()kkTkkkkkkkkyBssyBsyBs（2.10）由此，若()0kkTkkyBss，则可取2[()]1kkTkkyBss，即2()()1,()()kkkkTkkkkkTkkkTkkkyBsyBsEyBssyBss（2.11）故得对称秩1的校正公式如下：1()()()kkkkTkkkkkkTkkyBsyBsBByBss（2.12）类似地，利用拟牛顿方程（2.1.5），对称秩1的修正可得1()()()kkkkTkkkkkkTkksHysHyHHsHyy（2.13）有了对称秩1校正公式后，利用它可以构造求解一个无约束优化问题的一个拟牛顿算法，步骤如下：算法2.1（对称秩1算法）步0给定初始点0nx，终止误差01，初始对称正定矩阵0H（通常取单位矩阵nI），令0k.步1若kg，停止运算，输出kx作为近似极小点。步2计算搜索方向kkkdHg.步3用线性搜索技术求步长k.步4令1kkkkxxd，由对称秩1校正公式（2.13）确定1kH.步5令1kk，转步1.2.2BFGS算法BFGS校正是目前最流行，也是最有效的牛顿校正，它是由Broyden，Fletcher，Goldfarb和Shanno在1970年各自独立提出的拟牛顿法，故称BFGS算法，其基本思想是：在（2.6）中去修正矩阵kE为秩2矩阵()()kkTkkTkEuuvv（2.14）其中,kknuv为待定向量,为待定实数，于是拟牛顿方程（2.4）可得[()()]kkTkkTkkkBuuvvsy（2.15）或者等价地[()][()]kTkkkTkkkkkusuvsvyBs（2.16）最优化方法课程设计4不难发现，满足（2.16）的向量ku和kv不唯一，可取ku和kv分别平行于kkBs和ky，即令,kkkkkuBsvy，其中,为待定的参数，于是有22()()kkTkkTkkkEBssByy（2.17）将,kkuv的表达式代入（2.16）得[()]()[()]()kTkkkTkkkkkkkBssBsysyyBs（2.18）整理得22{[()]1}{[()]1}0kTkkkTkkkksBsBsysy（2.19）故可令2[()]1=0kTkksBs及2[()]1=0kTkys，即2211==()()kTkkTkksBsys，（2.20）从而得到BFGS秩2修正公式如下：1()()()()kkTkkTkkkkkTkkTkkBssByyBBsBsys（2.21）显然，由（2.21）可知，若kB对称，则校正后的1kB也对称，并且可以证明BFGS校正公式的如下性质：引理2.1设kB对称正定，1kB由BFGS校正公式（2.21）确定，那么1kB的对称正定的充要条件是()0kTkys.证必要性是显然的。因1()()kTkkTkkyssBs，故若1kB正定，则显然有()0kTkys.下面证明充分性.设()0kTkys，且正定，由校正公式（2.21），对任意的0nd有221()()()()TkTkTTkkkkTkkTkkdBsdydBddBdsBsys（2.22）因kB对称正定，故存在对称正定矩阵1/2kB，使得1/21/2kkkBBB，从而利用Cauchy-Schwarz不等式得最优化方法课程设计52221/21/221/21/2()[()()]TkTkkkkkkkdBsBdBsBdBs1/21/21/21/2()()()()TkTkkkkkBdBdBsBs()[()]TkTkkkdBdsBs（2.23）不难发现，式（2.23）中等号成立的充要条件是存在实数0k，使得1/21/2kkkkBdBs，即kkds故若不等式（2.23）严格成立，则由（2.22）得21()[()]()0()()TkTkTkTTkkkkkTkkTkkdBdsBsdydBddBdsBsys（2.24）否则，若（2.23）中等号成立，即存在k，使得kkds，则由（2.22）（2.23）得22221[()]()()0()()kTkTkTkTkkkkkTkkTksydydBdysysys（2.25）故对任意的0nd，总有10TkdBd.证毕。引理2.2若在BFGS算法中采用精确线搜索或Wolfe搜索准则，则有()0kTkys.证注意到对于精确线搜索有1()0kTkgd.故1()()()0kTkkkTkkTkkkysggdgd对于Wolfe搜索准则，利用该准则的第二个不等式（即()()kkTkkTkkfxddgd）得1()()(1)()kTkkkTkkTkkkysggdgd(1)()0kTkkgd证毕.已有证明表示，Armijo搜索准则一般不能保证()0kTkys。但Armijo准则因其简单且易于程序实现而深得人们的喜爱，因此，为了保证采用Armijo准则时矩阵序列{}kB的对称正定性，可采用如下的校正方式：最优化方法课程设计61,()0()(),()0()()kTkkkkTkkTkkTkkkkkTkkTkkBysBBssByyByssBsys（2.26）不难发现，只要0B对称正定，上述校