毕业论文(设计)_无约束优化问题算法初探.doc文档32页推荐下载 ㊣ 精品文档 值得下载

类在迭代过程中仅用到函数值，不必计算函数的导数，这类方法称为直接法或搜索法。

般说来，直接法的收敛速度较慢，只是在变量较少时才适用。

但迭代法的迭代步骤简单，特别是当目标函数的解析表达式十分复杂，甚至写不出具体表达式时，他们的导数很难求得，或根本不存在，这时，就只有用直接法了。

另类是在计算过程中要用到函数的阶导数和或二阶导数，这时，在中总假定有阶或二阶连续偏导数由于用到函数的解析性质，故称为解析法。

关键词关键词无约束优化牛顿迭代信赖域算法梯度法引言第章直接法第二章牛顿法及其修正算法牛顿法原始牛顿法阻尼牛顿法修正牛顿法拟牛顿法牛顿拉弗森方法第三章梯度法最速下降法共轭梯度法第四章信赖域法解无约束优化问题的新算法第五章算法的收敛性第六章算法的数值检验结束语参考文献谢辞引言无约束优化计算方法是数值计算领域中十分活跃的研究课题之。

快速地求解无约束优化问题，除了其自身的重要性外，还体现在它也构成些约束优化问题的子问题。

因此，对于无约束优化问题，如何设计快速有效的算法直都是优化工作者十分关心的问题。

本文第二章给出了用梯度法求解对称正定线性方程组的族新步长，并建立其收敛性。

我们从插值的角度进步解释了步长，并将中给出的步长公式推广到数值实验表明，些步长的选取能够取得很好的数值效果。

第三章对共轭梯度法进行了些改进，给出了三种改进方案，并建立了算法对致凸函数的收敛性。

修改后的方法在算法进行过程中能够产生下降方向，算法无需重开始。

数值结果表明，修改后的算法比著名的，共轭梯度法表现要好。

第四章给出个解无约束优化问题的子空间算法，并建立了它对致凸函数的收敛性。

该算法具有合理利用内存，收敛速度快等优点„„第章直接法直接法往往以直观或以计算实践为基础而产生，这类算法的特点是只要求计算函数值本身，因而易于使用，但是与另些要求计算偏导数值的方法相比，又收敛得慢。

所以直接法常常用于变量极少而函数比较复杂且不易计算偏导数的情形。

第二章牛顿法及其修正算法为了寻找收敛速度较快的求解无约束问题的优化算法，我们在每轮迭代中用适当的二次函数来近似目标函数，即利用二阶导数的无约束最优化方法，并用迭代点处指向近似二次函数的极小点作为搜索方向。

牛顿法设，在点处具有连续二阶偏导数，且在点的海赛矩阵正定，是的个极小点的第轮估计值。

把在点展开为泰勒级数，并取二阶近似为下面来求的平衡点，记矩阵向量数将式代入式，得到则有令，记为的平衡点，则有或因此得到令则有称为牛顿方向。

牛顿算法的步骤如下选取初始数据。

选取初始点，给定终止误差，令求梯度向量。

计算，若，停止迭代，输出，否则，进行步骤。

构造牛顿方向。

计算，取求下迭代点。

令，转步骤。

原始牛顿法原始牛顿法的基本原理是原目标函数用在迭代点邻域展开的泰勒二次多项式去近似的代替，再以这个二次函数的极小点作为原目标函数的下个迭代点，这样重复迭代若干次后，使迭代点点列逐步逼近原目标函数的极小点。

二次逼近函数可写为式中分别为原目标函数在点的梯度和赫森矩阵。

的极小点可由极值存在的必要条件，令其梯度来求得，亦即这样，若为可逆矩阵，将上式等号两边左乘以，则得将取作下个优化迭代点，即可得到原始牛顿法的迭代公式为由上式可知原始牛顿法的搜索方向为这个方向称牛顿方向。

由式还可看到迭代公式中没有步长因子，所以原始牛顿法是种定步长的搜索迭代。

当目标函数是二次函数时，由于二次泰勒展开函数与原目标函数不是近似而是完全相同的二次式，赫森矩阵是个常数矩阵，用式原始牛顿法从任初始点出发，只需步迭代即达的极小点，因此牛顿法也是种具有二次收敛性的算法。

对于非二次函数，若函数的二次性态较强，或迭代点已进入极小点的邻域，则其收敛速度也是很快的，这是牛顿法的主要优点。

但原始牛顿法由于迭代公式中没有步长因子，而是定步长迭代，对于非二次型目标函数，有时会使函数值上升，即出现的情况，这表明原始牛顿法不能保证函数值稳定地下降，在严重的情况下甚至可能造成迭代点列的发散而导致计算失败。

修正牛顿法为了克服牛顿法的弱点，人们保留选取牛顿法方向作为搜索方向，舍弃了其步长恒等于而用维搜索确定最有步长。

这种方法通常称为修正牛顿法。

修正后的牛顿法的迭代公式为其中是维搜索得到的最优步长，满足修正牛顿法的算法步骤与梯度法完全类似，只是有利的搜索方向换成了式所给的方向。

