第3章一维搜索方法(已排).ppt

《第3章一维搜索方法(已排).ppt》由会员分享，可在线阅读，更多相关《第3章一维搜索方法(已排).ppt（23页珍藏版）》请在得力文库 - 分享文档赚钱的网站上搜索。

1、当方向当方向 给定，求最佳步长就是求一元函数给定，求最佳步长就是求一元函数:的极值问题，这一过程被称为一维搜索的极值问题，这一过程被称为一维搜索.一维搜索方法分类：一维搜索方法分类：(a)试探法；试探法；(b)插值法插值法第第3章一维搜索方法章一维搜索方法当采用数学规划法寻求多元函数的极值点时，一般要进当采用数学规划法寻求多元函数的极值点时，一般要进行一系列如下格式的迭代计算行一系列如下格式的迭代计算:13.1一维搜索的基本思想一维搜索的基本思想 O f(a)b x*x a l1.单谷单谷(峰）区间峰）区间l在给定区间内仅有一个谷值的函数称为单谷数，其区间称在给定区间内仅有一个谷值的函数称为单

2、谷数，其区间称为单谷区间。为单谷区间。2.找初始单谷区间是一维找初始单谷区间是一维搜索的第一步搜索的第一步.第二步使区间缩小。第二步使区间缩小。单谷区间中一定能求得一个单谷区间中一定能求得一个极小点极小点函数值：函数值：“大小大大小大”图形：图形：“高高低低高高”2（1）选定初始点）选定初始点a,初始步长初始步长hh0，计算计算 y1f(a1)，y2f(a1h)。（2）比较比较y1和和y2。（a）如如y1y2,向右前进；加大步长向右前进；加大步长 h2 h，转（转（3）向前。）向前。（b）如如y1y2,向左后退；向左后退；h h0，转（转（3）向后探测。）向后探测。（c）如如y1y2，极小点在

3、极小点在a1和和a1h之间。之间。l基本思想：基本思想：l对对f(x)任选一个初始点任选一个初始点a1及初始步长及初始步长h，通过比较这两点函通过比较这两点函数值的大小，确定第三点位置，比较这三点的函数值大小，数值的大小，确定第三点位置，比较这三点的函数值大小，确定是否为确定是否为“高高低低高高”形态。形态。3.2确定初始单谷区间的进退法确定初始单谷区间的进退法步骤：步骤：3（3）产生新的探测点）产生新的探测点a3a1h，y3f(a3);（4）比较函数值）比较函数值 y2与与y3：（a）如如y20时，时，a,b=a1,a3;hy3,加大步长加大步长 h2 h，a1=a2,a2=a3,转（转（3

4、）继）继续探测。续探测。4y1y3y2y2y1a3a2a2a1a1Oaa3h0h02h0y1y2a2a3a1a2a1Oaa32h0h0h0y3y1y2y1y2y3a1a2确定初始单谷区间进退法示意图确定初始单谷区间进退法示意图确定初始单谷区间进退法示意图确定初始单谷区间进退法示意图5f(a1)f(b1)f(a1)f(b1)f(a1)f(b1)a1a1 a1 b1baabab b1b1f1f（a1），），f2f（b1）l搜索区间确定之后，采用区间消去法逐步缩短搜索区间，搜索区间确定之后，采用区间消去法逐步缩短搜索区间，从而找到极小点的数值近似解。从而找到极小点的数值近似解。l假定在搜索区间内假定

5、在搜索区间内a,b 任取两点任取两点a1,b1;3.3区间消去法原理区间消去法原理6f(a1)f(b1)f(a1)f(b1)f(a1)f(b1)a1a1 a1b1baabab b1 b1综合为两种情况：综合为两种情况：若若 则取则取 为缩短后的搜索区间。为缩短后的搜索区间。若若 则取则取 为缩短后的搜索区间。为缩短后的搜索区间。l f1f（a1），），f2f（b1）l(1)如如f1f2,则缩小的新区间为则缩小的新区间为a1,b;l(3)如如f1=f2,则缩小的新区间为则缩小的新区间为a1,b17l黄金分割法适用于黄金分割法适用于a,b区间上的任何单谷函数求极小值区间上的任何单谷函数求极小值问题

6、。对函数除要求问题。对函数除要求“单谷单谷”外不作其他要求，甚至可以不外不作其他要求，甚至可以不连续。因此，这种方法的适应面相当广。连续。因此，这种方法的适应面相当广。l黄金分割法也是建立在区间消去法原理基础上的试探方法。黄金分割法也是建立在区间消去法原理基础上的试探方法。l在搜索区间内在搜索区间内a,b适当插入两点适当插入两点 ，将区间分成三段；，将区间分成三段；l利用区间消去法，使搜索区间缩小，通过迭代计算，使搜利用区间消去法，使搜索区间缩小，通过迭代计算，使搜索区间无限缩小，从而得到极小点的数值近似解。索区间无限缩小，从而得到极小点的数值近似解。3.4黄金分割法黄金分割法8将区间分成三段

7、将区间分成三段将区间分成三段将区间分成三段黄金分割法还要求在保留下来的区间内再插入一点所形黄金分割法还要求在保留下来的区间内再插入一点所形成的区间新三段，与原来区间的三段具有相同的比例分布成的区间新三段，与原来区间的三段具有相同的比例分布。9 f(a1)f(a2)f(a1)f(a2)a1 a1 a2abab a2黄金分割法要求插入两点：黄金分割法要求插入两点：黄金分割法区间消去示意：黄金分割法区间消去示意：10l黄金分割法的搜索过程：黄金分割法的搜索过程：l1）给出初始搜索区间及收敛精度）给出初始搜索区间及收敛精度，将赋以，将赋以0.618。l2）按坐标点计算公式计算）按坐标点计算公式计算 ，

8、；并计算其对应的函数值。；并计算其对应的函数值。l3）根据区间消去法原理缩短搜索区间。为了能用原来的坐标点计算）根据区间消去法原理缩短搜索区间。为了能用原来的坐标点计算公式，需进行区间名称的代换，并在保留区间中计算一个新的试验点公式，需进行区间名称的代换，并在保留区间中计算一个新的试验点及其函数值。及其函数值。l如果如果 ，则新区间，则新区间 令令 ,记记N0=0;l如果如果 ，则新区间，则新区间l令令 ,记记N0=1;l4）检查区间是否缩短到足够小和函数值收敛到足够精度，如果收敛检查区间是否缩短到足够小和函数值收敛到足够精度，如果收敛条件满足，则取最后两试验点的平均值作为极小点的数值近似解。

9、如条件满足，则取最后两试验点的平均值作为极小点的数值近似解。如果条件不满足则转向步骤果条件不满足则转向步骤5）。）。11f(a1)f(a2)f(a1)f(a2)a1(a)a1(a2)a2(b)abab a2(a1)a1a2l5）产生新的插入点：）产生新的插入点：l如如N0=0，则取则取 ；l如如N0=1，则取则取 ；l转向转向3）进行新的区间缩小。）进行新的区间缩小。12解：解：1)确定初始区间确定初始区间x1=x0=0,f1=f(x1)=2x2=x0+h=0+1=1,f2=f(x2)=1由于由于f1f2,应加大步长继续向前探测。应加大步长继续向前探测。x3=x0+2h=0+2=2,f3=f(

10、x3)=18由于由于f2f3,可知初始区间已经找到，即可知初始区间已经找到，即a,b=x1,x2=0,22)用黄金分割法缩小区间用黄金分割法缩小区间 第一次缩小区间：第一次缩小区间：x1=0+0.382X(2-0)=0.764,f1=0.282 x2=0+0.618 X(2-0)=1.236,f2=2.72 f10.2例例例例 3-1 3-1用黄金分割法求函数用黄金分割法求函数用黄金分割法求函数用黄金分割法求函数f(f(x x)=3)=3x x3 3-4-4x x+2+2的极小点，的极小点，的极小点，的极小点，给定给定给定给定 x x0 0=0,=0,h h=1,=0.2=1,=0.2。13第

