第03章一维搜索方法

1、课程内容课程内容第一部分第一部分 现代机械设计概述现代机械设计概述第二部分第二部分 机械优化设计机械优化设计第三部分第三部分 创新设计创新设计triz 第四部分第四部分 绿色设计绿色设计第五部分第五部分 逆向设计逆向设计第三章 一维搜索方法第一节第一节 概概 述述第二节第二节 搜索区间的确定与区间消去法原理搜索区间的确定与区间消去法原理第四节第四节 一维搜索的插值方法一维搜索的插值方法第三节第三节 一维搜索的试探方法一维搜索的试探方法 1.1.用黄金分割法求函数用黄金分割法求函数f(xf(x)=x)=x2 2-3x+5-3x+5在区间在区间11，1.81.8中中的极小点，迭代终止使用点距准则的

2、极小点，迭代终止使用点距准则, ,=0.3=0.3。 第三章 练习2. 2. 用用0.6180.618法对函数法对函数f(xf(x)=x)=x1 12 2+ 25x+ 25x2 22 2，从起点，从起点x= x= 22沿方向沿方向 1004s进行一维搜索，进行一维搜索，a=0,b=0.1,a=0,b=0.1,要求精度要求精度 0001. 0，步长，步长h=0.02h=0.02。 （可编程）（可编程） 解析解：解析解： 0030718. 0919877128. 1*x686164. 3)(*xf020030718. 0*第三章 练习3.3.用牛顿法求极小点，用牛顿法求极小点，f()= f()=

3、4 4-4-4 3 3-3-3+5+5，初始，初始点点0 0=2.5=2.5，迭代终止使用点距准则迭代终止使用点距准则, ,=0.2=0.2。4.4.用二次插值法求用二次插值法求迭代两次后的迭代两次后的极小点，极小点，f()= f()= sinsin，初始区间，初始区间4,54,5。寻查步长寻查步长h h的确定的确定寻查步长寻查步长h h：一维搜索的步长。若选得太小，需要迭代的次：一维搜索的步长。若选得太小，需要迭代的次数增多；若选得太大，虽然一步就可以把极小点数增多；若选得太大，虽然一步就可以把极小点包括起来，但给下一步搜索极小点增加了负担。包括起来，但给下一步搜索极小点增加了负担。步长步长

4、h h的取法：的取法： 第一次迭代时，使用下面的公式来求第一次迭代时，使用下面的公式来求h h),min()(kdkh1)()()()()(ktkkxfdxfestk2)()(kxfest1001101极小值的一个偏小估计值极小值的一个偏小估计值以后各次迭代用前一次迭代所走的距离作为步长以后各次迭代用前一次迭代所走的距离作为步长)()(1kkxxh1. 0.6181. 0.618的来历的来历2. 2. 黄金分割法黄金分割法3. 3. 牛顿法迭代公式的推导牛顿法迭代公式的推导4. 4. 牛顿法迭代法牛顿法迭代法第三章 一维搜索方法重点内容结 束第三章 一维搜索方法)1()()()()(kkxkk

5、kdxx一维最优化问题一维最优化问题只有一个设计变量的优化问题只有一个设计变量的优化问题一维搜索方法一维搜索方法 一维优化问题的数值选代方法一维优化问题的数值选代方法一维问题的优化方法是多维问题优化方法的基础一维问题的优化方法是多维问题优化方法的基础 迭代格式迭代格式)()()()1(kkkkdxx （k k=0,1,2,=0,1,2,） 第三章第三章 第一节第一节 概述概述第一节第一节 概概 述述一维优化的目的一维优化的目的在既定的在既定的)(kx和和)(kd因子因子)(k，使迭代产生的新点，使迭代产生的新点) 1( kx的函数值为该方向上的最小。的函数值为该方向上的最小。 下寻找最优步长下

6、寻找最优步长即求即求)(k为变量的一维优化问题的极值：为变量的一维优化问题的极值：*)()()()(*)()()(min)()(kkkkkkffxfdxdx1一维搜索最优化方法：一维搜索最优化方法：1 1）解析法：利用一元函数的极值条件）解析法：利用一元函数的极值条件0)(*f求求*第三章第三章 第一节第一节 概述概述须精确计算导数，函数复杂时无法进行。须精确计算导数，函数复杂时无法进行。*2 2）数值计算法：格点法，黄金分割法（试探法），）数值计算法：格点法，黄金分割法（试探法）， 分数法，二次插值法分数法，二次插值法数值解法过程：数值解法过程：*2.2.在搜索区间在搜索区间 a a，b b

7、 中采用各种搜索法逐步缩小中采用各种搜索法逐步缩小 此区间，获得此区间，获得*的近似值的近似值所以求解所以求解主要采用数值法。主要采用数值法。1.1.确定确定所在区间，定初始搜索区间所在区间，定初始搜索区间 a a，b b 第三章第三章 第一节第一节 概述概述第二节第二节 搜索区间的确定与区间消去法原理搜索区间的确定与区间消去法原理)(f单变量函数，单峰函数，凸函数，初始搜单变量函数，单峰函数，凸函数，初始搜索区间特征：函数值为高索区间特征：函数值为高- -低低- -高，高，)(f有唯一的极小点有唯一的极小点*一、确定区间的外推法（进退法）一、确定区间的外推法（进退法）0给定初值，给定初值，h

8、 h 初始步长初始步长0h01h12试点试点 )( )(2211ffff1 1）第三章第三章 第二节第二节 搜索区间的确定与区间消去法原理搜索区间的确定与区间消去法原理2 2）12ff时，前进运算时，前进运算)( 3323ffh a) a)当当32ff 、点的函数值、点的函数值满足（高，低，高）。满足（高，低，高）。,31b)b)当当32ff 、点不满足（高，低，高）、点不满足（高，低，高）2为起点，步长加倍为起点，步长加倍hhh233221,:2重复搜索，前进，直至出现三个试点（高，低，高）重复搜索，前进，直至出现三个试点（高，低，高）,31为搜索区间。为搜索区间。 初始搜索区间确定初始搜索

