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

1、无约束最优化直接方法和间接方法的异同一、什么是无约束最优化最优化方法（也称做运筹学方法）是近几十年形成的，它主要运用数学方法研究各种系统的优化途径及方案，为决策者提供科学决策的依据。最优化方法的主要研究对象是各种有组织系统的管理问题及其生产经营活动。其的目的在于针对所研究的系统， 求得一个合理运用人力、 物力和财力的最佳方案， 发挥和提高系统的效能及效益， 最终达到系统的最优目标。 实践表明， 随着科学技术的日益进步和生产经营的日益发展， 最优化方法已成为现代管理科学的重要理论基础和不可缺少的方法，被人们广泛地应用到公共管理、经济管理、工程建设、国防等各个领域，发挥着越来越重要的作用。最优化问

2、题分为无约束最优化和约束最优化问题， 约束最优化问题是具有辅助函数和形态约束条件的优化问题， 而无约束优化问题则没有任何限制条件。 无约束最优化问题实际上是一个多元函数无条件极值问题。虽然在工程实践中，大多数问题都是具有约束的优化问题，但是优化问题的处理上可以将有约束的优化问题转化为无约束最优化问题，然后按无约束方法进行处理。或者是将约束优化问题部分转化为无约束优化问题，在远离极值点和约束边界处按无优化约束来处理， 在接近极值点或者约束边界时按照约束最优化问题处理。所以无约束优化问题的解法不仅是优化设计方法的基本组成部分，也是优化方法的基础。无约束最优化方法大致分为两类：一类是使用导数的间接方

3、法，即在计算过程中要用到目标函数的导数； 另一类是直接方法， 即只要用到目标函数值， 不需要计算导数。这里我们比较这两类方法的异同。二、无约束最优化方法1. 使用导数的间接方法1.1 最速下降法函数的负梯度方向是函数值在该点下降最快的方向。将 n 维问题转化为一系列沿负梯度方向用一维搜索方法寻优的问题，利用负梯度作为搜索方向， 故称最速下降法或梯度法。无约束优化问题的数学模型可以表示为：min f xxRn，我们假设函数xf x 具有一阶连续偏导数。最速下降法在处理这一类问题时，从初始迭代点x 1出发，选择一个目标函数值下降最快的方向d k ，以利于尽快达到极小点。最速下降法的迭代公式为：1)

4、给定初点 x 1Rn ，允许误差0 ，置 k 1 ；2)计算搜索方向 d kf x k；3)若 d k，则停止计算； 否则，从 x k出发，沿着 d k 进行一维搜索， 求 k ，使得：f (x kkd k) min f (x kd k)4)令 x k 1x kkd k，置 kk 1，转步骤 2。梯度下降法有如下特点：1理论明确，程序简单，对初始点要求不严格。2对一般函数而言，梯度法的收敛速度并不快（线性收敛），因为最速下降方向仅仅是指某点的一个局部性质。3梯度法相邻两次搜索方向的正交性，决定了迭代全过程的搜索路线呈锯齿状，在远离极小点时逼近速度较快，而在接近极小点时逼近速度较慢。4梯度法的收

5、敛速度与目标函数的性质密切相关。对于等值线(面 )为同心圆（球）的目标函数，一次搜索即可达到极小点。1.2 牛顿法牛顿法在 x k 邻域内用一个二次函数来近似代替原目标函数，并将的极小点作为对目标函数求优的下一个迭代点。 经多次迭代，使之逼近目标函数的极小点。牛顿法的迭代公式为：x k 1x k2 f (x k ) 1f (x k ) 。牛顿法有如下特点：1初始点应选在极点附近，有一定难度；2若迭代点的海赛矩阵为奇异，则无法求逆矩阵，不能构造牛顿法方向；3不仅要计算梯度，还要求海赛矩阵及其逆矩阵，计算量和存储量大。此外，对于二阶不可微的函数也不适用；4虽然牛顿法有上述缺点，但在特定条件下它具有

6、收敛最快的优点（2 级收敛），并为其他的算法提供了思路和理论依据。1.3 共轭梯度法共轭梯度法的基本思想是把共轭性与最速下降法相结合， 利用已知点处的梯度构造一组共轭方向， 并沿着这组方向进行搜索， 求出目标函数的极小点。 其计算步骤为：1)给定初点 x 1Rn ，允许误差0 ，置： y 1x 1 ,d1f (y 1 ), k j 1；2)若 f (y j )，则 停止 计算 ； 否则 ，做 一维 搜索 ，求 j ，使 得：f (y jj d j) min f (y jd j ) ，令 y j 1y jj d j；3)如果 jn ，转步骤 4，否则转步骤 5；f ( y j 1 )24)令 d

