一类修正的Perry共轭梯度法及其全局收敛性

1、一类修正的Perry共轭梯度法及其全局收敛性摘要 本文提出了一种包含了Perry共轭梯度法的修正形式的新共轭梯度法. 该方法确保了在精确线搜索下的充分下降的独立性. 本文所提方法的一个重要性质就是，通过使用一个新的正割条件，在逼近目标函数的二阶曲率信息时具有高阶准确性. 此外，我们所给的方法对于满足Wolfe线搜索条件的一般函数具有全局收敛性. 我们的数值实验表明，就效率和鲁棒性而言，所提方法总体上比经典的共轭梯度法更具适用性. 关键词：无约束优化；共轭梯度法；充分下降性；混合割线方程；全局收敛性1 引言 考虑一个无约束优化问题 (1)其中是上的一个光滑的线性函数，其梯度记为.求解问题（1），

2、共轭梯度法在效率上是一个很好的选择，尤其是共轭梯度法对于大规模问题有低存储和收敛性的特点. 一般而言，一个非线性共轭梯度法从初始点开始，产生一组点列，使用如下的迭代格式 （2）其中是（1）式解的第步逼近；是由某个特定的非线性搜索得到的步长；是搜索方向，定义如下 （3）且是标量. 在所参阅的文献中已经提出过几类，并由此而产生具有相当高计算效率与收敛性质特特点的共轭梯度法.经典的公式包括HS，FR以及PRP.本文中，我们重点是Perry法，其参数是 （4）其中,.该种共轭梯度法基于的是拟牛顿法的思想，在关于无约束优化问题的文章中，已被公认为是最有效的方法之一. 在过去的十几年里，专家学者们都致力于

3、有高计算效能和强收敛性特性的新共轭梯度法的发展. 特别是，诸多研究人员基于割线方程提出新的共轭梯度法，其在逼近二阶曲率信息时具有高度准确性.在合适的条件下，这些方法都是具有全局收敛性的，且有时候数值实验的效果比经典的共轭梯度法还要好. 但是，这些方法并没有满足充分下降条件. 因此，在他们的分析和应用中开始新的研究以得到保证收敛性的新算法. 袁亚湘和戴彧虹等考虑了提出了一不同的方法提高共轭梯度法的数值实验效能. 他们所提出的共轭梯度法在Wolfe线搜索条件下产生了新的下降方向. 基于这个想法，Zhang等人考虑去修正按如下方式修正搜索方向： （5）如此就满足充分下降条件.他们的方法所具有的比较吸

4、引人的一个性质就是满足了，独立地线搜索和的选择.此外，（5）式中的由其他已有的共轭梯度法公式所确定，我们就可以得到相关修正的共轭梯度法，参见文献16,17,19,31,44-46.近来，研究人员特别关注杂合上述两种方法以得到拥有良好数值实验效果和强收敛性的方法. 进一步分析，已提出的新共轭梯度法包含了产生下降方向，避免由此而来的常见的低效重启这些好的特质. 这些方法已经表现出全局收敛性以及理论上比经典方法更具优势，通过新修正的割线方程在逼近最小函数的曲率中展现出了更高精确度. 作者展现了一些数值结果来说明他们所提方法的计算效能与鲁棒性. 沿着这个方向，我们提出一种新的共轭梯度法，该方法保证了充

5、分下降性与线搜索独立精确性. 通过使用一新的混合割线条件，我们所提出的方法在逼近目标函数的二阶曲率信息上表现出更高的精确度. 而且，在Wolfe线搜索条件下的全局收敛性也得到保证. 我们的实验结果也证明了所提方法的计算效能和鲁棒性. 本文以下部分的内容这样安排：第二节，给出我们的目标和所提共轭梯度法. 第三节，给出全局收敛性分析. 第四节，使用文献18中性能选项陈列数值实验. 第五节. 给出我们的总结性结论. 2 修正的perry共轭梯度法在本节，我们再次说明，对于拟牛顿法，Hessian阵的近似矩阵是变化着的，所以一个新的矩阵满足如下割线条件 , （6）在现有的迭代中，标准的割线方程（6）只

