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

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

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

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

4、极小点。最速 下降法的迭代公式为：给定初点xG)e Rn，允许误差8 0，置k = 1 ；计算搜索方向d(k) = -Nf侦)；若|d(k)片8，则停止计算；否则，从x(k)出发，沿着d(k)进行一维搜索，求人k,使得：f (x()+ 人 d() = min f (x() + Xd() k人令 x(+i) = x(k)+ 人 d(k)，置 k = k +1，转步骤 2。k梯度下降法有如下特点：.理论明确，程序简单，对初始点要求不严格。对一般函数而言，梯度法的收敛速度并不快(线性收敛)，因为最速下 降方向仅仅是指某点的一个局部性质。3 .梯度法相邻两次搜索方向的正交性，决定了迭代全过程的搜索路线

5、呈锯 齿状，在远离极小点时逼近速度较快，而在接近极小点时逼近速度较慢。4.梯度法的收敛速度与目标函数的性质密切相关。对于等值线(面)为同心 圆(球)的目标函数，一次搜索即可达到极小点。1.2牛顿法牛顿法在x (k )邻域内用一个二次函数来近似代替原目标函数，并将的极小点 作为对目标函数求优的下一个迭代点。经多次迭代，使之逼近目标函数的极小 点。牛顿法的迭代公式为：x(k+1) = x(k) V 2 f (x(k)-1 -Vf (x(k)。牛顿法有如下特点：.初始点应选在极点附近，有一定难度；.若迭代点的海赛矩阵为奇异，则无法求逆矩阵，不能构造牛顿法方向；.不仅要计算梯度，还要求海赛矩阵及其逆矩

6、阵，计算量和存储量大。此外，对于二阶不可微的函数也不适用；.虽然牛顿法有上述缺点，但在特定条件下它具有收敛最快的优点(2级 收敛)，并为其他的算法提供了思路和理论依据。1.3共轭梯度法共轭梯度法的基本思想是把共轭性与最速下降法相结合，利用已知点处的梯 度构造一组共轭方向，并沿着这组方向进行搜索，求出目标函数的极小点。其 计算步骤为：给定初点 x(i)e Rn，允许误差 0，置：yG)= x(1),dG)= -Vf (yG), k = j = 1 ；若|W(y(j)| ,则停止计算；否则，做一维搜索，求七，使得：f (y。) + 人 d(j) = min f (y(j) + 人dG)，令 y(j

7、+i)= y(j) + 人 d(j)； j人j如果j 直接法11优化算法 最速下降法牛顿法共轭梯度法 1拟牛顿法1 1III III1 11信赖域法 模式搜索法 1 1 1 I 1 ! 1 1 1 ! 1 1 ! 1单纯形法111111111 1Powell 法计算量 需要计算 一阶导数， 计算量不 ，大需要计算 海赛矩阵， 计算量大 计算量不 大1 计算量不大 计算量大1 计算量小1111111111 计算量小1111111111 计算量小存储量存储量小存储量大存储量小1存储量大1存储量大 1 1 存储量小111111 11111存储量小111111 11111存储量小收敛速度 慢（线性收 敛）快（2阶收 敛）块（2阶收 敛）1 快（超线性 收敛速率）1 1 11 III III Illi 快 III I 慢1 1 1 1 1 1 1 1 1 II 慢1 1 1 1 1 1 1 1 1 II 快复杂性！ 仅计算一阶: 导数，不复! 杂需要计算海! 赛矩