一维优化方法

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,2019/11/22,长江大学机械工程学院(HQS),#,2024/11/14,1,3-1,问题的提出,如：,*,在上次迭代中已求得,，,由某种逻辑方式,（,如负梯度方向,、,共轭方向等,）,给定,，,每次迭代可归结为以,为变量的一维问题,。,一）一维问题是多维问题的基础,则,当,2024/11/14,2,上例中，,2,）取最优步长：,上例中，,-,能使目标函数值下降的步长,；,1,）取下降步长：,二）,的确定方法,2024/11/14,3,三）一维搜索的步骤,*,区间缩短率,：,当该区间的长度小于预先给定的一个很小的正数,，,则可认为该区间中的某点,(,如中点,),是最优点,。,2),将含最优点的区间不断缩小,特点：,高,-,低,-,高,1),确定一个包含最优点的初始搜索区间,2024/11/14,4,3-2,确定初始搜索区间的进退算法,前进计算,后退计算,试探后作前进或后退计算,。,一）基本思路,2024/11/14,5,h=h,0,y,1,=f(x,1,),、,x,2,=x,1,+h,、,y,2,=f(x,2,),给定,x,1,、,h,0,y,1,y,2,y,2,y,3,是,h=2h,x,3,=x,2,+h,、,y,3,=f(x,3,),结束,否,h=-h,x,3,=x,1,y,3,=y,1,a=x,1,、,b=x,3,是,x,1,=x,2,y,1,=y,2,x,2,=x,3,y,2,=y,3,是,a=x,3,、,b=x,1,否,h0,否,二,),迭代步骤,初始进退距,前进计算,后退计算,2024/11/14,6,k,h,x,1,y,1,x,2,y,2,x,3,y,3,1,0.1,0.2,0 9,0.1 8.203,0.3 6.681,2,0.4,0.1 8.203,0.3 6.681,0.7 4.429,3,0.8,0.3 6.681,0.7 4.429,1.5 7.125,2024/11/14,7,k,h,x,1,y,1,x,2,y,2,x,3,y,3,1,0.1,-0.2,1.8 12.096,1.9 14.377,1.9 14.377,1.8 12.096,1.6 8.488,2,-0.4,1.8 12.096,1.6 8.488,1.2 4.584,3,-0.8,1.6 8.488,1.2 4.584,0.4 5.992,2024/11/14,8,3-3,格点法,a,b,先将搜索区间分成若干等分，计算出当中的,n,个等分点的目标函数值,.,再通过比较,找出其中的最小点，则该点的两个邻近点围成缩短了的新区间。,一）基本思路,2024/11/14,9,二）每轮迭代区间的缩短率,1,）思路简单，编程容易，宜于离散型优化问题；,三）特点,2,）计算量大，不宜用于高维优化问题。,2024/11/14,10,3-4,黄 金 分 割 法,一）基本思路,为预先给定的误差限,。,2,）,缩短区间的总次数,1,）,将区间按一定的比例缩小，且正常迭代时每缩短一次区间只需计算一次函数值,。,2024/11/14,11,令,得,：,其正根为,：,证,：,*,关于,的证明,2024/11/14,12,关于缩小区间总次数的证明,即,证：,2024/11/14,13,给定,否,否,是,是,止,二,),迭代步骤,*,也可采用迭代次数是否大于或等于,k,作终止准则。,2024/11/14,14,3-5,二次插值法,原函数,用三点二次插值多项式来逼近原函数。,一）基本思路,2024/11/14,15,二）二次插值曲线的极小点,求出,a,、,b,后得,2,）求系数,a,和,b,1,）求驻点,插值多项式：,2024/11/14,16,三）区间的缩短,x,4,=0.5(x,1,+x,2,),f,4,=f(x,4,),x,1,=x,4,f,1,=f,4,x,3,=x,2,f,3,=f,2,x,2,=x,4,f,2,=f,4,x,1,=x,p,f,1,=f,p,x,3,=x,2,f,3,=f,2,x,2,=x,p,f,2,=f,p,x,1,=x,2,f,1,=f,2,x,2,=x,p,f,2,=f,p,x,3,=x,p,f,3,=f,p,是,否,输出,二次插值法缩小区间流程图,输入,x,p,x,2,f,4,f,2,f,2,f,p,x,p,0,x*=x,p,f,*,=f,p,x,*,=x,2,f,*,=f,2,否,给定,x,1,、,x,3,、,否,否,是,结 束,是,是,是,本书认为是由于区间缩到很小时因计算机舍入误差引起，可取中间点输出。,2024/11/14,19,)A=0,),这表明此时三个插值点共线。,2024/11/14,20,3-5,三次两点插值法,二）插值多项式,根据两点处的目标函数值和一阶导数插值。,一）插值条件,2024/11/14,21,三）插值多项式系数,2024/11/14,22,四）插值函数的极小点,由,得,因有极小，,其二阶导数应大于,0,：,应取,“,+,”,号,故有,*,如何选取,？,2024/11/14,23,六）终止准则,五）缩短区间的方法,1,）,当,2,）,当,*,2024/11/14,24,七）迭代步骤,输入,a,b,计算,计算,A,，,B,，,C,，,D,A=0,是,否,A,0,是,否,计算,结束,否,是,否,是,