7、 jf ( y j 1 )1j d j ，其中， j2 ；f ( y j )5)令 x k1y n1 ,y 1x k 1 , d 1f ( y 1 ) ，置 j1, kk1，转步骤 2。共轭梯度法有如下特点：1程序简单，存储量少，具有最速下降法的优点，而在收敛速度上比最速下降法快，具有二次收敛性；2适用于维数较高 (50 维以上 )、一阶偏导数易求的优化问题。共轭梯度法在第一个搜索方向取负梯度方向，而其余各步的搜索方向将负梯度偏转一个角度，即对负梯度进行修正， 实质上是对最速下降法的改进。在 n 次迭代后如果没有达到收敛精度，则通常以重置负梯度方向开始，直到满足精度为止。1.4 拟牛顿法牛顿法

8、成功的关键在于利用了Hesse矩阵提供的曲率信息，而计算Hesse矩阵工作量大，并且有的目标函数的Hesse矩阵很难计算，甚至不好求出。为了克服牛顿法的缺点， 人们提出仅利用目标函数一阶导数的方法，拟牛顿法就是利用目标函数值 f 和一阶导数 g 的信息，构造出目标函数的Hesse矩阵的曲率近似，同时具有收敛速度快的优点。1.5 信赖域方法无优化方法的一般策略是，给定点x k 后，定义搜索方向 d k ，再从 x k 出发沿着 d k 做一维搜索，而信赖域方法另辟蹊径，给定点x k 后，确定一个变化范围，通过常取 x k 为中心的区域，称为信赖域，在此域内优化目标函数的二次逼近式，按照一定模式求

9、出后继点x k 1 。如果不满足精度要求，再定义x k 1 为中心的信赖域， 并在此域内优化目标函数新的二次逼近式， 直到达到精度。 该方法的特点是在一定条件下具有全局收敛性。2. 直接方法2.1 模式搜索法搜索模式法是 Hooke 和 Jeeves在 1961 年提出的，这种方法的基本思想，从几何意义上看， 寻找具有较小函数值的 “山谷”力图使迭代产生的序列沿 “山谷”走向逼近极小点， 算法从初始基点开始， 包括两种类型的移动： 探测移动和模式移动。探测移动依次沿 n 个坐标轴进行， 用以确定新的基点和有利于函数值下降的方向。模式移动沿相邻两个基点连线方向进行，试图顺着“山谷”使函数值更快地

10、减小。有如下特点：1最简单的直接优化方法之一，方法易懂，程序简单，无需求导，计算费用低；2可靠性差、效率低，当目标函数等值线具有脊线形态时可能失败；3该方法适用于目标函数导数不存在或不易求得、维数较低( 一般， l 5)的情况。其探索路线较长，而且显然是问题的维数愈多求最优解得效率愈低。2.2 单纯形法单纯形法也是一种不使用导数的求解无约束极小化问题的直接搜索方法，与前面几种方法不同，在这种方法中，给定Rn 中的一个单纯形后，求出n+1 个顶点上的函数值，确定出有最大函数值的点，和最小函数值的点，然后通过反射、扩展、压缩等方法求出一个较好点，用它取代最高点，构成新的单纯形，或者通过向最低点收缩

11、形成新的单纯形，用这样的方法逼近极小点。2.3 Powell方法Powell法是以共轭方向为基础的收敛较快的直接法之一，是一种十分有效的算法。直接利用迭代点的目标函数值来构造共轭方向，然后从任一初始点开始，逐次沿共轭方向作一维搜索求极小点。该方法直接利用函数值逐次构造共轭方向， 并在改进的算法中增加了判断原方向组是否需要替换和哪个方向需要替换， 保证了共轭方向的生成， 具有二次收敛性，收敛速度快，可靠性好，但编程较复杂。是直接搜索法中最为有效的算法之一。三、无约束最优化直接方法和间接方法的异同直接方法与使用导数的方法相比，一般来说，收敛的比较慢，但是，它对目标函数不要求导数存在，迭代简单，编制程序一般也比较容易。如下表所示：无约束最优化算法计算量存储量收敛速度复杂性需要计算一存储量小慢（线性收仅计算一阶最速下降法阶导数，计敛）导数，不复算量不大杂牛顿法需要