一维搜索线性搜索.pptx

1第3章 一维搜索方法3.1 概述3.1.1 一维问题是多维问题的基础 求目标函数 f(X)的极小点，从理论上说需要求解方程：其中那么如何来求 f(X)的极小点呢？基本思想:这种方法是逐次迭代的方法，在电子计算机上很容易实现，这种方法是逐次迭代的方法，在电子计算机上很容易实现，因此它在优化设计中被广泛地采用。因此它在优化设计中被广泛地采用。第1页/共66页2这个过程称为一维搜索过程。如：如：则则当当Sk方向上的任何一点可以表示为其中是步长因子，为实系数，此时 Sk 方向上任何一点的目标函数值为 ，它是参数的一元函数。那么在沿 Sk 方向求的极小点，这就是求一元函数 的极小问题，它可表示为：第2页/共66页一维搜索示意图一维搜索示意图第3页/共66页 求多元函数极值点，需要进行一系列的一维搜索。可求多元函数极值点，需要进行一系列的一维搜索。可见见一维搜索是优化搜索方法的基础一维搜索是优化搜索方法的基础。求解一元函数求解一元函数 的极小点的极小点 ，可采用，可采用解析解解析解法法，即利用一元函数的极值条件，即利用一元函数的极值条件 求求在用函数在用函数 的导数求的导数求 时，所用的函数时，所用的函数 是仅以步长因子是仅以步长因子 为变量的一元函数，而不是为变量的一元函数，而不是以设计点以设计点 x x 为变量的多元函数为变量的多元函数 。3.1.2 的确定方法的确定方法第4页/共66页为了直接利用 的函数式求解最佳步长因子 。把 或它的简写形式 进行泰勒展开，取到二阶项，即 将上式对 进行微分并令其等于零，给出 极值点 应满足的条件 从而求得第5页/共66页这里是直接利用函数 而不需要把它化成步长因子 。的函数 。不过，此时需要计算 点处梯度 和海赛矩阵 H H 。解析解法的缺点需要进行求导计算。对于函数关系复杂、求导困难或无法求导的情况，使用解析法将是非常不便的。因此，在优化设计中，求解最佳步长因子因此，在优化设计中，求解最佳步长因子 主要采用主要采用数值解法数值解法，利用计算机通过反复迭代计算求得最佳步长因，利用计算机通过反复迭代计算求得最佳步长因子的近似值。子的近似值。数值解法的基本思路是：首先确定 所在的搜索区间，然后根据区间消去法原理不断缩小此区间，从而获得 的数 值近似解。第6页/共66页 解析法解析法:f(X f(X(k)(k)+S+S(k)(k)沿沿S S(k)(k)方向在方向在x x(k)(k)点泰勒展开；点泰勒展开；取二次近似：取二次近似：对对求导，令其为零。求导，令其为零。求得最优步长求得最优步长第7页/共66页数值解法基本思路：解析解法对于函数关系复杂、求导困难等情况难以实现。在实际优化设计中，数值解法的应用更为有效，且适合计算机的运算特点。一维搜索也称直线搜索。这种方法不仅对于解决一维最优化问题具有实际意义，而且也是求解多维最优化问题的重要支柱。一维搜索一般分为两大步骤：(1)(1)确定初始搜索区间aa，bb，该区间应是包括一维函数极小点在内的单谷区间。(2)(2)在单谷区间a,ba,b内通过缩小区间寻找极小点。先确定 在的搜索区间，然后根据区间消去法原理不断缩小此区间所，从而获得 的数值近似解。第8页/共66页1、确定搜索区间的外推法 在给定区间内仅有一个谷值（或有唯一的极小点）的函数称为单谷函数，其区间称为单谷区间。函数值：“大小大”图形：“高低高”单谷区间中一定能求得一个极小点。3.2 确定初始区间确定初始区间第9页/共66页从 开始，以初始步长 向前试探。如果函数值上升，则步长变号，即改变试探方向。如果函数值下降，则维持原来的试探方向，并将步长加倍。区间的始点、中间点依次沿试探方向移动一步。此过程一直进行到函数值再次上升时为止，即可找到搜索区间的终点。最后得到的三点即为搜索区间的始点、中间三点和终点，形成函数值的“高低高”趋势。单谷区间单谷区间第10页/共66页f(x)0130f(x)31说明：单谷区间内，函数可以有不可微点，也可以是不连续函数；第11页/共66页外推方法基本思想：对 任选一个初始点 及初始步长 ，通过比较这两点函数值的大小，确定第三点位置，比较这三点的函数值大小，确定是否为“高低高”形态。步骤：1 1）选定初始点a a1 1，初始步长h=hh=h0 0，计算y y1 1=f(a=f(a1 1)和y y2 2=f(a=f(a1 1+h)+h)2 2）比较y y1 1和y y2 2；a a）如果y y1 1yy2 2，向右前进，加大步长h=2hh=2h0 0，转（3 3）向前；b b）如果y y1 1yyy3 3 ，加大步长h=2hh=2h，a a1 1=a=a2 2,a,a2 2=a=a3 3,转（3 3）继续探测；b b）如果y y2 2y0h0否否初始进退距初始进退距前进计算后退计算第20页/共66页，搜索区间确定之后，采用区间消去法逐步缩短搜索区间，从而找到极小点的数值近似解。假定在搜索区间 内任取两点 ，且 3.3 区间消去方法区间消去方法第21页/共66页(1)(1)f f（a a1 1）f f（b b1 1）,则极小点必在区间则极小点必在区间aa，b b1 1 内内;第22页/共66页(1)(1)f f（a a1 1）f f（b b1 1）,则极小点必在区间则极小点必在区间 1 1，bb内内;第23页/共66页(1)(1)f f（a a1 1）f f（b b1 1）,则极小点必在区间则极小点必在区间 1 1，bb内内;(3)(3)f f（a a1 1）=f f（b b1 1）,则极小点必在区间则极小点必在区间 1 1，b b1 1 内内可以总结为两种情况：若 ，则取a,b1为缩小后的搜索区间。若 ，则取a1,b为缩小后的搜索区间。第24页/共66页试探法 黄金分割法插值法 二次插值法3 一维搜索方法分类 从前面的分析可知，每次缩短区间，只需要在区间内再插入一点并计算其函数值。而插入点的位置，可以由不同的方法来确定。就形成了不同的一维搜索方法。一维搜索方法分类第25页/共66页3.4 黄金分割法（法）黄金分割法黄金分割法的搜索过程第26页/共66页 概述在实际计算中，最常用的一维搜索试探方法是黄金分割法，又称作法。我们可以通过学习黄金分割法来了解一维搜索试探方法的基本思想。在搜索区间 a,ba,b内适当插入两点1 1、2 2，并计算其函数值。1 1、2 2将区间分成三段。应用函数的单谷性质，通过函数值大小的比较，删去其中一段，使搜索区间得以缩短。然后再在保留下来的区间上作同样的处置，如此迭代下去，使搜索区间无限缩小，从而得到极小点的数值近似解。3.4 黄金分割法（法）第27页/共66页黄金分割法是建立在区间消去法原理基础上的试探方法。适用于a,ba,b区间上的任何单谷函数求极小值问题。对函数除要求“单谷”外不作其它要求，甚至可以不连续。因此，这种方法的适应面相当广。黄金分割法对插入点的要求：1 1）要求插入点1 1、2 2 的位置相对于区间a,ba,b两端点具有对称性，即 其中 为待定常数。1.黄金分割法黄金分割法第28页/共66页2 2）黄金分割法还要求在保留下来的区间内再插入一点所形成的区间新三段，与原来区间的三段具有相同的比例分布。即每次缩小所得的新区间长度与缩小前区间长度之比（即：区间收缩率）为定值。第29页/共66页设原区间a,ba,b长度为1 1如下图所示，保留下来的区间 a,a,2 2 长度为 ，区间缩短率为 。为了保持相同的比例分布，新插入点 3 3应在 位置上，1 1 在原区间的 位置应相当于在保留区间的 位置。故有 取方程正数解，得第30页/共66页1、2将区间分成三段将区间分成三段 黄金分割法要求在黄金分割法要求在黄金分割法要求在黄金分割法要求在保留下来的区间内再保留下来的区间内再保留下来的区间内再保留下来的区间内再插入一点所形成的区插入一点所形成的区插入一点所形成的区插入一点所形成的区间新三段，与原来区间新三段，与原来区间新三段，与原来区间新三段，与原来区间的三段具有相同的间的三段具有相同的间的三段具有相同的间的三段具有相同的比例分布比例分布比例分布比例分布 。两内分点值两内分点值:结论：结论：所谓黄金分割是指将一线段分成两段的方法，使整段长与较长段的长度所谓黄金分割是指将一线段分成两段的方法，使整段长与较长段的长度比值等于较长段与较短段长度的比值即比值等于较长段与较短段长度的比值即 。第31页/共66页黄金分割法要求插入两点：黄金分割法区间消去示意图：黄金分割法（法）黄金分割法（法）第32页/共66页2.2.黄金分割法的搜索过程黄金分割法的搜索过程（1）给出初始搜索区间 及收敛精度 ，将 赋以 。（2）按坐标点计算公式计算 并计算其对应的函数值 黄金分割法（法）黄金分割法（法）第33页/共66页（3）根据区间消去法原理缩短搜索区间。为了能用原来的坐标点计算公式，进行区间名称的代换，并在保留区间中计算一个新的试验点及其函数值。黄金分割法（法）黄金分割法（法）第34页/共66页（4）检查区间是否缩短到足够小和函数值收敛到足够精度，如果收敛条件满足，则取最后两试验点的平均值作为极小点的数值近似解。如果条件不满足则转向步骤5。（5）产生新的插入点：如N0=0，则取（5）如果条件满足，则取最后两试验点的平均值作为极小点的数值近似解。黄金分割法（法）黄金分割法（法）缩短区间的总次数（迭代次数）:第35页/共66页黄金分割法程序框图黄金分割法程序框图给定否否是是止也可采用迭代次数是否大于或等于 k 作终止准则。第36页/共66页37迭代序号aby1比较y20-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-3：用黄金分割法求 的极小值 ，搜索区间是解：第37页/共66页38解析解：第38页/共66页例 3-1 用黄金分割法求函数f(x)=3x3-4x+2的极小点，给定 x0=0,h=1,。解：1）确定初始区间a1=x0=0,f1=f(a1)=2a2=x0+h=0+1=1,f2=f(a2)=1由于f1f2,应加大步长继续向前探测。a3=x0+2h=0+2=2,f3=f(a3)=18由于f2f3,可知初始区间已经找到，即a,b=a1,a3=0,22）用黄金分割法缩小区间 第一次缩小区间：a1(2-0)=0.764,f1 a2=0+0.618(2-0)=1.236,f2 f1f2,故新区间a,b=x1,b=0.472,1.236因为 b-a=1.236-0.472=0.7640.2,应继续缩小区间。第三次缩小区间：l令 x1=x2l x2Xl由于f10.2,应继续缩小区间。第40页/共66页 第四次缩小区间：令 x2=x1 x1X X由于f10.2,应继续缩小区间。第五次缩小区间：l令 x2=x1l x1Xl由于f1f2,故新区间a,b=x1,b=0.584,0.764l因为 b-a=0.764-0.584=0.180.2,停止迭代。极小点与极小值：xX(0.584+0.764)=0.674,f(x第41页/共66页n概述概述n n一维搜索问题是在某一确定区间内寻求一元函数的极小点一维搜索问题是在某一确定区间内寻求一元函数的极小点的位置，在某些情况下，如果没有函数表达式，但能够给的位置，在某些情况下，如果没有函数表达式，但能够给出若干试验点处的函数值，就可以根据这些点处的函数值，出若干试验点处的函数值，就可以根据这些点处的函数值，利用利用插值法插值法建立函数的某种近似表达式，进而求出函数的建立函数的某种近似表达式，进而求出函数的极小点，并用它作为原来函数极小点的近似值。这种方法极小点，并用它作为原来函数极小点的近似值。这种方法称作称作插值法插值法，又称作，又称作函数逼近法函数逼近法。一维搜索的二次插值法一维搜索的二次插值法第42页/共66页试探法（如黄金分割法）与插值法的比较：不同点：表现在试验点（插入点）位置的确定方法不同。第43页/共66页多项式是函数逼近的一种常用工具。在搜索区间内可以利用若干试验点处的函数值来构造低次多项式，用它作为函数的近似表达式，并用这个多项式的极小点作为原函数极小点的近似。常用的插值多项式为二次多项式。o牛顿法（切线法）利用一点的函数值、一阶导数值和二阶导数值来构造二次函数。1.1.二次插值法（抛物线法）利用三个点的函数值形成一个抛物线来构造二次函数。第44页/共66页1、牛顿法（切线法）、牛顿法（切线法）对于一维搜索函数 ，假定已经给出极小点的一个较好的近似点 ，在 点附近用一个二次函数 来逼近函数 。然后以该二次函数 的极小点作为 极小点的一个新的近似点 。根据极值必要条件：第45页/共66页牛顿法的几何解释：牛顿法的几何解释：在上图中，在 处用一抛物线 代替曲线 ，相当于用一斜线 代替 。这样各个近似点是通过对 作切线求得与 轴的交点找到，故牛顿法又称为切线法。第46页/共66页牛顿法的计算步骤：牛顿法的计算步骤：1 1）给定初始点 ，控制误差 ，并令 2 2）计算 3 3）求 4 4）若 ，则求得近似解 ，停止计算，否则作5 5）。5 5）令 转2 2）。第47页/共66页例题：给定 ，试用牛顿法求其极小点 。解：1 1）给定初始点 ，控制误差 2 2）3 3）4 4）第48页/共66页重复上边的过程，进行迭代，直到 为止。可得到计算结果如下表:表3-2 牛顿法的搜索过程k01234值ak35.166674.334744.03964.00066f(ak)-52153.3518332.301993.382990.00551f(ak)-24184.33332109.4458686.8699284.04720ak+15.166674.334744.039604.000664.00059第49页/共66页优点：收敛速度快。缺点：每一点都要进行二阶导数，工作量大；当用数值微分代替二阶导数，由于舍入误差会影响迭代速度；要求初始点离极小点不太远，否则有可能使极小化发散或收敛到非极小点。牛顿法的特点：第50页/共66页、二次插值法（抛物线法）、二次插值法（抛物线法）基本思想：基本思想：二次插值的基本思想是利用目标函二次插值的基本思想是利用目标函数在不同数在不同3 3 3 3点的函数值构成一个与原函数点的函数值构成一个与原函数f f f f(x x x x)相近似的二次多项式相近似的二次多项式p p p p(x x x x)，以函数，以函数p p p p(x x x x)的极的极值点值点x x x xp p(即即p p p p(x*x*x*x*p p p p)=0)=0)=0)=0的根的根)作为目标函数作为目标函数f f f f(x x x x)的近似极值点。的近似极值点。第51页/共66页（1）二次插值多项式的构成及其极值点）二次插值多项式的构成及其极值点设 在单谷区间中的三点 的相应函数值，则可以做出如下的二次插值多项式：第52页/共66页多项式 的极值点可从极值的必要条件求得，即 ，n为了确定这个极值点，只需计算出系数a a1 1和a a2 2 。其方法法是利用a a0 0、a a1 1、a a2 2的联立方程组中相邻两个方程消去a a0 0 ，从而得到关于a a1 1、a a2 2的方程组第53页/共66页解得所以第54页/共66页如果令如果令则则这样就得到了这样就得到了f()极小点极小点*的近似解的近似解p。）如果区间长度 足够小，则由 便得出我们所要求的近似极小点 第55页/共66页2 2）如果不满足，必须缩小区间 ，根据区间消取法原理不断缩小区间。根据区间消去法原理，需要已知区间内两点的函数值。其中点2 2的函数值y y2 2=f=f（2 2）已知，另外一点可取p p点并计算其函数值y yp p=f=f（p p）。当 y y2 2yyp p 时取 1 1，p p 为缩短后的搜索区间（如右图）。当y y2 2yyp p 时取 2 2，3 3 为缩短后的搜索区间。第56页/共66页二二次次插插值值法法程程序序框框图图第57页/共66页例1：用二次插值法求 上的极小点。12144.524.54.705120355y1-0.756802-0.977590y2-0.977590-0.999974y3-0.958924-0.958924p4.7051204.710594yp-0.999974-0.999998二二次次插插值值法法计计算算过过程程示示例例第58页/共66页例例 2 2 用二次插值法求函数用二次插值法求函数f f(x x)=3)=3x x3 3-4-4x x+2+2的极小的极小点，给定点，给定 x x0 0=0,=0,。2 2）用二次插值法逼近极小点相邻三点的函数值:x x1 1=0,=0,x x2 2=1,=1,x x3 3=2;=2;f f1 1=2,=2,f f2 2=1,=1,f f3 3=18.=18.代入公式：x xp p*0.555,f0.555,fp p解 :1 1）确定初始区间初始区间 a a,b b=0,2,=0,2,中间点x x2 2=1,=1,f f(x x2 2)=1)=1。第59页/共66页由于f fp p f f2 2,x xp p*0.2,|=1-0.555=0.4450.2,应继续迭代。在新区间，相邻三点的函数值:x x1 1=0,=0,x x2 2=0.555,=0.555,x x3 3=1;=1;f f1 1=2,=2,f f2 2=0.292,=0.292,f f3 3=1,=1,代入x xp p*公式计算得：x xp p*0.607,f0.607,fp p 由于f fp p x x2 2,新区间 a a,b b=x x2 2,b b=0.555,1=0.555,1|x x2 2-x xp p*|=|0.555-0.607|=0.0520.2,|=|0.555-0.607|=0.0520.2,迭代终止。x xp p*第60页/共66页例例 3 用二次插值法求用二次插值法求 的极值点。的极值点。初始搜索区间初始搜索区间 ，。解：取x x2 2点为区间 x x1 1,x x3 3 的中点 ，计算x x1 1,x x2 2,x x3 3 3 3点处的函数值f f1 1=19=19，f f2 2=-96.9375=-96.9375，f f3 3=124=124。可见函数值满足“高低高”形态。以x x1 1,x x2 2,x x3 3为插值点构造二次曲线。求第一次近似的二次曲线p p(x x)的极小值点，由公式得：比较函数值可知第61页/共66页 这种情况应消除左边区段 。然后用 作为x x1 1,x x2 2,x x3 3新3 3点,重新构造二次曲线p p(x x)，如此反复计算，直到 为止。整个迭代过程的计算结果列于表。第62页/共66页第63页/共66页 插值法和试探法的比较试探法中试验点位置是由某种给定的规律确定的，它不考虑函数值的分布。例如，黄金分割法是按等比例缩短率确定的。插值法中，试验点位置是按函数值近似分布的极小点确定的。试探法仅仅利用了试验点函数值大小的比较，而插值法还要利用函数值本身或者其导数信息。试探法仅对试验点函数值的大小进行比较，而函数值本身的特性没有得到充分利用，这样即使对一些简单的函数，例如二次函数，也不得不象一般函数那样进行同样多的函数值计算。插值法是利用函数在已知试验点的值（或导数值）来确定新试验点的位置。当函数具有比较好的解析性质时（例如连续可微性），插值法比试探法效果更好。第64页/共66页复习l 初始区间的确定方法l 黄金分割算法l 二次差值的计算第65页/共66页感谢您的观看！第66页/共66页