第三章 一维搜索(线性搜索)

第三章一维搜索方法3.1概述3.2确定初始区间3.3缩小区间3.4黄金分割法〔0.618法〕3.5一维搜索的插值方法编辑课件第3章一维搜索方法3.1概述3.1.1一维问题是多维问题的根底求目标函数f(X)的极小点，从理论上说需要求解方程：其中那么如何来求f(X)的极小点呢？根本思想:这种方法是逐次迭代的方法，在电子计算机上很容易实现，因此它在优化设计中被广泛地采用。2编辑课件这个过程称为一维搜索过程。如：则当Sk方向上的任何一点可以表示为其中α是步长因子，为实系数，此时Sk方向上任何一点的目标函数值为，它是参数α的一元函数。那么在沿Sk方向求的极小点，这就是求一元函数

的极小问题，它可表示为：3编辑课件一维搜索示意图编辑课件求多元函数极值点，需要进行一系列的一维搜索。可见一维搜索是优化搜索方法的根底。求解一元函数的极小点，可采用解析解法，即利用一元函数的极值条件求在用函数的导数求时，所用的函数是仅以步长因子为变量的一元函数，而不是以设计点x为变量的多元函数。3.1.2的确定方法为了直接利用的函数式求解最正确步长因子。把或它的简写形式进行泰勒展开，取到二阶项，即将上式对进行微分并令其等于零，给出极值点应满足的条件从而求得编辑课件这里是直接利用函数而不需要把它化成步长因子。的函数。不过，此时需要计算点处梯度和海赛矩阵H。解析解法的缺点——需要进行求导计算。对于函数关系复杂、求导困难或无法求导的情况，使用解析法将是非常不便的。因此，在优化设计中，求解最正确步长因子主要采用数值解法，利用计算机通过反复迭代计算求得最正确步长因子的近似值。数值解法的根本思路是：首先确定所在的搜索区间，然后根据区间消去法原理不断缩小此区间，从而获得的数值近似解。编辑课件解析法:①f(X(k)+αS(k))沿S(k)

方向在x(k)

点泰勒展开；②取二次近似：

对α求导，令其为零。

④求得最优步长编辑课件数值解法根本思路：解析解法对于函数关系复杂、求导困难等情况难以实现。在实际优化设计中，数值解法的应用更为有效，且适合计算机的运算特点。

一维搜索也称直线搜索。这种方法不仅对于解决一维最优化问题具有实际意义，而且也是求解多维最优化问题的重要支柱。一维搜索一般分为两大步骤：(1)确定初始搜索区间[a，b]，该区间应是包括一维函数极小点在内的单谷区间。(2)在单谷区间[a,b]内通过缩小区间寻找极小点。先确定在的搜索区间，然后根据区间消去法原理不断缩小此区间所，从而获得的数值近似解。编辑课件1、确定搜索区间的外推法在给定区间内仅有一个谷值〔或有唯一的极小点〕的函数称为单谷函数，其区间称为单谷区间。函数值：“大—小—大〞图形：“高—低—高〞单谷区间中一定能求得一个极小点。3.2确定初始区间编辑课件从开始，以初始步长向前试探。如果函数值上升，那么步长变号，即改变试探方向。如果函数值下降，那么维持原来的试探方向，并将步长加倍。区间的始点、中间点依次沿试探方向移动一步。此过程一直进行到函数值再次上升时为止，即可找到搜索区间的终点。最后得到的三点即为搜索区间的始点、中间三点和终点，形成函数值的“高－低－高〞趋势。单谷区间编辑课件f(x)0α1α3α0f(x)α3α1说明：单谷区间内，函数可以有不可微点，也可以是不连续函数；编辑课件外推方法基本思想：对任选一个初始点及初始步长，通过比较这两点函数值的大小，确定第三点位置，比较这三点的函数值大小，确定是否为“高—低—高”形态。步骤：1〕选定初始点a1，初始步长h=h0，计算y1=f(a1)和y2=f(a1+h)2〕比较y1和y2；a〕如果y1>y2，向右前进，加大步长h=2h0，转〔3〕向前；b〕如果y1<y2，向左后退，h=-2h0，将a1和a2,y1和y2的值互换。转〔3〕向后探测；c〕如果y1=y2，极小点在a1和a1+h之间。3〕产生新的探测点a3=a2+h，y3=f(a3)；编辑课件4〕比较函数值y2和y3：a〕如果y2>y3，加大步长h=2h，a1=a2,a2=a3,转〔3〕继续探测；b〕如果y2<y3，那么初始区间得到：a=min[a1,a3],b=max[a1,a3]，函数最小值所在区间为[a,b]。编辑课件右图表示沿的正向试探。每走一步都将区间的始点、中间点沿试探方向移动一步〔进行换名〕。经过三步最后确定搜索间，并且得到区间始点、中间点和终点所对应的函数值。y1y3→y2y2→y1a3→a2a2→a1a1Oaa3h0h02h0图3-2正向搜索的外推法右图所表示的情况是：开始是沿的正方向试探，但由于函数值上升而改变了试探方向，最后得到始点，中间点和终点

