英语原文共 21 页，剩余内容已隐藏，支付完成后下载完整资料
关于共轭梯度法的总结
摘要：本文对多种非线性共轭梯度算法的发展情况进行总结，并着重分析了各算法的全局收敛性。
关键字：非线性共轭梯度法，无约束优化问题，非线性规划
AMS分类：90C06,90C26,65Y20
1. 介绍。共轭梯度法包含一系列无约束优化算法，具有消耗存储空间小、强局部和全局收敛性的特点。Golub与Olsquo;Leary对共轭梯度法发展历史的总结从Cornelius Lanczos和Magnus Hestenes和其他学者（Forsythe, Motzkin, Rosser, Stein）在数值分析机构的研究工作和Eduard Stiefel在Edig. 的独立研究工作开始。在Hestenes与Stiefel在1952发表的文章中，共轭梯度法作为一种求解对称正定线性优化问题的算法被提出。
文中着重介绍共轭梯度算法在非线性无约束优化问题中的应用：hellip;
其中目标函数为有下界的n元连续可微函数。非线性共轭梯度算法生成一个迭代序列，从给定初始迭代开始，通过迭代公式：hellip;
其中非负步长通过线搜索算法求得，搜索方向由下式求解：hellip;
在这里beta为共轭系数，g定义为目标函数的梯度函数的转置，其中梯度函数为行向量而g为列向量。不同的共轭梯度法对应标量beta选取的不同。
选取欧式范数，定义向量y为g的差值，表1.1按照时间顺序列出了共轭系数选取的不同。1964年Fletcher与Reeves提出的FR共轭梯度法通常被认为是第一个非线性共轭梯度法，这是因为Fletcher与Reeves在提出FR共轭梯度法的文章中着重应用于非线性优化问题，Hestenes与Stiefel在1952提出的HS共轭梯度法着重应用于对称正定线性优化问题。hellip;
Daniel所提出的共轭系数与其他共轭梯度法的共轭系数有着本质上的区别，本文对Daniel所提出的共轭系数不做讨论。对于大规模优化问题，不需要目标函数Hessian阵信息的共轭系数通常比需要的共轭梯度法具有更大优势。在表1.1的剩余共轭系数中，除最新提出的HZ共轭系数，其他共轭系数的分母有三种选取方案，分子有两种选取方案，共组成共轭系数六种不同的选取。
若目标函数为强凸二次函数，而理论上来说，表1.1中的八种共轭系数在精确线搜索下相互等价。而对于非二次目标函数，不同共轭系数可能大相径庭。现今具有最为优越数值表现的共轭梯度法为动态选取共轭系数的混合算法、基于最新提出HZ共轭系数的HZ共轭梯度法。在数值实验报告中，对于CUTEr测试函数集，HZ共轭梯度法具有最为优越的数值表现，排名第二的算法为DY/HS混合算法和L-BFGS算法，并且应用近似Wolfe线搜索的算法具有更为优越的数值表现。
本文着重分析共轭梯度法的全局收敛性，因此，本应讨论的二次终止性在本文中不予讨论。在第二章，本文讨论了基于Wolfe准则的经典线搜索终止准则，并提出Zoutendijk条件。在第三章，本文简略总结了初始搜索方向对全局收敛性的影响。在第四章，本文讨论了其中一种分子所对应的共轭系数的共轭梯度法的全局收敛性。在第五章，本文讨论了另一种分子所对应的共轭系数的共轭梯度法的全局收敛性。第四章中关于全局收敛性的理论比第五章中的理论更为成熟，然而另一方面，第五章中的共轭梯度法通常具有更为优越的数值表现。第六章介绍了通过动态选取第四章和第五章中的共轭系数得到的混合算法。第七章介绍了基于最新提出的HZ共轭系数的HZ共轭梯度法，此算法最突出的理论优势是在一定条件下搜索方向永远是下降方向。第八章共轭梯度法的预处理技术。
2. 线搜索技术与Zoutendijk条件。在共轭梯度法的每一步迭代过程中，选取趋近于局部极小点的步长alpha：hellip;
由于步长非负，搜索方向应当满足如下下降性：hellip;
对任意迭代过程，若存在常数使下式成立：hellip;
则称搜索方向满足充分下降条件。
共轭梯度法的线搜索技术的终止条件通常基于Wolfe准则的一些不同版本。标准Wolfe准则如下：hellip;
其中，搜索方向为下降方向。强Wolfe准则由Wolfe准则中的下降性条件和第二个不等式的加强版本组成：hellip;
广义Wolfe准则将Wolfe准则中的第二个不等式替换为下式：hellip;
广义Wolfe准则是强Wolfe准则的推广。理论上，希望求得满足标准Wolfe准则的步长。然而对于某些共轭梯度法，需要应用强Wolfe准则来保证全局收敛性和增强理论性质。
最近提出的近似Wolfe准则如下：hellip;
其中，近似Wolfe准则的第一个不等式与Wolfe准则中的第二个不等式等价。而第二个不等式在目标函数为二次函数的条件下与Wolfe准则中的下降性条件等价。而对于一般目标函数，近似Wolfe准则中的第二个不等式是下降性条件的二次近似版本。注意到近似Wolfe准则与广义Wolfe准则具有一致的格式，将广义Wolfe准则中选取特定参数可得近似Wolfe准则。
无论是标准Wolfe准则、强Wolfe准则还是广义Wolfe准则，都用于共轭梯度法的全局收敛性。而近似Wolfe准则用于提高计算精度和数值表现，而不涉及全局收敛理论，然而近似Wolfe准则的数值表现通常比其他版本的Wolfe准则更为优越。Wolfe准则中的下降性条件将计算精度限制在机器精度的平方根水平，而应用近似Wolfe准则可以达到机器精度。应用近似Wolfe线搜索技术的算法通常具有更快的收敛速度，这是因为近似Wolfe线搜索算法求解目标函数的局部极小点而标准Wolfe线搜索算法和强Wolfe线搜索算法求解目标函数的一阶近似的局部极小点。
在共轭梯度法的收敛性分析中通常要求下述假设：
Lipschitz连续假设：在水平集的某个邻域中，梯度函数Lipschitz连续，即存在正常数使得下式成立：hellip;
有界性假设：水平集有界，即存在常数使得下式成立：hellip;
现提出Zoutendijk条件，Zoutendijk条件常用于证明共轭梯度法的全局收敛性，最初由Zoutendijk和Wolfe提出。
定理2.1. 在共轭梯度法的任何一步迭代过程中，若搜索方向为下降方向且步长满足Wolfe线搜索条件，当Lipschitz连续假设成立时，下式成立：hellip;
共轭梯度法的全局收敛性的证明常基于Zoutendijk条件和下述条件：
- 满足充分下降条件，
- 存在常数能够控制搜索方向的范数。
则联立Zoutendijk条件与(a), (b)可得：hellip;
共轭梯度法的全局收敛性在本文的定义为迭代至某一步时梯度范数为零或者梯度范数的下极限为零。
另一个关于Zoutendijk条件的结论如下，
定理2.2. 在共轭梯度法的任何一步迭代过程中，若搜索方向为下降方向且步长满足强Wolfe线搜索条件，当Lipschitz连续假设成立时，下两式中必有一式成立：hellip;
注意到在定理2.1和定理2.2中，均假设满足下降性条件和Wolfe准则，而这两项假设互相独立，因此在进行线搜索时，需要满足某个版本的Wolfe准则，并且需要保证生成的搜索方向为下降方向，在最新提出DY共轭梯度法中，下降性条件在Wolfe线搜索下自动满足，并且最新提出的HZ共轭梯度法满足充分下降条件。
3. 初始搜索方向。选取负梯度方向作为共轭梯度法的初始搜索是必要的。Crowder和Wolfe在1972年举例说明，即使对于强凸二次函数，若初始搜索方向不是负梯度方向，共轭梯度法的收敛速率仅仅为一阶的。Powell在1976得出更强的结论，若目标函数为凸二次函数，且初始搜索方向为随机方向，则共轭梯度法要么在有限步内收敛要么收敛速率仅仅为一阶的。更进一步，通过分析初始迭代点与初始搜索方向之间的关系，可以得出一阶收敛速率比有限步收敛更常出现。
为了使共轭梯度法在任意初始搜索方向下有限步收敛，Nazareth提出如下三项搜索方向迭代公式：hellip;
其中初始迭代方向为随机下降方向。若目标函数为凸二次函数，则对于任意步长，上述迭代公式生成的搜索方向相对于目标函数的Hessian阵共轭。然而，这个迭代公式在实际计算中并没有显著使用。
4. 其中一种分子的共轭系数对应的共轭梯度法。FR共轭系数、DY共轭系数和CD共轭系数具有相同的分子。这类算法与其他算法一项理论上的区别是这类算法的全局收敛性仅要求Lipschitz连续假设而不要求有界性假设。最早的关于FR共轭梯度法的全局收敛性的结论有Zoutendijk在1970年提出，他证明精确线搜索下的FR共轭梯度法具有全局收敛性。Powell在1977年指出精确线搜索下的FR共轭梯度法有受阻的嫌疑，即FR共轭梯度算法会产生数步对优化结果无显著贡献的小步长，FR共轭梯度法较差的数值表现通常被认为是此受阻现象导致的。
最早的关于非精确线搜索下的FR共轭梯度法的全局收敛性的结论由Al-Baali在1985提出。在sigmalt;0.5的强Wolfe线搜索下，Al-Baali证明FR生成满足充分下降条件的搜索方向，并给出如下精确结论：hellip;
最终，在Zoutendijk条件的基础上建立了全局收敛性。然而当sigma=0.5时搜索方向不一定满足充分下降条件。
Liu等人将Al-Baali所建立的全局收敛性理论扩展至sigma=0.5的情形。Dai与Yuan更进一步指出，在FR算法的迭代过程中，至少有一步迭代过程生成的搜索方向满足充分下降条件，即：hellip;
由于搜索方向满足下降性条件，最新的定理2.2也可用于推导sigmalt;0.5的强Wolfe线搜索下的FR共轭梯度法的全局收敛性。
Dai与Yuan提出，即使对于强凸二次函数，sigmagt;0.5的强Wolfe线搜索下的FR共轭梯度法所生成的搜索方向不一定满足下降性条件。因此必须要求Wolfe参数sigmalt;0.5以满足下降性条件。在实际使用Wolfe准则时，要求sigma趋近于1通常是效率最高的。因此sigmalt;0.5的约束严重限制了线搜索参数的选取。另一方面，Dai与Yuan指出一些情形下可以使用负搜索方向作为搜索方向，另一些情形下，可跳过搜索点的迭代过程。若梯度的范数有上界，则在Lipschitz连续假设下，标准Wolfe线搜索下的FR共轭梯度法在Dai与Yuan提出的改进下全局收敛。
强Wolfe线搜索技术可放宽为广义Wolfe线搜索技术，当广义Wolfe线搜索参数之和小于一时具有全局收敛性。而在强Wolfe线搜索技术中，只需要求sigmalt;0.5。因此广义Wolfe线搜索参数之和小于一的条件比sigmalt;0.5的条件要弱。
Fletcher提出的CD共轭梯度法与FR共轭梯度法具有密切联系，在精确线搜索下CD共轭系数与FR共轭系数等价。CD共轭梯度法与FR共轭梯度法之间一项重要的全别是，强Wolfe线搜索下的CD共轭梯度法具有全局收敛性而不需要FR共轭梯度法的sigmalt;0.5条件。更进一步，对于特定参数的广义Wolfe线搜索，CD共轭系数小于等于FR共轭系数。因此，通过定理2.2可得全局收敛性。另一方面，对于广义Wolfe线搜索参数的一些特定取值，Dai与Yuan构造搜索方向的范数指数级增长的测试函数，此时CD共轭梯度法收敛于梯度不为零的点。在一些特殊情况中，强Wolfe线搜索下的CD共轭梯度法可能不收敛于稳定点。
DY共轭梯度法与CD共轭梯度法或FR共轭梯度法有着本质上的区别。在标准Wolfe线搜索下，DY共轭梯度法所生成搜索方向必定满足下降性条件。更进一步，当Lipschitz连续假设成立时，DY共轭梯度法具有全局收敛性。Dai进一步分析DY共轭梯度法后提出下述重要性质，将DY共轭梯度法生成的搜索方向的下降性与充分下降条件联系在一起。
定理4.1. 考虑任意使搜索方向为下降方向的线搜索下的DY共轭梯度法，若梯度函数的范数具有上下界，则下述充分下降性条件成立：hellip;
在分析DY共轭梯度法的过程中，Dai与Yuan也建立了关于全局收敛性的理论，将共轭系数表述为如下形式：hellip;
FR共轭系数对应于上式一种特殊情形，DY共轭系数可表述为下述形式：hellip;
因此，DY共轭系数具有上式得另一种形式，得出如下结论。
定理4.2. 考虑任意共轭梯度法，其中共轭系数具有上述格式，搜索方向满足下降性条件，Lipschitz连续假设成立，并且下式成立：hellip;
则该共轭梯度法全局收敛。
上述定理可推出，标准Wolfe线搜索下的DY共轭梯度法具有全局收敛性，这是因为：hellip;
sigmalt;0.5的强Wolfe线搜索下的FR共轭梯度法具有全局收敛性，这是因为：hellip;
5. 另一种分子的共轭系数对应的共轭梯度法。尽管对前一种分子的共轭系数对应的共轭梯度法的全局收敛性已有相对成熟的理论分析，之前已指出这些算法都存在受阻的嫌疑，即这些算法会产生数步对优化结果无显著贡献的小步长。PRP共轭系数、HS共轭系数和LS共轭系数具有相同的分子，并且具有重开始性来解决受阻问题：当迭代至某一步产生一个小步长时，下一步生成的共轭系数自动趋于零。因此，下一步的共轭系数变小使得下一步生成的搜索方向趋近于负梯度方向。在这种意义上，PRP共轭梯度法、HS共轭梯度法和LS共轭梯度法自动调节共轭系数来解决受阻问题。在实际计算中，这些算法的数值表现通常比前一种分子的共轭系数对应的共轭梯度法的数值表现更加优越。
当目标函数为强凸函数并且采用精确线搜索时，PRP共轭梯度法具有
全文共6231字，剩余内容已隐藏，支付完成后下载完整资料
资料编号：[11760]，资料为PDF文档或Word文档，PDF文档可免费转换为Word
以上是毕业论文外文翻译，课题毕业论文、任务书、文献综述、开题报告、程序设计、图纸设计等资料可联系客服协助查找。
