第3章一维搜索方法.ppt

第3章一维搜索方法.ppt

《第3章一维搜索方法.ppt》由会员分享，可在线阅读，更多相关《第3章一维搜索方法.ppt（68页珍藏版）》请在冰点文库上搜索。

机械优化设计,第三章一维搜索方法,第三章一维搜索方法,当采用数学规划法寻求多元函数的极值点时，一般要进行一系列如下格式的迭代计算：

当方向,给定，求最佳步长,就是求一元函数,的极值问题。

这一过程被称为一维搜索。

第一节一维搜索的概念,求多元函数极值点，需要进行一系列的一维搜索。

可见一维搜索是优化搜索方法的基础。

求解一元函数的极小点，可采用解析解法，即利用一元函数的极值条件求在用函数的导数求时，所用的函数是仅以步长因子为变量的一元函数，而不是以设计点x为变量的多元函数。

为了直接利用的函数式求解最佳步长因子。

可把或它的简写形式进行泰勒展开，取到二阶项，即将上式对进行微分并令其等于零，给出极值点应满足的条件从而求得,这里是直接利用函数而不需要把它化成步长因子。

的函数。

不过，此时需要计算点处的梯度和海赛矩阵。

解析解法的缺点需要进行求导计算。

对于函数关系复杂、求导困难或无法求导的情况，使用解析法将是非常不便的。

因此，在优化设计中，求解最佳步长因子主要采用数值解法，利用计算机通过反复迭代计算求得最佳步长因子的近似值。

数值解法的基本思路是：

首先确定所在的搜索区间，然后根据区间消去法原理不断缩小此区间，从而获得的数值近似解。

一维搜索是优化搜索方法的基础。

2023年10月30日7时16分,一维搜索方法解析法高等数学已学过，即利用一维函数的极值条件：

求,一维搜索方法数值解法分类,1.解析法：

步骤:

f（X（k）+S（k）沿S（k）方向在x（k）点进行泰勒展开；取二次近似：

对求导，令其为零。

数值解法基本思路：

先确定所在的搜索区间，然后根据区间消去法原理不断缩小此区间，从而获得的数值近似解。

解析解法对于函数关系复杂、求导困难等情况难以实现。

在实际优化设计中，数值解法的应用更为有效，且适合计算机的运算特点。

一维搜索也称直线搜索。

这种方法不仅对于解决一维最优化问题具有实际意义，而且也是求解多维最优化问题的重要支柱。

一维搜索一般分为两大步骤：

（1）确定初始搜索区间a，b，该区间应是包括一维函数极小点在内的单谷区间。

（2）在单谷区间a,b内通过缩小区间寻找极小点。

1、确定搜索区间的外推法,在给定区间内仅有一个谷值（或有唯一的极小点）的函数称为单谷函数，其区间称为单谷区间。

函数值：

“大小大”,图形：

“高低高”,单谷区间中一定能求得一个极小点。

第二节搜索区间的确定与区间消去法原理,从开始，以初始步长向前试探。

如果函数值上升，则步长变号，即改变试探方向。

如果函数值下降，则维持原来的试探方向，并将步长加倍。

区间的始点、中间点依次沿试探方向移动一步。

此过程一直进行到函数值再次上升时为止，即可找到搜索区间的终点。

最后得到的三点即为搜索区间的始点、中间三点和终点，形成函数值的“高低高”趋势。

说明：

单谷区间内，函数可以有不可微点，也可以是不连续函数；,外推方法,基本思想：

对任选一个初始点及初始步长，通过比较这两点函数值的大小，确定第三点位置，比较这三点的函数值大小，确定是否为“高低高”形态。

步骤：

1）选定初始点a1，初始步长h=h0，计算y1=f（a1）和y2=f（a1+h）,2）比较y1和y2；,a）如果y1y2，向右前进，加大步长h=2h0，转（3）向前；b）如果y1y2，向左后退，h=-2h0，将a1和a2,y1和y2的值互换。

