数值解单变量最优化p

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,4.5.2,无约束最优化问题的数值解法,4.5.2.1,单变量最优化问题的数值解法（一维搜索）,一、消去法的基本概念,1,消去法的基本思想,利用单峰函数在可行域内只有一个极值点的特点，设法逐步缩小搜索最优点的区间，直至找到最优点，并达到允许的精度为止。消去法分为：,同时消去法,：同时计算一批点的函数值，然后比较各函数值的大小，再消去一部分区间，直至达到精度要求。,序贯消去法,：从第二个点起，每计算一个点的函数值，就与前一个点的函数值进行比较，消去部分区间后再安排下一个计算点，如此序贯进行，直至达到精度要求。,2,序贯法缩小搜索区间,设：一元函数,y(x),在区间,a,0,b,0,内为单峰函数，若首先在,a,0,b,0,内任取两点,x,1,，,x,2,(x,1,x,2,),，,并计算函数值,y(x,1,),，,y(x,2,),，,这时可能的三种情况为：,（,1,）,y(x,1,)y(x,2,),则,x,*,在,x,1,b,0,之内,（,3,）,y(x,1,)=y(x,2,),则,x,*,在,x,1,x,2,之内,根据上面分析，可将搜索区间缩小。在余下的区间内继续选择新点，比较新点的函数值，直至区间缩小到精度要求，找到最优点。,a,0,b,0,0,9,10,11,12,13,3,4,5,6,7,8,1,2,X,1,x,1,3,不定区间,当进行,n,次函数值的计算与比较后，可以得出这,n,个函数值中的最小值，,f(x,m,),及最小点,x,m,以及其左右的邻点,x,k,、,x,r,，,而真正的最小点,x,*,必落在,x,r,与,x,k,之内。,将,x,r,与,x,k,之间的区间称为不定区间,l,n,，且,l,n,=,x,r,x,k,不定区间的影响因素：,与计算次数,n,有关；,l,0,=b,0,a,0,一定时，,n,l,n,与计算点的分布方式有关，即与,x,i,的确定方法有关,显然，,l,n,越小，则,x,m,与,x,*,越接近，用,x,m,近似,x,*,越可靠，即精度越高。,l,n,=,x,r,x,k,4,区间缩短率,n,次函数值的计算与比较后，不定区间与原始区间的比值,当,l,0,一定时，,E,n,l,n,相同计算次数下，,E,n,越小的方案越好,二 对无约束函数的搜索,求单峰所在区间的进退算法,消去法的应用基础是目标函数,f(x),在,a,0,b,0,内为单峰函数。,问题：,（,1,）怎样确定,f(x),为单峰函数,（,2,）怎样确定,f(x),的单峰所在区间,a,0,b,0,一般采用进退算法解决这两个问题。,1,、进退算法的基本思想,由单峰函数的性质可知，对于存在极小值的单峰函数，在极小点左边，函数值严格下降，而在极小点右边，函数值应严格上升。,据此，可以从某个给定的初始点出发，沿着函数值下降的方向逐步前进（或后退）直至发现函数值开始上升为止。由两边高中间低的三点函数值，就可以确定极小值所在的初始区间,a,0,，,b,0,2,、进退算法,(1),选定初始点,a,0,与步长,h,(2),计算并比较,y,（,a,0,）和,y,（,a,0,+h,），,根据比较结果有前进和后退两种可能：,前进计算：,后退运算：,前进计算,：若,y,（,a,0,）,y,（,a,0,+h,），,则步长加倍，计算,y,（,a,0,+3h,）。若,y,（,a,0,+h,）,y,（,a,0,+3h,），,则令,a,0,=a,0,，,b,0,=a,0,+3h,若,y,（,a,0,+h,）,y,（,a,0,+3h,）,，令,a,0,=a,0,+h,，,h=2h,，,重复上述前进运算。,后退运算,：若,y,（,a,0,）,y,（,a,0,+h,）,则后退计算,y,（,a,0,-h,）,;,若,y,（,a,0,-h,）,y,（,a,0,），,则令,a,0,=a,0,-h,，,b,0,=a,0,+h,，,停止运算。,否则继续后退。,例：,求函数 的极小所在区间,初始点,a,0,=1,，,步长,h=1,解：,h=a,0,=1,所以应后退,应继续后退，后退时步长加倍，所以计算,后退，计算,找到了函数值大（）、小（）、大（）的三点，即,a,0,=a,0,-3h=-2,，,b,0,=a,0,=1,用进退算法找到了初始搜索区间,a,0,，,b,0,为,-2,，,1,