《维搜索方法》PPT课件.ppt

第第3章章 一维搜索方法一维搜索方法l 当当采采用用数数学学规规划划法法寻寻求求多多元元函函数数的的极极值值点点时时，一般要进行一系列如下格式的迭代计算一般要进行一系列如下格式的迭代计算:当方向当方向 给定给定，求最佳步长，求最佳步长 就是求一元函数就是求一元函数:的极值问题，这一过程被称为一维搜索的极值问题，这一过程被称为一维搜索(单变量优化单变量优化).).一维搜索方法分类：一维搜索方法分类：(a)试探法试探法；(b)插值法插值法 1 1、单谷、单谷(峰）区间峰）区间 在给定区间内仅有一个谷值在给定区间内仅有一个谷值(极大或极小极大或极小)的函数的函数称为单谷数，其区间称为单谷区间称为单谷数，其区间称为单谷区间3.1 一维搜索的基本思想一维搜索的基本思想 O f(a)b x*x a 函数值：函数值：“大小大小大大”图形：图形：“高高低低高高”单谷区间中一定能求得单谷区间中一定能求得一个极小点一个极小点 2 2、一维搜索的基本思想、一维搜索的基本思想 方向导数找初始单谷区间是一维搜索的第一步方向导数找初始单谷区间是一维搜索的第一步.第二步使区间缩小第二步使区间缩小 收敛精度或迭代精度收敛精度或迭代精度3.2 确定初始单谷区间的进退法确定初始单谷区间的进退法 基本思想：基本思想：基本思想：基本思想：对对f(x)任选一个初始点任选一个初始点a1及初始步长及初始步长h，通过比较通过比较这两点函数值的大小，确定第三点位置，比较这三点这两点函数值的大小，确定第三点位置，比较这三点的函数值大小，确定是否为的函数值大小，确定是否为“高高低低高高”形态形态步骤：步骤：步骤：步骤：（1）选定初始点选定初始点x1，初始步长，初始步长h，计算计算 f 1f(x1),f 2f(x1+h)（2）比较比较f 1和和f 2。（a）如如f 1 f 2,向右前进；加大步长向右前进；加大步长 h 2 h，转（转（3）向前）向前 （b）如如f 1 f 2,向左后退；向左后退；h-h0，转（转（3）向后探测，）向后探测，（c）如如f 1 f 2，极小点在极小点在x1 x1 h 之间。之间。(3）产生新的探测点产生新的探测点a3a1h，y3f(a3);(4)比较函数值比较函数值 y2与y3：（a）如如y20时，a,b=a1,a3;hy3,加大步长加大步长 h2 h，a1=a2,a2=a3,转（3）继续探测继续探测3.3 黄金分割法法)区间消去法原理：搜索区间确定之后，采用区间消去法逐步搜索区间确定之后，采用区间消去法逐步缩短搜索区间，从而找到极小点的数值近似解缩短搜索区间，从而找到极小点的数值近似解 假定在搜索区间内假定在搜索区间内a,b 任取两点任取两点a1,b1;f(a1)f(b1)f(a1)f(b1)f(a1)f(b1)a1a1 a1 b1baabab b1b1f1f（a1），f2f（b1）l f1f（a1），f2f（b1）l(1)如f1f2,则缩小的新区间为a1,b;l(3)如f1=f2,则缩小的新区间为a1,b1f(a1)f(b1)f(a1)f(b1)f(a1)f(b1)a1a1 a1b1baabab b1 b1综合为两种情况：若 则取 为缩短后的搜索区间。若 则取 为缩短后的搜索区间。黄金分割法 黄金分割律是公元前六世纪，希腊的大数学家毕达哥拉黄金分割律是公元前六世纪，希腊的大数学家毕达哥拉斯发现的：如果把一条线段分成两部分，长段和短段的长斯发现的：如果把一条线段分成两部分，长段和短段的长度之比是，整条线段和长段的比也是时，才是和黄金一样度之比是，整条线段和长段的比也是时，才是和黄金一样最完美的分割，进行分割的这个点就叫黄金分割点最完美的分割，进行分割的这个点就叫黄金分割点 l 黄金分割法适用于黄金分割法适用于a,ba,b区间上的任何单谷函数求极小值区间上的任何单谷函数求极小值问题。对函数除要求问题。对函数除要求“单谷单谷”外不作其他要求，甚至可以外不作其他要求，甚至可以不连续。因此，这种方法的适应面相当广不连续。因此，这种方法的适应面相当广l 黄金分割法也是建立在区黄金分割法也是建立在区间间消去法原理基消去法原理基础础上的上的试试探方探方法法。l 在搜索区在搜索区间间内内a,ba,b适当插入两点适当插入两点 ，将区，将区间间分成分成三段三段；l 利用区利用区间间消去法，使搜索区消去法，使搜索区间缩间缩小，通小，通过过迭代迭代计计算，使算，使搜索区搜索区间间无限无限缩缩小，从而得到极小点的数小，从而得到极小点的数值值近似解近似解 将区将区将区将区间间间间分成三段分成三段分成三段分成三段 黄金分割法还要求在保留下来的区间内再插入一点所形成的区间新三段，与原来区间的三段具有相同的比例分布 f(a1)f(a2)f(a1)f(a2)a1 a1 a2abab a2黄金分割法要求插入两点：黄金分割法要求插入两点：黄金分割法区间消去示意：黄金分割法区间消去示意：l黄金分割法的搜索过程：黄金分割法的搜索过程：l1）给出初始搜索区间及收敛精度，将 赋以。l2）按坐标点计算公式计算 ,；并计算其对应的函数值。l3）根据区间消去法原理缩短搜索区间。为了能用原来的坐标点计算公式，需进行区间名称的代换，并在保留区间中计算一个新的试验点及其函数值。l如果 ，则新区间 令 ,记N0=0;l如果 ，则新区间 ，l令 ,记N0=1;l4）检查区间是否缩短到足够小和函数值收敛到足够精度，如果收敛条件满足，则取最后两试验点的平均值作为极小点的数值近似解。如果条件不满足则转向步骤5）。l5）产生新的插入点：l 如N0=0，则取 ；l 如N0=1，则取 ，l转向3）进行新的区间缩小。f(a1)f(a2)f(a1)f(a2)a1(a)a1(a2)a2(b)abab a2(a1)a1a2黄金分割法例例例例 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 1,=。解：解：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(x3)=18由于由于f2f3,可知初始区间已经找到，即可知初始区间已经找到，即a,b=x1,x2=0,22)用黄金分割法缩小区间用黄金分割法缩小区间 第一次缩小区间：第一次缩小区间：x1X X x2=0+0.618 X X f1f2,故新区间故新区间a,b=x1,b=0.472,1.236l因为因为 b-a=1.236-0.472=0.7640.2,应继续缩小区间。应继续缩小区间。第三次缩小区间：第三次缩小区间：l令令 x1=x2l x2X Xl由于由于f10.2,应继续缩小区间。应继续缩小区间。第四次缩小区间：第四次缩小区间：l令令 x2=x1l x1X Xl由于由于f10.2,应继续缩小区间。应继续缩小区间。第五次缩小区间：第五次缩小区间：l令令 x2=x1l x1X Xl由于由于f1f2,故新区间故新区间a,b=x1,b=0.584,0.764l因为因为 b-a=0.764-0.584=0.180.2,停止迭代。停止迭代。极小点与极小值：极小点与极小值：xX X(0.584+0.764)=0.674,f(x例3-2 对函数 ，当给定搜索区间 时，试用黄金分割法求极小点。迭代迭代 序号序号ab比较0 0-3-30.0560.0561.9441.9445 50.1150.115 7.6677.6671 1-3-3-1.111-1.1110.0560.0561.9441.944-0.987-0.987-0.987-0.9873 3-1.832-1.832-1.111-1.111-0.665-0.6650.0560.056-0.987-0.987-0.987-0.9875 5-1.386-1.386-1.111-1.111-0.940-0.940-0.665-0.6653.3 二次插值法(抛物线法)二次插值的基本思想是利用目标函数在不同二次插值的基本思想是利用目标函数在不同3 3点的函点的函数值构成一个与原函数数值构成一个与原函数f(x)相近似的二次多项式相近似的二次多项式p(x)，以函数以函数p(x)的的极值点极值点 (即即p(x)=0的根的根)作为目标函数作为目标函数f(x)的近似极值点的近似极值点x23p2p1f3x*1xf(x)p(x)xx1p3f2fp 1 1、二次多项式、二次多项式 p(x)的构成及其极小点的构成及其极小点l设设原原目目标标函函数数的的初初始始单单峰峰区区间间为为x1,x3 。函函数数在在x1,x2,x3 3点处函数值分别为点处函数值分别为f1,f2,f3，求待定系数求待定系数a0,a1和和a2,并代入上式，得：并代入上式，得：2 2、缩短区间缩短区间l 假若假若f(x)本身为二次函数，则在理论上按前式一本身为二次函数，则在理论上按前式一次求值就可找到最优点次求值就可找到最优点。l 若若f(x)为高于二次的函数或为其他函数为高于二次的函数或为其他函数,可采用区可采用区间消去法逐步缩小区间间消去法逐步缩小区间。l 根据根据xp*，x2，f(xp*)和和f(x2)的相互关系，分的相互关系，分6种情种情况进行区间缩小。况进行区间缩小。l 在已有的四在已有的四x1，x2，x3，xp*中选择新的三个点中选择新的三个点x1，x2，x3，再进行二次插值。，再进行二次插值。l选点要求：选点要求：l x1x2f2，f2f3 （高低高高低高形态）形态）l 如果如果 ，以，以x2,xp*中函数值较小的点作中函数值较小的点作为最优点为最优点x*。二二二二次次次次插插插插值值值值法法法法区区区区间间间间缩缩缩缩短短短短的的的的几几几几种种种种情情情情况况况况二二二二次次次次插插插插值值值值法法法法区区区区间间间间缩缩缩缩短短短短的的的的几几几几种种种种情情情情况况况况二二二二次次次次插插插插值值值值法法法法区区区区间间间间缩缩缩缩短短短短的的的的几几几几种种种种情情情情况况况况例例例例 3 33 3 用二次插值法求函数用二次插值法求函数用二次插值法求函数用二次插值法求函数f(f(x x)=3)=3x x3 3-4-4x x+2+2的极小的极小的极小的极小点，给定点，给定点，给定点，给定 x x0 0=0,=0,h h=1,=1,。l解解 1）确定初始区间）确定初始区间初始区间初始区间a,b=0,2,另有一中间点另有一中间点x2=1。2）用二次插值法逼近极小点）用二次插值法逼近极小点相邻三点的函数值相邻三点的函数值:x1=0,x2=1,x3=2;f1=2,f2=1,f3=18.代入公式：代入公式：xp*0.555,fpl在新区间，相邻三点的函数值在新区间，相邻三点的函数值:x1=0,x2=0.555,x3=1;f1=2,f2=0.292,f3=1。lxp*0.607,fp由于由于fpx2,新区间新区间a,b=x2,b=0.555,1|x2-xp*|=|0.555-0.607|=0.0520.2,迭代终止。迭代终止。lxp*由于由于fpf2,xp*0.2,应继续迭代。应继续迭代。l例例 3-4 用用二二次次插插值值法法求求 的的极极值值点。初始搜索区间点。初始搜索区间 ，。l解解：取取x2点点为为区区间间 x1,x3 的的中中点点，,计计算算x1,x2,x3 3点点处处的的函函数数值值f1=19，f2，f3=124。可可见见函函数数值满足值满足“高低高高低高”形态。形态。l以以x1,x2,x3为插值点构造二次曲线，为插值点构造二次曲线，l求第一次近似的二次曲线求第一次近似的二次曲线p(x)的极小值点，由公式得。的极小值点，由公式得。l比较函数值可知比较函数值可知l这这种种情情况况应应消消除除左左边边区区段段 。然然后后用用 作作为为x1,x2,x3新新3点点,重重新新构构造造二二次次曲曲线线p(x)，如如此此反反复复计计算算，直直到到 为止。整个迭代过程的计算结果列于表为止。整个迭代过程的计算结果列于表2-2.l从表中可见，经从表中可见，经7次迭代后，次迭代后，终止迭代。故最优点终止迭代。故最优点