第１９卷 第３期 运 筹 与 管 理 Ｖｏ１．１９，Ｎｏ．３ ２０１０年６月 ＯＰＥＲＡＴＩＯ ＮＳ ＲＥＳＥＡＲＣＨ ＡＮＤ ＭＡＮＡＧＥＭＥＮＴ ＳＣＩＥＮＣＥ Ｊｕｎ．２０１０ 推广的Ｗｏ１ｆｅ搜索下一族共轭梯度法的全局收敛性 范建芬 ， 孔德成 ， 谢铁军。 （１．临沂第四中学，山东２７６０００；２．首都师范大学数学系，北京１０００３７；３．北京科技大学应用科学学院，北京１０００８３） 摘 要：共轭梯度法是求解无约束优化问题的一种重要的方法，尤其适用于大规模优化问题的求解．本文提出一 族包含ＦＲ方法和ＣＤ方法的新的共轭梯度法，证明了其在推广的Ｗｏｌｆｅ非精确线搜索条件下具有全局收敛性． 最后对算法进行了数值试验，试验结果验证了该算法的有效性。 关键词：无约束优化；共轭梯度法；Ｗｏｌｉｆ￣线搜索；全局收敛性 中图分类号：０２２４ 章标识码：Ａ 文章编号：１００７—３２２１（２０１０）０３—００８１—０４ Ｇ ｌｏｂａｌ Ｃｏｎｖｅｒｇｅｎｃｅ ｏｆ ａ Ｃｌａｓｓ ｏｆ Ｃｏｎｊｕｇａｔｅ Ｇ ｒａｄｉｅｎｔ Ｍｅｔｈｏｄｓ ｗｉｔｌｈ ａｎ Ｅｘｔｅｎｄｅｄ Ｗｏｌｆｅ Ｌｉｎｅ Ｓｅａｒｃｈ ＦＡＮ Ｊｉａｎ—ｆｅｎ，ＫＯＮＧ Ｄｅ—ｃｈｅｎｇ，ＸＩＥ Ｔｉｅ・ｊｕｎ （１．Ｌｉｎｙｉ Ｎｏ．４ Ｍｉｄｄｌｅ Ｓｃｈｏｏｌ，Ｓｈａｎｄｏｎｇ ２７６０００，Ｃｈｉｎａ；２．Ｄｅｐｔ ｏｆＭａｔｈ，Ｃａｐｉｔａｌ Ｎｏｒｍａｌ Ｕｎｉｖｅｒｓｉｔｙ，Ｂｅｌｉｔｎｇ １０００３７，Ｃｈｉｎａ；３．Ａｐｐｌｉｅｄ Ｓｃｉｅｎｃｅ Ｓｃｈｏｏｌ，ＵＳＴ Ｂｅｒｉｎｇ，Ｂｅｉｊｉｎｇ １０００８３，Ｃｈｉｎａ） Ａｂｓｔｒａｃｔ：Ｃｏｎｊｕｇａｔｅ ｇｒａｄｉｅｎｔ ｍｅｔｈｏｄ ｉｓ １ ｍｅｔｈｏｄ ｆｏｒ ｓｏｌｖｉｎｇ ｎｏｎｌｉｎｅａｒ ｏｐｔｉｍｉｚａｔｉｏｎ ｐｒｏｂｌｅｍｓ，ｅｓｐｅｃｉａｌｌｙ ｌａｒｇｅ— ｓｃａｌｅ ｐｒｏｂｌｅｍｓ．Ｉｎ ｔｈｉｓ ｐａｐｅｒ ａ ｃｌａｓｓ ｏｆ ｎｅｗ ｃｏｎｊｕｇａｔｅ ｇｒａｄｉｅｎｔ ｍｅｔｈｏｄｓ ｉｓ ｐｒｅｓｅｎｔｅｄ，ｗｉｔｈ ｗｈｉｃｈ ｔｈｅ ｇｌｏｂａｌ ｃｏｎ— ｖｅｒｇｅｎｃｅ ｗｉｔｈ ｇｅｎｅｒａｌｉｚｅｄ Ｗｏｌｆｅ ｌｉｎｅ ｓｅａｒｃｈ ｉｓ ｐｒｏｖｅｎ．Ｆｉｎａｌｌｙ，ｓｏｍｅ ｎｕｍｅｒｉｃ ｔｅｓｔｓ ｈａｖｅ ｂｅｅｎ ｄｏｎｅ ａｎｄ ｔｈｅ ｒｅｓｕｌｔｓ ｓｈｏｗ ｔｈａｔ ｔｈｅ ａｌｇｏｒｉｔｈｍ ｉｓ ｅｆｆｅｃｔｉｖｅ． Ｋｅｙ ｗｏｒｄｓ：ｕｎｃｏｎｓｔｒａｉｎｅｄ ｏｐｔｉｍｉｚａｔｉｏｎ；ｃｏｎｊｕｇａｔｅ ｇｒａｄｉｅｎｔ ｍｅｔｈｏｄ；Ｗｏｌｆｅ ｌｉｎｅ ｓｅａｒｃｈ；ｇｌｏｂａｌ ｃｏｎｖｅｒｇｅｎｃｅ ０ 引言 考虑无约束优化问题（Ｐ）ｍａｘｆ（ ），其中 ）为Ｒ 上的连续可微函数．求解（Ｐ）问题的非线性共轭梯 ＥＲ 度法具有如下迭代格式： ＋１＝ ＋ｄ ｄ （１） ， ｆ—ｇ ，ｋ＝１ ｄ ｉ—ｇＩ＋卢 ｄ —ｌ， ≥２ （２） 其中ｇ ＝ｖｆ（ ），ｄ 为搜索方向。 ｌ＞０是通过某种线搜索计算出的步长，卢 为某种参数，不同的卢 对 应不同的共轭梯度法．著名的卢 公式有 ＪＢ ＝ ： ｇ Ｔ（ｇ —ｇ 一１） 收稿日期：２００９—０３—１８ 作者简介：范建芬（１９８３－），山东临沂人，硕士，主要从事最优化理论方法与应用的研究；孔德成（１９８２．），山东临沂人，硕士，主要从事非 线性发展方程、最优化理论与方法的研究；谢铁军（１９６２一），北京人，副教授，主要从事最优化理论方法与应用的研究。 ８２ 运 筹 与 管 理 ２０１０年第１９卷 卢 ：拿 ， ａｋ１Ｙ‘ １ ：一 ａｋ一１ｇＩ一１ ，ＪＢ ｒ：一 Ｃｔｉｔ一１ＹＩ一１ 这里用ＩＩ・ｌｌ表示欧氏范数，Ｙ㈧＝ｇ 一ｇ 。 步长 的选取应满足一定的搜索条件。推广的Ｗｏｌｆｅ非精确线搜索要求 满足 ＋Ｏｔ ｄＩ）≤ ）＋６ ｄ：ｇＩ ｒｏｌｇ；ｄ ≤ｇ（ ＋ Ｉｄ ） ｄＩ≤一 ２ｇ：ｄ 。＝ ：＝ 时，推广的Ｗｏｌｆｅ线搜索就是强Ｗｏｌｆｅ线搜索。 ＦＲ方法具有较好的理论收敛性（见 ）．ＣＤ方法的收敛性见 （３） （４） 其中０＜６＜ 。＜１， ：为任意非负数。当 ＝ ，ｏｒ ＝＋。。，时，推广的Ｗｏｌｆｅ线搜索就是Ｗｏｌｆｅ线搜索；当 ，其一重要性质是只要强ｗｏⅡｅ 线搜索中的参数ｏｒ＜１，方法在每次迭代便产生一个下降搜索方向．本文为吸收这两种方法的优点提出一 族新的共轭梯度法，其ＩＢ 公式如下 Ｅ 一ＩＪ ｇ ｌ （“ｄ Ｊｒｌｇ 一ｌ—‘ ｌ １ｇＩ—ｌ ｌＪ ） ，ｃ、 —— ＿ 其中 ， ≥０为参数，且“＋ ：１。因为精确线搜索下有：一ｄ ｒ ｇ㈧＝Ｉｌ ｇ Ｊｌ ，所以，精确线搜索下 －－ａｔ ，故方法（１）、（２）和（５）是共轭梯度法。 －本文对目标函数作如下假设： （１），（ ）在 上连续可微有下界； （２ ）的梯度函数ｇ（ ）是Ｌｉｐｓｅｈｉｔｚ连续的，即存在Ｌ＞０，使得 ｆｆ ｇ（ ）一ｇ（ｙ）《≤ —Ｙ ｌｆ，Ｖ ，Ｙ∈Ｒ 本文证明了共轭梯度法（１）（２）（５）在步长 满足：０＜ ＜ 。＜１， ：＝０的推广的Ｗｏｌｆｅ线搜索条件 （３）（４）式时的下降性和全局收敛性． １ 搜索方向的下降性 引理１ 在假设（Ｈ）成立的条件Ｆ，考虑共轭梯度法族（１）、（２）和（５）式，如果步长 满足推厂的 Ｗｏｌｆｅ线搜索（３）和（４），参数取值满足：“，／Ｊ≥０，且 ＋１－＇＝１，０＜艿＜ ＜１， ２＝０。若对任何的ｋ均有 ｇ ＃－０，则 一 ｌｌ ｇ≤ １ 一 ｌ“ （６） 对所有ｋ成立． 证明不妨设对任何的ｋ均有ｇ ≠０．下面用归纳法证明（６）对所有ｋ成立。 ｌ＇故当 ＝ｌ时，（６）成立。 首先，由（２）式得：一 假设对任意尼一・有（６）成立，则此时６ ＝ 垒 兰 鼬（２） 一 小 ≥。 （７） （８） 自（４）（７）（８）式及假 ．一１ｌ ｇ ｌ （ｕｌｄ；一。ｇ 一。—— Ｉ Ｉｇ 一。ｌＩ ）．．ｓ。ｇ 一，ｄＩ一。 ———————— 一 ■ｔ—————————————— —ｉ—————————一ｌｌ ｇ 一。ｌｌ ｄ：～ ｇＩ一。 一ｌ ｌｇＩ ｌ ｌｇ 一，ｄ ｌ＋ ． ≤ 即（６）式第二个不等式对ｋ成立。 另一方面．由（４）（７）（８）式。得 第３期 范建芬，等：推广的Ｗｏｌｆｅ搜索下一族共轭梯度法的全局收敛性 ８３ 一—————＿’＝ｌ—ＩＪＬ————— 一 一｝ｌ ｇ ｌｌ ，引ｌ十ａ Ｌ———————■『Ｉ＝ｌ ｌ ｌｇＩＩ ｌ ｌｇ ｌ ｌ即（６）式第一个不等式对ｋ也成立。证毕。 显然，由引理１中（６）式的第一个不等式，我们可知搜索方向的充分下降条件成立。 ２收敛性结果 引理２ 在假设（Ｈ）成立的条件下，考虑形如（１）、（２）的一般算法，如果ｇ ｄ ≤０， ＞０满足推广 的Ｗｏｌｆｅ准则（３）（４），则有 ｌｌ ｄ下面给出收敛性结果。 一∞ （９） 定理在假设（日）成立的条件下，考虑共轭梯度法族（１）（２）（５）式，如果步长 满足推广的Ｗｏｌｆｅ 线搜索（３）和（４），参数取值满足：“， ≥０，且“＋ ＝１，０＜占＜ｏｒ。＜１，ｒｏ ＝０．则算法产生的迭代点列｛ ｝ 或者对某个ｋ有ｇ ＝０或者有下式成立 ｉｍｉｎｆＩ Ｉｇ Ｉｌ＝０ 证明（１０） 不失一般性，对任何的ｋ均有ｇ ≠０，则由引理１知（６）式成立。从而 ｄ ＜０， ＞０，于是由 引理２知（９）式成立。 对（２）式中ｄ ＝一ｇ ＋ ｄ㈧两边取模方，得 ｌ Ｉｄ ｌｌ ：ｌｆ ｇ ｌ 一２ｌ ｇ ｄ 一。＋ ：ｌｌ ｄ 一。ｌ ｌ（１１） （１２） 由（６）式第一个不等式可得到 将（１１）两边同除以ｌＩ ｇ ｌ ，并令ｆｌ ： ＝一 ÷≤ — ，同时由（４）（５）（７）（１２）式，得 一Ｉ ｌｌ 一Ｉ击ｇ一ｌ ｌ Ｊ 鲁ｌ ｇ ｌ ‘ Ｉ ｇ ｌ ｇ≤音 卢 １ ｇ ｌ （ｌ ｄ：一ｌｇ —ｌ— ｌ ＩｇＩ—ｌ ｌ ）一ｓｌｌｇＩＴ—ｌｄＩ一１ ｇ ～。ＩＩ ｄ ｒｇ 一 一 ｌｌ ｇ ｌ １ ｌｌ ｇ‘ｌ ｌ（１３） ≤—— ｌ ｌｇ ＝ｔｋｌ＋ －＋ｚ（ （・＋二 ）箐一 ＋音（・＋ ） ） 注意到 。＝ ，将（１３）式递推，得 ≤ 由（１４）式及上式，得６ 得 Ｔ ２＝ 一 卉≤ ｔ ≤－…－７ ｌ ｌｇ 『 ｌ（１４） （１５） （１６） 设若定理不真，则必存在正常数 ＞０，使得 ｌ ｌｇ ＩＩ≥ｙ，Ｖ ｋ≥１ ４≥ ≥∑÷≥∑ ＝＋Ｉ≥ Ｉ去≥荟１ Ｉ≥ 芸＝＋∞ ≥ １８４ 运 筹 与 管 理 ２０１０年第１９卷 显然，与（９）式矛盾，进而（１０）式得证。证毕。 ３数值实验 选取如下‘算例对本文提出的公式进行数值试验： 例１ （ ）＝ｌＯＯ［ｘ３一（ ＋ ２） ／４］ ＋（１－ｘ。） ＋（１一 ２） ，初值 ０＝（２，０，２） ，最优解 ‘＝（１，１，１） 。 例２ （ ）：１００（ 一 ）。＋（１一 ）。，初值 。＝（１．４５，１．５） ，最优解 ：（１，１）ＴＯ 侈４ ３ （ ）＝（ｅ 一 ２） ＋１００（ ２一 ３） ＋（ｔａｎ（ ３一 ）） ＋ ，初值 ０＝（２，２，一２，一２） 。 例４ ｆ４（ｘ）＝［１．５一 （１一 ：）］ ＋［２．２５一 。（１一 ；）］ ＋［２．６２５一 （１一 ；）］ ，初值 。＝（１，１） ， 最优解 ＝（３，０．５）Ｔ。 例５ 优解 （ ）＝（ ＋ｌＯｘ２） ＋５（ ３一 ） ＋（ ２＋２ｘ３） ＋１０（ １＋１０ｘ ） ，初值 ０＝（３，一１，０，１） ，最 ＝（０，０，０，０）Ｔ。 侈 ６厂６（ ）＝１００（ 一 ） 一（１一 。） ＋９０（ 一 ；） ＋（１一 。）。＋ｌＯ（ｘ ＋ 一２） ＋０．１（ ：一 ） ， 初值 ＝（１，０，１，０） ，最优解 ＝（１，１，１，１） 。 表１ 参数 函数 （ ） （ ） 在计算过程中取６：１／４， ＝２／５，ｏｒ ＝０，数值试验结果如表１。 精度 本文算法 迭代次数 １０ ０ ｌ０‘ ０ ５７ ２２ ＦＲ方法 迭代次数 ｌ４３ ２３ ＣＤ方法 迭代次数 ２２０ ２３ “． ｕ＝０．５，ｖ＝０．５ ｕ：０．５．ｖ＝０．５ ｌ １ｇ（ Ｉ） ３．５９２１０９ｅ一０ｌ １ ３．０９３９１７ｅ．０ｌ １ ｇ（ Ｉ）ｌｌ ８．８ｌｌ１９５ｅ一０ｌｌ ４．７６０５８６ｅ．０ｌ ｌ ０ ｇ（ ）ｌ １５．９８９３３２ｅ一０ｌｌ ９．４２３４２７ｅ．０ｌ ｌ （ （ ： （ ： （ ： ｕ＝０．５，ｖ＝０．５ １１＝０．４．ｖ＝０．６ ｕ＝０．１．ｖ＝０．９ １１＝０．５．ｖ＝０．５ ｌＯ一 １０—３ ｌ０—３ １０—５ ２７ ９ ７４ ７４ ６．２６６４２ｌｅ．ｏ０３ ３．５６７５３４ｅ ｏｏ４ ７．８８ｌｌ２３ｅ～００４ ５．１１６３５０ｅ，００６ ４２ ｌ６ １Ｏｌ ９５ ４．０７９３９４ｅ．００３ ２．７５８３００ｅ．００４ ８．１３７２４９ｅ．００４ ７．９４７０８６ｅ．００６ ４４ ２ｌ ２２１ ｌｌ７ ９．１９４９２５ｅ．ｏｏ３ ９．５２２４２０ｅ．００４ ８．７７９１４６ｅ．００４ ９．１６１２７１ｅ－００６ 由以上数值试验结果可以看出，本文提出的共轭梯度法数值表现良好，参数“和 的取值对于数值结 果的影响是否具有内在规律是有待进一步研究的问题． 参考文献： ［１］Ｚｏｕｔｅｎｄｉｊｋ Ｇ．Ｎｏｎｌｉｎｅａｒ ｐｒｏｇｒａｍｍｉｎｇ，ｃｏｍｐｕｔａｔｉｏｎａｌ ｍｅｔｈｏｄｓ，ｉｎ：ｉｎｔｅｇｅｒ ａｎｄ ｎｏｎｌｉｎｅａｒ ｐｒｏｇｒａｍｍｉｎｇ（ａｂａｄｉｅ Ｊ，ｅｄ．），Ａｍ— ｓｔｅｒｄａｍ：Ｎｏｒｔｈ・Ｈｏｌｌａｎｄ，１９７０：３７—８６． ［２］ Ｐｏｗｅｌｌ Ｍ Ｊ Ｄ．Ｎｏｎｃｏｎｖｅｘ ｍｉｎｉｍｉｚａｔｉｏｎ ｃａｌｃｕｌａｔｉｏｎ ａｎｄ ｔｈｅ ｃｏｎｊｕｇａｔｅ ｇｒａｄｉｅｎｔ ｍｅｔｈｏｄ［Ｃ］．Ｉｎ：Ｌｅｃｔｕｒｅ Ｎｏｔｅｓ ｉｎ Ｍａｔｈｅｍａｔｉｃｓ， Ｂｅｒｌｉｎ：Ｓｐｒｉｎｇｅｒ—Ｖｅｒｌａｇ，１９８４，１０６６：１２２—１４１． ［３］ Ａ１一Ｂａａｌｉ Ｍ．Ｄｅｓｃｅｎｔ ｐｒｏｐｅｒｔｙ ａｎｄ ｇｌｏｂａｌ ｃｏｎｖｅｒｇｅｎｃｅ ｏｆ ｔｈｅ ｆｌｅｔｃｈｅｒ—ｒｅｅｖｅｓ ｍｅｔｈｏｄ ｗｉｔｈ ｉｎｅｘａｃｔ ｌｉｎｅ ｓｅａｒｃｈ［Ｊ］ ＩＭＡ Ｊ Ｎｕｍ． ｂｅｒ Ａｎａｌ，１９８５，５：１２１～１２４． Ｉｎｓｔｉ・ ［４］ Ｌｉｕ Ｇ Ｈ，Ｈａｎ Ｊ Ｙ，Ｙｉｎ Ｈ Ｘ．Ｇｌｏｂａｌ ｃｏｎｖｅｒｇｅｎｃｅ ｏｆｔｈｅ ｌｆｅｔｃｈｅｒ—ｒｅｅｖｅｓ ａｌｇｏｒｉｔｈｍ ｗｉｔｈ ａｎ ｉｎｅｘａｃｔ ｌｉｎｅ ｓｅａｒｃｈ［Ｍ］ Ｒｅｐｏｒｔｔｕｔｅ ｏｆ Ａｐｐｌｉｅｄ Ｍａｔｈｅｍａｔｉｃｓ，Ａｃａｄｅｍｉａ Ｓｉｎｉｃａ，１９９３． ［５］Ｄａｉ Ｙ Ｈ，Ｙｕａｎ Ｙ．Ｃｏｎｖｅｒｇｅｎｃｅ ｐｒｏｐｅｒｔｉｅｓ ｏｆ ｔｈｅ ｆｌｅｔｃｈｅｒ—ｒｅｅｖｅｓ ｍｅｔｈｏｄ［Ｊ］．ＩＭＡＪ．Ｎｕｍｅｒ Ａｎａｌ，１６（２）：１５５—１６４． ［６］戴或红，袁亚湘．广义Ｗｏｌｆｅ线搜索下Ｆｌｅｔｃｈｅｒ—Ｒｅｅｖｅｓ方法的全局收敛性［Ｊ］．高等学校计算数学学报，１９９６，１８（２）： １４２．１４８． ［７］杜学武，韩伯顺，张连生．包含ＦＲ方法的～类无约束极小化方法的全局收敛性［Ｊ］．运筹学学报，２００４，８（４）：１—９． ［８］陈继红，焦宝聪．一种新的非线性共轭梯度法的全局收敛性［Ｊ］．首都师范大学学报（自然科学版），２００６，２７（３）：１—４ ［９］范建芬，谢铁军，柳娟．一族新的共轭梯度法的全局收敛性［Ｊ］．运筹与管理，２００７，（２）：６７－７２． ［１Ｏ］Ｙｕａｎ Ｙ．Ｎｕｍｅｒｉｃａｌ ｍｅｔｈｏｄｓ ｆｏｒ ｎｏｎｌｉｎｅａｒ ｐｒｏｇｒａｍｍｉｎｇ［Ｍ】．Ｓｈａｎｇｈａｉ Ｓｃｉｅｎｔｉｉｆｃ＆Ｔｅｃｈｎｉｃａｌ Ｐｕｂｌｉｓｈｅｒｓ（Ｉｎ Ｃｈｉｎｅｓｅ），１９９３． ［１ １］Ｄａｉ Ｙ Ｈ，Ｙｕａｎ Ｙ．Ｃｏｎｖｅｒｇｅｎｃｅ ｐｒｏｐｅｒｔｉｅｓ ｏｆ ｔｈｅ ｃｏｎｊｕｇａｔｅ ｄｅｓｃｅｎｔ ｍｅｔｈｏｄ［Ｊ］．Ａｄｖａｎｃｅｓ ｉｎ Ｍａｔｈｅｍａｔｉｃｓ（Ｉｎ Ｃｈｉｎｅｓｅ）， １９９６，２５（６）：５５２—５６２． ［１２］杜学武，叶留青，徐成贤．包含共轭下降法的一类无约束优化方法的全局收敛性［Ｊ］．工程数学学报，２００１，１８（２）：１１９—１２２．
