BFGS算法综述

２０１１年第１１期　（总第１４７期）　大众科技　ＤＡＺＨＯＮＧ　ＫＥＪＩ　Ｎｏ．１１。２０１１　（Ｃｕｍｕｌａｔｉｖｅｌｙ　Ｎｏ．１　４７）　ＢＦＧＳ算法综述　耿红梅　（扬州工业职业技术学院，江苏扬州２２５１２７）　【摘要】目前对一般无约束最优化问题的研究主要是以拟牛顿算法为主，并且随着研究的深入，各种基于修改原始拟牛　顿方程的新拟牛顿算法取得了较好的成果。文章主要对几种改进后的算法做个综述。　【关键词】ＢＦＧＳ算法；拟牛顿算法；全局收敛性；超线性收敛　【中图分类号】０２４２．２３　【文献标识码】Ａ　【文章编号】１００８—１１５１（２０１１）１１—０００３—０２　Ａｓｕｍｍａｒｙ　ｏｆＢＦＧＳ　ａｌｇｏｒｉｔｈｍ　Ａｂｓｔｒａｃｔ：Ａｔ　ｐｒｅｓｅｎｔ　ｔｈｅｒｅ　ｉｓ　ｎｏ　ｃｏｎｓｔｒａｉｎｔ　ｏｐｔｉｍｉｚｅｄ　ｎｅｓｔｉｎｇ　ｆｏｒ　ｔｈｅ　ｇｅｎｅｒａｌ　ｐｒｏｂｌｅｍ　ｏｆ　ｒｅｓｅａｒｃｈ　ｍａｉｎｌｙ　ｔｏ　ｐｌａｎｎｉｎｇ，ａｎｄ　ｗｉｔｈ　Ｎｅｗｔｏｎ’ｓ　ｍｅｔｈｏｄ　ｏｆ　ｓｔｕｄｙ，ａｌｌ　ｂａｓｅｄ　ｏｎ　ｔｈｅ　ｏｒｉｇｉｎａｌ　ｐｒｏｐｏｓｅｄ　ａｍｅｎｄｍｅｎｔ　Ｎｅｗｔｏｎ　ｏｆ　ｔｈｅ　ｅｑｕａｔｉｏｎ　ｉｓ　ａ　ｎｅｗ　ａｌｇｏｒｉｔｈｍ　ｆｏｒ　ｂｅｔｔｅｒ　ｒｅｓｕｌｔｓ．Ｔｈｉｓ　ａｒｔｉｃｌｅ　ｍａｉｎｌｙ　ｆｏｒ　ｓｅｖｅｒａｌ　ｉｍｐｒｏｖｅｄ　ａｌｇｏｒｉｔｈｍ　ｆｏｒ　ａ　ｒｅｖｉｅｗ．　Ｋｅｙ　ｗｏｒｄｓ：ＢＦＧＳ　ａｌｇｏｒｉｔｍ：ｑｕａｓｉ—Ｎｅｗｔｏｎ　ｍｅｔｈｏｄ：ｇｌｏｂａｌ　ｃｏｎｖｅｒｇｅｎｃｅ：ｓｕｐｅｒｌｉｎｅａｒ　ｃｏｎｖｅｒｇｅｎｃｅ　１引言　针对无约束最优化问题　ｍｉｎ　ｆ（ｘ）　ｘＥＲ　ｘｋｎ　ｘｋ＋九ｋｌｋ　ｌ　＝一Ｂ－、ｇ　依次产生点列　｝，其中　为搜索步长，　其中ｆ：Ｒ一　Ｒｌｆ∈ｒ：。ＢＦＧＳ算法是求解此类问题的最　，为有效的算法，故对它的研究很受关注，而拟牛顿方程在拟　牛顿算法的研究中又起到举足轻重的作用。近年来，基于修　改原始拟牛顿方程的新拟牛顿算法的研究吸引了大批的国内　外学者，他们在修改原始拟牛顿方程时除了利用梯度信息还　融入了函数值信息，使得新拟牛顿算法表现出比较好的性质。　在此基础上，各种改进的ＢＦＧＳ算法应运而生。并且近年来，　ｇ　＝Ｖｆ（ｘ　），Ｂ　是Ｖ　ｆ（ｘ　）的一个近似，Ｂ　由下式迭　代：　Ｔ　舞　・。　（１．２）　（１．３）　其中　Ｓｋ＝Ｘｋ＋ｔ—　＝　ＹＩ＝ｇ　＋ｌ——ｇ　对于拟牛顿算法收敛性质的研究一直是非线性最优化算法理　论研究的一个热点。带非精确搜索的拟牛顿算法的研究是从　１９７６年Ｐｏｗｅｌ１的工作开始的，他证明了带Ｗｏｌｆ搜索的ＢＦＧＳ算　法的全局收敛性和超线性收敛性。１９８９年Ｎｏｃｅｄａｌ等利用一新　的分析技巧，在目标函数是一致凸的条件下，证明了带回追　参数　满足　Ｉｌ－ｔ　Ｉ　　ｌ（１・４）　搜索的ＢＦＧＳ算法的全局收敛性和超线性收敛速度。下面主要　就各种改进的ＢＦＧＳ算法及其收敛性做个简单的综述。　ｔ’为一常数，对所有的ｋ成立。　（２）文［２］提出了一种与回追搜索有关的可行线性搜索，　其方法如下：　２几种改进后的算法　（１）文［１］提出了一类改进的ＢＦＧＳ算法，算法从任意初　始点　，初始任意对称正定阵　出发，通过迭代形式　改变的回追搜索：　【收稿日期】２０１卜０８—１６　【作者简介】耿红梅（１９８２～），女，江苏扬州人，扬州工业职业技术学院基础部讲师，研究方向为教育学、运筹与控制论。　一３．　第一步：选定常数　∈（Ｏ，１），　＞ｏ’Ｏ＜ｆ＜ｆ，＜１，令　：＝ａ。　第二步：若　满足　ｆ（ｘｋ＋　）≤，（　）＋以ｇ　Ｔ　（１・５）　则到第五步；否则到下一步。　第三步：在　，ｒ，　】中任选一数　，令　：＝　。　第四步：若　满足（１．５）式，则令　。：：　，终止；否则　回到第三步。　第五步：在『Ｌ　，ｆ’　　ｆ　ｊ］　中任选一数力，令　：＝　。　第六步：若　满足（１．５）式，则回到第五步，否则３，ｋ：＝　。　此搜索规则的特点是，到搜索的最后，　满足　厂（　＋　）　，（　）＋巩ｇ　Ｔ　（１・６）　＋五　）＞ｆ（ｘｋ）＋　ｇ　・７　其中五ｅ　在这种新搜索下，当目标函数为一致凸时，亦具有全局　收敛性。　（３）文［３］提出一种基于新拟牛顿方程的新改进ＢＦＧＳ　算法：　算法模型如下：　第一步：给定初始点Ｘ．∈Ｒ　及初始　×ｒｌ对称正定阵　Ｂ．，令ｋ：１：　第二步：计算ｇ＾：ｖｆ（　），若ｌＩｇ＾ＩＩ：０则停；否则转第三步；　第三步：令　＝一　ｇＩ：　第四步：￣ｘｋ　＝　十　，其中步长　由ｗｏｌｆｅ线性搜　索准则确定，　即给定　（ｏ　）（　，１）　，　若　，　厂（　＋　）＜－ｆ（ｘｋ）＋ｍｇｒｌｋ，ｇ（　＋　厶）　同时成立，　则取　＝１：否则取　０使满足　，（　＋　）　（　）＋　ｇ　，　ｇ（　＋　）　ｌｋ　，２　ｇ　第五步：计算　＋。＝Ｖｆ（ｘ　），若　０＝０则停；　一　筹　中　＋１一Ｘｋ：Ｙ　ｇ　＋ｌ—ｇ　：　ｆ　：　【，（　＋　）一　（　）一　Ｔｇ　】＋　，　∈【０，１】　Ｙｋ　ｙ：＝ＢＩ“　Ｉ。　第六步：令ｋ：ｋ＋１．转第三步。　此种算法在目标函数一致凸的情况下亦具有全局收敛　性。　（４）文［４］提出了一种新拟牛顿方程，并给出了基于新　拟牛顿方程的修改ＢＦＧＳ校正公式，结合Ｗｏｌｆｅ非精确线性搜　索提出新的拟牛顿算法：对于问题（１），记　＝　【　Ｉ），ｇ　＝　【　Ｉ　Ｊ，　＝　＋ｌ—　Ｉ，　ｇｋ＋ｌ—ｇｋ，　Ｇｋ：ｖ　，ｃ　），　表示欧式范数。当ｌＩ　ＩＩ充分小，，（　）充分光　滑时有：　＝　＋１－ｇ￣＋ｌ￣　＋　Ｇ　・群一　ｌ　Ｔ　・　＋去　＋。・　＋。（　Ｉ２　ｇ　・　＝　＋。・　一Ｇ　・　１　Ｔ　１Ｅ　・　一　・　＋。ｑ　ｌｒ）‘。　Ｇ　・　＝Ｇ¨・群一　＋．・　＋　１　ｔ，¨・　＋Ｄ（Ｉ　ｌｒ）　４　其中　¨∈Ｒ　和　＋。∈　…　是三阶和四阶张量。因　为Ｇ　・　＝　Ｇ¨　，　由（２），（３）和（４）得：　６　Ｇ　ｎ６ｔ≈６ｊ　ｙ　＋１２（Ａ一　“　＋ｓ６：ｇ｝“＋７６ｒｇ　＋６　Ｇｔ６　通过６：Ｇ　６　２Ｌ　ｋ　一　一ｇＴｋ６ｋ　帮６：Ｇｔ６　锱６　ｙｔ，　我们得到：　Ｇ　≈ｔ６ｒｙ　＋２（１一ｒ）（　一　一ｇ　），ｖｔ∈【０，ｌ】　考虑迭代　＝　＋　，ｄ　＝一　’ｇ　（５）　其中　为　的近似矩阵，　为搜索步长。用Ｂｋ近似　￣　Ｇ　，于是得到新拟牛顿方程如下：　＋。　：　＋（５＋ｆ）　：　（　＋　＿＇，　）：　６）　其中　＝２（　一　＋１）＋（ｇ　＋ｇｋ）　，ｔ∈【０，１】　＋　由（６）我们给出如下校正公式：　＝　一　＋器㈣　我们采用ｗ。１ｆｅ线性搜索准则：固定ｐｃ（Ｏ，　∈（　，１），　选择以，使之满足：　（９）　由于Ｗｏｌｆｅ准则不能保证　＞０，而且考虑到实际计　算的需要，我们给出如下校正公式：　（下转第１０页）　．４．　｝　｝　用相对路径控制各影片剪辑实例“暂停”的代码为：　ｏｎ（ｒｅｌｅａｓｅ）｛　用相对路径控制各影片剪辑实例“暂停”的代码为：　ｏｎ（ｒｅｌｅａｓｅ）｛　ｔｈｉｓ．ｓｔｏｐ　０　／／控制当前影片剪辑时间轴上　（即子影片剪辑２）动画的暂停　－ａｒｅｎｔ．ｓｔｏｐ０：ｐ　／／控制当前影片剪辑实例的上一　层（即主时间轴）动画的暂停　一ｔｈｉｓ．ｓｔｏｐ　０：／／控制当前影片剪辑时间轴上（即孙剪　辑）动画的暂停　ｐａｒｅｎｔ．ｓｔｏｐ　＿０：／／控制当前影片剪辑实例的上一层　（即子影片剪辑１）实例动画的暂停　ｐａｒｅｎｔ．＿＿ｐａｒｅｎｔ．ｓｔｏｐ（）：　轴动画的暂停　ｐａｒｅｎｔ．＿＿ｐａｒｅｎｔ．ｚ２＿ｐａｒｅｎｔ．ｚｌｉｎｃ．ｓｔｏｐ（）：　／／控制子影片剪辑１　／／控制主时间　实例动画的暂停　ｐａｒｅｎｔ．ｚｌ　ｍｃ．ｓｕｎ　ｍｃ．ｓｔｏｐ（）：／／控制子影片剪辑１　实例下的孙剪辑实例动画的暂停　＿ｍｃ．ｓｔｏｐ　０：　／／控制子影片剪　辑２实例动画的暂停　）　）　（４）若当前层为孙影片剪辑，各影片剪辑实例的路径可　以这样来表述：　主时间轴用＿ｐａｒｅｎｔ．＿ｐａｒｅｎｔ表示，子影片剪辑１实例　用＿ｐａｒｅｎｔ表示，子影片剪辑２实例可以用　ｐａｒｅｎｔ．＿＿ｐａｒｅｎｔ．ｚ２ｍｃ表示，孙影片剪辑实例用ｔｈｉＳ表示。　３结论　通过上面的例子我们可以得出这样的结论，一个动画的　实现可以有多种方法，教师的教学的目的要让学生学会举一　反三，理解并掌握代码的灵活运用。如在上述的目录结构图　若“播放”与“暂停”按钮在孙影片剪辑上，用相对路　径控制各影片剪辑实例“播放”的代码为：　ｏｎ（ｒｅｌｅａｓｅ）｛　中，如果主时间轴下有更多的子影片剪辑实例怎么去编写代　码，如果孙影片剪辑实例在其它影片剪辑下如何去编写代码，　以孙影片剪辑下面如果还有它的下一级影片剪辑实例又如何　ｔｈｉＳ．ｐｌａｙ（）；　（即孙剪辑）动画的播放　／／控制当前影片剪辑时间轴上　去编写代码。在处理实际问题的时候要能够灵活多变，自己　编写出适合的代码，从而做出更优秀的ＦＬＡＳＨ作品。　【参考文献】　ｐａｒｅｎｔ．ｐｌａｙ０：／／控制当前影片剪辑实例的上一层　＿（即子影片剪辑１）实例动画的播放　ｐａｒｅｎｔ．～ｐａｒｅｎｔ．ｐｌａｙ　０：／／控制主时间轴动画的　ｍｃ．ｐｌａｙ　０：　／／控制子影片剪　播放　ｐａｒｅｎｔ．ｐａｒｅｎｔ．ｚ２－【１美国普林斯计算机教育研究中心＼北京金企鹅文化发展　１】中心联合主编．ＦＬＡＳＨ　８中文版精品教程【ｉ　．北京艺术与　科学电子出版社，　辑２实例动画的播放　（上接第４页）　＋　㈣　第三步。　此新拟牛顿算法对一般非凸无约束优化问题具有全局收　敛性。　ＩＢ　，　否则　３小结　爵　－ｒ）　其中　是正常数，且　∈【　ｌ，　２】，０＜　ｌ＜　２　无约束的优化问题在钢铁、电力、医学等方面都有着广　泛的应用，在不同的领域不同的问题上所具备的条件不一样，　就需要我们继续研究探索出计算速度更快、收敛性更好的改　进和成果。随着计算机硬件、软件水平的提高和新型算法的　在此基础上，我们可以把问题（１）的算法设计如下：　第一步：选取初始点ｘ　∈Ｒ　，初始对称正定矩阵　Ｂｌ∈Ｒ…，正常数　，　，￡，　，　，令七：＝１；　出现，ＢＦＧＳ算法问题仍有深人研究的必要，以满足各方面的　需要。　第二步：若　『ｌ＜　，停止迭代；　第三步：　Ｂｋｄｋ＋　：０，确定下降搜索方向　；　第四步：由Ｗｏｌｆｅ搜索准则确定搜索步长　；　【参考文献】　…１李正峰Ｍ邓乃扬．两个修改ＢＦＧＳ算法的收敛性Ⅱ】．高等学　校计算数学学报，１９９６，１８（４）．　ｆ２刘光辉，韩继业．２１结合一种新搜索的Ｂｒｏｙｄｅｎ算法类的全　局收敛性　系统科学与数学，１９９８，１８（１）．　【３】王安平，马烁，赵天玉．一种改进的ＢＦＧＳ算法及其全局收敛　性分析卟河北科技大学学报，２００９，１（３）．　【４】时平平，王希云．基于新拟牛顿方程的拟牛顿法对一般目　标函数的全局收敛性Ⅱ］．太原科技大学学报，２００８，２９（３）．　第五步：令　川＝　＋　否则转第六步；　，若　ｌＩ＜占则停止迭代；　第六步：用公式（１０）校正　得Ｂ　令　：＝　＋１，转　１０．　．