第四章无约束优化方法.ppt

图4－12 坐标轮换法原理图（动画演示） 2. 搜索方向与步长的确定 （1）搜索方向的确定 3.搜索步长的确定 关于 值通常有以下几种取法 （1）加速步长法 （2）最优步长法 最优步长法就是利用一维最优搜索方法来完成每一次迭代，即 此时可以采用0.618方法或二次插值方法来计算 的值。 图4－14 最优步长法的搜索路线 4 . 坐标轮换法存在的问题 图4－15 坐标轮换法在各种不同情况下的效能 （a）搜索有效；（b）搜索低效；（c）搜索无效 第八节 Powell法（方向加速法） Powell法是利用共轭方向可以加速收敛的性质所形成的一种搜索算法。 第九节 单形替换法 一、基本思想 单纯形替换法也是一种不使用导数的求解无约束极小化问题的直接搜索方法，与前面几种方法不同的是，单纯形替换法不是利用搜索方向从一个点迭代到另一个更优的点，而是从一个单纯形迭代到另一个更优的单纯形。 对于第k轮第i次的计算 第k轮第I次的迭代方向，它轮流取n维坐标的单位向量。 图4－13 加速步长法的搜索路线 一、共轭方向的生成 二、基本算法 三、改进的算法 在鲍维尔基本算法中，每一轮迭代都用连结始点和终点 所产生出的搜索方向去替换原来向量组中的第一个向量， 而不管它的“好坏”。 改进的算法是：首先判断原向量组是否需要替换。如需要 替换，在产生新的向量。 改进算法的具体步骤： 定义：单纯形 n维空间中的恰好有n+1个顶点（极点）的有界的凸多面体称之为一个单纯形。 根据定义，可知，一维空间中的单纯形是线段，二维空间中的单纯形是三角形，而三维空间中的单纯形则是四面体。 在单纯形替换算法中，从一个单纯形到另一个单纯形的迭代主要通过反射、扩张、收缩和缩边这4个操作来实现。下面以二维问题为例来对4种操作进行说明（参见下图）。 （1）反射——设除了最劣点X1以外的基余顶点的中心为X4，作X1关于点X4的对称点X5，称X5为X1的反射点。求反射点的过程称之为反射。 （2）扩张——在得到反射点X5之后，如果X5优于原单纯形的最劣点（即有 ），表明反射方向（X5—X1）是有利方向，反射成功。若进一步有 ，可沿反射方向前进适当的距离到点X6。X6称之为扩张点，求扩张点的过程称之为扩张。扩张之后，若扩张点X6优于反射点X5，则扩张成功，以X6取代X1，得新单纯形{X6,X2,X3}；否则，扩张失败，舍弃扩张点，以反射X5点取代X1，得新单纯形{X5,X2,X3}。 设当前的单纯形的顶点为X1，X2，X3，且有 * 第四章无约束优化方法 第一节 概述 从第一章列举的机械设计问题，大多数实际问题是约束优化问题。 约束优化问题的求解——转化为一系列的无约束优化问 题实现的。 因此，无约束优化问题的解法是优化设计方法的基本组 成部分，也是优化方法的基础。 无约束优化问题的极值条件 解析法 数值法 数学模型复杂时不便求解 可以处理复杂函数及没有数学表达式 的优化设计问题 搜索方向问题是无约束优化方法的关键。 各种无约束优化方法的区别：确定搜索方向的方法不同。 无约束优化方法分类 利用目标函数的一阶或二阶导数 利用目标函数值 （最速下降法、共轭梯度法、牛顿法） （坐标轮换法、鲍威尔等） 第二节 最速下降法 优化设计追求目标函数值最小，若搜索方向取该点的负梯度 方向，使函数值在该点附近的范围内下降最快。 按此规律不断走步，形成以下迭代算法： 以负梯度方向为搜索方向，所以称最速下降法或梯度法。 搜索方向确定为负梯度方向，还需确定步长因子 即求一维搜索的最佳步长，既有 由此可知，在最速下降法中，相邻两个迭代点上的函数 梯度相互垂直。而搜索方向就是负梯度方向，因此相邻 两个搜索方向互相垂直。 例4-1 求目标函数 的极小点。 第三节牛顿型方法 在第三章中，我们已经讨论了一维搜索的牛顿方法。 得出一维情况下的牛顿迭代公式 对于多元函数，在 泰勒展开，得 设 为函数的极小点，根据极值的必要条件 这是多元函数求极值的牛顿法迭代公式。 例4-2 用牛顿法求 的极小值。 对牛顿法进行改进，提出“阻尼牛顿法” 第四节共轭方向及共轭方向法 为了克服最速下降法的锯齿现象，提高收敛速度，发展了 一类共轭方向法。搜索方向是共轭方向。 一、共轭方向的概念 共轭方向的概念是在研究二次函数 时引出的。 首先考虑二维情况 如果按最速下降法，选择负梯度方向为搜索方向，会产生锯齿现象。 为避免锯齿的发生，取下一次的迭代搜索方向直接指向极 小点，如果选定这样的搜索方向，对于二元二次函