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

非线性共轭梯度法的文献综述 摘要：共轭梯度法最早是由Hestenes和Stiefel于1952年提出来的，用于解正定系数矩阵的线性方程组，在这个基础上，Fletcher和Reeves于1964年首先提出了解非线性最优化问题的共轭梯度法。由于共轭梯度法不需要矩阵存储，且有较快的收敛速度和二次终止性等优点，于是，共轭梯度法的理论研究受到了人们的关注，现在共轭梯度法已经广泛地应用与实际问题中。 关键词：共轭梯度法，非线性最优化，线性搜索，收敛性 1.共轭梯度法 共轭梯度法最早是由计算数学家Hestenes和几何学家Stiefel在20世纪50年代初为求解线性方程组 Ax?b,x?Rn 而独立提出的。他们奠定了共轭梯度法的基础，他们的文章详细讨论了求解线性方程组的共轭梯度法的性质以及它和其他方法的关系。当A对称正定时，上述线性方程组等价于最优化问题 1TminxAx?bTxnx?R2 基于此，Hestenes和Stiefel的方法可视为求解二次函数极小值的共轭梯度法。 1964年，Fletcher和Reevse将此方法推广到非线性优化，得到了求一般函数极小值的共轭梯度法。 而本书中，戴彧虹和袁亚湘介绍了多种类型的共轭梯度法，各方法的区分主要在于每次迭代的方向上，并且他们检验了每种方法在不同搜索下的全局收敛性。在他们的研究中，目标函数连续可微有下界，导数满足Lipschitz条件，他们通过对Zoutendijk条件的判断，通常用反证的方法来考察全局各共轭梯度法的全局收敛性问题。 对于无约束优化问题 minf(x)nx?R 一般给出一初值x1，经由算法迭代产生x2,x3,?。在第k次迭代，当前迭代点 nxd?Rkk为，用一种方法产生一搜索方向。然后下一迭代点为： xk?1?xk??kdk 其中，迭代方向dk的不同选取产生了不同的共轭梯度法，?k为步长因子，步长的不同选取产生了不同的搜索准则。而本书着重研究各方法在精确线搜索，Curry原则，强Wolfe线搜索和推广的Wolfe线搜索下的收敛性。其中： 1 精确线搜索要求每次迭代的步长满足：f(xk??kdk)?minf(xk??dk)??0 Curry原则要求每次迭代的步长?k为一维函数?k(?)?{f(xk??dk):??0}的第一个极小点。 强Wolfe线搜索要求每次迭代的步长满足： Tf(xk??kdk)?f(xk)???kdkgk TTdkg(xk??kdk)??dkgk 其中，0?????1。 推广的Wolfe线搜索要求每次迭代的步长满足： Tf(xk??kdk)?f(xk)???kdkgk TTT?1dkgk?dkg(xk??kdk)???2dkgk 其中0???1,?1?(?,1),?2?0。 而迭代方向一般为： ?gk,k?1?dk????gk??kdk?1,k?2 可知迭代方向的不同由?k产生，故?k的不同选取产生的各种共轭梯度法，戴彧虹和袁亚湘介绍了如下方法，有： Fletcher和Reeves在1964年求解线性方程组推广而得的共轭梯度法，简称FR方法。 Polak和Ribiere和Polyak在1969年独立提出的一种非线性共轭梯度法，简称PRP方法。Hestenes和Stiefel给出的另一种HS方法。 Fletcher在1987年引入的共轭下降法，简称为CD方法。 戴彧虹和袁亚湘在1995年提出的新的共轭梯度法，简称为DY方法。 本书中给出了各种方法在不同搜索标准下的收敛性条件和全局收敛证明。 2.全局收敛性及条件 全局收敛性保证了算法从任何初始点开始都可以找到满足任意精度的近似解。所以最优化方法的收敛性是算法领域最基本的问题之一。本书中，戴彧虹和袁亚湘着重研究了不使用重新开始技术的共轭梯度法的全局收敛性，而他们研究的方法，因为有着不同的修正公式，以及不同的搜索策略，故而有不同的收敛性质。下面分别介绍这些方法。 2.1 FR方法 FR方法中，?k的选取按公式： 2 ?FR k?gk gk?122 早期对于FR方法的分析是基于精确线搜索。Powell在精确线搜索下分析了FR方法可能连续产生小步长的性质，而FR方法的这种可能连续产生许多小步长的性质，在很大程度上也解释了为何FR方法在数值计算中有时表现得很差。但Zoutendijk证明了采取精确线搜索的FR方法对一般非凸函数总收敛。 由于精确线搜索在每步迭代时的难以操作