维搜索法课件

1、维搜索法第三章第三章 常用的一维优化方常用的一维优化方法法3 31 1 概述概述3 32 2 单峰区间的确定单峰区间的确定3 33 3 黄金分割法黄金分割法3 35 5 二次插值法二次插值法3 34 Fibonacci4 Fibonacci法法作业作业维搜索法3 31 1 概述概述一、问题的提出一、问题的提出1 1、实际设计工作中会遇到一维优化设计问题、实际设计工作中会遇到一维优化设计问题在长为在长为350cm350cm、宽为、宽为260cm260cm的长的长方形不锈钢板的四角，各剪去一方形不锈钢板的四角，各剪去一个小正方形，做成一个无盖的储个小正方形，做成一个无盖的储水箱，试确定正方形的边长

2、，使水箱，试确定正方形的边长，使储水箱的容积最大。储水箱的容积最大。 f xxxxmax( )(3502 ) (2602 ) s t x. .0130 x维搜索法2 2、多维优化设计转化为一维优化设计问题、多维优化设计转化为一维优化设计问题多维优化问题求解过程：多维优化问题求解过程：(1)( )( )kk+kkXXd X(1)d(0)0 d(1)(2)d(3)d(2)X(3)X(4)XX(0)( )( )min()min()min ( )kkf Xf Xd 维搜索法二、一维优化方法的分类二、一维优化方法的分类1.1.解析法解析法2.2.数值法数值法( )0dd ( )( )( )( )( )2

3、( )( )( )( )()1()()()2kkkkTkk Tkkf Xdf Xf XddH Xd ( )( )( )( )( )()()0kTkk Tkkf XddH Xd由由( )( )( )( )( )()()kTkk Tkkf XddH Xd 方程求根法方程求根法区间收缩法区间收缩法二分法、切线法、割线法等二分法、切线法、割线法等分数（分数（FibonacciFibonacci）法、黄金法、黄金分割（分割（0.618)0.618)法、插值法等法、插值法等得得维搜索法3 32 2 单峰区间的确定单峰区间的确定定义定义 设设 * *是是 ()()的极小点，若存在闭区间的极小点，若存在闭区间

4、aa，bb，使得，使得 * *aa，bb，且使函数值呈，且使函数值呈“高高低低高高”的形态，即函数的形态，即函数 ()()在闭区间在闭区间aa，bb中有唯一极小点，则称中有唯一极小点，则称aa，bb是是 ()()单峰单峰区间区间. .一、单峰区间的定义一、单峰区间的定义非单峰区间非单峰区间单峰区间单峰区间维搜索法二、单峰区间的确定二、单峰区间的确定确定搜索区间的一种简单的方法是进退法，其基本思想是从某一点出发，按确定搜索区间的一种简单的方法是进退法，其基本思想是从某一点出发，按一定的步长，确定函数值呈一定的步长，确定函数值呈“高高低低高高”的三点。如果一个方向不成功，的三点。如果一个方向不成功

5、，就退回来，再沿相反的方向寻找。具体算法步骤如下：就退回来，再沿相反的方向寻找。具体算法步骤如下：(4)(4)如果如果k=1,k=1,则置则置 2 2=,=, 2 2= = , ,和和h=-h=-h,h,转转(2);(2);否则置否则置 1 1=2 2, , 1 1= = 2 2,2=3, ,2=3, 2 2= = 3 3, 3=, , 3=, 3 3= = , ,并令并令a=mina=min1 1,3 3, b=max, b=max1 1,3 3, , 停止停止计算计算. .(1)(1)取初始步长取初始步长h h，置初始值，置初始值 3 3=0=0， 3 3= = (3 3) )，并置，并置

6、k=0.k=0.(2)(2)置置=3 3+h+h， = = () ()和和k=k+1.k=k+1.(3)(3)如果如果 3 3, ,则置则置 2 2=3 3, , 2 2= = 3 3, , 3 3=, =, 3 3= = 和和 h=2h,k=k+1,h=2h,k=k+1,转转(2);(2);3h2h4h12维搜索法二、单峰区间的确定二、单峰区间的确定3h2h4h124habhhab维搜索法开始开始输入：输入：h h置置 3 3=0=0， 3 3= = (3 3) )，k=0k=0置置=3 3+h+h， = = (),k=k+1 (),k=k+1 2 2=3 3, , 2 2= = 3 3,

7、, 3 3=,=, 3 3= = , , h=2h,k=k+1 h=2h,k=k+1 2 2? ?yesyesnonoa=aa=a1 1b b= =b ba=aa=ab b= a= a2 212a baaabab新区间长旧区间长维搜索法黄金分割法黄金分割法(Golden(GoldenSectionSectionMethod)Method)又称为又称为0.6180.618法，法，是用于在单峰函数区间上求极小的一种方法。其基本思想是是用于在单峰函数区间上求极小的一种方法。其基本思想是通过取试探点和进行函数值比较，使包含极小点的搜索区间通过取试探点和进行函数值比较，使包含极小点的搜索区间不断减少，当