及它们的对应函数值

从而形成单谷区间为一维搜索区间。y1←y2a2←a3a1←a2←a1Oaa32h0h0h0y3y1←y2←y1y2←y3a1←a2图3-3反向搜索的外推法编辑课件khx1x2x30h0初始点初始点+h012h0初始点初始点+h0初始点+3h024h0初始点+h0初始点+3h0初始点+7h038h0初始点+3h0初始点+7h0初始点+15h0前进搜索步骤表编辑课件khx1x2x30h0初始点初始点+h012h0初始点+h0初始点初始点-2h024h0初始点初始点-2h0初始点-6h038h0初始点-2h0初始点-6h0初始点-14h0后退搜索步骤表khx1y1x2y2x3y310.10.2090.18.2030.36.68120.40.18.2030.36.6810.74.42930.80.36.6810.74.4291.57.125解：19编辑课件khx1y1x2y2x3y310.1-0.21.812.0961.914.3771.914.3771.812.0961.68.4882-0.41.812.0961.68.4881.24.5843-0.81.68.4881.24.5840.45.992

运用进退法确定出初始搜索区间[a,b]后，便可采用一维优化方法来求出函数f(x)在区间内的最优点x*。20编辑课件2.程序框图h=h0y1=f(x1)、x2=x1+h、y2=f(x2)给定x1、h0y1≥y2y2≥y3是h=2hx3=x2+h、y3=f(x3)结束否h=-hx3=x1y3=y1a=x1、b=x3是x1=x2y1=y2x2=x3y2=y3是a=x3、b=x1否h>0否初始进退距前进计算后退计算21编辑课件

，

搜索区间确定之后，采用区间消去法逐步缩短搜索区间，从而找到极小点的数值近似解。

假定在搜索区间内任取两点，且

3.3区间消去方法编辑课件(1)f〔a1〕<f〔b1〕,那么极小点必在区间[a，b1]内;编辑课件(1)f〔a1〕<f〔b1〕,那么极小点必在区间[a，b1]内;(2)f〔a1〕>f〔b1〕,那么极小点必在区间[α1，b]内;编辑课件(1)f〔a1〕<f〔b1〕,那么极小点必在区间[a，b1]内;(2)f〔a1〕>f〔b1〕,那么极小点必在区间[α1，b]内;(3)f〔a1〕=f〔b1〕,那么极小点必在区间[α1，b1]内可以总结为两种情况：若，则取[a,b1]为缩小后的搜索区间。若，则取[a1,b]为缩小后的搜索区间。编辑课件试探法黄金分割法插值法二次插值法3一维搜索方法分类从前面的分析可知，每次缩短区间，只需要在区间内再插入一点并计算其函数值。而插入点的位置，可以由不同的方法来确定。就形成了不同的一维搜索方法。一维搜索方法分类编辑课件3.4黄金分割法〔0.618法〕黄金分割法黄金分割法的搜索过程编辑课件概述在实际计算中，最常用的一维搜索试探方法是黄金分割法，又称作0.618法。我们可以通过学习黄金分割法来了解一维搜索试探方法的根本思想。在搜索区间[a,b]内适当插入两点α1、α2，并计算其函数值。α1、α2将区间分成三段。应用函数的单谷性质，通过函数值大小的比较，删去其中一段，使搜索区间得以缩短。然后再在保存下来的区间上作同样的处置，如此迭代下去，使搜索区间无限缩小，从而得到极小点的数值近似解。3.4黄金分割法〔0.618法〕编辑课件黄金分割法是建立在区间消去法原理根底上的试探方法。适用于[a,b]区间上的任何单谷函数求极小值问题。对函数除要求“单谷〞外不作其它要求，甚至可以不连续。因此，这种方法的适应面相当广。黄金分割法对插入点的要求：1〕要求插入点α1、α2的位置相对于区间[a,b]两端点具有对称性，即