9、区间确定取取以以第三章第三章 第二节第二节 搜索区间的确定与区间消去法原理搜索区间的确定与区间消去法原理12ff 3 3）时，后退运算，取时，后退运算，取hh将将2211,ff与对调，对调，h23计算计算)(33ff a) a)当当23ff 时，、点时，、点,13b)b)当当23ff 时，、不满足（高，低，高）时，、不满足（高，低，高）2为起点，为起点，步长加倍步长加倍hhh233221,2后退，反复搜索直至出现（高后退，反复搜索直至出现（高低低高）高）,13为搜索区间。为搜索区间。 初始搜索区间确定初始搜索区间确定以以取取满足（高，低，高）满足（高，低，高）第三章第三章 第二节第二节 搜索区

10、间的确定与区间消去法原理搜索区间的确定与区间消去法原理外外推推法法程程序序框框图，图，如如图图所所示。示。 第三章第三章 第二节第二节 搜索区间的确定与区间消去法原理搜索区间的确定与区间消去法原理二、区间消去法原理：二、区间消去法原理： 基本思想：当搜索区间基本思想：当搜索区间 a a，b b 确定之后，逐步缩小搜索确定之后，逐步缩小搜索区间，直至最小点存在的范围达到允许的误差范围为止。区间，直至最小点存在的范围达到允许的误差范围为止。在区间在区间 a a ，b b 内任取两点内任取两点a a1 1，b b1 1，使，使a a a a1 1 b b1 1 b b。 图图3 35 5 区间消去法