6、使用了可得到的梯度信息并且忽视了函数值. Zhang等人以及Xu扩展了割线方程（6），得到了一个修正的割线条件，即在两个连续点处既包含梯度也包含函数值，具体如下 （7）其中 （8） 且是一个满足的向量参数. 注意到为了让目标函数是二次的，其应当满足. 那么，修正的割线方程（7）降为标准的割线方程（6）. 此外，修正的割线方程（7）的理论优势可以从下面的定理中看出. 定理1 假定函数足够光滑且充分小，则下面两个无穷小关系是成立的. 很明确，定理1表明了修正的割线方程（7）优于经典的割线方程（6），因为比更好地逼近了. 近来，Babaie-Kafaki等人7发现的特征值比1大（如），标准的割线方程

7、（6）在预期上比割线方程（7）更精确. 为了解决这个不足，该文作者考虑了割线方程（7）的一种扩展形式，如下： （9）其中参数且通过设定时，其他情况下，使参数可在（6）与（9）式之间转换. 本文中，也提出了几种向量参数的选择，该参数可以产生不同计算效率修正形式的割线方程. 首先，Zhang和Xu43以及之后的Yabe和Takano39提出了和两种参数的选择形式. 此处，为了应用上39,43中关于修正割线方程的有趣性质，我们考虑向量参数作为向量的凸集组合而提出一种混合这些方程的形式，如： . （10）注意到，在7中之前方程中的将（9）变为了修正的割线方程. 因此，我们提出的混合割线方程可以考虑为7

8、中所示修正的割线方程的一种拓展形式. 接着，受到文献4,10中观点的启发，我们提出一种适应性公式来计算,是基于Li和Fukushima27所提出的修正形式的割线方程. 为了提高我们的混合割线方程的精度，是通过使用两个之前步骤信息而计算出来的. 更特别的是，可根据割线方程（9）来计算，在第迭代时，如下形式的修正割线方程应当满足： （11）其中其中，,是一个正常数. 将（11）式与做内积并利用修正的割线方程（9），在经过几步简单的代数运算之后，我们就可以得到 （12）其中，而 （13）注意到（13）中的分母通常是不为0的，否则（9）式就表示使用了经典的割线方程（6）. 此外，为了在（10）中得到一

9、个凸组合，我们把的特征值限定于0，1之间，也就是说如若我们就令；若,就令. 接下来，考虑修正的割线方程（9）的理论优势和29，30，40，41中的Perry共轭梯度法计算效率做比较. 我们提出的Perry公式的一种修正形式如下： （14）这里，由（8）式和（9）式定义. 进一步地，为了保证我们所提方法会产生下降方向，我们使用47中德修正FR共轭梯度法的想法. 更特别的是，搜索方向由下定义 （15）很容易就能看出，使用任何线搜索都能满足 （16） 若目标函数是一个严格凸二次函数，且步长由精确线搜索确定，那么我们就有且.因此我们的公式（14）降为含线性共轭梯度法框架的Hestenes-Stiefe

10、l公式. 而且，为了对一般函数也具有全局收敛性，我们用类似于22中Gilbert和Nocedal的方法，通过令 （17）限制公式的最小值. 下面，我们给出所提修正Perry共轭梯度法（MP-CG）的算法. 算法21（MP-CG）Step 1：初始点,且；令.Step 2：如果，则停止；否则，转Step3.Step 3：用方程（15）计算下降方向.Step 4：使用Wolfe线搜索 （18） （19） 确定一个步长.Step 5: 令.Step 6: 令，转Step 2.注1 在算法21中，因为（15）中的变更的参数是由方程（17）计算出来的，我们称之为算法.此外，因为线搜索满足（18）和（19

