非线性共轭梯度法的文献综述

非线性共轭梯度法的文献综述研究摘要：共轭梯度法最早是由Hestenes和Stiefel于1952年提出来的，用于解正定系数矩阵的线性方程组，在这个基础上，Fletcher和Reeves于1964年首先提出了解非线性最优化问题的共轭梯度法。由于共轭梯度法不需要矩阵存储，且有较快的收敛速度和二次终止性等优点，于是，共轭梯度法的理论研究受到了人们的关注，现在共轭梯度法已经广泛地应用与实际问题中。 关键词：共轭梯度法，非线性最优化，线性搜索，收敛性1.共轭梯度法 共轭梯度法最早是由计算数学家Hestenes和几何学家Stiefel在20世纪50年代初为求解线性方程组而独立提出的。他们奠定了共轭梯度法的基础，他们的文章详细讨论了求解线性方程组的共轭梯度法的性质以及它和其他方法的关系。当对称正定时，上述线性方程组等价于最优化问题 基于此，Hestenes和Stiefel的方法可视为求解二次函数极小值的共轭梯度法。1964年，Fletcher和Reevse将此方法推广到非线性优化，得到了求一般函数极小值的共轭梯度法。 而本书中，戴彧虹和袁亚湘介绍了多种类型的共轭梯度法，各方法的区分主要在于每次迭代的方向上，并且他们检验了每种方法在不同搜索下的全局收敛性。在他们的研究中，目标函数连续可微有下界，导数满足Lipschitz条件，他们通过对Zoutendijk条件的判断，通常用反证的方法来考察全局各共轭梯度法的全局收敛性问题。 对于无约束优化问题 一般给出一初值，经由算法迭代产生。在第k次迭代，当前迭代点为，用一种方法产生一搜索方向。然后下一迭代点为：其中，迭代方向的不同选取产生了不同的共轭梯度法，为步长因子，步长的不同选取产生了不同的搜索准则。而本书着重研究各方法在精确线搜索，Curry原则，强Wolfe线搜索和推广的Wolfe线搜索下的收敛性。其中：精确线搜索要求每次迭代的步长满足：Curry原则要求每次迭代的步长为一维函数的第一个极小点。强Wolfe线搜索要求每次迭代的步长满足：其中，。推广的Wolfe线搜索要求每次迭代的步长满足：其中。而迭代方向一般为： 可知迭代方向的不同由产生，故的不同选取产生的各种共轭梯度法，戴彧虹和袁亚湘介绍了如下方法，有：Fletcher和Reeves在1964年求解线性方程组推广而得的共轭梯度法，简称FR方法。Polak和Ribiere和Polyak在1969年独立提出的一种非线性共轭梯度法，简称PRP方法。Hestenes和Stiefel给出的另一种HS方法。Fletcher在1987年引入的共轭下降法，简称为CD方法。戴彧虹和袁亚湘在1995年提出的新的共轭梯度法，简称为DY方法。本书中给出了各种方法在不同搜索标准下的收敛性条件和全局收敛证明。2.全局收敛性及条件 全局收敛性保证了算法从任何初始点开始都可以找到满足任意精度的近似解。所以最优化方法的收敛性是算法领域最基本的问题之一。本书中，戴彧虹和袁亚湘着重研究了不使用重新开始技术的共轭梯度法的全局收敛性，而他们研究的方法，因为有着不同的修正公式，以及不同的搜索策略，故而有不同的收敛性质。下面分别介绍这些方法。2.1 FR方法 FR方法中，的选取按公式： 早期对于FR方法的分析是基于精确线搜索。Powell在精确线搜索下分析了FR方法可能连续产生小步长的性质，而FR方法的这种可能连续产生许多小步长的性质，在很大程度上也解释了为何FR方法在数值计算中有时表现得很差。但Zoutendijk证明了采取精确线搜索的FR方法对一般非凸函数总收敛。 由于精确线搜索在每步迭代时的难以操作性，实际计算中通常使用非精确线搜索。1985年，Al-Baali证明了使用参数的强Wolfe线搜索的FR方法必满足充分下降条件，且全局收敛。Liu、Han、和Yin将Al-Baali的结果推广到了。戴彧虹和袁亚湘通过考虑相邻两迭代点列的技巧，发现只要FR方法的每个搜索方向下降，则任意两个相邻迭代点列中至少有一个使得充分下降条件成立，从而证明方法全局收敛。由于的强Wolfe线搜索能保证FR方法在每一迭代点列产生一个下降方向，因此的强Wolfe线搜索下FR全局收敛。但若，戴彧虹和袁亚湘给出了反例，即无法保证FR方法的全局收敛性。此外，戴彧虹和袁亚湘提出了广义线搜索下的FR方法，并证明了采用广义Wolfe线搜索或广义Armijo线搜索的FR方法全局收敛。2.2 PRP方法和HS方法 PRP方法中，的选取按公式： PRP方法是目前认为数值表现最好的共轭梯度法之一。当算法产生一个小步长时，由PRP方法定义的搜索方向自动靠近负梯度方向，从而有效避免了FR方法可能连续产生小步长的缺陷。由此，Powell证明了当步长趋于零时，PRP方法全局收敛，且采用精确线搜索的PRP方法对一致凸函数全局收敛。但对一般非凸函数，Powell举出了三维情况下的反例，表面即使按Curry原则选取步长因子，PRP方法可能在六点附近循环，且任意一点都不是目标函数的稳定点。 当n=2时，Powel证明了采取Curry准则的PRP方法对一般非凸函数的收敛性。由于当线搜索精确且n=2时，Broyden凸簇拟牛顿法会产生和PRP方法完全相同的点列，戴彧虹利用了Powell提出的二维例子，说明了采取Wolfe非精确线搜索的Broyden凸簇拟牛顿法对一般非凸函数不必收敛。 如果使用非精确线搜索如强Wolfe线搜索，戴彧虹举出例子表明，即使一致凸，而且参数充分小，PRP方法都有可能产生一个上升搜索方向。进而，如果要求每一搜索方向都下降，则采取非精确线搜索的PRP方法对凸函数收敛。对一般非凸函数，Powell建议限制PRP方法中的参数为非负。 避免当很大时，相邻两搜索方向会趋于相反。Gilbert和Nocedal考虑了Powell的上述建议，并在适当的搜索条件下，建立了上述修正PRP方法对一般非凸函数的全局收敛结果。 然而，Gilbert和Nocedal也举出例子表明，即使对于一致凸的目标函数，也可能为负。于是，Grippo和Lucidi设计了一种Armijo型的线搜索，即每次迭代步长满足：并证明了原始PRP方法在该线搜索下，对一般非凸函数全局收敛。根据Armijo型线搜索下的性质，可得出存在一个常数，满足每次迭代的步长均大于此常数。由此给出新的性质，即取常数步长因子的PRP方法在每次迭代都产生一个下降方向，并且全局收敛。 HS方法中，的选取按公式： 与PRP方法相比，HS方法的一重要性质为共轭关系式：。不论线性搜索是否精确，总是成立。但HS方法的理论性质和计算表现与PRP方法很类似。戚厚铎等考虑了修正的HS方法：并在无充分下降条件下，建立了方法的全局收敛性。2.3 CD方法 CD方法中，的选取按公式： CD又称共轭下降法，由Fletcher在1987年引入。CD法一个很重要的性质为：只有强Wolfe条件中的参数，方法在每次迭代便产生一个下降搜索方向，这与FR方法和PRP方法不同，因为FR方法和PRP方法在这时对一致凸函数都有可能产生一个上升搜索方向，如2.1和2.2中所述。采取强Wolfe非精确线搜索的共轭梯度法，只要每个搜索方向下降，即可保证收敛性。故这一结论为CD方法的收敛性分析提供了一个非常有力的工具，不过采取强Wolfe非精确线搜索的CD方法，无法保证其全局收敛性。 对于推广的Wolfe线搜索，若参数满足。可得到。类似于FR方法中的收敛性证明，可以看出，当满足参数满足上述式子时，CD法必全局收敛。相反的，若参数满足，可构造出例子，使得CD方法收敛于一个非稳定点，表明是必要的。若参数满足，戴彧虹和袁亚湘发现，这时可能以指数级数增长。由此，他们给出一般性证明，表面对任意正常数，满足推广的Wolfe线搜索的CD方法不必收敛。此外，戴彧虹和袁亚湘构造了一个凸二次函数的反例。表明是必要的。 由上可见，虽然一般参数的强Wolfe条件即可保证CD方法在每步产生一个下降搜索方向，但CD方法的收敛性质并不好。此外，当线搜索精确时， 由2.1已FR方法的若干缺陷可知，CD方法有着和FR方法同样的数值缺点，即可能连续产生许多小步长而不恢复。CD方法在实际的数值表现中与FR方法相差不大。但对CD方法的研究，找到了一种新的共轭梯度法。2.4 DY方法 DY方法中，的选取按公式：的选取是在CD方法的研究中得到的。CD方法在强Wolfe线搜索时的收敛性质不佳。为解决这个问题，即希望每次总能产生一个下降方向。戴彧虹和袁湘江降低了线搜索条件，在Wolfe线搜索下研究了共轭梯度法。 由上所述，每次总是产生一个下降方向，故的选取需使得满足，由此得。令，且约束。由此得。结合Wolfe线搜索条件，得到了上述选取的形式。当线搜索精确时，DY方法中的公式等价于FR公式，由此知DY方法是对应着一个新的共轭梯度法。此方法由戴彧虹和袁湘江于1995年提出，且他们严格证明了采取Wolfe线搜索的DY方法在每一步均产生一个下降方向，并且方法全局收敛。故DY方法不使用强Wolfe非精确线搜索而仅使用Wolfe非精确线搜索也可得到很好的收敛效果，此结果进一步揭示了非线性共轭梯度法不同于线性共轭梯度法的一面。对于DY方法，戴彧虹在不使用任何线搜索的情况下，证明了方法在远离最优点时，充分下降条件必对大部分迭代点列成立。由此性质知DY方法在一般的线搜索下全局收敛。3.一些方法的改进和创新3.1 杂交共轭梯度法由上述收敛性部分中可知，关于参数有如下计算公式：，其中，。它们对应的共轭梯度法依次为FR、PRP、DY和HS方法。PRP方法是数值表现最好的非线性共轭梯度法之一，但即使采取精确线搜索也不一定收敛。相反的，虽然FR方法的数值表现不佳，但其全局收敛性很好。一个结合这两办法的想法自然就产生了，为了结合这两方法的优点，TouatiAhmed和Storey考虑结合PRP方法和FR方法，首先引入了杂交共轭梯度法，对的选取满足如下要求：这方法确实可以避免FR方法可能连续产生小步长的缺点。由此，Gilbert和Nocedal进一步研究了杂交方法，对的选取采用了：这种方法的好处在于，允许了参数取负数。然而，Gilbert和Nocedal进行了大量数值实验，其结果表明，这种方法的数值表现虽然比FR方法好一些，但仍比PRP方法差很多。另外，戴彧虹和袁亚湘研究了DY方法和HS方法的杂交共轭梯度法，这种方法比上述FR方法和PRP方法的杂交共轭梯度法好在，它们不要求线搜索满足强Wolfe条件，而只需线搜索满足Wolfe条件。他们选取的满足且他们进行的大量数值试验表面DY方法和HS方法的杂交共轭梯度法的计算表现非常好。在对较为困难的问题时，它比PRP方法还要好很多。3.2 共轭梯度法簇众所周知，大部分拟牛顿法可以用统一的表达式表示，并可统一进行研究。较大的拟牛顿法有Huang簇和Wu簇。根据拟牛顿法的簇类而联想到，共轭梯度法是否存在簇类，由此可以统一对其研究？戴彧虹和袁亚湘研究了单参数共轭梯度法簇，FR方法和DY方法关于参数的计算公式其分子和分母的下标只相差1，于是它们可以形式地表为：。由此取，。引入参数，令，由此定义了一簇共轭梯度法，它可看作FR方法和DY方法的某种线性组合。由此导出的满足在推广的Wolfe线搜索下，戴彧虹和袁亚湘研究出了如下性质。当时，每一个搜索方向为下降方向且方法在下述意义下收敛：（*）当时，方法在（*）下收敛。由此，对任意的，参数满足，则每一个搜索方向均为下降方向，且方法在（*）下收敛。此外，Nazareth视FR方法、PRP方法、HS方法和DY方法为四种主要的共轭梯度法，并提出了两个参数的共轭梯度法簇。戴彧虹基于上述四种方法以及CD方法和LS方法等六种形式较为简单的共轭梯度法，提出了三参数共轭梯度法簇。3.3 最短余量法最短余量法最早由Hestenes在1980年提出，其中的迭代方向与上述方法不同，有如下形式：，且。此种形式中，若线性搜索精确，不难得出：。当线搜索精确且目标函数为严格凸二次函数时，上述方法定义的迭代方向是其顶点分别为，的（k-1）维单纯形中的最短向量。最短余量法中的方向也可写为如下形式：，其中满足。为了研究当目标函数为一般非线性函数时，最短余量法对应于何种标准的共轭梯度法，并研究其他标准共轭梯度法，Pytlak在迭代方向中引入了一个参量，即考虑：。与之前的共轭梯度法相比，即迭代方向由参数产生的方法，当线搜索精确时，最短余量法中的参数满足关系：，由于的选取，更进一步知：。由此得出结论：如果，则。故当线搜索精确时，原始的最短余量法对应于FR方法。称之为最短余量法的FR格式或FRSR方法。令，则，当线搜索精确且目标函数为二次凸函数时，这种方法退化为线性共轭梯度法。称之为最短余量法的PRP格式或PRPSR方法。此外，考虑，则这种方法被称为最短余量法的格式或方法。且这些方法有统一的算法，如下：步1：取步2：如果，停；利用某种线搜索方法求；。步3：测试，若不成立， 若，测试，若不成立， 若令，置转步2。步4：若，；若，；若，。步5：计算；k：=k+1， 转步2。对于非精确线搜索的情况，戴彧虹和袁亚湘分析了三种线搜索下最短余量法的收敛性。三种线搜索为强Wolfe线搜索（1），步长因子有界的Wolfe线搜索（2）以及Armijo线搜索（3），即给定参数，取，其中m为使得成立的最小负整数。当目标函数下方有界，导数满足Lipschitz连续时。算法满足时，三种线搜索下有成立。当目标函数下方有界，导数满足Lipschitz连续时。算法满足时，在（2）和（3）的搜索下有成立。当目标函数二次连续可微，水平集有界，并且存在常数，使得，其中I为1或2，如果线搜索为Wolfe线搜索或（3）的搜索，则有成立。当目标函数的水平集有界，导数Lipschitz连续，算法满足对（1）的线搜索，成立。由此分析得，采取精确线搜索的PRPSR算法对一般非凸函数不一定收敛，但采取（2）或（3）的线搜索的PRPSR算法对一般非凸函数全局强收敛。采取强Wolfe线搜索的PRPSR算法不一定收敛，但算法全局收敛。3.4 Beale-Powell重新开始方法如果共轭梯度算法在每n步沿负梯度方向作一重新开始，进一步，如果线搜索精确或渐进精确，则重新开始的共轭梯度算法的收敛速度可从原来的线性提高到n步超线性收敛。可知重新开始的共轭梯度算法无论是在全局收敛性还是在收敛速度方面，都比原来的共轭梯度算法具有更好的性质。但这种重新开始策略具有一些缺点，一是它舍去了算法沿前一次搜索方向搜索得到的二阶导数信息，二是重新开始的频率一般与目标函数的性质有关，而不是简单地取目标函数的维数。故如何设计一种更有效的重新开始方法，引起了不少人的兴趣。Beale给出了一个方法，其中迭代方向，其中t为小于k的一个整数。但McGuire和Wolfe就Beale的三项方法作了数值试验，数值结果非常令人失望。之后Powell通过引入一个新的重新开始准则，即如果，不成立，也使方法重新开始，克服了McGuire和Wolfe的困难，且获得了令人满意的数值结果。共轭梯度法还有一些相关方法，如平行切线法、TTR方法以及无记忆拟牛顿法，这些为共轭梯度法的几个变种。还有预条件共轭梯度法，这与拟牛顿法有一个内在联系。这些方法显示了共轭梯度法与其他一些方法的关联度，以及共轭梯度法的一些良好性质。4.共个梯度法与其他算法的比较 在所有需要计算导数的的优化方法中，最速下降法是最简单的，但它速度太慢。拟牛顿法收敛速度很快，被广泛认为是非线性规划中最有效的方法，但它需要存储矩阵以及通过求解线性方程组来计算搜索方向，这对于求解一些大规模问题几乎是