一维优化方法.pptx

2024/8/10 周六13-1 3-1 3-1 3-1 问题的提出问题的提出问题的提出问题的提出 如：如：*在上次迭代中已求得在上次迭代中已求得，由某种逻辑方式由某种逻辑方式（如负梯度方向如负梯度方向、共轭共轭方向等方向等）给定给定，每次迭代可归结为以每次迭代可归结为以 为变量的一维问题为变量的一维问题。一）一维问题是多维问题的基础一）一维问题是多维问题的基础则则当当2024/8/10 周六2上例中，上例中，2 2）取最优步长：）取最优步长：上例中，上例中，-能使目标函数值下降的步长能使目标函数值下降的步长；1 1）取下降步长：）取下降步长：二）二）的确定方法的确定方法2024/8/10 周六3 三）一维搜索的步骤三）一维搜索的步骤*区间缩短率区间缩短率：当该区间的长度小于预先给定的一个很小的正数当该区间的长度小于预先给定的一个很小的正数 ，则可认为该区间中的某点则可认为该区间中的某点(如中点如中点)是最优点是最优点。2)2)将含最优点的区间不断缩小将含最优点的区间不断缩小特点：特点：高高-低低-高高1)1)确定一个包含最优点的初始搜索区间确定一个包含最优点的初始搜索区间2024/8/10 周六43-2 3-2 3-2 3-2 确定初始搜索区间的进退算法确定初始搜索区间的进退算法确定初始搜索区间的进退算法确定初始搜索区间的进退算法前进计算前进计算后退计算后退计算试探后作前进或后退计算试探后作前进或后退计算。一）基本思路一）基本思路2024/8/10 周六5h=hh=h0 0y y1 1=f(x=f(x1 1)、x x2 2=x=x1 1+h+h、y y2 2=f(x=f(x2 2)给定给定x x1 1、h h0 0y y1 1yy2 2y y22y y3 3是是h=2hh=2hx x3 3=x=x2 2+h+h、y y3 3=f(x=f(x3 3)结束结束否否h=-hh=-hx x3 3=x=x1 1y y3 3=y=y1 1a=xa=x1 1、b=xb=x3 3是是x x1 1=x=x2 2y y1 1=y=y2 2x x2 2=x=x3 3y y2 2=y=y3 3是是a=xa=x3 3、b=xb=x1 1否否h0h0否否二二)迭代步骤迭代步骤初始进退距初始进退距前进计算前进计算后退计算后退计算2024/8/10 周六6khx1 y1x2 y2x3 y310.10.20 90.1 8.2030.3 6.68120.40.1 8.2030.3 6.6810.7 4.42930.80.3 6.6810.7 4.4291.5 7.1252024/8/10 周六7khx1 y1x2 y2x3 y310.1-0.21.8 12.096 1.9 14.3771.9 14.3771.8 12.0961.6 8.488 2-0.41.8 12.0961.6 8.4881.2 4.5843-0.81.6 8.4881.2 4.5840.4 5.9922024/8/10 周六83-3 3-3 3-3 3-3 格点法格点法格点法格点法 ab 先将搜索区间分成若干等分，计算出当中的先将搜索区间分成若干等分，计算出当中的n n个等分个等分点的目标函数值点的目标函数值.再通过比较再通过比较,找出其中的最小点，则该找出其中的最小点，则该点的两个邻近点围成缩短了的新区间。点的两个邻近点围成缩短了的新区间。一）基本思路一）基本思路2024/8/10 周六9二）每轮迭代区间的缩短率二）每轮迭代区间的缩短率1 1）思路简单，编程容易，宜于离散型优化问题；）思路简单，编程容易，宜于离散型优化问题；三）特点三）特点2 2）计算量大，不宜用于高维优化问题。）计算量大，不宜用于高维优化问题。2024/8/10 周六103-4 3-4 3-4 3-4 黄黄黄黄 金金金金 分分分分 割割割割 法法法法一）基本思路一）基本思路为预先给定的误差限为预先给定的误差限。2）缩短区间的总次数缩短区间的总次数1）将区间按一定的比例缩小，且正常迭代时将区间按一定的比例缩小，且正常迭代时每缩短一次区间只需计算一次函数值每缩短一次区间只需计算一次函数值。2024/8/10 周六11令令得得：其正根为其正根为：证证：*关于关于 的证明的证明2024/8/10 周六12关于缩小区间总次数的证明关于缩小区间总次数的证明即即证：证：2024/8/10 周六13给定给定否否否否是是是是止止二二)迭代步骤迭代步骤*也可采用迭代次数是否大也可采用迭代次数是否大于或等于于或等于 k k 作终止准则。作终止准则。2024/8/10 周六143-5 3-5 3-5 3-5 二次插值法二次插值法二次插值法二次插值法 原函数原函数用三点二次插值多项式来逼近原函数。用三点二次插值多项式来逼近原函数。一）基本思路一）基本思路2024/8/10 周六15二）二次插值曲线的极小点二）二次插值曲线的极小点求出求出a a、b b后得后得2 2）求系数）求系数a a和和b b1 1）求驻点）求驻点插值多项式：插值多项式：2024/8/10 周六16 三）区间的缩短三）区间的缩短x4=0.5(x1+x2)f4=f(x4)x1=x4f1=f4x3=x2f3=f2x2=x4f2=f4x1=xpf1=fpx3=x2f3=f2x2=xpf2=fpx1=x2f1=f2x2=xpf2=fpx3=xpf3=fp是是否否输出输出二次插值法缩小区间流程图二次插值法缩小区间流程图输入输入xpx2f4f2f2fpxp0 x*=xp,f*=fpx*=x2,f*=f2否否给定给定 x1、x3、否否否否是是结结 束束是是是是是是 本本书书认认为为是是由由于于区区间间缩缩到到很很小小时时因因计计算算机机舍舍入入误误差差引引起起，可可取取中中间间点点输输出。出。2024/8/10 周六19)A=0)A=0)这表明此时三个插值点共线。这表明此时三个插值点共线。2024/8/10 周六203-5 3-5 3-5 3-5 三次两点插值法三次两点插值法三次两点插值法三次两点插值法 二）插值多项式二）插值多项式根据两点处的目标函数值和一阶导数插值。根据两点处的目标函数值和一阶导数插值。一）插值条件一）插值条件2024/8/10 周六21三）插值多项式系数三）插值多项式系数2024/8/10 周六22四）插值函数的极小点四）插值函数的极小点由由得得因有极小，因有极小，其二阶导数应大于其二阶导数应大于0 0：应取应取“+”号号故有故有*如何选取如何选取？2024/8/10 周六23六）终止准则六）终止准则五）缩短区间的方法五）缩短区间的方法1）当当2）当当*2024/8/10 周六24七）迭代步骤七）迭代步骤输入输入a,b,计算计算计算计算A，B，C，DA=0是是否否A0是是否否计算计算结束结束否否是是否否是是