其中为待定常数。1.黄金分割法编辑课件2〕黄金分割法还要求在保存下来的区间内再插入一点所形成的区间新三段，与原来区间的三段具有相同的比例分布。即每次缩小所得的新区间长度与缩小前区间长度之比〔即：区间收缩率〕为定值。编辑课件设原区间[a,b]长度为1如以下图所示，保存下来的区间[a,α2]长度为，区间缩短率为。为了保持相同的比例分布，新插入点α3应在位置上，α1在原区间的位置应相当于在保存区间的位置。故有取方程正数解，得α1、α2将区间分成三段黄金分割法要求在保存下来的区间内再插入一点所形成的区间新三段，与原来区间的三段具有相同的比例分布。两内分点值:结论：所谓黄金分割是指将一线段分成两段的方法，使整段长与较长段的长度比值等于较长段与较短段长度的比值即。编辑课件黄金分割法要求插入两点：黄金分割法区间消去示意图：3.4黄金分割法〔0.618法〕编辑课件2.黄金分割法的搜索过程（1）给出初始搜索区间及收敛精度，将赋以

。

〔2〕按坐标点计算公式计算并计算其对应的函数值3.4黄金分割法〔0.618法〕编辑课件〔3〕根据区间消去法原理缩短搜索区间。为了能用原来的坐标点计算公式，进行区间名称的代换，并在保存区间中计算一个新的试验点及其函数值。3.4黄金分割法〔0.618法〕编辑课件〔4〕检查区间是否缩短到足够小和函数值收敛到足够精度，如果收敛条件满足，那么取最后两试验点的平均值作为极小点的数值近似解。如果条件不满足那么转向步骤5。〔5〕产生新的插入点：如N0=0，那么取〔5〕如果条件满足，那么取最后两试验点的平均值作为极小点的数值近似解。3.4黄金分割法〔0.618法〕缩短区间的总次数〔迭代次数〕:编辑课件黄金分割法程序框图给定否否是是止也可采用迭代次数是否大于或等于k作终止准那么。编辑课件迭代序号aby1比较y20-30.0561.94450.115<7.6671-3-1.1110.0561.944-0.987<0.1152-3-1.832-1.1110.056-0.306>-0.9873-1.832-1.111-0.6650.056-0.987<-0.8884-1.832-1.386-1.111-0.665-0.851>-0.9875-1.386-1.111-0.940-0.665例3-3：用黄金分割法求的极小值，搜索区间是解：38编辑课件解析解：39编辑课件例3-1用黄金分割法求函数f(x)=3x3-4x+2的极小点，给定x0=0,h=1,ε=0.2。解：1〕确定初始区间a1=x0=0,f1=f(a1)=2a2=x0+h=0+1=1,f2=f(a2)=1由于f1>f2,应加大步长继续向前探测。a3=x0+2h=0+2=2,f3=f(a3)=18由于f2<f3,可知初始区间已经找到，即[a,b]=[a1,a3]=[0,2]2〕用黄金分割法缩小区间第一次缩小区间：a1=0+0.382×(2-0)=0.764,f1=0.282a2=0+0.618×(2-0)=1.236,f2=2.72f1<f2,新区间[a,b]=[a,a2]=[0,1.236],b-a>0.2编辑课件第二次缩小区间：令x2=x1=0.764,f2=f1=0.282

x1=0+0.382X(1.236-0)=0.472,f1=0.317由于f1>f2,故新区间[a,b]=[x1,b]=[0.472,1.236]因为b-a=1.236-0.472=0.764>0.2,应继续缩小区间。

第三次缩小区间：令x1=x2=0.764,f1=f2=0.282

x2=0.472+0.618X(1.236-0.472)=0.944,f2=0.747由于f1<f2,故新区间[a,b]=[a,x2]=[0.472,0.944]因为b-a=0.944-0.472=0.472>0.2,应继续缩小区间。编辑课件

第四次缩小区间：令x2=x1=0.764,f2=f1=0.282

x1=0.472+0.382X(0.944-0.472)=0.652,f1=0.223由于f1<f2,故新区间[a,b]=[a,x2]=[0.472,0.764]因为b-a=0.764-0.472=0.292>0.2,应继续缩小区间。第五次缩小区间：令x2=x1=0.652,f2=f1=0.223