转（3）向后探测；c）如果y1=y2，极小点在a1和a1+h之间。

3）产生新的探测点a3=a2+h，y3=f（a3）；,4）比较函数值y2和y3：

a）如果y2y3，加大步长h=2h，a1=a2,a2=a3,转（3）继续探测；b）如果y2y3，则初始区间得到：

a=mina1,a3,b=maxa1,a3，函数最小值所在区间为a,b。

右图表示沿的正向试探。

每走一步都将区间的始点、中间点沿试探方向移动一步（进行换名）。

经过三步最后确定搜索间，并且得到区间始点、中间点和终点所对应的函数值。

y1,y3y2,y2y1,a3a2,a2a1,a1,O,a,a3,h0,h0,2h0,图3-2正向搜索的外推法,右图所表示的情况是：

开始是沿的正方向试探，但由于函数值上升而改变了试探方向，最后得到始点，中间点和终点及它们的对应函数值，从而形成单谷区间为一维搜索区间。

y1y2,a2a3,a1a2a1,O,a,a3,2h0,h0,h0,y3,y1y2y1,y2y3,a1a2,图3-3反向搜索的外推法,前进搜索步骤表,后退搜索步骤表,2、区间消去法原理,基本思想：

（1）f（a1）f（b1）,则极小点必在区间1，b内;（3）f（a1）=f（b1）,则极小点必在区间1，b1内,根据以上所述，只要在区间a,b内取两个点，算出它们的函数值并加以比较，就可以把搜索区间a,b缩短成a,b1，1，b或1，b1。

对于第一种情况，我们已算出区间a,b1内1点的函数值，如果要把搜索区间a,b1进一步缩短，只需在其内再取一点算出函数值并与f

（1）加以比较，即可达到目的。

对于第二种情况，同样只需再计算一点函数值就可以把搜索区间继续缩短。

第三种情形与前面两种情形不同，因为在区间1，b1内缺少已算出的函数值。

要想把区间1，b1进一步缩短，需在其内部取两个点（而不是一个点）计算出相应的函数值再加以比较才行。

如果经常发生这种情形，为了缩短搜索区间，需要多计算一倍数量的函数值，这就增加了计算工作量。

程序设计技巧为了避免多计算函数值，我们把第三种情形合并到前面两种情形中去。

例如，可以把前面三种情形改为下列两种情形：

从上述的分析中可知，为了每次缩短区间，只需要在区间内再插入一点并计算其函数值。

如此反复进行下去，当搜索区间长度足够小时，可用区间内的某点作为极小点的近似值。

若则取为缩短后的搜索区间。

若则取为缩短后的搜索区间。

3、一维搜索方法分类,根据插入点位置的确定方法，可以把一维搜索法分成两大类：

试探法：

即按照某种规律来确定区间内插入点的位置，此点位置的确定仅仅按照区间缩短如何加快，而不顾及函数值的分布关系。

如黄金分割法，裴波纳契法等。

裴波纳契数列：

1、1、2、3、5、8、13、21、34、55、89、144,插值法（函数逼近法）：

通过构造插值函数来逼近原函数，用插值函数的极小点作为区间的插入点，如牛顿法（切线法）、二次插值法（抛物线法）、三次插值法等。

概述在实际计算中，最常用的一维搜索试探方法是黄金分割法，又称作0.618法。

我们可以通过学习黄金分割法来了解一维搜索试探方法的基本思想。

在搜索区间a,b内适当插入两点1、2，并计算其函数值。

1、2将区间分成三段。

应用函数的单谷性质，通过函数值大小的比较，删去其中一段，使搜索区间得以缩短。

然后再在保留下来的区间上作同样的处置，如此迭代下去，使搜索区间无限缩小，从而得到极小点的数值近似解。

第三节一维搜索的试探方法黄金分割法,黄金分割法黄金分割法是建立在区间消去法原理基础上的试探方法。

适用于a,b区间上的任何单谷函数求极小值问题。

