无约束最优化直接方法和间接方法的异同.doc

《无约束最优化直接方法和间接方法的异同.doc》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、最优化理论与算法小论文——无约束最优化直接方法和间接方法的异同翁乐怡无约束最优化直接方法和间接方法的异同一、什么是无约束最优化最优化方法（也称做运筹学方法）是近几十年形成的，它主要运用数学方法研究各种系统的优化途径及方案，为决策者提供科学决策的依据。最优化方法的主要研究对象是各种有组织系统的管理问题及其生产经营活动。其的目的在于针对所研究的系统，求得一个合理运用人力、物力和财力的最佳方案，发挥和提高系统的效能及效益，最终达到系统的最优目标。实践表明，随着科学技术的日益进步和生产经营的日益发展，最优化方法

2、已成为现代管理科学的重要理论基础和不可缺少的方法，被人们广泛地应用到公共管理、经济管理、工程建设、国防等各个领域，发挥着越来越重要的作用。最优化问题分为无约束最优化和约束最优化问题，约束最优化问题是具有辅助函数和形态约束条件的优化问题，而无约束优化问题则没有任何限制条件。无约束最优化问题实际上是一个多元函数无条件极值问题。虽然在工程实践中，大多数问题都是具有约束的优化问题，但是优化问题的处理上可以将有约束的优化问题转化为无约束最优化问题，然后按无约束方法进行处理。或者是将约束优化问题部分转化为无约束优化

3、问题，在远离极值点和约束边界处按无优化约束来处理，在接近极值点或者约束边界时按照约束最优化问题处理。所以无约束优化问题的解法不仅是优化设计方法的基本组成部分，也是优化方法的基础。无约束最优化方法大致分为两类：一类是使用导数的间接方法，即在计算过程中要用到目标函数的导数；另一类是直接方法，即只要用到目标函数值，不需要计算导数。这里我们比较这两类方法的异同。二、无约束最优化方法1.使用导数的间接方法1.1最速下降法5最优化理论与算法小论文——无约束最优化直接方法和间接方法的异同翁乐怡函数的负梯度方向是函数值

4、在该点下降最快的方向。将n维问题转化为一系列沿负梯度方向用一维搜索方法寻优的问题，利用负梯度作为搜索方向，故称最速下降法或梯度法。无约束优化问题的数学模型可以表示为：，我们假设函数具有一阶连续偏导数。最速下降法在处理这一类问题时，从初始迭代点出发，选择一个目标函数值下降最快的方向，以利于尽快达到极小点。最速下降法的迭代公式为：1)给定初点，允许误差，置；2)计算搜索方向；3)若，则停止计算；否则，从出发，沿着进行一维搜索，求，使得：4)令，置，转步骤2。梯度下降法有如下特点：1．理论明确，程序简单，对初

5、始点要求不严格。2．对一般函数而言，梯度法的收敛速度并不快（线性收敛），因为最速下降方向仅仅是指某点的一个局部性质。3．梯度法相邻两次搜索方向的正交性，决定了迭代全过程的搜索路线呈锯齿状，在远离极小点时逼近速度较快，而在接近极小点时逼近速度较慢。4．梯度法的收敛速度与目标函数的性质密切相关。对于等值线(面)为同心圆（球）的目标函数，一次搜索即可达到极小点。1.2牛顿法牛顿法在邻域内用一个二次函数来近似代替原目标函数，并将的极小点作为对目标函数求优的下一个迭代点。经多次迭代，使之逼近目标函数的极小点。牛顿

6、法的迭代公式为：。牛顿法有如下特点：1．初始点应选在极点附近，有一定难度；2．若迭代点的海赛矩阵为奇异，则无法求逆矩阵，不能构造牛顿法方向；3．5最优化理论与算法小论文——无约束最优化直接方法和间接方法的异同翁乐怡不仅要计算梯度，还要求海赛矩阵及其逆矩阵，计算量和存储量大。此外，对于二阶不可微的函数也不适用；1．虽然牛顿法有上述缺点，但在特定条件下它具有收敛最快的优点（2级收敛），并为其他的算法提供了思路和理论依据。1.3共轭梯度法共轭梯度法的基本思想是把共轭性与最速下降法相结合，利用已知点处的梯度构造

7、一组共轭方向，并沿着这组方向进行搜索，求出目标函数的极小点。其计算步骤为：1)给定初点，允许误差，置：；2)若，则停止计算；否则，做一维搜索，求，使得：，令；3)如果，转步骤4，否则转步骤5；4)令，其中，；5)令，置，转步骤2。共轭梯度法有如下特点：1．程序简单，存储量少，具有最速下降法的优点，而在收敛速度上比最速下降法快，具有二次收敛性；2．适用于维数较高(50维以上)、一阶偏导数易求的优化问题。共轭梯度法在第一个搜索方向取负梯度方向，而其余各步的搜索方向将负梯度偏转一个角度，即对负梯度进行修正，实

8、质上是对最速下降法的改进。在n次迭代后如果没有达到收敛精度，则通常以重置负梯度方向开始，直到满足精度为止。1.4拟牛顿法5最优化理论与算法小论文——无约束最优化直接方法和间接方法的异同翁乐怡牛顿法成功的关键在于利用了Hesse矩阵提供的曲率信息，而计算Hesse矩阵工作量大，并且有的目标函数的Hesse矩阵很难计算，甚至不好求出。为了克服牛顿法的缺点，人们提出仅利用目标函数一阶导数的方法，拟牛顿法就是利用目标函数值f和一阶导数g的信息，构造