《维搜索方法》PPT课件.ppt

课程内容,第一部分 现代机械设计概述 第二部分 机械优化设计 第三部分 创新设计TRIZ 第四部分 绿色设计 第五部分 逆向设计,第三章 一维搜索方法,第一节 概 述,第二节 搜索区间的确定与区间消去法原理,第四节 一维搜索的插值方法,第三节 一维搜索的试探方法,1.用黄金分割法求函数f(x)=x2-3x+5在区间1，1.8中的极小点，迭代终止使用点距准则,=0.3。,。,第三章 练习,解析解：,第三章 练习,3.用牛顿法求极小点，f()= 4-4 3-3+5，初始点0=2.5，迭代终止使用点距准则,=0.2。,4.用二次插值法求迭代两次后的极小点，f()= sin，初始区间4,5。,寻查步长h的确定,寻查步长h：一维搜索的步长。若选得太小，需要迭代的次数增多；若选得太大，虽然一步就可以把极小点包括起来，但给下一步搜索极小点增加了负担。,步长h的取法： 第一次迭代时，使用下面的公式来求h,极小值的一个偏小估计值,以后各次迭代用前一次迭代所走的距离作为步长,1. 0.618的来历 2. 黄金分割法 3. 牛顿法迭代公式的推导 4. 牛顿法迭代法,第三章 一维搜索方法 重点内容,结 束,第三章 一维搜索方法,一维最优化问题只有一个设计变量的优化问题 一维搜索方法 一维优化问题的数值选代方法 一维问题的优化方法是多维问题优化方法的基础,迭代格式,（k=0,1,2,）,第三章 第一节 概述,第一节 概 述,一维优化的目的在既定的,和,因子,，使迭代产生的新点,的函数值为该方向上的最小。,下寻找最优步长,即求,为变量的一维优化问题的极值：,一维搜索最优化方法： 1）解析法：利用一元函数的极值条件,求,第三章 第一节 概述,须精确计算导数，函数复杂时无法进行。,2）数值计算法：格点法，黄金分割法（试探法）， 分数法，二次插值法 数值解法过程：,2.在搜索区间a，b中采用各种搜索法逐步缩小 此区间，获得,的近似值,所以求解,主要采用数值法。,1.确定,所在区间，定初始搜索区间a，b,第三章 第一节 概述,第二节 搜索区间的确定与区间消去法原理,单变量函数，单峰函数，凸函数，初始搜索区间特征：函数值为高-低-高，,有唯一的极小点,一、确定区间的外推法（进退法）,给定初值，h 初始步长,试点,1）,第三章 第二节 搜索区间的确定与区间消去法原理,2）,时，前进运算,a)当,、点的函数值满足（高，低，高）。,b)当,、点不满足（高，低，高）,为起点，步长加倍,重复搜索，前进，直至出现三个试点（高，低，高）,为搜索区间。,初始搜索区间确定,取,以,第三章 第二节 搜索区间的确定与区间消去法原理,3）,时，后退运算，取,将,对调，,计算,a)当,时，、点,b)当,时，、不满足（高，低，高）,为起点，步长加倍,后退，反复搜索直至出现（高低高）,为搜索区间。,初始搜索区间确定,以,取,满足（高，低，高）,第三章 第二节 搜索区间的确定与区间消去法原理,外推法程序框图，如图所示。,第三章 第二节 搜索区间的确定与区间消去法原理,二、区间消去法原理： 基本思想：当搜索区间a，b确定之后，逐步缩小搜索区间，直至最小点存在的范围达到允许的误差范围为止。在区间a ，b内任取两点a1，b1，使aa1b1b。,图35 区间消去法原理,比较f (a1)，f (b1)，有三种情况,（1）,丢掉,，留下,，图a,（2）,丢掉,，留下,图b，,第三章 第二节 搜索区间的确定与区间消去法原理,注意： 每次迭代中所保留点与新取点间的位置应该是对称的,区间消去法优劣评价指标。区间缩短率E,En=Ln/L0 Ln经n次迭代后的缩短区间，L0=b-a 原始区间,1由于区间缩小时插入点的位置确定方法不同， 形成了不同的一维搜索方法。 试探法：黄金分割法，Fibonaci数列法 2函数逼近法（插值法） 二次插值法,三次插值法,三、一维搜索方法的分类,第三章 第二节 搜索区间的确定与区间消去法原理,第三节 一维搜索的试探方法,一、0.618法的由来,要求：保留点在新区间的位置与丢去点原区间位置相当。,丢去,假设消去,取对称点,位置，相当于原来,第三章 第三节 一维搜索的试探方法,这种分割称为黄金分割，这种分割保证了每次区间的,）未变均为0.618，n次迭代缩短率,缩短率E（,黄金分割法的意义：,为将一段线分为两段的方法，使整段长与较长段比例等于较长段与较短段长度之比：,第三章 第三节 一维搜索的试探方法,（2）计算,比较函数值,并缩短搜索区间,取新点,二、迭代过程及算法框图,第三章 第三节 一维搜索的试探方法,(3)判断迭代终止条件,当,时，终止迭代，取,，转步骤(2),为收敛精度,如不满足条件,取新点,第三章 第三节 一维搜索的试探方法,0.618法程序框图如图,第三章 第三节 一维搜索的试探方法,例3-1,对函数,，当给定搜索区间,时，试用黄金分割法求极小点,。,解:,首先插入两点：,，,所以消去区间,则新的搜索区间,不变，,而端点,的端点,第三章 第三节 一维搜索的试探方法,第一次迭代：,插入点,则新的搜索区间为,列出前五次迭代的结果,第三章 第三节 一维搜索的试探方法,5次迭代后求得的最优解,解析解法可求得其精确解,第三章 第三节 一维搜索的试探方法,一、牛顿法,极值必要条件：,对上式求导得：,第四节 一维搜索的插值方法,插值法是利用若干试验点的函数值，利用插值方法建立函数的某种近似表达式，并求出该函数的极小点，用作原来函数极小点的近似值，逐步逼近极值点。,第三章 第四节 一维搜索的插值方法, 作为新的插值点,（k =0,1,2,）,牛顿法的几何意义如图39所示：,依次继续，得牛顿法迭代公式,第三章 第四节 一维搜索的插值方法,应为,的根，过,点的切线方程,为,，由,，得解,，再由,作切线与横坐标的交点,逐渐逼近,第三章 第四节 一维搜索的插值方法,一维搜索的切线法,牛顿法的迭代步骤见教材 牛顿法的特点： 收敛速度快 需要计算一阶、二阶导数，有局限，计算工作量较大 ,用一个二次多项式来逼近目标函数，然后求该二次多项式的极小点，逐次拟合，以达到精度为止,三点使,使,，作二次插值多项式：,二、二次插值法（抛物线法）,在a,b内取,时，迭代过程会发散,第三章 第四节 一维搜索的插值方法,在,三点上应满足插值条件,，即,由此可求得插值系数a0,a1,a2（见教材）,的极小点,可由,得：,为,极小点,的近似解。,第三章 第四节 一维搜索的插值方法,比较,与,大小和函数值,取其相邻两点，,a),舍去区间,新的三个插值点为,b),(,左侧)，舍去区间,，新的三个插值点为,1.如果,的大小取f小者，并,形成新的三个插值点：,图a所示,缩小搜索区间,下图所示,第三章 第四节 一维搜索的插值方法,2.如果,a),舍去区间,，新插值点为,b),，舍去区间,，新插值点为,原则：新的三个插值点应满足,在新区间内再用二次插