8、区间长度缩短到一定程度时，就得到函数极小不断减少，当区间长度缩短到一定程度时，就得到函数极小点的近似值。点的近似值。3 33 3 黄金分割法黄金分割法一、黄金分割法的取点原则一、黄金分割法的取点原则1. 1. 对称取点对称取点2. 2. 等区间收缩率等区间收缩率3. 3. 留点可用留点可用维搜索法(1)()ba2()ba210 510.618210.382()aaba20.618()aaba二、黄金分割法的区间收缩率二、黄金分割法的区间收缩率()ba(1)()ba11a22aababa1a2a(1)()ba2()bab维搜索法(1)(1)置初始搜索区间置初始搜索区间a,ba,b，并置精度要求，

9、并置精度要求 ，并计算左右试探点，并计算左右试探点 a al l=a+0.382(b-a)=a+0.382(b-a) a a2 2=a+0.618(b-a)=a+0.618(b-a)及相应的函数值及相应的函数值 l l= = (a(al l) )， 2 2= = (a(a2 2). ).三、黄金分割法的步骤三、黄金分割法的步骤(3)(3)若若|b-a|,|b-a|,做做: :如果如果 l l 2 2，则置，则置 * *=a=a1 1；否则置；否则置 * *=a=a2 2， 停止计算停止计算( ( * *作为问题的解作为问题的解) )。否则转。否则转(2).(2).(2)(2)如果如果 l l

10、2 2，去掉区间，去掉区间11，a al l. .详细计算结果见下表详细计算结果见下表维搜索法 不要求每次迭代区间的收缩比不变不要求每次迭代区间的收缩比不变, ,而希望在试验点而希望在试验点个数相同的情况下，找出一种选取试验点的最佳策略，个数相同的情况下，找出一种选取试验点的最佳策略，使得最终的极小区间的长度达到最小，换句话说，如使得最终的极小区间的长度达到最小，换句话说，如果规定试验点的个数为果规定试验点的个数为n，且最终区间长度为，且最终区间长度为1，问问如何选取这如何选取这n个点，使得原始区间的长度最大？个点，使得原始区间的长度最大？ 令令Ln表示试验点数为表示试验点数为n n、最终区间

11、长度为、最终区间长度为1 1时，原始时，原始区间区间a,ba,b的最大可能长度。的最大可能长度。 设设 l为左试探点，为左试探点， r r为右试探点，如果极小点为右试探点，如果极小点 * *位于区间位于区间aa， l ，则在此区间内至多还可以有，则在此区间内至多还可以有n-2n-2个个试验点，因此试验点，因此 l -a -aLn2. .3 34 Fibonacci4 Fibonacci法法维搜索法另一方面另一方面, ,如果极小点如果极小点 * *位于区间位于区间 l,b,b内内, ,则包括则包括 r在在内内, ,还可以作还可以作n-1n-1个试验点，所以个试验点，所以 b- b- l Ln-1

12、n-1. . 因此因此 b-a=(b- b-a=(b- l)+()+( l -a) -a) Ln2 + Ln-1n-1, ,故有如下关系式故有如下关系式: : Ln Ln2 + Ln-1n-1显然显然, ,不计算函数值和仅计算一点处的函数值都不能使不计算函数值和仅计算一点处的函数值都不能使极小区间缩小，即极小区间缩小，即 L0 = = L1 =1. =1.由此可得，如果原始区间长度满足递推关系由此可得，如果原始区间长度满足递推关系 F0 = = F1，Fn = = Fn2 + Fn-1n-1则则Fn将是最大原始区间的长度将是最大原始区间的长度. .维搜索法Fn称为称为FibonacciFibo

13、nacci数。数。FibonacciFibonacci方法的基本思想与方法的基本思想与0.6180.618法相同法相同. .在搜索区间在搜索区间a,ba,b上上, ,先取左、右试验点先取左、右试验点 l 和和 r 比较函数值比较函数值f( ( l) )和和f( ( r) )重新确定搜索区间重新确定搜索区间. .(1)(1)若若f( ( l) ) ) f( ( r) )，去掉区间，去掉区间a, a, r, ,令令a= a= l，b=b,b=b,再计算新的试探点再计算新的试探点维搜索法所以所以FibonacciFibonacci方法与方法与0.6180.618法一样法一样, ,除第一次外除第一次外

