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

第三章一维搜索方法,3.1概述3.2确定初始区间3.3缩小区间3.4黄金分割法（0.618法）3.5一维搜索的插值方法,2,第3章一维搜索方法,3.1概述,3.1.1一维问题是多维问题的基础,求目标函数f(X)的极小点，从理论上说需要求解方程：,其中,那么如何来求f(X)的极小点呢？,基本思想:,这种方法是逐次迭代的方法，在电子计算机上很容易实现，因此它在优化设计中被广泛地采用。,3,这个过程称为一维搜索过程。,如：,当,Sk方向上的任何一点可以表示为,其中是步长因子，为实系数，此时Sk方向上任何一点的目标函数值,为，它是参数的一元函数。那么在沿Sk方向求,的极小点，这就是求一元函数的极小问题，它可表示为：,一维搜索示意图,求多元函数极值点，需要进行一系列的一维搜索。可见一维搜索是优化搜索方法的基础。求解一元函数的极小点，可采用解析解法，即利用一元函数的极值条件求在用函数的导数求时，所用的函数是仅以步长因子为变量的一元函数，而不是以设计点x为变量的多元函数。,3.1.2的确定方法,为了直接利用的函数式求解最佳步长因子。把或它的简写形式进行泰勒展开，取到二阶项，即将上式对进行微分并令其等于零，给出极值点应满足的条件从而求得,这里是直接利用函数而不需要把它化成步长因子。的函数。不过，此时需要计算点处梯度和海赛矩阵H。解析解法的缺点需要进行求导计算。对于函数关系复杂、求导困难或无法求导的情况，使用解析法将是非常不便的。因此，在优化设计中，求解最佳步长因子主要采用数值解法，利用计算机通过反复迭代计算求得最佳步长因子的近似值。数值解法的基本思路是：首先确定所在的搜索区间，然后根据区间消去法原理不断缩小此区间，从而获得的数值近似解。,解析法:f(X(k)+S(k)沿S(k)方向在x(k)点泰勒展开；取二次近似：,对求导，令其为零。,求得最优步长,数值解法基本思路：,解析解法对于函数关系复杂、求导困难等情况难以实现。在实际优化设计中，数值解法的应用更为有效，且适合计算机的运算特点。,一维搜索也称直线搜索。这种方法不仅对于解决一维最优化问题具有实际意义，而且也是求解多维最优化问题的重要支柱。,一维搜索一般分为两大步骤：(1)确定初始搜索区间a，b，该区间应是包括一维函数极小点在内的单谷区间。(2)在单谷区间a,b内通过缩小区间寻找极小点。,先确定在的搜索区间，然后根据区间消去法原理不断缩小此区间所，从而获得的数值近似解。,1、确定搜索区间的外推法,在给定区间内仅有一个谷值（或有唯一的极小点）的函数称为单谷函数，其区间称为单谷区间。,函数值：“大小大”,图形：“高低高”,单谷区间中一定能求得一个极小点。,3.2确定初始区间,从开始，以初始步长向前试探。如果函数值上升，则步长变号，即改变试探方向。如果函数值下降，则维持原来的试探方向，并将步长加倍。区间的始点、中间点依次沿试探方向移动一步。此过程一直进行到函数值再次上升时为止，即可找到搜索区间的终点。最后得到的三点即为搜索区间的始点、中间三点和终点，形成函数值的“高低高”趋势。,说明：单谷区间内，函数可以有不可微点，也可以是不连续函数；,外推方法,基本思想：对任选一个初始点及初始步长，通过比较这两点函数值的大小，确定第三点位置，比较这三点的函数值大小，确定是否为“高低高”形态。,步骤：,1）选定初始点a1，初始步长h=h0，计算y1=f(a1)和y2=f(a1+h),2）比较y1和y2；,a）如果y1y2，向右前进，加大步长h=2h0，转（3）向前；b）如果y1y3，加大步长h=2h，a1=a2,a2=a3,转（3）继续探测；b）如果y20.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,概述一维搜索问题是在某一确定区间内寻求一元函数的极小点的位置，在某些情况下，如果没有函数表达式，但能够给出若干试验点处的函数值，就可以根据这些点处的函数值，利用插值法建立函数的某种近似表达式，进而求出函数的极小点，并用它作为原来函数极小点的近似值。这种方法称作插值法，又称作函数逼近法。,3.5一维搜索的二次插值法,试探法（如黄金分割法）与插值法的比较：,不同点：表现在试验点（插入点）位置的确定方法不同。,多项式是函数逼近的一种常用工具。在搜索区间内可以利用若干试验点处的函数值来构造低次多项式，用它作为函数的近似表达式，并用这个多项式的极小点作为原函数极小点的近似。常用的插值多项式为二次多项式。牛顿法（切线法）利用一点的函数值、一阶导数值和二阶导数值来构造二次函数。二次插值法（抛物线法）利用三个点的函数值形成一个抛物线来构造二次函数。,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用二次插值法求函数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缩短率确定的。插值法中，试验点位置是按函数值近似分布的极小点确定的。试探法仅仅利用了试验点函数值大小的比较，而