x1=0.472+0.382X(0.764-0.472)=0.584,f1=0.262由于f1>f2,故新区间[a,b]=[x1,b]=[0.584,0.764]因为b-a=0.764-0.584=0.18<0.2,停止迭代。极小点与极小值：x*=0.5X(0.584+0.764)=0.674,f(x*)=0.222编辑课件概述一维搜索问题是在某一确定区间内寻求一元函数的极小点的位置，在某些情况下，如果没有函数表达式，但能够给出假设干试验点处的函数值，就可以根据这些点处的函数值，利用插值法建立函数的某种近似表达式，进而求出函数的极小点，并用它作为原来函数极小点的近似值。这种方法称作插值法，又称作函数逼近法。3.5

一维搜索的二次插值法编辑课件试探法〔如黄金分割法〕与插值法的比较：不同点：表现在试验点〔插入点〕位置确实定方法不同。编辑课件多项式是函数逼近的一种常用工具。在搜索区间内可以利用假设干试验点处的函数值来构造低次多项式，用它作为函数的近似表达式，并用这个多项式的极小点作为原函数极小点的近似。常用的插值多项式为二次多项式。牛顿法〔切线法〕利用一点的函数值、一阶导数值和二阶导数值来构造二次函数。二次插值法〔抛物线法〕利用三个点的函数值形成一个抛物线来构造二次函数。编辑课件1、牛顿法〔切线法〕对于一维搜索函数，假定已经给出极小点的一个较好的近似点，在点附近用一个二次函数来逼近函数

。然后以该二次函数的极小点作为极小点的一个新的近似点。根据极值必要条件：编辑课件牛顿法的几何解释：在上图中，在处用一抛物线代替曲线，相当于用一斜线代替。这样各个近似点是通过对作切线求得与轴的交点找到，故牛顿法又称为切线法。编辑课件牛顿法的计算步骤：1）给定初始点，控制误差，并令2）计算3）求4）若，则求得近似解，停止计算，否则作5）。5）令转2）。编辑课件例题：

给定，试用牛顿法求其极小点。解：1〕给定初始点，控制误差2〕3〕4〕编辑课件重复上边的过程，进行迭代，直到为止。可得到计算结果如下表:表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编辑课件优点：收敛速度快。缺点：每一点都要进行二阶导数，工作量大；当用数值微分代替二阶导数，由于舍入误差会影响迭代速度；要求初始点离极小点不太远，否那么有可能使极小化发散或收敛到非极小点。牛顿法的特点：编辑课件２、二次插值法〔抛物线法〕根本思想：二次插值的根本思想是利用目标函数在不同3点的函数值构成一个与原函数f(x)相近似的二次多项式p(x)，以函数p(x)的极值点xp(即p′(x*p)=0的根)作为目标函数f(x)的近似极值点。〔1〕二次插值多项式的构成及其极值点设在单谷区间中的三点

的相应函数值

，那么可以做出如下的二次插值多项式：编辑课件多项式的极值点可从极值的必要条件求得，即，

为了确定这个极值点，只需计算出系数a1和a2

。其方法法是利用a0、a1、a2的联立方程组中相邻两个方程消去a0

，从而得到关于a1、a2的方程组编辑课件解得所以编辑课件如果令那么这样就得到了f(α)极小点α*的近似解αp。

１）如果区间长度

足够小，则由

便得出我们所要求的近似极小点

编辑课件2）如果不满足，必须缩小区间

，根据区间消取法原理不断缩小区间。根据区间消去法原理，需要区间内两点的函数值。其中点α2的函数值y2=f〔α2〕，另外一点可取αp点并计算其函数值yp=f〔αp〕。当y2<yp时取[α1，αp]为缩短后的搜索区间〔如右图〕。当y2≥yp时取[α2，α3]为缩短后的搜索区间。编辑课件二次插值法程序框图编辑课件例1：用二次插值法求

上的极小点。

12α144.5α24.54.705120α355y1-0.756802-0.977590y2-0.977590-0.999974y3-0.958924-0.958924αp4.7051204.710594yp-0.999974-0.999998二次插值法计算过程例如编辑课件例2用二次插值法求函数f(x)=3x3-4x+2的极小点，给定x0=0,ε=0.2。2〕用二次插值法逼近极小点相邻三点的函数值:x1=0,x2=1,x3=2;f1=2,f2=1,f3=18.代入公式：xp*＝0.555,fp=0.292解:1〕确定初始区间初始区间[a,b]=[0,2],中间点x2=1,f(x2)=1。编辑课件由于fp<f2,xp*

<x2,新区间[a,b]=[a,x2]=[0,1]|x2-xp*

|=1-0.555=0.445>0.2,