优化设计第四次课PPT课件.ppt

《优化设计第四次课PPT课件.ppt》由会员分享，可在线阅读，更多相关《优化设计第四次课PPT课件.ppt（48页珍藏版）》请在金锄头文库上搜索。

1、第三节黄金分割法 一 黄金分割法的基本原理 黄金分割法的基本思想 每次缩小后的新区间长度与原区间长度的比值始终是一个常数 此常数为0 618 也就是说每次的区间的缩小率等于0 618 1 黄金分割法的原理 2 再进一步缩小区间 可在区间内取一点 该点与原来的点对称 即 若 则丢掉段 保留段 即为缩小后的新区间 由于和是开始时的区间的两个对称点 因此有 于是本次的区间缩小率为 按每次区间的缩小率相等的原则 有 由此关系式可以求出区间缩小率 即 取其正根 得 3 二 黄金分割法的搜索过程 4 5 黄金分割法的程序框图 6 例 用黄金分割法求函数的最优解 已知初始搜索区间为 迭代精度 7 第四节一维

2、搜索的插值方法 如果给定的问题是在某一确定区间内寻求函数的极小点位置 虽然没有函数表达式 但我们可以知道一些试验点处的函数值 我们可以根据这些点处的函数值 利用插值方法建立函数的某种近似表达式 进而求出函数的极小点 并用它作为原来函数极小点的近似值 这种方法称作插值方法 又称作函数逼近法 8 插值方法和试探方法都是利用区间消去法原理将初始搜索区间不断缩短 从而求得极小点的数值近似解 二者不同之处在于试验点位置的确定方法不同 在试探法中试验点位置是有某种给定的规律确定的 它不考虑函数值的分布 例如 黄金分割法是按照等比例缩短率确定的 而在插值法中 试验点位置是按函数值近似分布的极小点确定的 试探

3、法仅仅利用了试验点函数值大小的比较 而插值法还要利用函数值本身或者其导数信息 由于试探法仅对试验点函数值的大小进行比较 而函数值本身的特性没有得到充分利用 这样即使对一些简单的函数 例如二次函数 也不得不像一般函数那样进行同样多的函数值计算 插值法则是利用函数在已知试验点的值 或导数值 来确定新试验点的位置 当函数具有比较好的解析性质时 例如连续可微性 插值方法比试探方法效果更好 9 多项式是函数逼近的一种常用工具 在搜索区间内我们可以利用若干试验点处的函数值来构造低次多项式 用它作为函数的近似表达式 并用这个多项式的极小点作为原函数极小点的近似 常用的插值多项式为二次多项式 因此 我们介绍两

4、种用二次函数逼近原理函数的方法 一种方法是抛物线法 二次插值法 它是利用三个点的函数值形成一个抛物线来构造此二次函数的 一种方法是牛顿法 牛顿切线法 它是利用一点的函数值 一阶导数值和二阶导数值来构造此二次函数的 10 一 二次插值法 二次插值法是求一元函数最优解的另一种常用方法 这种方法是在已确定的单峰区间内 利用若干点的函数值构成一个低次的插值多项式 用它拟合原来的一元函数 求出这个插值多项式的极小点 并近似地作为原函数的极小点 由于低次多项式的极小点求解比较容易 所以常用二次或三次插值多项式来逼近目标函数 分别称为二次插值法或三次插值法 二次插值法 又称抛物线法 计算简单 并且具有一定计

5、算精度 应用较广 11 二次插值法的基本原理 二次插值的原理 式中 为待定系数 根据插值条件 所求的二次插值多项式曲线应通过三个插值点 如图中虚线所示 因此 这三个点都应满足二次插值多项式式 即 12 为了求解多项式 的极值点 令其一阶导数等于零 即 于是 式 是二次多项式的极值点表达式 将系数和计算出来代入式 即可确定这个极值点 在线性方程组式 中 利用相邻两个方程消去 可得到含和的方程组 13 解上述方程组 就得到所需的系数和 并代入式 就得到极值点公式 就是函数在区间的近似最优解 一般记作 处的函数值会比函数值 和都好 就是说 该点比 三点更接近最优点 由于二次多项式仅是原函数的近似描述