对函数除要求“单谷”外不作其它要求，甚至可以不连续。

因此，这种方法的适应面相当广。

黄金分割法对插入点的要求：

1）要求插入点1、2的位置相对于区间a,b两端点具有对称性，即其中为待定常数。

2）黄金分割法还要求在保留下来的区间内再插入一点所形成的区间新三段，与原来区间的三段具有相同的比例分布。

即每次缩小所得的新区间长度与缩小前区间长度之比（即：

区间收缩率）为定值。

设原区间a,b长度为1如下图所示，保留下来的区间a,2长度为，区间缩短率为。

为了保持相同的比例分布，新插入点3应在位置上，1在原区间的位置应相当于在保留区间的位置。

故有取方程正数解，得,1、2将区间分成三段,黄金分割法要求在保留下来的区间内再插入一点所形成的区间新三段，与原来区间的三段具有相同的比例分布。

黄金分割法的搜索过程,

（1）给出初始搜索区间及收敛精度，将赋以,

（2）按坐标点计算公式计算并计算其对应的函数值,（3）根据区间消去法原理缩短搜索区间。

为了能用原来的坐标点计算公式，进行区间名称的代换，并在保留区间中计算一个新的试验点及其函数值。

（4）检查区间是否缩短到足够小和函数值收敛到足够近，如果条件不满足返回到步骤

（2）。

（5）如果条件满足，则取最后两试验点的平均值作为极小点的数值近似解。

缩短区间的总次数（迭代次数）:

黄金分割法程序框图,给定,也可采用迭代次数是否大于或等于k作终止准则。

举例,对函数,，当给定搜索区间,时，试用黄金分割法求极小点,。

例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由于f1f2,应加大步长继续向前探测。

a3=x0+2h=0+2=2,f3=f（a3）=18由于f2f3,可知初始区间已经找到，即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.72f10.2,第二次缩小区间：

令x2=x1=0.764,f2=f1=0.282x1=0+0.382X（1.236-0）=0.472,f1=0.317由于f1f2,故新区间a,b=x1,b=0.472,1.236因为b-a=1.236-0.472=0.7640.2,应继续缩小区间。

第三次缩小区间：

令x1=x2=0.764,f1=f2=0.282x2=0.472+0.618X（1.236-0.472）=0.944,f2=0.747由于f10.2,应继续缩小区间。

第四次缩小区间：

令x2=x1=0.764,f2=f1=0.282x1=0.472+0.382X（0.944-0.472）=0.652,f1=0.223由于f10.2,应继续缩小区间。

第五次缩小区间：

令x2=x1=0.652,f2=f1=0.223x1=0.472+0.382X（0.764-0.472）=0.584,f1=0.262由于f1f2,故新区间a,b=x1,b=0.584,0.764因为b-a=0.764-0.584=0.180.2,停止迭代。

极小点与极小值：

x*=0.5X（0.584+0.764）=0.674,f（x*）=0.222,第四节一维搜索的插值方法,概述一维搜索问题是在某一确定区间内寻求一元函数的极小点的位置，在某些情况下，如果没有函数表达式，但能够给出若干试验点处的函数值，就可以根据这些点处的函数值，利用插值法建立函数的某种近似表达式，进而求出函数的极小点，并用它作为原来函数极小点的近似值。

这种方法称作插值法，又称作函数逼近法。

试探法（如黄金分割法）与插值法的比较：

不同点：

表现在试验点（插入点）位置的确定方法不同。

多项式是函数逼近的一种常用工具。

在搜索区间内可以利用若干试验点处的函数值来构造低次多项式，用它作为函数的近似表达式，并用这个多项式的极小点作为原函数极小点的近似。

常用的插值多项式为二次多项式。

牛顿法（切线法）利用一点的函数值、一阶导数值和二阶导数值来构造二次函数。

二次插值法（抛物线法）利用三个点的函数值形成一个抛物线来构造二次函数。

