资源描述
单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,第三章 常用的一维优化方法,31,概述,32,单峰区间的确定,33,黄金分割法,35,二次插值法,34,Fibonacci法,作业,31 概述,一、问题的提出,1、实际设计工作中会遇到一维优化设计问题,在长为,350cm,、宽为,260cm,的长方形不锈钢板的四角，各剪去一个小正方形，做成一个无盖的储水箱，试确定正方形的边长，使储水箱的容积最大。,2、多维优化设计转化为一维优化设计问题,多维优化问题求解过程：,二、一维优化方法的分类,1.解析法,2.数值法,由,方程求根法,区间收缩法,二分法、切线法、割线法等,分数（,Fibonacci）,法、黄金分割（0.618)法、插值法等,得,32 单峰区间的确定,定义 设*是,()的极小点，若存在闭区间a，b，使得*a，b，且使函数值呈“高低高”的形态，即函数,()在闭区间a，b中有唯一极小点，则称a，b是,()单峰区间.,一、单峰区间的定义,非单峰区间,单峰区间,二、单峰区间的确定,确定搜索区间的一种简单的方法是进退法，其基本思想是从某一点出发，按一定的步长，确定函数值呈“高低高”的三点。如果一个方向不成功，就退回来，再沿相反的方向寻找。具体算法步骤如下：,(4)如果k=1,则置,2,=,2,=,和h=-h,转(2);否则置,1,=,2,1,=,2,2=3,2,=,3, 3=,3,=,并令a=min,1,3, b=max,1,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);,二、单峰区间的确定,开始,输入：h,置,3,=0，,3,=,(,3,)，k=0,置=,3,+h，,=,(),k=k+1,2,=,3,2,=,3, ,3,=,3,=,h=2h,k=k+1,2,?,yes,no,a=a,1,b,=,b,a=a,b,= a,2,黄金分割法(GoldenSectionMethod)又称为0.618法，是用于在单峰函数区间上求极小的一种方法。其基本思想是通过取试探点和进行函数值比较，使包含极小点的搜索区间不断减少，当区间长度缩短到一定程度时，就得到函数极小点的近似值。,33 黄金分割法,一、黄金分割法的取点原则,1. 对称取点,2. 等区间收缩率,3. 留点可用,二、黄金分割法的区间收缩率,(1)置初始搜索区间a,b，并置精度要求，并计算左右试探点,a,l,=a+0.382(b-a),a,2,=a+0.618(b-a),及相应的函数值,l,=,(a,l,)，,2,=,(a,2,).,三、黄金分割法的步骤,(3)若|b-a|,做:如果,l,2,，则置,*,=a,1,；否则置,*,=a,2,， 停止计算(,*,作为问题的解)。否则转(2).,(2)如果,l,2,，去掉区间1，a,l,.,详细计算结果见下表,不要求每次迭代区间的收缩比不变,而希望在试验点个数相同的情况下，找出一种选取试验点的最佳策略，使得最终的极小区间的长度达到最小，换句话说，如果规定试验点的个数为,n,，且最终区间长度为,1，,问如何选取这,n,个点，使得原始区间的长度最大？,令,L,n,表示试验点数为n、最终区间长度为1时，原始区间a,b的最大可能长度。,设,l,为左试探点，,r,为右试探点，如果极小点,*位于区间a，,l,，则在此区间内至多还可以有n-2个试验点，因此,l,-a,L,n2,.,34 Fibonacci法,另一方面,如果极小点,*位于区间,l,b内,则包括,r,在内,还可以作n-1个试验点，所以,b-,l,L,n-1,.,因此 b-a=(b-,l,)+(,l,-a),L,n2,+ L,n-1,故有如下关系式:,L,n,L,n2,+ L,n-1,显然,不计算函数值和仅计算一点处的函数值都不能使极小区间缩小，即,L,0,=,L,1,=1.,由此可得，如果原始区间长度满足递推关系,F,0,=,F,1,，F,n,=,F,n2,+ F,n-1,则,F,n,将是最大原始区间的长度.,F,n,称为Fibonacci数。Fibonacci方法的基本思想与0.618法相同.在搜索区间a,b上,先取左、右试验点,l,和,r,比较函数值,f,(,l,)和,f,(,r,)重新确定搜索区间.,(1)若,f,(,l,) ,f,(,r,)，去掉区间a,r,令a=,l,，b=b,再计算新的试探点,所以Fibonacci方法与0.618法一样,除第一次外,以后每次只计算一个点处的函数值.Fibonacci方法每次保留的区间长度为F,k-1,F,k,因此若计算n个试验点,最终的区间长度。因此,任给一精度要求,要求最终的区间长度小于,即有,因此,任给一精度要求,要求最终的区间长度小于,即有,那么选择n满足,(1)置初始搜索区间a，b，并置精度要求，选取分离间隔（b-a），并计算左右试探点,l,=a+,F,n-2,/,F,n,(b-a)，,r,=a+,F,n-1,/,F,n,(b-a)及相应的函数值,f,l,f,(,l,),f,r,f,(,r,) 。,算法步骤,(2)置n=n-1。,(3)如果,f,r,f,(,r,) ，则置b=,r,，,r,=,l,，,f,r,f,l,， 。如果n2,则计算,l,=a+,F,n-2,/,F,n,(b-a) ，,f,l,f,(,l,) ；否则计算,l,=,r,-，,f,l,f,(,l,) 。,(4),f,l,f,r,，置a=,l,，,l,=,r,，,f,l,f,r,；如果n2，则计算,r,=a+,F,n-1,/,F,n,(b-a) ，,f,r,f,(,r,) ；否则计算,r,=,l,+，,f,r,f,(,r,) 。,(5)若n=1，做：如果,f,r,f,(,r,) ，则置=,r,；否则置=,r,，停止计算(作为问题的极小点)。否则转(2)。,插值法是一类重要的一维搜索方法，其基本思想是利用搜索区间上某些点的信息构造插值多项式(通常不超过三次)p()，逐步用p()的极小点来逼近,()的极小点*。当,()有比较好的解析性质时,插值法比区间收缩法(如0.618法)的效果好.本节介绍三种较为常见的插值法.,34 二次插值法,在单峰区间a,b中，已知函数在三点 ,1,、,2,、,3,（,1,2,2,、,3,2,，即三点满足“两端高中间低”。,这三个点可由得到：,一、二次插值法的思想,由数值分析的知识,得到过三个点(,1,，,1,)、 (,2,，,2,) 、 (,3,，,3,)的二次插值公式为,对上式求导数，并求解方程p()=0，得到p()的极小点,用作为*的估计值,并计算处的函数值,=,()。,第一次的近似结果往往不够理想，需要作进一步的近似。,现已得到四个点(,1,，,1,)、 (,2,，,2,) 、 (,3,，,3,)和(，,),如何选取三个点呢?,仍然按照最初的原则，选取满足“两端高中间低”的三个点。,二、二次插值法的区间收缩过程,(1)取初始点,1,2,2,，,2,3,，置精度要求.,三、二次插值法算法步骤：,(2)计算,A=2,1,(,2,-,3,)+,2,(,3,-,1,)+,3,(,1,-,2,),若A=0，则置=,2,=,2, 停止计算(输出,的信息).,(3)计算,=,1,(,2,2,- ,3,2,)+,2,(,3,2, ,1,2,)+,3,(,1,2,- ,2,2,)/A,若,3，,则置=,2,=,2,，,停止计算,(输出,的信息),。,(4)计算,=,()。若|-,2,|,则停止计算(作为极小点)。,(5)如果(2,3)，则:,若,2,，则置 ,1,=,2,，,1,=,2,，,2,=，,2,=,；,否则置 ,3,=,3,=,;,否则(1,2):,若,2,，则置,3,=,2,3,=,2,，,2,=,2,=,；,否则置 ,1,=,2,=,，,转(2).,四、二次插值法程序框图：,作业,用黄金分割法编程求解函数,的极小点,X,（1）,。,优化方法程序实现之一,用黄金分割法编程求解函数,的极小点,X,（1）,。,
展开阅读全文