11、）的Wolfe线搜索条件，这就可以知道对任意的，,这表明公式（14）与（17）的定义是可行的. 3 全局收敛性在本节，我们基于以下对目标函数的假设，给出所提算法的全局收敛性分析. 假设1 水平集是有界的，即，存在一个正常数，使得 （20）假设2 在的某个领域内，是可微的，其梯度满足李普希茨连续，即存在一个正常数，使得 , （21）因为是一个下降数列，那么由算法MP-CG产生的点列包含于之中，且存在一个常数使得且，其满足假设1和2，存在正常数使得 . （22）为了更好的说明收敛性分析，先阐释如下的引理. 引理17. 如果假设1和2 对方程（9）定义的成立,我们就有 （23）下面一个引理是满足Wo

12、lfe线搜索条件（18）和（19）的共轭梯度法的一个通用结论. 引理2 如果假设1和2成立. 考虑形式（2）的任何方法，其中是一个下降方向，使得且满足Wolfe线搜索条件（18）和（19），那么.显然，从引理2和（16）就可以得到 , （23）该式对全局收敛性的分析相当有益. 接着，我们对统一形式的凸函数形成算法MP-CG的全局收敛性. 定理2 假定假设1和2 都成立，且是一致凸的，也就是说存在一个常数,使得 （24）如果点列是由算法MP-CG所产生，那么可知，对于某个要么成立，要么成立. 证明：假设对任意的，恒成立. 那么证明就可分为三步：Step 1.首先，我们给估计一个较小的边界. 从假

13、设（24）的凸性以及方程（9），我们有 （25）Step 2.对于，我们得到一边界. 结合引理1与关系式（20），（25），我们得到 （26）Step 3.我们给出的一个上界. 利用（15）和（16），我们可知在方程（23）中插入的上界，则，证毕. 接下来，我们展示算法对一般非线性函数的全局收敛性. 首先，我们给出一个引理即，渐近地，搜索方向缓慢改变. 引理3 如果假设1和2成立，令和是由算法产生的点列，如果存在一个常数，使得 （27）则且其中证明 首先，记，否则（16）就会导出.因此，就有了定义. 现定义 （28）其中，接着，通过方程（15），我们有 （29）使用该关系式，其中明确了,且有此

14、外，使用该式需先明确,我们可以得到 （30）紧接着，我们给估测一个上界.注意到 （31）根据Wolfe条件（19），我们可以得到通过重排之前的不等式，我们可得到同（31）式一起，我们有 （32）另外，其在方程（29）、引理1和关系式（20），（22），（23）遵循的定义，即存在一个常数，使得因此，我们就可建立的一个上界. 通过关系式（23），（28），（33）以及（35），我们能得到至此，证明完成. 接下来，我们给出一个引理，该引理可以表明当步长很小，这也就表明算法MP-CG不会出现无效率的干扰现象36时，也会很小. 这个性质与性质（*）相似但有一点不同，即它源于Gilbert和Nocedal

15、22.引理4 如果假设1和2成立. 令和是由算法产生的点列，如果存在一个常数，使得方程（35）成立. 那么就存在常数且使得对所有的 （34）而且 （35）证明. 使用关系式（9），（16）和（19），我们可以得到用上述不等式以及（9），（22）和（35），我们可以得到 （36）因此，通过设定以及，我们就能有关系式（34）和（35）成立，至此也就完成了证明. 从方程（17）中的定义可以看出，对任意的，成立. 所以，对于算法，我们就能得到引理4中的相同结果. 接着，使用引理3和4，我们建立算法的全局收敛性定理，其证明过程与文献24中的定理3.2相似，我们在此再展示一遍以表示文章的完整性. 定理3 若假设1和2成立. 是算法得到的点列，那么我们就能有 （37）证明 我们使用放缩的方法来处理. 假定结论（37）不正确，也就是说，存在一个常数使得对所有的均有成立. 证明过程分为一下几个步骤. Step1.步长是有界的. 观察到，对任意的，都有根据假设1以及三角不等式，我们有 （38）记是一个正整数，且足够大使得 , （39）其中和分别由（20）和（34）定义. 根据引理3，我们可以选择足够大使得 （40）对任意的且，使用（40）式以及可喜