最优化优秀结课论文

共轭梯度法是介于最速下降法与牛顿法之间的一个方法。它仅需要利用一阶导数信息，但克服了最速下降法收敛慢的缺点，又避免了牛顿法需要存储和计算Hesse矩阵并求逆的缺点。共轭梯度法不仅是解决大型线性方程组最有用的发发之一，也是解大型非线性最优化问题最有效的算法之一。共轭梯度法最早是由计算数学家Hestenes和几何学家Stiefel在20世纪50年代初为求解线性方程组AxbnxR而各自独立提出的。他们合作的文章被公认为共轭梯度法的奠基之作。该文详细讨论了求解线性方程组的共轭梯度法的性质以及它和其他方法的关系。在A为对称正定阵时，上述线性方程组等价于最优化问题1min2nTTxRxAxbx。由此，Hestenes和Stiefel的方法也可视为求二次函数。提到最优化问题，这里首先介绍最速下降法。考虑线性方程组Axb的求解问题，其中A是给定的n阶对称正定矩阵，b是给定的n维向量。为此我们定义二次泛函()2TTxxAxbx对最速下降法做一简单分析就会发现，负梯度方向虽从局部来看是最佳的下山方向，但从整体来看并非最佳。这就促使人们去寻求更好的下山方向，当然，我们自然希望每步确定新的下山方向付出的代价不要太大。共轭梯度法就是根据这一意思设计的，其具体计算过程如下：给定初始向量0x，第一步仍选负梯度方向为下山方向，即0p=0r，于是有0000TTrpAp，1000xxp，11rbAx对以后各步，例如，第k+1步(1k),下山方向就不再取kr，而是在过点kx由向量kr和1kp所张成的二维平面21{:,}kkkxxrpR内找出使函数下降最快的方向作为新的下山方向kp。考虑在2上的限制：1111(,)()()()2()TTkkkkkkkkkkkkxrpxrpAxrpbxrp直接计算可得：12()TTTkkkkkkrArrAprr1112()TTkkkkrAppAp其中最后一式用到了10Tkkrp，这可由kr的定义直接验证。令==0，即知在2内有唯一的极小点~001kkkxxrp，其中0和0满足方程组001TTTkkkkkrArrAprr(1)01011TTkkkkrAppAp0(2)上式蕴含着0kr必有00，因此我们可取~01001()kkkkpxxrp作为新的下山方向。显然，这是在平面2内可得到的最佳下山方向，令010k，则由(2)式得到1111TkkkTkkrAppAp。这样确定的kp满足1TkkpAp=0，即所谓的kp与1kp是相互共轭的。kp确定以后k的确定仍用公式k=TkkTkkrppAp，然后计算1kkkkxxp。总结上述讨论，可得如下计算公式：k=TkkTkkrppAp1kkkkxxp11kkrbAx1TkkkTkkrAppAp11kkkprp在实际计算中，常将上述公式进一步简化，从而得到一个形式上更为简单而且对称的计算公式。首先来简化1kr的计算公式：11kkrbAx=()kkkbAxp=kkkrAp（3）因为kAp在计算k时已经求出，所以，计算1kr时可以不必将1kx代入方程去计算，而是由（3）得到。再来简化k和k的计算公式。我们需要用到下面的关系式：1110TTTkkkkkkrrrprp，k=1,2,…（4）这些关系式的证明包含在方程组（1）（2）的证明中。由（3）（4）导出1111111()TTTkkkkkkkkkrAprrrrr，111()TTTkkkkkkkkkpApprrpr。由此可得：TkkkTkkrrpAp，11TkkkTkkrrrr最优化方法的收敛性是算法研究领域的基本问题。一种算法是否具备应用价值，取决于是否具备局部或全局收敛性，以及收敛速度的快慢。共轭梯度法不同的方向修正公式，以及采用何种线搜索策略来确定步长，都取决于它的收敛性质。下面重点简述两个共轭梯度法收敛性的成果。1.FR方法：早期对FR方法的收敛性研究是建立在精确线搜索基础上的。Powell在精确线搜索下，得到FR方法的一个很不利的性质，即：如果FR方法在某一步产生一个很小的步长，则相继的许多步长也可能非常小。同时，Powell还给出了FR方法最简单的全局有效性分析。这些分析解释了为什么FR方法在数值表现上并不十分满意。尽管FR方法可能收敛速度很慢，Zoutendijk证明了采取精确线搜索的FR方法对一般非凸函数总是收敛的。在实际计算中，人们通常采用非精确线搜索，而不是使用精确线搜索。最早的非精确线搜索的全局收敛结果是由A1．Baali在1985年给出的，他证明了使用参数12的强Wolfe线搜索的FR方法一定满足充分下降条件，而且是全局收敛的。有人后将A1．Baali的结果推广到了12。通过分析使用推广的Wolfe线搜索的FR方法，通过考虑相邻两个迭代点列，发现只要FR方法的每个搜索方向下降，那么任意相邻两个迭代点列中至少有一个使得充分下降条件成立，从而较简单的证明了12时采用强Wolfe线搜索的算法的全局收敛性。对于12，有人举出反例表明，FR方法可能产生一个上升方向而导致失败，并且提出了一种广义线搜索策略，证明了FR方法在广义Wolfe线搜索的全局收敛性。2．PRP方法：PRP方法是目前认为数值表现最好的共轭梯度算法之一。当算法产生一个小步长时，由PRP方法定义的搜索方向kd自动靠近负梯度方向，从而较为有效地避免FR方法可能连续产生小步长的缺陷。基于此，Powell证明了当步长1kkksxx趋于0时PRP方法的全局收敛性。进一步可以得到，采取精确线搜索的PRP方法对一致凸函数的全局收敛性。但对一般非凸函数，Powell举出了一个三维的反例表明，即使按Curry原则选取步长因子，PRP方法可能在6个点附近进行循环，而其中任意一点都不是目标函数的稳定点。在二维时，Powe11证明了采取Curry原则的PRP方法对一般非凸函数的收敛性。如果使用非精确线搜索，戴彧虹举例表明，即使对于一致凸函数，采用强wolfe线搜索，且参数充分接近于0，PRP方法都有可能产生一个上升方向。如果再要求每一个搜索方向下降，那么PRP方法对凸函数是收敛的。对一般非凸函数，Powell建议限制PRP方法中的参数PRPk为非负max{,0}PRPkk这样做的目的是避免当║kd║很大时，相邻两个搜索方向会产生相反的趋势。Gilbert和Nocedal接受了Powell的上述建议，并在适当的线搜索条件下，得到了上述修正PRP方法对一般非凸函数的全局收敛性结果。然而，Gilbert和Nocedal也举出反例表明，即使对一致凸的目标函数，PRP也可能为负。于是，Grippo和Lucidi设计了一种Armijo型的线搜索，并证明了原始PRP方法在该线搜索下，对一般非凸函数的全局收敛性。他们的结果是应用当步长ks很小时，PRP方法的方向接近最速下降方向的性质。戴彧虹和袁亚湘得出PRP方法一个新的性质，即证明了取常数步长因子的PRP方法在每次迭代都产生一个下降方向，而且全局收敛。但是，他的这种常数步长因子的选取依赖于Lipschitz常数L，而L在实际计算中很难预先估计，因此并不容易实现。共轭梯度法在实际生活中的应用很广泛，对数学科学的研究、生产生活有着重要意义，这里我们以一例进行说明分析。例：用FR共轭梯度法解极小化问题121222122123)(minxxxxxxf这里我们将用到共轭梯度法相关的数学模型：共轭梯度法是一个典型的共轭方向法，它的每一个共轭方向是相互共轭的而这些搜索方向kd仅仅是负梯度方向kg与上一次迭代的搜索方向1kd的组合。因此，存储量少计算方便记11kkkkdgd左乘GdTk1并使得01kTkGdd1111kTkkTkkGddGdg（Hestenes-Stiefel）我们可以将数值公式1111kTkkTkkGddGdg改写为evesFletcherggggWolfeCrowderggdgggkTkkTkkkTkkkTkkRe,111111注意到对于正定二次函数kkkrbGxg其中kr是方程组bGxk的残量，以及kTkkTkkTkkTkkkkkkGddrrGdddgGdrr,1下面给出关于正定二次函数极小化的共轭梯度法。算法步骤：步1（初始步）给出0,0x；计算bGxr00令0:,00krd步2如果kr停止步3计算kkkkkTkkTkkdxxGddrr1kkkkkTkkTkkkkkkdrdrrrrGdrr11111步4令,1kk转步2通过Matlab软件进行计算，函数从初始点Tx)4,2(0开始迭代，计算两次，得出最优解Tx)1,1(2。最优化方法课程论文浅谈几种共轭梯度法及其收敛性的理论和发展学院：理学院班级：信息102班姓名：牟鹏宇学号：2010052215