11、原理区间消去法原理比较比较f f ( (a a1 1) )，f f ( (b b1 1) )，有三种情况，有三种情况 （1 1）)()(11bfaf 丢掉丢掉,1bb，留下，留下,1ba，图，图a a（2 2）)()(11bfaf 丢掉丢掉,1aa，留下，留下,1ba, ,图图b b，第三章第三章 第二节第二节 搜索区间的确定与区间消去法原理搜索区间的确定与区间消去法原理注意：注意： 每次迭代中所保留点与新取点间的位置应该是对称的每次迭代中所保留点与新取点间的位置应该是对称的区间消去法优劣评价指标。区间消去法优劣评价指标。区间缩短率区间缩短率e e e en n= =l ln n/ /l l0

12、 0l ln n经经n n次迭代后的缩短区间，次迭代后的缩短区间，l l0 0= =b b- -a a 原始区间原始区间 1 1由于区间缩小时插入点的位置确定方法不同，由于区间缩小时插入点的位置确定方法不同， 形成了不同的一维搜索方法形成了不同的一维搜索方法。 试探法：黄金分割法，试探法：黄金分割法，fibonacifibonaci数列法数列法 2 2函数逼近法（插值法）函数逼近法（插值法） 二次插值法二次插值法, ,三次插值法三次插值法 三、一维搜索方法的分类三、一维搜索方法的分类第三章第三章 第二节第二节 搜索区间的确定与区间消去法原理搜索区间的确定与区间消去法原理第三节第三节 一维搜索的

13、试探方法一维搜索的试探方法 一、一、0.6180.618法的由来法的由来 要求：保留点在新区间的位置与丢去点原区间位置相当。要求：保留点在新区间的位置与丢去点原区间位置相当。 丢去丢去假设消去假设消去),(2b211 取对称点取对称点21,位置，相当于原来位置，相当于原来1在原区间的在原区间的1的位置的位置?2第三章第三章 第三节第三节 一维搜索的试探方法一维搜索的试探方法2这种分割称为黄金分割，这种分割保证了每次区间的这种分割称为黄金分割，这种分割保证了每次区间的原区间长新区间长）未变）未变均为均为0.6180.618，n n次迭代缩短率次迭代缩短率1nne缩短率缩短率e e（01122.6

14、180339887. 0215黄金分割法的意义：黄金分割法的意义：)1 ( :1 为将一段线分为两段的方法，使整段长与较长段比为将一段线分为两段的方法，使整段长与较长段比例等于较长段与较短段长度之比：例等于较长段与较短段长度之比：第三章第三章 第三节第三节 一维搜索的试探方法一维搜索的试探方法)(618.01abb)(618. 02aba（2 2）计算）计算)(),(2211ffff比较函数值比较函数值21ff 和并缩短搜索区间并缩短搜索区间b221取新点取新点)(618. 01abb21ff ，丢去，丢去,2b，取，取,2aa 若若二、迭代过程及算法框图二、迭代过程及算法框图,ba内取两个计

15、算点内取两个计算点与与2（1 1）在初始区间）在初始区间1第三章第三章 第三节第三节 一维搜索的试探方法一维搜索的试探方法(3)(3)判断迭代终止条件判断迭代终止条件212y yyandbab*2 ab当当时，终止迭代，取时，终止迭代，取，转步骤，转步骤(2)为收敛精度为收敛精度如不满足条件如不满足条件 若若21ff 丢去丢去,1a取取,1ba112 取新点取新点)(618. 02aba第三章第三章 第三节第三节 一维搜索的试探方法一维搜索的试探方法0.6180.618法程序框图如图法程序框图如图 第三章第三章 第三节第三节 一维搜索的试探方法一维搜索的试探方法例例3-12)(2f53*对函数

16、对函数，当给定搜索区间，当给定搜索区间时，试用黄金分割法求极小点时，试用黄金分割法求极小点。解解: : 3a5b 12首先插入两点：首先插入两点： 056. 0) 35(618. 05)(1abb944. 1) 35(618. 03)(2aba667. 7)(,115. 0)(2211fyfy12yy ， 所以消去区间所以消去区间 ,2b,ba3a则新的搜索区间则新的搜索区间不变，不变， 而端点而端点 944. 12b的端点的端点01. 0第三章第三章 第三节第三节 一维搜索的试探方法一维搜索的试探方法第一次迭代：第一次迭代： 插入点插入点 111. 1) 3944. 1 (618. 0944

17、. 1)(1abb056. 02115. 0)(,987. 0)(2211fyfy由于由于 12yy ，故消去区间，故消去区间 ,2b则新的搜索区间为则新的搜索区间为 056. 0 , 3列出前五次迭代的结果列出前五次迭代的结果 迭代序号迭代序号a a12by1比较比较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第三章第三章 第三节第三节 一维搜索的试探方法一维搜索的试探方法5 5次迭代后求得的最优解次迭代后求得的最

18、优解 0255. 1)665. 0386. 1(21)(21*ba0007. 1)(*f解析解法可求得其精确解解析解法可求得其精确解1)(, 1*f 第三章第三章 第三节第三节 一维搜索的试探方法一维搜索的试探方法一、牛顿法一、牛顿法200000)(21)()()()( ffff极值必要条件：极值必要条件：0)(1对上式求导对上式求导得：得： 0)()(0100 ff第四节第四节 一维搜索的插值方法一维搜索的插值方法 插值法是利用若干试验点的函数值，利用插值方法建插值法是利用若干试验点的函数值，利用插值方法建立函数的某种近似表达式，并求出该函数的极小点，用立函数的某种近似表达式，并求出该函数的

19、极小点，用作原来函数极小点的近似值，逐步逼近极值点。作原来函数极小点的近似值，逐步逼近极值点。,0ba, ,在在0点附近用一个二次函数点附近用一个二次函数)(来逼近来逼近)(f将将)(f在在0点点taylortaylor展开并保留二次项展开并保留二次项 首先取初始点首先取初始点第三章第三章 第四节第四节 一维搜索的插值方法一维搜索的插值方法)()(0001ff 作为新的插值点作为新的插值点)()(1kkkkff （k =0,1,2,） 牛顿法的几何意义如图牛顿法的几何意义如图3 39 9所示：所示：依次继续，得牛顿法迭代公式依次继续，得牛顿法迭代公式第三章第三章 第四节第四节 一维搜索的插值方

20、法一维搜索的插值方法*应为应为0)(f的根，过的根，过)(,00f 点的切线方程点的切线方程为为)()(000 ff，由，由0 ，得解，得解1，再由，再由)(,11f 作切线与横坐标的交点作切线与横坐标的交点.2逐渐逼近逐渐逼近*第三章第三章 第四节第四节 一维搜索的插值方法一维搜索的插值方法一维搜索的切线法一维搜索的切线法牛顿法的迭代步骤见教材牛顿法的迭代步骤见教材牛顿法的特点：牛顿法的特点：收敛速度快收敛速度快需要计算一阶、二阶导数，有局限，计算工作量较大需要计算一阶、二阶导数，有局限，计算工作量较大0)( f用一个二次多项式来逼近目标函数，然后求该二次多用一个二次多项式来逼近目标函数，然

21、后求该二次多项式的极小点，逐次拟合，以达到精度为止项式的极小点，逐次拟合，以达到精度为止321,三点使三点使ba321使使)()()(321fff，作二次插值多项式：，作二次插值多项式： 二、二次插值法（抛物线法）二、二次插值法（抛物线法）在在 a a, ,b b 内取内取时，迭代过程会发散时，迭代过程会发散2210)( aaap第三章第三章 第四节第四节 一维搜索的插值方法一维搜索的插值方法在在321,三点上应满足插值条件三点上应满足插值条件)()(fp，即，即232310332222102221211011)()()()()()(aaafpaaafpaaafp由此可求得插值系数由此可求得插值系数a a0 0,a,a1 1,a,a2 2（见教材）（见教材）)(p的极小点的极小点p可由可由02)(21ppaap得：得：2112aap1p为为)(f极小点极小点*的近似解。的近似解。 第三章第三章 第四节第四节 一维搜索的插值方法一维搜索的插值方法1p比较比较与与2大小和函数值大小和函数值)(),(21ffp取其相邻两点，取其相邻两点，21pa)a)()(21fafp舍去区间舍去区间,3p新的三个插值点为新的三个插值点为32211,pb) b) )()(21fafp( (*2在左侧左侧) )，舍去区间，舍去区间,21，新的三