6、 一般不能一次就达到函数的最优点 需要多次缩小区间 反复做二次插值多项式 使最后求得的多项式的最优点与原函数最优点距离充分小 直到满足精度的要求为止 14 区间的缩小 若 即排列顺序为 将改为 则有 引用前面讲的消去法的思想来缩小区间 即比较有关点的函数值大小来消去一部分区间 比较 的函数值与的大小 有下面两种情况 15 如图a 所示 此时取新区间 并作符号置换 如图b c 所示 此时取新区间 并作符号置换 a b c 16 d e f 若 即排列顺序为 也把改为 则为 比较 两点函数值与有下面两种情况 如图e f 所示 此时取新区间 并作符号置换 17 二次插值计算步骤 1 确定初始搜索区间

7、 该区间应为单峰区间 确定方法采用第二节的进退算法 在区间内取一点 将三点 作为二次插值的初始点 点的选择有下列两种方式 与两端点和等距 即取 与两端点和不等距 常采用的比例关系为 3 按照式 计算二次插值函数的极值点 并把它改换为 18 4 若满足计算精度要求 则停止计算 并输出极小点和极小值 若不满足精度要求 则要进一步缩小搜索区间 19 二 牛顿法 牛顿法又称切线法 该法求无约束一维极值问题的收敛速度较快 它的每一步迭代方向都是沿着当前函数值下降方向 牛顿法的有效性依赖于初始点的选择 牛顿法的基本原理 对于一维函数 假定已给出极值点附近一个较好的近似点 因为一个连续可微的函数在极值点附近

8、可用一个二次函数近似 所以可在点附近用一个二次函数来近似函数函 即在将进行泰勒展开并保留到二次项 有 20 即 得到 依此继续 可得牛顿法迭代公式 21 牛顿法原理 牛顿法的几何解释 如图所示 在a 中 在处用一抛物线代替曲线 相当于用一斜线代替曲线 抛物线极值点作为第一个近似点应处于斜线与轴的交点处 如图b 所示 这样各个近似点是通过对作切线求得与轴的交点而找到的 所以牛 顿法又称切线法 22 牛顿法的计算步骤 给定初始点 精度 令 计算 求 若则求得近似解 停止计算 否则转步骤 令 转步骤 23 例 试用牛顿法求函数的极小点 24 牛顿法最大的优点是收敛速度快 但是在每一点处都要计算函数的

9、二阶导数 因而增加了每次迭代的工作量 特别是用数值微分代替二阶导数时 舍入误差会影响牛顿法的收敛速度 当很小时这个问题更严重 另外 牛顿法要求初始点选得要比较好 也就是说离极小点不太远 否则有可能使极小化序列发散或收敛到非极小点 25 作业 26 无约束优化方法 27 第一节概述 研究机械优化设计中的无约束优化问题是出于以下几个方面的考虑 首先 在机械优化设计中 也有些实际问题 其数学模型本身就是一个无约束优化问题 或者除了在非常接近最终极小点的情况下 都可以按无约束问题来处理 其次 研究无约束优化问题的解法也可以为更好地求解约束优化问题打下良好的基础 最后 由于无约束问题的求解比较容易 并且

10、已经有许多行之有效的算法 因此 把约束优化问题转换成无约束优化问题是解约束优化问题的一类有效算法 无约束优化方法已经逐渐成为对某些工程问题进行分析的一个有效的方法 28 求目标函数的极值时 若对设计变量没有任何限制 可在实欧氏空间中任意取值 则称为无约束问题 它的一般形式为 求 使 4 1 式中 为维设计变量 为目标函数 求解式 4 1 可以利用第2章所讲的无约束极值条件存在的必要条件 即 4 2 解上式所确定的方程组 求得驻点后 再根据充分条件来判断是否为极小点 29 解上述方程组 求得驻点后 再根据极值点所需满足的充分条件 海色矩阵正定 来判定是否为极小值点 但上式是一个含有n个未知量 n

11、个方程的方程组 并且在实际中一般是非线性的 对于非线性方程组的求解 一般是很难用解析法求解的 需要采用数值计算方法逐步求出非线性联立方程组的解 但是 与其用数值计算方法求解非线性方程组 倒不如用数值计算方法直接求解无约束极值问题 因此 本章将介绍求解无约束优化问题常用的数值解法 30 无约束问题下降算法的基本迭代格式 下降算法的迭代过程 在求解多变量无约束极值问题时 一般不去解式 4 2 而是直接从原问题式 4 1 中的特征出发 构成一种使用目标函数值步步减小的下降迭代算法 这一算法的基本思想是沿着目标函数值降低的方向 一步步向前搜索 最终找到最优解 迭代过程如上图所示 31 下降算法步骤归纳

