王国文 假大空话 永远解不开的密码quantu

非线性共轭梯度法的文献综述研究 摘要：共轭梯度法最早是由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方法差很多。