11、三次缩小区间：第三次缩小区间：l令令 x1=x2=0.764,f1=f2=0.282lx2=0.472+0.618X(1.236-0.472)=0.944,f2=0.747l由于由于f10.2,应继续缩小区间。应继续缩小区间。第二次缩小区间：第二次缩小区间：l令令 x2=x1=0.764,f2=f1=0.282lx1=0+0.382X(1.236-0)=0.472,f1=0.317l由于由于f1f2,故新区间故新区间a,b=x1,b=0.472,1.236l因为因为 b-a=1.236-0.472=0.7640.2,应继续缩小区间。应继续缩小区间。14第四次缩小区间：第四次缩小区间：l令令 x

12、2=x1=0.764,f2=f1=0.282lx1=0.472+0.382X(0.944-0.472)=0.652,f1=0.223l由于由于f10.2,应继续缩小区间。应继续缩小区间。第五次缩小区间：第五次缩小区间：l令令 x2=x1=0.652,f2=f1=0.223lx1=0.472+0.382X(0.764-0.472)=0.584,f1=0.262l由于由于f1f2,故新区间故新区间a,b=x1,b=0.584,0.764l因为因为 b-a=0.764-0.584=0.180.2,停止迭代。停止迭代。极小点与极小值：极小点与极小值：x*=0.5X(0.584+0.764)=0.674

