1、第四章 一维搜索方法,概述搜索区间的确定一维搜索的试探方法黄金分割法一维搜索的插值方法牛顿法(切线法)二次插值法,第四章 一维搜索方法,概述,直接搜索法更适合于工程实践对于单个变量（一维问题）的直接搜索，通常称为一维搜索或线性搜索多维问题转化为一维问题求解,第四章 一维搜索方法,多维和一维间的转换,多维目标函数的极值问题，通常采用数值迭代的方法求解每一步的格式都是从某一定点xk出发沿着某一使函数值下降的规定方向dk，找出在此方向的极值点xk+1。在任何一次迭代计算过程中，当起步点和方向确定之后，就把求多维问题的目标函数的极小值这个多维问题，转变成求一个变量即步长ak的最优值的一维问题沿着规定方
2、向求ak的最优值以使f(xk+akdk)得到极小值的过程，就是一维搜索或一维最优化问题，而ak则称为一维搜索的最优化步长多维问题就转换为一系列的一维搜索问题,第四章 一维搜索方法,求解一元函数 的极小点，可采用解析解法和数值解法。解析解法：,第四章 一维搜索方法,第四章 一维搜索方法,a2,第四章 一维搜索方法,第四章 一维搜索方法,第四章 一维搜索方法,三、一维搜索方法的分类,区间内插入点的位置，可以用不同的方法来确定。这样就形成了不同的一维搜索方法。可将一维搜索方法分成两大类。一类称作试探法。这类方法是按某种给定的规律来确定区间内插入点的位置。此点位置的确定仅仅按照区间缩短如何加快，而不顾
3、及函数值的分布关系。属于试探法一维搜索的有黄金分割法，裴波纳契(Fibonacci)法等。另一类一维搜索方法称作插值法或函数逼近法。这类方法是根据某些点处的某些信息，如函数值、一阶导数、二阶导数等，构造一个插值函插值法、三次插值法等。,第四章 一维搜索方法,一维搜索方法,第一是初始点的x0选取，x0应尽量选择靠近极值点，这样就能较快找到极值点第二是搜索方向的dk确定。从xk出发沿什么方向很快找到f(x)的极小点？以不同的原则选取dk就构成了优化方法中各种不同的方法第三在确定了搜索方向dk后，关键的问题是如何进行沿dk方向的一维搜索,第四章 一维搜索方法,一维搜索方法,采用数值解法代替解析解法第
4、一步是确定搜索区间，即最优步长ak所在的区间a,b，搜索区间应为单峰区间，区间内目标函数应只有一个极小值第二步是在此区间内求最优步长ak，使目标函数f(xk+ak)达到极小，即通过某种原理不断缩小搜索区间，从而获得最优步长a*的数值近似解。,第四章 一维搜索方法,进退法确定搜索区间,理论依据：由单峰函数的性质，在极小点左边的函数值应随着步长的增加一直下降，而在极小点右边的函数值则应严格上升。给定初始点t0及初始步长h前进运算搜索区间可确定为,将步长增加二倍,否则步长加倍重复上述运算,否则转下页,第四章 一维搜索方法,进退法确定搜索区间,后退运算搜索区间可确定为,将步长a0缩短为a0/4，以a0
5、/4为步长反方向搜索,否则步长加倍继续后退运算,第四章 一维搜索方法,一维搜索方法的分类,为了每次缩短区间，只需要在区间内再插入一点并计算其函数值。然而，对于插入点的位置，是可以用不同的方法来确定的。一类称作试探法：区间内插入点位置的确定仅仅按照区间缩短如何加快，而不顾及函数值的分布关系黄金分割法、裴波纳契（Fibonacci）等一类称作插值法或函数逼近法：构造一个插值函数来逼近原来函数，用插值函数的极小点作为区间的插入点牛顿法、二次插值法等,第四章 一维搜索方法,一维搜索的试探方法黄金分割法,是最常用的一维搜索试探方法，又称作0.618法适用于区间上的任何单谷函数求极小值问题对函数除要求“单
6、谷”外不作其他要求，甚至可以不连续基本思路：在搜索区间内适当插入两点，并计算其函数值。将区间分成三段。应用函数的单谷性质，通过函数值大小的比较，删去其中一段，使搜索区间得以缩短。然后再在保留下来的区间上作同样的处置，如此迭代下去，使搜索区间无限缩小，从而得到极小点的数值近似解。,第四章 一维搜索方法,黄金分割法,黄金分割法要求插入点1、2的位置相对于原区间a,b的两端点具有对称性，即黄金分割法还要求在保留下来的区间内再插入一点所形成的区间新三段，与原来区间的三段具有相同的比例分布,第四章 一维搜索方法,黄金分割法的搜索过程,给出初始搜索区间a,b及收敛精度，将赋以0.618按前页中坐标点比例公
7、式计算1和2，并计算其对应的函数值f(1)和f(2)。比较函数值，利用进退法缩短搜索区间检查区间是否缩短到足够小和函数值是否收敛到足够近，如果条件不满足则返回到步骤如果条件满足则取最后两试验点的平均值作为极小点的数值近似值,第四章 一维搜索方法,+,a+,第四章 一维搜索方法,黄金分割法程序框图,给定 a,b,0.618,a1=b-(b-a);y1=f(a1);a2=a+(b-a);y2=f(a2);,y1y2,a=a1;a1=a2;y1=y2;a2=a+(b-a);y2=f(a2),b=a2;a2=a1;y2=y1;a1=b-(b-a);y1=f(a1),a*=(a+b)/2,结束,是,否,
8、是,否,第四章 一维搜索方法,黄金分割法已知：F(x)=x4-4x3-6x2-16x+4,求极小值，极小值点，区间，迭代次数？用进退法确定区间，用黄金分割法求极值。#include#include#define e 0.001#define tt 0.01float f(double x)float y=pow(x,4)-4*pow(x,3)-6*pow(x,2)-16*x+4;return(y);finding(float*p1,float*p2)float x1=0,x2,x3,t,f1,f2,f3,h=tt;int n=0;x2=x1+h;f1=f(x1);f2=f(x2);if(f2f
9、1)h=-h;t=x2;x2=x1;x1=t;,第四章 一维搜索方法,do x3=x2+h;h=2*h;f3=f(x3);n=n+1;while(f3x3)t=x1;x1=x3;x3=t;*p1=x1;*p2=x3;return(n);gold(float*p)float a,b,x1,x2,f1,f2;int n=0;finding(printf(n The nunmber 2 is%d.,n2),第四章 一维搜索方法,例题：黄金分割法（一）,对函数f(x)x2+2x，给定搜索区间-3x5时，用黄金分割法求极小点x*,此时a=-3，b=5，按公式计算两插入点,计算两插入点的函数值,消去区间a
10、2,b，新的搜索区间a,b的端点a=-3不变，而b=a2=1.944,第四章 一维搜索方法,例题：黄金分割法（二）,依次重复黄金分割法的迭代过程，前五次迭代的结果假定，经过5次迭代后已满足收敛精度要求，则得该问题的精确解为,第四章 一维搜索方法,一维搜索的插值方法,假定我们的问题是在某一确定区间内寻求函数的极小点位置，虽然没有函数表达式，但能够给出若干试验点处的函数值。我们可以根据这些点处的函数值，利用插值方法建立函数的某种近似表达式，进而求出函数的极小点，并用它作为原来函数极小点的近似值。这种方法称作插值法，又称作函数逼近法。,第四章 一维搜索方法,插值方法与试探方法的对比,相同之处在于都是
11、利用区间消去法原理将初始搜索区间不断缩短，从而求得极小点的数值近似解。不同之处在于试验点位置的确定方法不同。在试探法中试验点位置是由某种给定的规律确定。在插值法中试验点位置是按函数值近似分布的极小点确定。试探法仅仅利用了试验点函数值的大小的比较，而插值法还要利用函数值的本身或者其导数信息。由于试探法仅对试验点数值的大小进行比较，而函数值本身的特性没有得到充分利用插值法则是利用函数在已知试验点的值（或导数值）来确定新试验点的位置。当函数具有比较好的性质时(例如连续可微性)，插值方法比试探法效果更好。,第四章 一维搜索方法,一维搜索的插值方法,多项式是函数逼近的一种常用工具。在搜索区间内我们可以利
12、用若干试验点处的函数值来构造低次多项式，用它作为函数的近似表达式，并用这个多项式的极小点作为原函数极小点的近似。常用的插值多项式为二次多项式。牛顿法（切线法）：利用一点的函数值、一阶导数值和二阶导数值来构造此二次函数抛物线法（二次插值法）：它利用三个点的函数值形成一个抛物线来构造此二次函数,第四章 一维搜索方法,牛顿法,对于一维搜索函数，假定已给出极小点的一个较好的近似点a0，因为一个连续可微的函数在极小点附近与一个二次函数很接近，所以可以在a0点附近用一个二次函数来逼近函数，即在点a0将f(a)进行泰勒展开，并保留到二次项，有然后以二次函数的极小点作为极小点的一个新近似点，根据极值必要条件
13、依此继续下去，可得牛顿法迭代公式,第四章 一维搜索方法,第四章 一维搜索方法,牛顿法的计算步骤,给定初始点a0，控制误差，令k=0计算f(x)在ak点的一阶和二阶导数利用牛顿法迭代公式求ak+1若|ak+1-ak|，则求得近似解a*=ak+1，停止计算，否则作第步令k=k+1，然后转第步,第四章 一维搜索方法,牛顿法,最大优点是收敛速度快缺点每一点处都要计算函数的导数和二阶导数，因而增加了每次迭代的工作量用数值微分代替二阶导数时，舍入误差会影响牛顿法的收敛速度，当二阶导数很小时问题更严重牛顿法要求初始点选得比较好，即不能离极小点太远，否则在可能使极小化序列发散或收敛到非极小点,第四章 一维搜索
14、方法,上机实验,进退法确定搜索区间上机编程黄金分割法上机编程二次插值法上机编程汽车转向梯形优化设计,第四章 一维搜索方法,二次插值法（一）,又称抛物线法。利用y=f(x)在单谷区间中的三点x1f(x2)f(x3)，作出如下的二次插值多项式多项式的极值点可以从极值的必要条件求得,第四章 一维搜索方法,二次插值法（二）P(x)的系数确定与极小点的计算,ap=1/2(a1+a3-c1/c2),第四章 一维搜索方法,二次插值法（三）缩短搜索区间,(1)如果搜索区间足够小，则可用P(x)的极小点x4作为f(x)的极小值x*的近似解(2)否则，必须缩短搜索区间（利用单谷函数的性质）重复进行二次插值法(1)
15、当x2f(x4)则取x2,x4,x3。(2)当x2x4时，如果f(x2)f(x4)则取x1,x4,x2。,第四章 一维搜索方法,第四章 一维搜索方法,二次插值法（四）计算步骤,(1)确定搜索区间x1,x2,x3，给定计算精度0(2)计算f(xk)，置fk=f(xk)，k=1,2,3(3)按公式计算x4，并计算f4=f(x4)(4)检验|x4-x2|否。如果满足，则停止计算，取x*=x4，否则转(5)(5)如果x2x4，转(6)，否则当f2f4时，x1=x4，f1=f4，转(3)；当f2f4时，x3=x2，f3=f2，x2=x4，f2=f4，转(3)(6)当x2x4，当f2f4时，x3=x4，f
16、3=f4，转(3)；当f2f4时，x1=x2，f1=f2，x2=x4，f2=f4，转(3),第四章 一维搜索方法,二次插值法（四）计算机流程图,给定x1,x2,x3,计算f1,f2,f3,c1=(y2-y1)/(x3-x1);C2=(y2-y1)/x2-x1)-c1)/(x2-x3),x4=0.5*(x1+x3-c1/c2);f4=f(x4),|(f4-f2)/f2|,x*=x4,x2x4,f2f4,x3=x4;f3=f4,x1=x2;f1=f2;x2=x4f2=f4,f2f4,x1=x4;f1=f4,x3=x2;f3=f2;x2=x4f2=f4,结束,是,否,是,是,是,否,否,否,第四章 一维搜索方法,例题：牛顿法,给定f(x)=x4-4x3-6x2-16x+4，用牛顿法求其最小点,首先求出函数的一阶、二阶导函数,给定起始点a0=3，控制误差0.001,第四章 一维搜索方法,例题：二次插值法,用二次插值法示f(x)=sin(x)在4x5上的最小值,此时的搜索区间为4,5,迭代两次的计算过程及结果见下表,