14、, ,以后每次只以后每次只计算一个点处的函数值计算一个点处的函数值.Fibonacci.Fibonacci方法每次保留的区间长度方法每次保留的区间长度为为F Fk-1k-1F Fk k, ,因此若计算因此若计算n n个试验点个试验点, ,最终的区间长度。因此最终的区间长度。因此, ,任给任给一精度要求一精度要求, ,要求最终的区间长度小于要求最终的区间长度小于, ,即有即有因此因此, ,任给一精度要求任给一精度要求, ,要求最终的区间长度小于要求最终的区间长度小于, ,即有即有那么选择那么选择n n满足满足维搜索法(1)(1)置初始搜索区间置初始搜索区间aa，bb，并置精度要求，并置精度要求

15、，选取分离间隔，选取分离间隔 （b-ab-a） ，并计算左右试探点，并计算左右试探点 l =a+ =a+ Fn-2/ Fn(b-a)(b-a)， r =a+ =a+ Fn-1/ Fn(b-a)(b-a)及相应的函数值及相应的函数值flf( ( l), ), frf( ( r) ) 。算法步骤算法步骤(2)(2)置置n=n-1n=n-1。(3)(3)如果如果frf( ( r) ) ，则置，则置b= b= r， r = = l ， fr fl ， 。如果。如果n2,n2,则计算则计算 l =a+ =a+ Fn-2/ Fn(b-a) (b-a) ， flf( ( l) ) ；否则计算；否则计算 l

16、= = r - -， flf( ( l) ) 。(4) (4) fl fr ，置，置a= a= l ， l = = r ， fl fr ；如果；如果n2n2，则计算，则计算 r =a+ =a+ Fn-1/ Fn(b-a) (b-a) ， frf( ( r) ) ；否则计算；否则计算 r = = l + +， frf( ( r) ) 。(5)(5)若若n=1n=1，做：如果，做：如果frf( ( r) ) ，则置，则置= = r ；否则置；否则置= = r ，停，停止计算止计算(作为问题的极小点作为问题的极小点) )。否则转。否则转(2)(2)。维搜索法 插值法是一类重要的一维搜索方法，其基本思

17、想是利用搜索区插值法是一类重要的一维搜索方法，其基本思想是利用搜索区间上某些点的信息构造插值多项式间上某些点的信息构造插值多项式( (通常不超过三次通常不超过三次)p()p()，逐步用，逐步用p()p()的极小点来逼近的极小点来逼近 ()()的极小点的极小点 * *。当。当 ()()有比较好的解析性质有比较好的解析性质时时, ,插值法比区间收缩法插值法比区间收缩法( (如如0.6180.618法法) )的效果好的效果好. .本节介绍三种较为本节介绍三种较为常见的插值法常见的插值法. .3 34 4 二次插值法二次插值法 在单峰区间在单峰区间a,ba,b中，已知函数在三点中，已知函数在三点 1

18、1、 2 2、 3 3 （ 1 12 2 2 2、 3 3 2 2 ，即三点满足，即三点满足“两端高中间低两端高中间低”。 这三个点可由得到：这三个点可由得到：一、二次插值法的思想一、二次插值法的思想13221322 3或1a3b维搜索法由数值分析的知识由数值分析的知识, ,得到过三个点得到过三个点(1 1， 1 1) )、 (2 2， 2 2) ) 、 (3 3， 3 3) )的二次插值公式为的二次插值公式为对上式求导数，并求解方程对上式求导数，并求解方程p()=0p()=0，得到，得到p()p()的极小点的极小点222222123231312123231312()()()2()()() 维

19、搜索法用用 作为作为 * *的估计值的估计值, ,并计算并计算 处的函数值处的函数值 = = ()()。 第一次的近似结果往往不够理想，需要作进一步的近似。第一次的近似结果往往不够理想，需要作进一步的近似。 现已得到四个点现已得到四个点(1 1， 1 1) )、 (2 2， 2 2) ) 、 (3 3， 3 3) )和和(， ), ),如何如何选取三个点呢选取三个点呢? ? 仍然按照最初的原则，选取满足仍然按照最初的原则，选取满足“两端高中间低两端高中间低”的三个点。的三个点。a123a123a123a123二、二次插值法的区间收缩过程二、二次插值法的区间收缩过程维搜索法(1)(1)取初始点取初始点 1 12 2 2 2， 2 2 3 3 ，置精度要求，置精度要求. .三、二次插值法算法步骤：三、二次插值法算法步骤：(2)(2)计算计算 A=2A=2 1 1(2 2-3 3)+)+ 2 2(3 3-1 1)+)+ 3 3(1 1-2 2) ) 若若A=0A=0，则置，则置=2 2, , = = 2 2, , 停止计算停止计算( (输出输出, 的信息的信息). ).(3)(3)计算计算 = 1 1(2 22 2- - 3