第１８卷第１期 曲阜师范 大学学报 Ｖ０１．２８ ＮＯ．１ ２００２年１月 ］ｏｕｒｎａ１ ｎ｛Ｑｕ Ｎｏ｝ｆｎｉａｌ Ｕｎｉｖｅｒｓｉｔｙ Ｊａｎ ２Ｏ０２ 具有性质（＊）的一类共轭梯度法的全局收敛性 胡国芳①， 王海奇②， 屈 彪③ （第一作者：女，２９岁．砸士，讲师；①曲阜师范大学运筹研究所．２７３１６５、山东省曲阜市； ②滩坊师范学校，２６１】∞、山束古椎坊市；＠走连理工太学应用数学系．１１６１）２４，ｉＩ宁省大连市） 摘要：对具有性质（＊）的共轭梯度法进行了讨论该性质是由Ｊ唧 Ｃｈａｒ［凹和Ｊｏｒｇｅ Ｎｏｃｅｄａｌ在１９９２年 提出的Ｙｕｈｏ，￣ｇＤａｉ，Ｊｉｙｅ Ｈａｎ等人也对此进行 ｒ讨论．本文放松了现有结果中参数 ≥Ｏ的限制，井保证在 几种可行的线搜索下共轭梯度算法的全局收敛性 关键词：共轭梯度法；全局收敛性；线捏索 中图分类号：Ｏ２２１ ２ 文献标识码：Ａ 文章编号：１００１—５３３７（２００２）０１—０００１—０４ １ 引 言 考虑无约束最优化问题 ａｒｉｎｆ（ ）， （１．１） ∈ 其中，：Ｒ 一Ｒ 是一阶可微函数，求解（１ １）的共轭群度算法的一般迭代过程是 一’ｋ－１’ ｄ —ｇ； ＋ ｔｉｍ 一 ， ≥２（１ ２） 十Ｉ＝ｚ ＋＾ ， （１ ３） 其中扎是通过某种一维搜索而得到的步长， ：＝ｖｆ（ ）， 为参数． 已有下面著名的公式，它们依次 饺称为Ｆｌｅｔｃｈｅｒ－Ｒｅｅｖｅｓ（ＦＩＲ），Ｐｌｏａｋ—Ｒｉｂｉｅｒｅ（ＰＲ）和Ｈｅｓｔｅｎ￣ｓ—Ｓｔｉｅｆｅｌ（ＨＳ）公式 ＝ｌ ｌｇｋ ＩＩ！／ｌ ｌｇＨ Ｉ ， （１ ４） ＝ （ｇｋ—ｇ｝一１）／ｌ舰Ⅲ１ Ｉ， （１ ５） ＝ｇ Ｔ（懿一 一１）／ 一１ （ 一 一１） （１ ６） 由（１．４）～（１ ６）之一确定的迭代算法（１ ２）～（１．３）依此被称为ＦＲ，ＰＲ和ＨＳ共轭梯度法 在算法中，步长ｋ的选取应满足一定的下降条件，设ｄ 为下降方向，即满足ｇ ＜０，而ｇ盈 ≤ Ｉ Ｉ 称为充分下降条件 Ｗｏｌｆｅ搜索要求步长ｎ满足 ，（ ｝） ，（ ＋ ）≥ ｄ ， （１ ７） ｇ（ 十 ｝） ｄ ≥ｏｇ￣Ｔｄ ， 其中０＜ｐ＜ｄ＜１，而强ｗｌｄｆｅ搜索为式（１．７）和ｇ（ｚ＋ａｄｄＴｄ Ｉ≤一￣ｇ Ｔ也，其中０＜ｐ＜ｄ＜１． Ａｍｉ］ｏ线搜索为＾ 是ｔ＾ Ｉ ＝０，１，２，…｝（０＜ ＜１）满足（１．７）式的最大者． 性质｛＊）考虑形如（１ １）～（１ ２）的迭代算法，假设对任意 ，０＜７≤ｌ ｌｇ Ｉｆ≤７ 在此假设之下，我们称算法具有性质（＊），如果说存在常数ｂ＞１和 ＞０，对任意 ，有 Ｉ Ｉ≤６和Ｉｌ耻１ Ｉ≤ ＩＩ≤ ， 其中ｓ Ｉ＝ ｏ１７Ｈ． 收稿日期：２０ｏｌ一∞一ｏ９ 维普资讯 http://www.cqvip.com
， 曲阜师范大学学报（自然科学版） ２００２年 假设（Ｈ）（Ｌ）水平集Ｊ＝｛ ∈Ｒ Ｉ ，（、ｒ）≤，（ｚ０）｝有界 （２）在＋，的某邻域Ｎ上√（ ）连续可微，其梯度ｇ（ｚ）Ｌｉｐｓｃｈｉｔｚ连续，即存在常数Ｌ＞０，使得Ｊｌ ｇ（ｚ） 一ｇ（ ）ｌ≤Ｌ（ 一＿ｙ），Ｖ ， ∈．， 易见，在假设（Ｈ）之下，ＰＲ算法和ＨＳ算法都具有性质（＊），但对ＨＳ算法，还要求满足充分下降条件和 Ｗｏ Ｌｆｅ条件 ２主要结果 引理一】对于形如（１ １）～（１ ２）的算法．若在第 步 ＞０且 ≠ｏ，则有ＩＩ 一 ≤ ， 其 ＝ ． 引理２对形如（１ １）～（１ ２）的算法，假设算法具有性质（ ），且在假设 ｌｌ≥ 下，有舌＿厂乏Ｉ『＜ ，那么存在＾＞０，使得对任意 Ｃ－Ｎ及任意指标 ０，都存在一指标 ＞ ｏ，使得ｌＫ｛．ｄｌ＞ ，这里 础ｄ：＝｛ｉＣ－Ｊ￣ 七≤ ≤点十△１，ｌ ｌ＿ｌ ｌ｛＞ ， Ｋ｛ ｌ表示Ｋｉ． 中元素的个数，Ｎ表示自然数集下面出现的ｒ ”］表示大于 的最小的整数 证明（用反证法） 假设对 ＞Ｏ，存在△∈Ｎ和Ｋｏ，且对任意 ＞ ０，有Ｉ ． ≤５ －， 因算法具有性质（＊）及ｌ ｇ｝ ≥ ，类似文献［１ 中的引理４ ２得｝Ｉ ｄ ｌ 【≤ｃ（ ０＋２）， 故 Ｔ去１厂 ∞・这与假设条件 １ｒ麦１． ＜∞矛盾一 定理３对形如（１．１）～（１ ２）的算法，若具有下列性质： （ｉ）凤≥０，Ｖ ； （１１） Ｖ ， Ｉ｝∈Ｊ，以≠。，在假设ｌ ｌｌ≥ 之下，有 ］『ｊ ＜ ； （ｉｊｉ）性质（＊）成立． 那么，ｌｉｍｉｎｆｌ１ ：ｏ …证明由条件（ｊ）、（１）及引理１知，ｌ “ —Ｉｌ≤２昔爱昔，假设定理结论不真，则 ｊ ｙ＞０，对任 意 ，ｌ ≥ ，由假设２．１知，ｊ予＞０，Ｖ ≥１， ｇｋ ｉ≤ ，再由条件（ｉｉ）有 善－＝１ －“一“ ≤ｚ Ｉ＝ “— Ｉ Ｉ≤ｚ 毒Ｌ＝ １＿＿ Ｉ“ Ｉ＜ｍ （２ １） 由条件（ｉｊ）及假设（Ｈ）知，存在Ｂ＞０，使 ｆ ｌｌ＜Ｂ，（Ｖ ），对任意两指标 ， （ ≥ ） ＝∑ 一．１ｌ“ ∑ 一Ｉ ¨ ∑ｌｊ ｌ ｌ（ ．一 一．） … Ｉ＝ 因为 ＝１，所以 ∑ 一． ≤ｌｌ 一 ｛１＋∑ ．ＩＩ Ｉ．一“Ｈ ｌ ≤２Ｂ＋∑ 。…“ ｚＱ＿Ｉ （２ ２） 由条件（ｊ）、（ｉｉ）及引理２知，存在＾＞０，定义△：：ｒ毕］，由（２．１）可找到一指标 使得 ｌ １≤ １ －（２ ３） 由引理２知，存在一指标女＞ｈＯ，有埘．。＞ 对任意ｉ∈ ， ＋ —１ ，由（ｋａｕｃｈｖ Ｓｃｗａｒｚ不等式及（２ ３）有 维普资讯 http://www.cqvip.com
第ｌ期 胡苫芳等：具有性质（＊）的一类共轭梯度法的全局收敛性 ３ ｆｆ厂 将 ＝ ＋ 一１代人（２ ２） 由（２ ４）得 ：『｛≥ （ （ ｌ 一 ） ≤ｊ｛（、一 （２ ４） ：『｛≥∑ 一薹。 ．ＪＩ一一∑ 一 蔓 Ｉ．１ ｌＩ一。一一“ ≥㈩ ≥ ∑ 一１ 蓦。 １ Ｉ≥告Ｉ≥｛ ． Ｉ≥≥学 故有 ＜ 这与 的定义矛盾． 上述定理中的（Ｉ）可扩展为 告 ：＝（一（１＋ｅ）可 兰 ，（一ｌ＋ｅ） 明类似于上述定理证明，但需要将引理１换为如下引理 ），。＜ｅ＜１．而证 引理３对于形如（１．１）～（１．２）的算法，如果在第 步有，庳告 ，ｄ ≠０，则有 Ｉ “一“＾ｌ ＩＩ≤ ÷ 证明，其 ＝ 因为ｄ ≠０，故 定义有意义令 可一 — 『＿－ 因为 ＝一 ＋扁 一１ ＩＩ ｄ 一ｌ｜１ …… 一 ＋黼一 ＋ ，， … 俐 …一＝ 一 “卜１，因为．Ｉ“ ＩＩ＝ｌｌ“ —Ｉ ｌｌ＝１，故ＪＩ ＩＩ＝ｌ 一以“ 一】０＝ｌ＿ “ 一“ 一１ｌ ｌｌ，因为 故有 －＋ ＋ ＝－＋ ＝ ＋ ≤ ＋ ≥－＋ ， ≤ ＩＪ （１＋ ）（ 一 Ｈ ≤｛（ “ 一 －Ｊ＋ｌｌ“ 一乱“ 一 ）≤詈ｌｌ“ 故结论成立． 定理４对于形如（１ １）～（１ ２）的算法，若满足如下条件： （ｉ） 在 ，Ｖ｝； （¨） Ｖ ，｛３：ｋ【∈Ｊ，ｄ ≠ｏ，在假设 （ｉｌｉ）性质（＊）成立 Ｉ｝≥ｙ之下可得出∑ ＝Ｉ 则Ｊ Ｉ【１ｆＩＩ １Ｉ＝ｏ 证明利用引理２，引理３，类似定理３的证明即得 弓Ｉｉ里４１ 对于形如【ｌ＿１）的迭代算 是下降方向，步 满足ｗｏ１ｆｅ条 ５么蚤 …＜。。 引理５ 。 对于形如（１ １）～（１ ２）算法，若ｄ 为下降方向，步长 满足强ｗｏｌｆｅ条件，那么或者 ｌｉｍｉｎｆｌ ＿０ 者 廿 推论１对于形如（１ １）～（１．２）的算法，若具有下列发性质： （１ １ 氐 ，Ｖ ；（１１）对任意Ａ．强Ｗｏｈｅ条件和下降条件成立；（１１）性质（＊）成立 则Ｊ ｉ．ＪｆＩ Ｉ Ｉ＝０ 证明只需证定理中的条件（ｉｉ）成立即ＩＩＪ由条件（１１）可知｛ ；∈』，ｄ ≠０．在假设Ｉ ｇ女 ≥７时， 维普资讯 http://www.cqvip.com
曲阜师范大学学报（自然科学版） ２００２ 由引理４及条件（１）知， 可 ＜ 昔 ＜ｏ。，故定理４中的条件（１＿）成立． 由引理４及定理４得 推论２对于形如（１ １）～（Ｌ．２）的算法，若满足 （１） 则ｌｉｍｉｎｆ Ｉ 古△ ，Ｖ ｋ；（１＿）对任意ｋ，Ｗｏｌｆｅ条件和充分下降条件成立；（ｉｉｉ）性质（＊）成立 ＝０ 为任意方向，若 椭足如下搜索 引理６Ｉ 一 对于形如（１．１）的迭代算法， ＝ｓｉｇｎ（一ｇｆｆｄ ）ｍａｘＩ＾ ｌ ｍ＝０，１，…｝ 满足 ，（％）一，（ｚ ＋＾ ）≥ 艘 ｄ ， 其中 ，Ｐ∈（０，１），则对任意ｋ，或者ｆ（ｘｋ）一，（ｊ ＋ 一 ！（２ ５） ）≥ ）≥一可１ ｉ ｇｋ ｄ １，或者，（ ）一，（ （ｇｋＴ ） 川｛ｄ ｆ｝ ，这里 ｌ， ２为正数 由引理６及定理４得 推论３对于形如（１ １）～（１．２）的算法，若下列条件成立： （ｉ） ．古△ ，Ｖ ｋ；（１＇）满足Ａｎｎｉｊｏ线搜索和下降条件；（ｉ Ｊｉ）性质（＊）成立 ｉｎｆ ｇｋ则１ｉｍ Ｉ 【ｌＩ＝０ ．推论４对于形如（１ １）～（１ ２）的算法，若下列条件成立： （１） 且古△ ，Ｖ ｋ； （＿｛）取＾ ＝ｓｉｇｎ（一ｇｋＴｄ ）ｍａｘ｛＾ （ｉｉｉ）性质（＊）成立． 则１＿ｍｊｎ训ｇｋ ＩＩ＝０． ＝０，１，…ｔ满足（２、５）及０ ｇ １＞ Ｉｉ ｇｋ ＩＩ ； 参考文献： ［１］Ｇｉｉｂｅ．￣Ｊｃ，ＮＧｃｅｄａｌ Ｊ．Ｇｌｃｔ￣ 、，ｅｒｇｅｎｃｅｐｒｏｐｅｒｌｉ￣ｏｆ ｃｏ￣｝ｕｇａｔｅｇｒａｄｉｅｎｔｍｅｔｈｏｄｓｈｏｐｔｉｍｉｚａｔｉｏｎ［Ｊ：ＳＩ．￣Ｍ Ｊｏｕｒｎａｌ。ｆＯｐｔｉ— ｎ￣ｚａｌ［ｏｎ，１９９２，２（１）：２１～４２． ［２］Ｐｏｗｅ ｌ Ｍ Ｊ Ｐ．Ｎ。∞ｎｖｅ）【ｍｉｎｉｒａｉｚａｔｌｃｏｌ ｃａｌｃｕｌａｔｉｏｎｓ ａ：１ｄ ｔｈｅ ｃｏｎｊｕｇａｔｅ ｇｒａｄｉｅｎｔ ｍｅｔｈｏｄ［Ａ］Ｌｅｃｔｕｒｅ ｉｎ Ｍａｔｈｅｍａｔｉ￣［Ｄ］ １９８４ １０６６－１２２～ｌ４ｌ ：３］ＹｕｈｏｎｇＤａｉ，ＪｉｙｅＨａｎ，Ｃ．ｍａｎｇｈｕｉ Ｌｉｕ、ｅｔ ａ１．Ｃｏｎｖｅｒｇｅｎｃｅ ｐｒｏｐｅｒｔｉｅｓ ｏｆ ｎｏｎｌｉｎｅａｒ ｃｏｎｊｕｇａｔｅ ｇｒａｄｉｍｔｍｅｔｈｃｄ＇Ｌｊ］ＳＩＡＭｊｏｕｍａｔ ０ｆ Ｏｐｔｉｎｔｉｚａｔｉｏｎ，２０１３１１，１０：３４５～３５８ ＧＬ０ＢＡＬ ＣＯＮＶＥＲＧＥＮＣＥ ＯＦ ＣＯＮＪＵＧＡＴＥ ＧＲＡＤＩＥＮＴ ＭＥＴＨＯＤ ＨＡＶＩＮＧ ＰＲＯＰＥＲＴＹ（＊） ＨＵ Ｇｕｏ－ｆａｎｇＱ，ＷＡＮＧ Ｈａｌ—ｑｉ￣，Ｑｕ Ｂｉａｏ③ （＇Ｔ．）Ｉｎｓｔｉｔｕｔｅ ｏｆＯｐｅｒ￣ｋｍｓ Ｒｅ，ｅａｃｈ，Ｑｕｆｕ Ｎｏｒｍ￣ｌ Ｕｎｉｖｅ￣ｉｔｙ．２７３１６５，Ｑｕｆａ；＠Ｗｅｉｉｆｍｇ Ｎ￣ｒｃｃｍｌ Ｓｏｆｍｏ］，２６１１００，Ｗｅｉｆａｎｇ．Ｓｈａｎｇ＆ｍｇ ③Ｄｅｌ￣ｍａｅｎｔ ＡｐｐｌｉｅｄＭａｔｈｅｒｏ．ａｔｌｍ，ｒ） １¨１１Ｕｒｉｖｅｒｓｉｔｙ ｏｆＴｅｃｈｒｉｄ￣ｇｙ＿１１６０２４ Ｄａ］ｋａｎ．Ｌｉａｏｎ￣ｎｇ．ＰＲＣ） Ａｂｓｔｒａｃｔ：Ｉｎ ｔｈｉｓ ｐａｔｅｒ，ｔｈｅ ａｕｔｈｏｒｓ ｅｘｐｌｏｒｅ ａ ｃｌａ￣ｓ ｏｆ ｏｏｎｊｕｇａｔｅ ｇｒａｄｉｅｎｔ ｍｅｔｈｏｄｓ ｈａｖｉｎｇ ｐｒｏｐｅｒｔｙ（＊） ｗｈｉｃｈ ｈａｖｅ ｂｅｅｎ ｓｔｕｄｉｅｄ ｂｙ Ｊｏｒｇｅ Ｎｏｃｅｄａｌ，Ｙｕｈｏｎｇ Ｄａｉ ａｎｄ Ｊｉｙｅ Ｈａｎ．Ｔｈｅ ａｕｔｈｏｒｓ ｒｅｌａｘ ｔｈｅ ｌｉｍｉｔ ｏｆ ≥Ｏ ａｎｄ ｐｒｏｖｅｄ ｔｈｅ ｇｌｏｂａｌ ｏｏｎｖｅｒｇｅｎｅｅ ｏｆ ｔｈｅ ｃｏｎｊｕｇａｔｅ ｇｒａｄｉｅｎｔ ｍｅｔｈｏｄｓ ｗｉｔｈ ｐｒａｃｔｉｃａｌ ｌｉｎｅ ｓｅａｔｃｈｍ Ｋｅ３ ｗｏｒｄｓ：ｍｎｊｕｇａｔｅ ｇｒａｄｉｅｎｔ ｍｅｔｈｏｄｉ ｇｌｏ￣ｌ ｏ￣ｎｖｅｒｇｅｎｃｅ；ｌｉｎｅ ｓｅａｒｃｈ
因篇幅问题不能全部显示，请点此查看更多更全内容