现代设计理论与方法(优化设计第三章)ppt课件.pptx

《现代设计理论与方法(优化设计第三章)ppt课件.pptx》由会员分享，可在线阅读，更多相关《现代设计理论与方法(优化设计第三章)ppt课件.pptx（46页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、致知力行明德任责Kunming University of Science and TechnologyFaculty of Mechanical and Electrical Engineering现代设计理论与方法（优化设计）现代设计理论与方法（优化设计）第三章第三章 一维搜索方法一维搜索方法机电学院机电学院 刘孝刘孝保保明德任责 致知力行篮球比赛是根据运动队在规定的比赛时间里得分多少来决定胜负的，因此，篮球比赛的计时计分系统是一种得分类型的系统第一第一节 一一维搜索概述搜索概述1第二第二节 搜索区搜索区间与区与区间消去法原理消去法原理2第四第四节 一一维搜索的插搜索的插值方法方法4第三第

2、三节 一一维搜索的搜索的试探方法探方法 3第第三三章章 一一维维搜搜索索方方法法目 录第五第五节 本章小本章小结5明德任责 致知力行篮球比赛是根据运动队在规定的比赛时间里得分多少来决定胜负的，因此，篮球比赛的计时计分系统是一种得分类型的系统第一节 一维搜索概述 求解优化问题的基本解法有：求解优化问题的基本解法有：解析法解析法解析法解析法数数数数值值解法解法解法解法解解解解析析析析法法法法：即即利利用用数数学学分分析析(微微分分、变变分分等等）的的方方法法，根根据据函函数数（泛泛函函）极极值值的的必必要要条条件件和和充充分分条条件件求求出出其其最最优优解解析析解解的的求求解解方方法法 。在在目目

3、标标函函数数比比较较简简单时，求解还可以。单时，求解还可以。局限性：局限性：工程优化问题的目标函数和约束条件往往工程优化问题的目标函数和约束条件往往比较复杂，有时甚至还无法用数学方程描述，在这比较复杂，有时甚至还无法用数学方程描述，在这种情况下应用数学分析方法就会带来麻烦。种情况下应用数学分析方法就会带来麻烦。明德任责 致知力行篮球比赛是根据运动队在规定的比赛时间里得分多少来决定胜负的，因此，篮球比赛的计时计分系统是一种得分类型的系统 数数值迭代法的值迭代法的基本思路：基本思路：基本思路：基本思路：是进行是进行反复的数值计算反复的数值计算，寻求，寻求目标函数值目标函数值不断下降的可行计算点不断

4、下降的可行计算点，直到最后获得足够精度，直到最后获得足够精度的最优点。这种方法的求优过程大致可归纳为以下步骤：的最优点。这种方法的求优过程大致可归纳为以下步骤：1 1）首先初选一个尽可能靠近最小点的初始点）首先初选一个尽可能靠近最小点的初始点X X（0 0），从，从X X（0 0）出发按照一定的原则寻找可行方向和初始步长，向前跨出出发按照一定的原则寻找可行方向和初始步长，向前跨出一步达到一步达到X X（1 1）点；点；2 2）得到新点）得到新点X X（1 1）后再选择一个新的使函数值迅速下降的后再选择一个新的使函数值迅速下降的方向及适当的步长，从方向及适当的步长，从X X（1 1）点出发再跨出

5、一步，达到点出发再跨出一步，达到X X（2 2）点，点，并依此类推，一步一步地向前探索并重复数值计算，最终达到并依此类推，一步一步地向前探索并重复数值计算，最终达到目标函数的最优点。目标函数的最优点。数值解法求解步骤明德任责 致知力行篮球比赛是根据运动队在规定的比赛时间里得分多少来决定胜负的，因此，篮球比赛的计时计分系统是一种得分类型的系统优化过程中每一步的迭代形式为：优化过程中每一步的迭代形式为：式中：式中：X X（k k）第第k k步迭代计算所得到的点，称第步迭代计算所得到的点，称第k k步迭代点，步迭代点，亦为第亦为第k k步设计方案；步设计方案；a a（k k）第第k k步迭代计算的步

6、长；步迭代计算的步长；S S（k k）第第k k步迭代计算的探索方向。步迭代计算的探索方向。图图1-8 1-8 迭代计算机逐步逼近最优点过程示意图迭代计算机逐步逼近最优点过程示意图 用用迭迭代代法法逐逐步步逼逼近近最最优优点点的探索过程如图的探索过程如图1-81-8所示。所示。明德任责 致知力行篮球比赛是根据运动队在规定的比赛时间里得分多少来决定胜负的，因此，篮球比赛的计时计分系统是一种得分类型的系统 运用迭代法，每次迭代所得新的点的目标函数都应满运用迭代法，每次迭代所得新的点的目标函数都应满足足函数值下降函数值下降的要求，并且的要求，并且最终收敛最终收敛（1 1）选择选择搜索方向搜索方向搜索

7、方向搜索方向（2 2）确定步）确定步）确定步）确定步长长因子因子因子因子（3）给定收定收敛准准则迭代法要解决的迭代法要解决的问题：明德任责 致知力行篮球比赛是根据运动队在规定的比赛时间里得分多少来决定胜负的，因此，篮球比赛的计时计分系统是一种得分类型的系统第一节 一维搜索概述 当当采采用用数数学学规规划划法法寻寻求求多多元元函函数数的的极极值值点点时时，一般要进行一系列如下格式的迭代计算一般要进行一系列如下格式的迭代计算:当方向当方向 给定，求最佳步长给定，求最佳步长 就是求一元函数就是求一元函数 :的极值问题，这一过程被称为一维搜索的极值问题，这一过程被称为一维搜索.明德任责 致知力行篮球比

8、赛是根据运动队在规定的比赛时间里得分多少来决定胜负的，因此，篮球比赛的计时计分系统是一种得分类型的系统明德任责 致知力行篮球比赛是根据运动队在规定的比赛时间里得分多少来决定胜负的，因此，篮球比赛的计时计分系统是一种得分类型的系统 一维搜索方法解析法高等数学已学过，即利用一维函数的极一维搜索方法解析法高等数学已学过，即利用一维函数的极值条件：值条件：一维搜索方法数值解法分类一维搜索方法数值解法分类 一维搜索也称直线搜索。这种方法不仅对于解决一维最优化本一维搜索也称直线搜索。这种方法不仅对于解决一维最优化本身具有实际意义，而且也是解多维最优化问题的重要支柱。身具有实际意义，而且也是解多维最优化问题

9、的重要支柱。明德任责 致知力行篮球比赛是根据运动队在规定的比赛时间里得分多少来决定胜负的，因此，篮球比赛的计时计分系统是一种得分类型的系统1.1.解析法：解析法：步骤步骤:f(X:f(X(k)(k)+S+S(k)(k)沿沿S S(k)(k)方向在方向在x x(k)(k)点进行泰勒展开；点进行泰勒展开；取二次近似：取二次近似：一维搜索的目标函数可表示为：一维搜索的目标函数可表示为：明德任责 致知力行篮球比赛是根据运动队在规定的比赛时间里得分多少来决定胜负的，因此，篮球比赛的计时计分系统是一种得分类型的系统对对求导，令其为零。求导，令其为零。求得最优步长求得最优步长明德任责 致知力行篮球比赛是根据

10、运动队在规定的比赛时间里得分多少来决定胜负的，因此，篮球比赛的计时计分系统是一种得分类型的系统从上式看出，用解析法求最优步长面临的问题：从上式看出，用解析法求最优步长面临的问题：需要求导，对与复杂函数，求导困难和无法求需要求导，对与复杂函数，求导困难和无法求导的情况，将不适用。导的情况，将不适用。因此工程中，通常采用数值解法求最优步长，因此工程中，通常采用数值解法求最优步长，以迭代的方式逐步逼近最优解。以迭代的方式逐步逼近最优解。明德任责 致知力行篮球比赛是根据运动队在规定的比赛时间里得分多少来决定胜负的，因此，篮球比赛的计时计分系统是一种得分类型的系统第二节 搜索区间的确定与区间消去法原理

11、1 1、单谷、单谷(峰）区间峰）区间 在给定区间内仅有一个谷值的函数称为单谷数，其在给定区间内仅有一个谷值的函数称为单谷数，其区间称为单谷区间。区间称为单谷区间。一、一、一、一、一一一一维维搜索的基本思想搜索的基本思想搜索的基本思想搜索的基本思想O f(a)b x*x a 函数值：“大小大”图形：“高低高”单谷区间中一定能求得一个极小点找初始单谷区间是一维搜索的第一步；第二步使区间缩小。明德任责 致知力行篮球比赛是根据运动队在规定的比赛时间里得分多少来决定胜负的，因此，篮球比赛的计时计分系统是一种得分类型的系统f(x)0130f(x)31说明：单谷区间内，函数可以有不可微点，也可以是不连续函数

12、；明德任责 致知力行篮球比赛是根据运动队在规定的比赛时间里得分多少来决定胜负的，因此，篮球比赛的计时计分系统是一种得分类型的系统（2）外推方法基本思想：对 任选一个初始点 及初始步长 ，通过比较这两点函数值的大小，确定第三点位置，比较这三点的函数值大小，确定是否为“高低高”形态。步骤：1）选定初始点a1，初始步长h=h0，计算y1=f(a1)和y2=f(a1+h)2）比较y1和y2；a）如果y1y2，向右前进，加大步长h=2h0，转（3）向前；b）如果y1y3，加大步长h=2h，a1=a2,a2=a3,转（3）继续探测；b）如果y2y3，则初始区间得到：a=mina1,a3,b=maxa1,a

13、3，函数最小值所在区间为a,b。明德任责 致知力行篮球比赛是根据运动队在规定的比赛时间里得分多少来决定胜负的，因此，篮球比赛的计时计分系统是一种得分类型的系统khx1x2x30h0初始点初始点初始点初始点+h012h0初始点初始点初始点初始点+h0初始点初始点+3h024h0初始点初始点+h0初始点初始点+3h0初始点初始点+7h038h0初始点初始点+3h0初始点初始点+7h0初始点初始点+15h0前进搜索步骤表khx1x2x30h0初始点初始点初始点初始点+h012h0初始点初始点+h0初始点初始点初始点初始点-2h024h0初始点初始点初始点初始点-2h0初始点初始点-6h038h0初始

14、点初始点-2h0初始点初始点-6h0初始点初始点-14h0后退搜索步骤表明德任责 致知力行篮球比赛是根据运动队在规定的比赛时间里得分多少来决定胜负的，因此，篮球比赛的计时计分系统是一种得分类型的系统（3）搜索区间外推法程序框图是否是是否否初始进退距前进计算后退计算明德任责 致知力行篮球比赛是根据运动队在规定的比赛时间里得分多少来决定胜负的，因此，篮球比赛的计时计分系统是一种得分类型的系统khx1 y1x2 y2x3 y300.10.20 90.1 8.2030.3 6.68110.40.1 8.2030.3 6.6810.7 4.42920.80.3 6.6810.7 4.4291.5 7.1

15、25解：明德任责 致知力行篮球比赛是根据运动队在规定的比赛时间里得分多少来决定胜负的，因此，篮球比赛的计时计分系统是一种得分类型的系统khx1 y1x2 y2x3 y300.1-0.21.8 12.096 1.9 14.3771.9 14.3771.8 12.0961.6 8.488 1-0.41.8 12.0961.6 8.4881.2 4.5842-0.81.6 8.4881.2 4.5840.4 5.992明德任责 致知力行篮球比赛是根据运动队在规定的比赛时间里得分多少来决定胜负的，因此，篮球比赛的计时计分系统是一种得分类型的系统练习：确定练习：确定 在以下初始条件下的初始搜索区间。在以

16、下初始条件下的初始搜索区间。k kh hx x1 1 y y1 1x x2 2 y y2 2x x3 3 y y3 30 01 12 20 9 0 9 1 41 4 3 03 01 14 41 41 43 03 07 167 16得区间 k kh hx x1 1 y y1 1x x2 2 y y2 2x x3 3 y y3 30 01 1-2-25 4 5 4 6 96 96 96 95 45 4 3 03 01 1-4-45 45 43 03 0-1 16-1 16得区间 2）取解：1）取明德任责 致知力行篮球比赛是根据运动队在规定的比赛时间里得分多少来决定胜负的，因此，篮球比赛的计时计分系

17、统是一种得分类型的系统 编程演示Matlab编程实现外推法明德任责 致知力行篮球比赛是根据运动队在规定的比赛时间里得分多少来决定胜负的，因此，篮球比赛的计时计分系统是一种得分类型的系统2、区间消去法原理极小点必在区间 内。则取为 缩短后的搜索区间。基本思想：搜索区间确定之后，采用区间消去法逐步缩短搜索区间，从而找到极小点的数值近似解。基本原理：在搜索区间 内任取两点 且 计算其函数值得如下结论：明德任责 致知力行篮球比赛是根据运动队在规定的比赛时间里得分多少来决定胜负的，因此，篮球比赛的计时计分系统是一种得分类型的系统缩小的新区间为必在 。缩小的新区间为必在 ；明德任责 致知力行篮球比赛是根据

18、运动队在规定的比赛时间里得分多少来决定胜负的，因此，篮球比赛的计时计分系统是一种得分类型的系统3、一维搜索方法分类根据插入点位置的确定方法，可以把一维搜索法分成两大类：试探法：即按照某种规律来确定区间内插入点的位置，如黄金分割法，裴波纳契法等。裴波纳契数列：1、1、2、3、5、8、13、21、34、55、89、144 插值法（函数逼近法）：通过构造插值函数来逼近原函数，用插值函数的极小点作为区间的插入点，如二次插值法，三次插值法等。明德任责 致知力行篮球比赛是根据运动队在规定的比赛时间里得分多少来决定胜负的，因此，篮球比赛的计时计分系统是一种得分类型的系统第三节 一维搜索的试探方法黄金分割1、

19、前提 函数在区间 上是单谷函数。2、点的插入原则（1）要求插入点 的位置相对于区间 两端点具有对称性。（2）要求保留下来的区间内再插入一点所形成的新三段具有相同的比例分布。明德任责 致知力行篮球比赛是根据运动队在规定的比赛时间里得分多少来决定胜负的，因此，篮球比赛的计时计分系统是一种得分类型的系统3、点位置的确定方法结论：所谓黄金分割是指将一线段分成两段的方法，使整段长与较长段的长度比值等于较长段与较短段长度的比值两内分点值:明德任责 致知力行篮球比赛是根据运动队在规定的比赛时间里得分多少来决定胜负的，因此，篮球比赛的计时计分系统是一种得分类型的系统4、黄金分割法的搜索过程（1）给出初始搜索区

20、间 及收敛精度 ，将 赋以（2）按坐标点计算公式计算 并计算其对应的函数值（3）根据区间消去法原理缩短搜索区间。为了能用原来的坐标点计算公式，进行区间名称的代换，并在保留区间中计算一个新的试验点及其函数值。（4）检查区间是否缩短到足够小和函数值收敛到足够近，如果条件不满足返回到步骤（2）。（5）如果条件满足，则取最后两试验点的平均值作为极小点的数值近似解。缩短区间的总次数（迭代次数）:明德任责 致知力行篮球比赛是根据运动队在规定的比赛时间里得分多少来决定胜负的，因此，篮球比赛的计时计分系统是一种得分类型的系统5、黄金分割法程序框图给定否否是是止也可采用迭代次数是否大于或等于 k 作终止准则。明

21、德任责 致知力行篮球比赛是根据运动队在规定的比赛时间里得分多少来决定胜负的，因此，篮球比赛的计时计分系统是一种得分类型的系统例题：对函数，当给定搜索区间时，试用黄金分割法求极小点。表表3-1 3-1 黄金分割法的搜索过程黄金分割法的搜索过程迭代序迭代序号号aa1a2by1比较y20-30.0561.94450.1157.6671-3-1.1110.0561.944-0.987-0.9873-1.832-1.111-0.6650.056-0.987-0.9875-1.386-1.111-0.940-0.665明德任责 致知力行篮球比赛是根据运动队在规定的比赛时间里得分多少来决定胜负的，因此，篮球

22、比赛的计时计分系统是一种得分类型的系统实例编程利用matlab进行黄金分割法明德任责 致知力行篮球比赛是根据运动队在规定的比赛时间里得分多少来决定胜负的，因此，篮球比赛的计时计分系统是一种得分类型的系统第四节 一维搜索的插值方法 在某一确定的区间内寻求函数的极小点位置，虽然没有函数表达式，但能够给出若干点处的函数值。可以根据这些点处的函数值，利用插值方法建立函数的某种近似表达式，进而求出函数的极小点，并用它作为原来函数极小点的最小值，这种方法称作插值方法，又叫函数逼近法。明德任责 致知力行篮球比赛是根据运动队在规定的比赛时间里得分多少来决定胜负的，因此，篮球比赛的计时计分系统是一种得分类型的系

23、统试探法（如黄金分割法）与插值法的比较：相同点：两种方法都是利用区间消去法原理将初始搜索区间不断缩短，求得极小值的数值近似解。试探法：试验点是按照某种个特定的规律确定；不考虑函数值的分布；不同点：表现在试验点（插入点）位置的确定方法不同。插值法：试验点是按照函数值近似分布的极小点确定；利用了函数值本身及其导数信息。明德任责 致知力行篮球比赛是根据运动队在规定的比赛时间里得分多少来决定胜负的，因此，篮球比赛的计时计分系统是一种得分类型的系统1、牛顿法（切线法）对于一维搜索函数 ，假定已经给出极小点的一个较好的近似点 ，在 点附近用一个二次函数 来逼近函数 然后以该二次函数 的极小点作为 极小点的

24、一个新的近似点 。根据极值必要条件：明德任责 致知力行篮球比赛是根据运动队在规定的比赛时间里得分多少来决定胜负的，因此，篮球比赛的计时计分系统是一种得分类型的系统牛顿法的几何解释：在上图中，在 处用一抛物线 代替曲线 ，相当于用一斜线 代替 。这样各个近似点是通过对 作切线求得与 轴的交点找到，故牛顿法又称为切线法。明德任责 致知力行篮球比赛是根据运动队在规定的比赛时间里得分多少来决定胜负的，因此，篮球比赛的计时计分系统是一种得分类型的系统牛顿法的计算步骤：1）给定初始点，控制误差，并令 2）计算 3）求 4）若，则求得近似解 ，停止计算，否则作5）。5）令 转2）。明德任责 致知力行篮球比赛

25、是根据运动队在规定的比赛时间里得分多少来决定胜负的，因此，篮球比赛的计时计分系统是一种得分类型的系统例题：给定，试用牛顿法求其极小点 。解：1）给定初始点，控制误差 2）3）4）明德任责 致知力行篮球比赛是根据运动队在规定的比赛时间里得分多少来决定胜负的，因此，篮球比赛的计时计分系统是一种得分类型的系统重复上边的过程，进行迭代，直到 为止。可得到计算结果如下表:表表3-2 3-2 牛顿法的搜索过程牛顿法的搜索过程k k0 01 12 23 34 4值值a ak k3 35.166675.166674.334744.334744.03964.03964.000664.00066f(af(ak k

26、)-52-52153.35183153.3518332.3019932.301993.382993.382990.005510.00551f(af(ak k)-24-24184.33332184.33332109.44586109.4458686.8699286.8699284.0472084.04720a ak+1k+15.166675.166674.334744.334744.039604.039604.000664.000664.000594.00059明德任责 致知力行篮球比赛是根据运动队在规定的比赛时间里得分多少来决定胜负的，因此，篮球比赛的计时计分系统是一种得分类型的系统优点：收敛

27、速度快。缺点：每一点都要进行二阶导数，工作量大；当用数值微分代替二阶导数，由于舍入误差会影响迭代速度；要求初始点离极小点不太远，否则有可能使极小化发散或收敛到非极小点。牛顿法的特点：明德任责 致知力行篮球比赛是根据运动队在规定的比赛时间里得分多少来决定胜负的，因此，篮球比赛的计时计分系统是一种得分类型的系统、二次插值法（抛物线法）基本思想：利用目标函数在不同3点的函数值构成一个与原函数 相近似的二次多项式 ，以函数 的极值点 （即 的根）作为目标函数 的近似极值点。明德任责 致知力行篮球比赛是根据运动队在规定的比赛时间里得分多少来决定胜负的，因此，篮球比赛的计时计分系统是一种得分类型的系统（1

28、）二次插值多项式的构成及其极值点设 在单谷区间中的三点 的相应函数值，则可以做出如下的二次插值多项式：明德任责 致知力行篮球比赛是根据运动队在规定的比赛时间里得分多少来决定胜负的，因此，篮球比赛的计时计分系统是一种得分类型的系统多项式 的极值点可从极值的必要条件求得，即 明德任责 致知力行篮球比赛是根据运动队在规定的比赛时间里得分多少来决定胜负的，因此，篮球比赛的计时计分系统是一种得分类型的系统）如果区间长度 足够小，则由 便得出我们所要求的近似极小点 2）如果不满足，必须缩小区间，根据区间消取法原理不断缩小区间。结论明德任责 致知力行篮球比赛是根据运动队在规定的比赛时间里得分多少来决定胜负的

29、，因此，篮球比赛的计时计分系统是一种得分类型的系统二次插值的8种换名情况明德任责 致知力行篮球比赛是根据运动队在规定的比赛时间里得分多少来决定胜负的，因此，篮球比赛的计时计分系统是一种得分类型的系统二次插值法程序框图明德任责 致知力行篮球比赛是根据运动队在规定的比赛时间里得分多少来决定胜负的，因此，篮球比赛的计时计分系统是一种得分类型的系统例：用二次插值法求 上的极小点。表表3-4 3-4 二次插值法计算过程示例二次插值法计算过程示例12a144.5a24.54.705120a355y1-0.756802-0.977590y2-0.977590-0.999974y3-0.958924-0.958924ap4.7051204.710594yp-0.999974-0.999998本节结束