12、如下 1 选定一个初始点 置 2 确定适当的使目标函数值下降的搜索方向 应满足 上式的几何意思 表示点的下降方向应取过点与目标函数的梯度方向成钝角的范围内 或者说 与目标函数负梯度方向锐角的范围内 这是各种下降算法中确定搜索方向的一个总的原则 如图4 2所示 32 图4 2搜索方与梯度方向间的关系 3 确定步长因子 使得 4 按下面的迭代公式 确定下一个迭代点 即 式 4 6 是迭代算法运算的基本公式 5 判断是否满足迭代终止准则 是否为一个近似的极值点 33 34 无约束优化方法分类 一类是利用目标函数的一阶或二阶导数信息的无约束优化方法 如最速下降法 牛顿法 共扼梯度法及变尺度法等 另一类

13、是只利用目标函数值信息的无约束优化方法 加坐标轮换法 鲍咸尔法 Powell 及单纯形法等 第一类方法由于考虑了函数的变化率 因而收敛速度较快 但计算量一般较大 第二类方法能够避免在迭代过程中求解海色矩阵 进而可有效地减小计算量 根据确定搜索方向所使用信息性质的不同 无约束优化方法可以分为两类 35 第二节最速下降法 最速下降法是求解无约束多元函数极值问题的古老算法之一 早在1847年就已由柯西提出 该方法形式直观 原理简单 是其他更为实用有效的无约束和约束优化方法的理论基础 因此 最速下降法是无约束优化方法中最基本的方法之一 36 一 最速下降法的基本原理 设维目标函数 从迭代点出发 沿着按

14、某种方向所确定的方向 搜索极小点 其迭代算法如下 取搜索方向为负梯度方向 该方向的单位向量可表示为 其中 是点梯度的模 于是就形成了下面的迭代算法 4 7 37 式中 为最优步长因子 即在负梯度方向上 函数值达到最小的步长因子 可以按照一元函数极值的必要条件求得 也可以用一维搜索的0 618法或二次插值法直接迭代求出 最速下降法是以负梯度方向作为搜索方向 所以最速下降法又称为梯度法 根据一元函数极值的必要条件和多元复合运数求导公式 得 即 也可写成 38 由此可知 在最速下降法中 相邻两个迭代点上的函数梯度相互正交 而搜索方向就是负梯度方向 因此相邻两个搜索方向互相正交 下图为二维目标函数采用

15、最速下降法的搜索过程示意图 39 二 最速下降法的计算步骤 1 取初始点 收敛精度为 并令 2 计算点的梯度 以及搜索方向 4 进行一维搜索 求最佳步长 即 5 令 转步骤 2 40 最速下降法算法流程图 41 三 最速下降法的特点 42 同理 以后的迭代中也总是前后两次迭代方向互为正交 因此 随着迭代过程的进行 最速下降法的搜索路径呈现 之 字形的锯齿现象 越靠近极小点 搜索点的密度越大 降低了收敛速度 43 44 4 按负梯度方向搜索并不等同于以最短时间到达最优点 因为 负梯度方向是函数值最速下降方向 仅是迭代点邻域内的一种局部性质 从局部上看 在一点附近函数的下降是快的 但从整体上看则走了许多弯路 下降的并不算快 因此 从整个迭代过程来看 最速下降法并不具有 最速下降 的性质 总的来说 最速下降法采用了函数的负梯度方向作为下一步的搜索方向 整个搜索过程中收效速度较慢 越是接近极值点收敛越慢 这是它的主要缺点 但是 应用最速下降法可以使目标函数在开头几步下降很快 所以它可与其他无约束优化方法配合使用 特别是一些更有效的方法都是在对它进行改进后 或在它的启发下获得的 因此最速下降法仍是许多有约束和无约束优化方法的基础 45 例 利用梯度法求目标函数的极小值 设初始点 收敛精度 46 47 例 采用最速下降法求解函数的极小值 给定初始点 迭代精度 课堂作业 48