1、牛顿法（切线法）,对于一维搜索函数，假定已经给出极小点的一个较好的近似点，在点附近用一个二次函数来逼近函数,然后以该二次函数的极小点作为极小点的一个新的近似点。

根据极值必要条件：

牛顿法的几何解释：

在上图中，在处用一抛物线代替曲线，相当于用一斜线代替。

这样各个近似点是通过对作切线求得与轴的交点找到，故牛顿法又称为切线法。

牛顿法的计算步骤：

例题：

给定,，试用,牛顿法求其极小点。

解：

1）给定初始点,，控制误差,2）,3）,4）,重复上边的过程，进行迭代，直到,为止。

可得到计算结果如下表:

优点：

收敛速度快。

缺点：

每一点都要进行二阶导数，工作量大；,当用数值微分代替二阶导数，由于舍入误差会影响迭代速度；要求初始点离极小点不太远，否则有可能使极小化发散或收敛到非极小点。

牛顿法的特点：

、二次插值法（抛物线法）,基本思想：

二次插值的基本思想是利用目标函数在不同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的函数值y2=f

（2）已知，另外一点可取p点并计算其函数值yp=f（p）。

当y2yp时取1，p为缩短后的搜索区间（如右图）。

当y2yp时取2，3为缩短后的搜索区间。

程序设计技巧为了在每次计算插入点的坐标时能应用同一计算公式，新区间端点的坐标及函数值名称需换成原区间端点的坐标及函数值名称。

在每个新区间上仍取1、2、3三点及其相应函数值y1y2y3。

这样当计算插入点（即抛物线极小点p）位置时仍可以应用原来的计算公式。

根据p与2的相对位置，yp与y2的大小以及正向搜索（h0）或反向搜索（h0）的不同，具体换名有如下表所示的八种情况。

（P56）,上表中的中的h就是在进行外推法时求初始搜索区间过程中所形成的最后步长，h可正可负，分别对应于沿正向或反向进行的一维搜索。

分析上述八种换名情况可知，如果乘积的符号相同，那么正向搜索和反向搜索将采取同样的换名方式，从而可将上述八种情况合并成四种情况，从而可将程序框图简化。

二次插值法程序框图,例1：

用二次插值法求,上的极小点。

二次插值法计算过程示例,例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。

由于fp0.2,应继续迭代。

在新区间，相邻三点的函数值:

x1=0,x2=0.555,x3=1;f1=2,f2=0.292,f3=1,代入xp*公式计算得：

xp*0.607,fp=0.243,由于fpx2,新区间a,b=x2,b=0.555,1|x2-xp*|=|0.555-0.607|=0.0520.2,迭代终止。

xp*0.607,f*=0.243,例3用二次插值法求的极值点。

初始搜索区间，。

解：

取x2点为区间x1,x3的中点，,计算x1,x2,x33点处的函数值f1=19，f2=-96.9375，f3=124。

可见函数值满足“高低高”形态。

以x1,x2,x3为插值点构造二次曲线，求第一次近似的二次曲线p（x）的极小值点，由公式得：

，比较函数值可知,这种情况应消除左边区段。

然后用作为x1,x2,x3新3点,重新构造二次曲线p（x），如此反复计算，直到为止。

整个迭代过程的计算结果列于表。

插值法和试探法的比较试探法中试验点位置是由某种给定的规律确定的，它不考虑函数值的分布。

例如，黄金分割法是按等比例0.618缩短率确定的。

插值法中，试验点位置是按函数值近似分布的极小点确定的。

试探法仅仅利用了试验点函数值大小的比较，而插值法还要利用函数值本身或者其导数信息。

试探法仅对试验点函数值的大小进行比较，而函数值本身的特性没有得到充分利用，这样即使对一些简单的函数，例如二次函数，也不得不象一般函数那样进行同样多的函数值计算。

插值法是利用函数在已知试验点的值（或导数值）来确定新试验点的位置。

当函数具有比较好的解析性质时（例如连续可微性），插值法比试探法效果更好。