13、,f(x*)=0.22215 迭代迭代 序号序号ab比较比较0-30.0561.94450.1157.6671-3-1.1110.0561.944-0.987-0.9873-1.832-1.111-0.6650.056-0.987-0.9875-1.386-1.111-0.940-0.665例例例例3-23-2对函数对函数对函数对函数 ，当给定搜索区间，当给定搜索区间，当给定搜索区间，当给定搜索区间 时，时，时，时，试用黄金分割法求极小点。试用黄金分割法求极小点。试用黄金分割法求极小点。试用黄金分割法求极小点。16x23p2p1f3x*1xf(x)p(x)xx1p3f2fp二次插值的基本思想是

14、利用目标函数在不同二次插值的基本思想是利用目标函数在不同3点的点的函数值构成一个与原函数函数值构成一个与原函数f(x)相近似的二次多项式相近似的二次多项式p(x)，以函数以函数p(x)的极值点的极值点 (即即p(x)=0的根的根)作为目标函数作为目标函数f(x)的近似极值点。的近似极值点。3.5二次插值法二次插值法17l1.二次多项式二次多项式p(x)的构成及其极小点的构成及其极小点l设原目标函数的初始单峰区间为。函数在设原目标函数的初始单峰区间为。函数在x1,x2,x3 3点处点处函数值分别为函数值分别为f1,f2,f3，求待定系数求待定系数a0,a1和和a2,并代入上式，得：并代入上式，得

15、：18l假若假若f(x)本身为二次函数，则在理论上按前式一次求值就可找到最本身为二次函数，则在理论上按前式一次求值就可找到最优点优点。l若若f(x)为高于二次的函数或为其他函数为高于二次的函数或为其他函数,可采用区间消去法逐步缩可采用区间消去法逐步缩小区间小区间。l根据根据xp*，x2，f(xp*)和和f(x2)的相互关系，分的相互关系，分6种情况进行区间缩小。种情况进行区间缩小。l在已有的四在已有的四x1,x2,x3,xp*中选择新的三个点中选择新的三个点x1,x2,x3，再进行二次再进行二次插值。插值。l选点要求：选点要求：lx1x2f2,f2f3 （高低高形态）高低高形态）l如果如果 ，

16、以，以x2,xp*中函数值较小的点作为最优点中函数值较小的点作为最优点x*。2 2 缩短区间缩短区间缩短区间缩短区间192）用二次插值法逼近极小点）用二次插值法逼近极小点相邻三点的函数值相邻三点的函数值:x1=0,x2=1,x3=2;f1=2,f2=1,f3=18.代入代入公式：公式：xp*0.555,fp=0.292例例例例 3-3 3-3用二次插值法求函数用二次插值法求函数用二次插值法求函数用二次插值法求函数f(f(x x)=3)=3x x3 3-4-4x x+2+2的极小点，的极小点，的极小点，的极小点，给定给定给定给定 x x0 0=0,=0,h h=1,=0.2=1,=0.2。l解解

17、 1）确定初始区间）确定初始区间初始区间初始区间a,b=0,2,另有一中间点另有一中间点x2=1。20l在新区间，相邻三点的函数值在新区间，相邻三点的函数值:x1=0,x2=0.555,x3=1;f1=2,f2=0.292,f3=1.lxp*0.607,fp=0.243由于由于fpx2,新区间新区间a,b=x2,b=0.555,1|x2-xp*|=|0.555-0.607|=0.0520.2,迭代终止。迭代终止。lxp*0.607,f*=0.243由于由于fpf2,xp*0.2,应继续迭代。应继续迭代。21l例例 3-4用二次插值法求用二次插值法求 的极值点。初始搜的极值点。初始搜索区间索区间

18、 ，。l解：取解：取x2点为区间点为区间x1,x3的中点，的中点，,计算计算x1,x2,x3 3点处的函数值点处的函数值f1=19，f2=-96.9375，f3=124。可见函数值满足可见函数值满足“高低高高低高”形态。形态。l以以x1,x2,x3为插值点构造二次曲线，为插值点构造二次曲线，l求第一次近似的二次曲线求第一次近似的二次曲线p(x)的极小值点，由公式得。的极小值点，由公式得。l ，比较函数值可知比较函数值可知ll这种情况应消除左边区段这种情况应消除左边区段 。然后用。然后用 作为作为x1,x2,x3新新3点点,重新构造二次曲线重新构造二次曲线p(x)，如此反复计算，直到如此反复计算，直到 为止。整个迭为止。整个迭代过程的计算结果列于表代过程的计算结果列于表2-2.l从表中可见，经从表中可见，经7次迭代后，次迭代后，终止迭代。，终止迭代。故最优点故最优点 2223