阻尼牛顿法为消除原始牛顿法的上述弊病，对其加以改进，提出了阻尼牛顿法。

阻尼牛顿法每次迭代方向仍采用式表达的牛顿方向，但每次迭代需沿此方向作维搜索，求其最优步长因子。

即将原始牛顿法的迭代公式修改为此即阻尼牛顿法的迭代公式。

式中又称为阻尼因子，是通过沿牛顿方向维搜索寻优而得。

当目标函数的赫森矩阵处处正定时，阻尼牛顿法能保证每次迭代点的函数值均有所下降，从而保持了二次收敛的特性。

阻尼牛顿法的具体迭代步骤如下给定初始点，迭代精度，维数。

计算迭代点的梯度和梯度的模。

检验是否满足迭代终止条件若满足，停止迭代，输出最优解否则进行下步。

计算处的赫森矩阵，并求其逆矩阵。

确定牛顿方向，从点出发，沿方向进行维搜索求最优步长，使。

计算迭代新点。

置，返回步骤进行下次迭代计算。

拟牛顿方法拟牛顿方法也有人称为变尺度方法。

这是近二十多年来发展起来的类很有成效的寻优方法。

理论分析和计算实践都表明这类方法的收敛速度较快，同时又无需计算二阶偏导数矩阵。

这类方法的共同特点是移动方向由定义，其中为阶对称正定方阵可以任意选取，但通常取当时，由和以及确定，并满足如下的拟牛顿方程步长和下点由线性搜索确定。

第个变尺度法是戴维登于年首先提出的，而由弗莱彻和鲍威尔在理论上作了研究并于年公开发表，所以通常称为方法，在这个方法中的定义如下。

由于方法的成功，在其后十多年间，又提出了许多变尺度方法，这些方法只在的定义方法上有所不同。

在理论上，只要取得相同，那么在定条件下，由不同的变尺度方法产生的点列尣都只依赖于参数但在实际计算中，由于舍入误差的关系，由不同的变尺度方法产生的点列未尽相同。

最成功的变尺度法是法，它的定义为与方法相比，方法具有较好的数值稳定性。

牛顿拉弗森方法在要求计算偏导函数值的算法类中，般取移动方向满足，这里的表示矩阵或向量的转置运算，墷ƒ表示ƒ在点尣上的梯度，即式保证了在以为始点，为方向的半直线上定有点尣适合ƒƒ。

为了使式成立，往往取式中是阶的对称正定矩阵。

通常，步长的选取原则是取使为ƒ在半直线上的最小值点。

这样选取步长的过程称为精确线性搜索或简称线性搜索。

这时有亦即点上的梯度方向与移动方向成正交。

只要ƒ≠，总可以按上述方法进行迭代。

在定的假设下，能够证明ƒ，于是对于凸函数ƒ，点列的任何极限点都是ƒ的最小值点而对于般的非凸函数，即使不能保证的极限点是局部最小值点，但因目标函数值逐次减少，往往也能得到满意的结果。

可以证明，在由出发的所有同样长度的方向中，负梯度方向是使函数值下降最快的方向。

于是取移动方向为负梯度方向墷ƒ，或者等价地取中的为单位矩阵，并由线性搜索确定步长与下点。

这就是通常所谓的最陡下降法。

牛顿拉弗森法则以ƒ的二次近似为基础，在二阶偏导数矩阵墷ƒ为正定时，以此二次近似的最小值点为下点，即取，但这样得到的未必适合式，因此又改成以为移动方向，或者等价地在中取为ƒ，再通过线性搜索来确定与。

在些有关ƒ的假设下，对于这两个古老的方法，都可证明ƒ。

这两个方法各有其优缺点。

最陡下降法比较简单，并且除了函数值本身外，只需要计算阶偏导数的值但是理论分析和计算实践都表明这个方法的收敛速度很慢。

事实上，由及式可知，中的点沿着相互正交的方向交替前进，因此，即使对于二次严格凸函数，式中对称正定，只要不是数量矩阵，那么就曲折前进，且进展很慢。

当时如图所示。

与此相反，牛顿拉弗森方法收敛得快。

特别对于形如的二次严格凸函数，只要次迭代，就能达到最优解尣，即使对于般的函数ƒ，在些假设下，也可证明为二阶收敛。

这个方法不仅要计算个阶偏导数，而且还要计算个二阶偏导数，因此只在比较小或函数比较简单的情形才使用。

第三章梯度法最速下降法共轭梯度法由于在局部最小值点的邻近，函数的性状与二次凸函数十分相似，所以对于个好的寻优方法，人们要求它在应用于二次凸函数时有较快的收敛速度，即使最小值点不能象牛顿拉弗森方法那样步达到，也应在有限步内达到。

事实上，沿着空间中个两两正交的方向依次作线性搜索，定可以达到函数的最小值点。

于是通过变换尣，沿着尣空间中个满足的方向„，依次作线性搜索，就定能达到函数的最小值点。

满足式的个非零方向„，称为关于矩阵的共轭方向系。

世纪年代弗莱彻和