3一维搜索法ppt课件

第三章常用的一维优化方法,31概述,32单峰区间的确定,33黄金分割法,35二次插值法,34Fibonacci法,作业,1,31概述,一、问题的提出,1、实际设计工作中会遇到一维优化设计问题,在长为350cm、宽为260cm的长方形不锈钢板的四角，各剪去一个小正方形，做成一个无盖的储水箱，试确定正方形的边长，使储水箱的容积最大。,2,2、多维优化设计转化为一维优化设计问题,多维优化问题求解过程：,3,二、一维优化方法的分类,1.解析法,2.数值法,由,方程求根法,区间收缩法,二分法、切线法、割线法等,分数（Fibonacci）法、黄金分割（0.618)法、插值法等,得,4,32单峰区间的确定,定义设*是()的极小点，若存在闭区间a，b，使得*a，b，且使函数值呈“高低高”的形态，即函数()在闭区间a，b中有唯一极小点，则称a，b是()单峰区间.,一、单峰区间的定义,非单峰区间,单峰区间,5,二、单峰区间的确定,确定搜索区间的一种简单的方法是进退法，其基本思想是从某一点出发，按一定的步长，确定函数值呈“高低高”的三点。如果一个方向不成功，就退回来，再沿相反的方向寻找。具体算法步骤如下：,(4)如果k=1,则置2=,2=,和h=-h,转(2);否则置1=2,1=2,2=3,2=3,3=,3=,并令a=min1,3,b=max1,3,停止计算.,(1)取初始步长h，置初始值3=0，3=(3)，并置k=0.,(2)置=3+h，=()和k=k+1.,(3)如果3,则置2=3,2=3,3=,3=和h=2h,k=k+1,转(2);,6,二、单峰区间的确定,7,置=3+h，=(),k=k+1,2=3,2=3,3=,3=,h=2h,k=k+1,2=,2=,h=-h,1=2,1=2,2=3,2=3,3=,3=,a=min1,3,b=max1,3,yes,no,yes,no,三、算法框图,8,四、区间收缩原则与区间收缩率,yes,no,a=a1b=b,a=ab=a2,9,黄金分割法(GoldenSectionMethod)又称为0.618法，是用于在单峰函数区间上求极小的一种方法。其基本思想是通过取试探点和进行函数值比较，使包含极小点的搜索区间不断减少，当区间长度缩短到一定程度时，就得到函数极小点的近似值。,33黄金分割法,一、黄金分割法的取点原则,1.对称取点,2.等区间收缩率,3.留点可用,10,二、黄金分割法的区间收缩率,11,(1)置初始搜索区间a,b，并置精度要求，并计算左右试探点al=a+0.382(b-a)a2=a+0.618(b-a)及相应的函数值l=(al)，2=(a2).,三、黄金分割法的步骤,(3)若|b-a|,做:如果l2,则计算l=a+Fn-2/Fn(b-a)，flf(l)；否则计算l=r-，flf(l)。,(4)flfr，置a=l，l=r，flfr；如果n2，则计算r=a+Fn-1/Fn(b-a)，frf(r)；否则计算r=l+，frf(r)。,(5)若n=1，做：如果frf(r)，则置=r；否则置=r，停止计算(作为问题的极小点)。否则转(2)。,20,插值法是一类重要的一维搜索方法，其基本思想是利用搜索区间上某些点的信息构造插值多项式(通常不超过三次)p()，逐步用p()的极小点来逼近()的极小点*。当()有比较好的解析性质时,插值法比区间收缩法(如0.618法)的效果好.本节介绍三种较为常见的插值法.,34二次插值法,在单峰区间a,b中，已知函数在三点1、2、3（12、32，即三点满足“两端高中间低”。这三个点可由得到：,一、二次插值法的思想,21,由数值分析的知识,得到过三个点(1，1)、(2，2)、(3，3)的二次插值公式为,对上式求导数，并求解方程p()=0，得到p()的极小点,22,用作为*的估计值,并计算处的函数值=()。第一次的近似结果往往不够理想，需要作进一步的近似。现已得到四个点(1，1)、(2，2)、(3，3)和(，),如何选取三个点呢?仍然按照最初的原则，选取满足“两端高中间低”的三个点。,二、二次插值法的区间收缩过程,23,(1)取初始点12，23，置精度要求.,三、二次插值法算法步骤：,(2)计算A=21(2-3)+2(3-1)+3(1-2)若A=0，则置=2,=2,停止计算(输出,的信息).,(3)计算=1(22-32)+2(3212)+3(12-22)/A若3，则置=2,=2，停止计算(输出,的信息)。,24,(4)计算=()。若|-2|,则停止计算(作为极小点)。,(5)如果(2,3)，则:若2，则置1=2，1=2，2=，2=；否则置3=,3=;否则(1,2):若2，则置3=2,3=2，2=,2=；否