第３２卷第５期 重庆工商大学学报（自然科学版） ２０１５年５月 Ｖｏ１．３２ Ｎ０．５ Ｊ Ｃｈｏｎｇｑｉｎｇ Ｔｅｃｈｎｏｌ Ｂｕｓｉｎｅｓｓ Ｕｎｉｖ．（Ｎａｔ Ｓｃｉ Ｅｄ） Ｍａｖ．２０１５ ｄｏｉ：１０．１６０５５／ｊ．ｉｓｓｎ．１６７２—０５８Ｘ．２０１５．０００５．００４ 一个修正的三项ＬＳ共轭梯度法 焦佳佳 （重庆师范大学数学学院，重庆４０１３３１） 摘要：基于已有的共轭梯度法的思想，提出了一个三项ＬＳ共轭梯度方法，该方法能保证搜索方向在 不需要任何线搜索下具有充分下降性，并在适当条件下获得此方法对一般函数的全局收敛性． 关键词：共轭梯度法；充分下降性；全局收敛性 中图分类号：０２２４ 文献标识码：Ａ 文章编号：１６７２－０５８Ｘ（２０１５）０５－００１３－０４ １ 基础知识 考虑无约束优化问题： ｍｉｎ ）， ∈Ｒ （１） 其中厂：Ｒ 一Ｒ是连续可微函数．共轭梯度法是求解大规模无约束优化问题（１）的一种有效方法，其迭代格式 如下： ＋１ ＋ ｄ （２） ｄ ＝｛ｃ ３，【一 二ｇｋ ’二＋ ／３ ｋｄ？ｋ 一１，。， ≥ ｋ≥１ 其中ｇ ＝Ｖ ），ｄ 是搜索方向， 是用某线搜索得到的步长， 是参数．不同的参数表达式 对应着不同 的共轭梯度法，著名的有 ，卢：ＲＰ，卢 等．常用的线搜索有ｗｏ 线搜索、强ｗｏ 线搜索、Ａｒｍｉｊｏ－ｔｙｐｅ线搜索 等，其中Ｗｏｌｆｅ线搜索要求 满足 ＾＋ ｄ ）一 ）≤６ ＾ｇＴｄ （４） ｇ（ｘ ＋ ｄ ）Ｔｄ ＞ ｇ ｄ （５） Ａｒｍｉｊｏ—ｔｙｐｅ线搜索要求Ｏｄ 满足 ＋ａｋｄ ）≤ ）一６ ｌＩｄ ｌＩ。 （６） 与其他共轭梯度法相比，ＰＲＰ方法的数值表现是目前认为最好的方法之一，但该方法的收敛性不理想． 研究发现，ＰＲＰ方法收敛性不好的另一个原因在于它不具有充分下降陛．充分下降ｌ生是指对所有的ｋ，式（７） 成立： ｇＴａ ≤一ｃ Ｉ Ｉ（７） 其中ｃ为常数，此性质在收敛性分析中起着非常重要的作用．因此，许多学者都希望找到数值表现可与ＰＲＰ 相媲美同时Ｉ生质又比其好的方法． Ｙｕ，Ｇｕａｎ和Ｌｉ在文献［４］中提出了具有充分下降性的修正ＰＲＰ方法，其公式为 收稿日期：２０１４—０８—１０：修回日期：２０１４—１０—０８． 作者简介：焦佳佳（１９８８一），女，陕西铜川人，硕士研究生，从事最优化方法及其应用研究 １４ 重庆工商大学学报（自然科学版） 第３２卷 卢 ＲＰ＝ ： Ｐ一 ｄ 一 （８） 其中 ＞÷是常数．该方法能保证卢 胛Ｉ＞０，且不依赖于任何线搜索具有充分下降性，所以其数值表现优于 ＰＲＰ方法． Ｚｈａｎｇ等在文献［５］中给出一个三项的ＰＲＰ共轭梯度法，其方向定义为 ｄ ：ｆ＝ｉ—ｇ ， 。曼 ．—ｇ ＋ ｄ 一１—． 一１ｙ 一１， ≥１ （９） ‘９ 其中 ＝ Ｉｌｇ 一１ ＩＩ ，卢ＰＲＰ＝ Ｉ１ｇ 一１ ｌ ｌ，容易得到ｇｘ ｄ ＝一ｌ１ 与三项ＰＲＰ方法类似，具有充分下降性的三项ＬＳ公式定义为 广 ， ＝０ １ 一 ¨ 此方法仅仅利用了梯度值信息，忽略了函数值信息．文献［６］中给出了新的拟牛顿方程： Ｂ ｓ ＝ｙ０１ 其＇ｔｌ Ｙｋ－ １＝ｙ ＋ｔｌｌｇ ¨（ｆ＞０）． 此拟牛顿方程同时含有函数值信息和梯度值信息，且比原拟牛顿方法具有更好的收敛性和数值表现．受 此启发，此处给出一个三项ＬＳ共轭梯度方法，其方向定义为 ｆ—ｇ ， ＝０ ＭＬＳ ｒＤ 一 ｙ 一１口 一ｌ ／ ≥１ Ｌ 其中 ＬＳ： ．可以看出新公式同时含有梯度值信息和函数值信息． ２算法及其全局收敛性分析 为表述需要，称修正的三项ＬＳ共轭梯度算法为ＭＭＬＳ算法，其步骤如下： 步０：给出初值 １∈Ｒ ， Ｉ＞０，令ｄ１＝一ｇ１，ｋ＝１； 步１：若 ＿ｌ≤ ，则停止，否则转步２； 步２：步长Ｏ／ ＞０，由式（６）获得； 步３：令 ＝ ＋ ｄ ，ｇ ＝ｇ（ ），若ＩＩｇ ｌＩ≤８，则停止，否则转步４； 步４：计算 ，利用式（１１）计算ｄ ； 步５：令ｋ： ＋１，转步２． 为了讨论新方法的全局收敛性，假定目标函数满足如下基本假设： 假设（Ａ） 水平集／２＝｛ ∈Ｒ 假设（Ｂ） Ｌ＞０，使得 ）≤厂（ ）｝有界，即存在常数ａ＞０，使得 １ ｌ≤ａ，Ｖ ∈力 （１２） ）在水平集 的一个领域Ⅳ内连续可微，且其梯度ｇ（ ）满足Ｌｉｐｓｃｈｉｔｚ条件，即存在常数 ｌｌｇ（ｘ）一ｇ（ｙ）ｌｌ≤Ｚｌｌｘ—ｙｌｌ，Ｖ ，Ｙ∈Ｎ （１３） 第５期 焦佳佳：一个修正的三项ＬＳ共轭梯度法 １５ 根据上述假设，存在一个正的常数厂，对任意的 ∈１２，都有 （ ）Ｉ】≤Ｆ 成立． （１４） 引理１对后≥０，三项ＬＳ公式的搜索方向满足 ｇ ｄ ＝一１ｌｇ ｌＩ２ 证明如果 ＝０，则ｇ ｄ。＝一ＩＩｇ。 那么式（１５）成立．当 ≥１时，利用新方向的定义可得 （１５） －Ｉｌ ｌｌ ｌ＋ 证毕． 如 一 Ｔ＋ｌ ＿Ｉ ｌｌＩ ｌ引理２如果存在一个常数＿＞０，使得 ＩＩｇ 【ｌ≥ ，Ｖ 则存在一个常数Ｍ＞Ｏ，使得 （１６） ｌＩ ｌｌ≤Ｍ，Ｖ ｋ 证明考虑Ｙｋ 的定义，由式（１３）和（１４）知 （１７） ｌＩｙ０ ｌｌ≤Ｉｌｙ 一。ｌｌ＋ｆＩｌｇ 一 Ｉｌｓ 一。ｌｌ≤ ｌ１ ｓ 一 ｌｌ＋ｔＦ Ｉ ｌｓ 一 Ｉｌ＝（ ＋ｔＦ ）ＩＩ ｓ 一。ｌ Ｉ根据ｄ 的定义，由式（１３）（１４）（１６）和（１８）可得 ＝ ＋ 。＋ （１８） Ｉ［－ｇｋ ２ Ｉ［－ｇｋ ｌｌ＋２ 厂＋ ！ ２ ： ≤ ：！ ≤ （１９） ，＋，＋— ——— ‘ ＿ｌ…ｌｄ－１ｌＩ ｌ由式（６）和假设（Ａ）知 一１ｄ １ 一０（ｋ—｝∞） （２０） 故存在一个常数 ∈（０，１）和一个整数ｋ。，对所有的 ≥ 。有 ： ｙ‘ 。 ｌｄ 一，ｌｌ≤ 。（２１） 因此，对所有的 ≥ 。，由式（１９）和（２１）有 Ｉ≤厂＋占 Ｆ（１＋ ＋ ＋．．・＋ ＋ｓ “ｌｉｄ ＿Ｉ≤ ＋ ＩＩ 令 ｍａｘ｛ｆＩ ｔ ｆｄｚ ～，ｆ 。ｆｆ， １＋『Ｉｄ ｆＩｉ，故『 ｝ｌＩ≤ 。定理１假设（Ａ）和假设（Ｂ）成立，ｄ 由式（１１）确定，０ｃ 由Ａｒｍｉｊｏ－ｔｙｐｅ线搜索获得，￣ｌ］１ｌｉｍｉｎｆｉｌｇ ｌｌ＝０． ．证明如果定理１不成立，则有式（１６）成立・］／ｌ￣：ｌｉｍ ｉｎｆａ ＞０，则由式（１５）和（２０）式有ｌｉ ｎｆＩ ｊＩ＝０，这 与假设矛盾．］ｔＨ：￣：ｌｉｍ ｉｎｆｏｔ ＝０，则存在无限指标集Ｋ，使得 。 １６ 重庆工商大学学报（自然科学版） １ｉｍ ｋＥＫ． —｝∞ 第３２卷 ．‘＝０ （２２） 由算法步骤２可知，当ｋ∈Ｋ充分大时，ｐ－１Ｏｌ 不满足式（６），即 ＋ｐ＿。 ｄ ）一 ）＞一 ＯＺ ＩＩｄ ＿ ｌ（２３） 由中值定理，引理（２），式（１３）和（１５），存在ｈ ∈（０，１），使得 ％＋ｐ－ｉ ｄ ）－Ａ ） ｐ－ｉＯｔ ｇ（ｘ☆＋ ＿。 ｄ ） ｄｋ＝ ｐ－１ｐ Ｏｌ ｄ ＋）－１ｇ 口 十 Ｐ （ （ｇ 十 ＋ｈｋｎｋｐ一ｐ ｄ ）一ｇ ）Ｔｄ一 ｇ ａｋ≤ ｐ－ｐ １Ｏｏｔ ｋｇ 口 十 ＋ ｔｔｏ ｏｔｋ 。ＩＩｄ ａｋｌＩ 再由式（２３），当ｋ∈Ｋ充分大时，有 ｌｌｇ ｌ ≤ｐ－Ｘｌ（Ｌ＋ ） ｌＩｄ ＩＩ 因为｛ｄ ｝有界，１ｉａｒ ＝０，￣１］１ｌｉｍ ｉｎｆｌｌｇ 【ｌ＝０．这与假设矛盾，故结论成立． ＲＥ＾．＾—■∞ ｎ— ∞ ３ 结 论 对于求解大规模无约束优化问题，给出了一种修正的三项ＩＪｓ共轭梯度法，该方法不依赖任何线搜索， 具有充分下降性，并且在Ａｒｍｉｊｏ—ｔｙｐｅ线搜索下证明了该方法的全局收敛性． 参考文献： ［１］ＡＮＤＲＥＩ Ｎ．Ａ Ｄａｉ－Ｙｕａｎ Ｃｏｎｊｕｇａｔｅ Ｇｒａｄｉｅｎｔ Ａｌｇｏｒｉｔｈｍ ｗｉｔｈ Ｓｕｆｆｉｃｉｅｎｔ Ｄｅｓｃｅｎｔ ａｎｄ Ｃｏｎｊｕｇａｃｙ Ｃｏｎｄｉｔｉｏｎｓ ｆｏｒ Ｕｎｃｏｎｓｔｒａｉｎｅｄ Ｏｐｔｉｍｉｚａｔｉｏｎ［Ｊ］．Ａｐｐｌｉｅｄ Ｍａｔｈｅｍａｔｉｃｓ Ｌｅｔｔｅｒｓ，２００８，２１（２）：１６５—１７１ ［２］ＬＩＵ Ｙ，ＳＴＯＲＥＹ ｃ．Ｅｆｉｆｃｉｅｎｔ Ｇｅｎｅｒａｌｉｚｅｄ Ｃｏｎｊｕｇａｔｅ Ｇｒａｄｉｅｎｔ Ａｌｇｏｒｉｔｈｍｓ，Ｐａｒｔ １：Ｔｈｅｏｒｙ［Ｊ］．Ｊｏｕｍａｌ ｏｆ Ｏｐｔｉｍｉｚａｔｉｏｎ Ｔｈｅｏｒｙ ａｎｄ Ａｐｐｌｉｃａｔｉｏｎｓ，１９９１，６９（１）：１２９—１３７ ［３］ＧＩＬＢＥＲＴ Ｊ Ｃ，ＮＯＣＥＤＡＬ Ｊ．Ｇｌｏｂａｌ Ｃｏｎｖｅｒｇｅｎｃｅ Ｐｒｏｐｅｒｔｉｅｓ ｏｆ Ｃｏｎｊｕｇａｔｅ Ｇｒａｄｉｅｎｔ Ｍｅｔｈｏｄｓ ｆｏｒ Ｏｐｔｉｍｉｚａｔｉｏｎ［Ｊ］．ＳＩＡＭ Ｊｏｕｒｎａｌ ｏｎ Ｏｐｔｉｍｉｚａｔｉｏｎ，１９９２，２（１）：２１—４２ ［４］ＹＵ Ｇ，ＧＵＡＮ Ｌ，ＬＩ Ｇ．Ｇｌｏｂａｌ Ｃｏｎｖｅｒｇｅｎｃｅ ｏｆ Ｍｏｄｉｆｉｅｄ Ｐｏｌａｋ—Ｒｉｂｉｅｒｅ－Ｐｏｌｙａｋ Ｃｏｎｊｕｇａｔｅ Ｇｒａｄｉｅｎｔ Ｍｅｔｈｏｄｓ ｗｉｔｈ Ｓｕｆｆｉｃｉｅｎｔ Ｄｅｓｃｅｎｔ Ｐｒｏｐｅ￣ｙ［Ｊ］．Ｊｏｕｒｎａｌ ｏｆ Ｉｎｄｕｓｔｒｉａｌｎｄ Ｍａｎａｇｅｍｅｎｔａ Ｏｐｔｉｍｉｚａｔｉｏｎ，２００８（４）：５６５—５７９ ［５］ＺＨＡＮＧ Ｌ，ＺＨＯＵ Ｗ，ＬＩ Ｄ Ｈ．Ａ Ｄｅｓｃｅｎｔ Ｍｏｄｉｉｆｅｄ Ｐｏｌａｋ—Ｒｉｂｉ￣ｒｅ—Ｐｏｌｙａｋ Ｃｏｎｊｕｇａｔｅ Ｇｒａｄｉｅｎｔ Ｍｅｔｈｏｄ ａｎｄ Ｉｔｓ Ｇｌｏｂａｌ Ｃｏｎｖｅｒｇｅｎｃｅ ［Ｊ］．ＩＭＡ Ｊｏｕｒｎａｌ ｏｆ Ｎｕｍｅｒｉｃａｌ Ａｎａｌｙｓｉｓ，２００６，２６（４）：６２９—６４０ ［６］Ｌ１ Ｄ Ｈ，ＦＵＫＵＳＨＩＭＡ Ｍ．Ａ Ｍｏｄｉｉｆｅｄ ＢＦＧＳ Ｍｅｔｈｏｄ ａｎｄ Ｉｔｓ Ｇｌｏｂａｌ Ｃｏｎｖｅｒｇｅｎｃｅ ｉｎ Ｎｏｎｃｏｎｖｅｘ Ｍｉｎｉｍｉｚａｔｉｏｎ［Ｊ］．Ｊｏｕｒｎａｌ ｏｆ Ｃｏｍｐｕｔａｔｉｏｎａｌ ａｎｄ Ａｐｐｌｉｅｄ Ｍａｔｈｅｍａｔｉｃｓ，２００１（１）：１５—３５ ［７］ＮＡＲＵＳＨＩＮＭＡ Ｙ，ＹＡＢＥ Ｈ，ＦＩＯＲＤ Ｊ Ａ．Ａ Ｔｈｒｅｅ－ｔｅｒｍ Ｃｏｎｊｕｇａｔｅ Ｇｒａｄｉｅｎｔ Ｍｅｔｈｏｄ ｗｉｈ Ｓｕｆｔｉｆｃｉｅｎｔ Ｄｅｓｃｅｎｔ Ｐｒｏｐｅｒｔｙ ｆｏｒ Ｕｎｃｏｎｓｔｒａｉｎｅｄ Ｏｐｔｉｍｉｚａｔｉｏｎ［Ｊ］．ＳＩＡＭ Ｊｏｕｒｎａｌ ｏｎ Ｏｐｔｉｍｉｚａｔｉｏｎ，２０１１，２１（１）：２１２—２３０ Ａ Ｍｏｄｉｆｉｅｄ Ｔｈｒｅｅ－ｔｅｒｍ ＬＳ Ｃｏｎｊｕｇａｔｅ Ｇｒａｄｉｅｎｔ ｍＭｅｔｈｏｄ ＪＩＡＯ Ｊｉａ－ｊｉａ （Ｃｏｌｌｅｇｅ ｏｆ Ｍａｔｈｅｍａｔｉｃｓ Ｓｃｉｅｎｃｅ，Ｃｈｏｎｇｑｉｎｇ Ｎｏｒｍａｌ Ｕｎｉｖｅｒｓｉｔｙ，Ｃｈｏｎｇｑｉｎｇ ４０１３３１，Ｃｈｉｎａ） Ａｂｓｔｒａｃｔ：Ｂａｓｅｄ ｏｎ ｔｈｅ ｅｘｉｓｔｅｎｔ ｉｄｅａｓ ｏｆ ｔｈｅ ｃｏｎｊｕｇａｔｅ ｇｒａｄｉｅｎｔ ｍｅｔｈｏｄ，ｔｈｉｓ ｐａｐｅｒ ｐｒｏｐｏｓｅｓ ａ ｔｈｒｅｅ—ｔｅｒｍ ＬＳ ｃｏｎｊｕｇａｔｅ ｇｒａｄｉｅｎｔ ｍｅｔｈｏｄ．Ｔｈｅ ｐｒｅｓｅｎｔｅｄ ｍｅｔｈｏｄ ｃａｎ ｍａｋｅ ｔｈｅ ｓｅａｒｃｈ ｄｉｒｅｃｔｉｏｎ ｗｉｔｈ ｓｕｆｆｉｃｉｅｎｔ ｄｅｓｃｅｎｔ ｐｒｏｐｅｒｔｙ ｗｉｔｈｏｕｔ ａｎｙ ｌｉｎｅ ｓｅａｒｃｈ．Ｕｎｄｅｒ ｃｅｒｔａｉｎ ｍｉｌｄ ｃｏｎｄｉｔｉｏｎｓ，ｇｌｏｂａｌ ｃｏｎｖｅｒｇｅｎｃｅ ｉｓ ｏｂｔａｉｎｅｄ． Ｋｅｙ ｗｏｒｄｓ：Ｔｈｒｅｅ—ｔｅｒｍ Ｃｏｎｊｕｇａｔｅ Ｇｒａｄｉｅｎｔ Ｍｅｔｈｏｄ；ｓｕｆｉｆｃｉｅｎｔ ｄｅｓｃｅｎｔ ｐｒｏｐｅｒｔｙ；ｇｌｏｂａｌ ｃｏｎｖｅｒｇｅｎｃｅ