三章一维优化方法.ppt
第三章 一维优化方法,初始搜索区间的确定一维搜索的最优化方法1、格点法2、黄金分割法3、二次插值法教学要求：1、掌握初始搜索区间的确定方法 2、掌握黄金分割法 3、掌握二次插值法,一维搜索方法概述,在优化设计的迭代运算中，在搜索方向s(k)上寻求最优步长(k)的方法称一维搜索法。实际上一维搜索法就是一元函数极小化的数值迭代算法，其求解过程称为一维搜索。一维搜索法是非线性优化方法的基本算法，多元函数的迭代算法都可以归结为在一系列逐步产生的下降方向上的一维搜索。例如：下图所示的二维优化的例子。二维优化问题的一维搜索方向s(k)是由具体的优化方法决定的，迭代公式 x(k+1)=x(k)+(k)s(k)因此，二维优化问题minF(x1,x2)就可以表示为一维优化问题min f(),x2,x1,o,(k)S(k),S(k),x(k+1),x(k),x*,F(x(k),F(x(k+1),二维优化问题中的一维搜索,3.1 初始搜索区间的确定,在一维搜索时，需要确定一个搜索区间a,b，此区间必须包含函数的极小点 x*，因此搜索区间必须是单峰区间，即该区间内的函数值呈现“高-低-高”的趋势。如图所示，通过将搜索区间a,b逐渐缩小，直至足够小，就可以得到近似最优点。,在一维搜索时，需要确定一个搜索区间a,b，此区间必须包含函数的极小点 x*，因此搜索区间必须是单峰区间，即该区间内的函数值呈现“高-低-高”的趋势。如图所示，通过将搜索区间a,b逐渐缩小，直至足够小，就可以得到近似最优点。,f(x),f(x),x,x,a,a,x*,x*,b,b,确定初始搜索区间的进退法,一、试探搜索极小点位置 设函数为 y=f(x),给定初始点为x1，选定的初始步长为h0。由初始点x1沿x轴正向取x2点，x2=x1+h0，计算x1、x2的函数值y1、y2，比较y1、y2 的大小，则极小点的位置有如图所示两种情况 1、若y2 y1，则极小点位于x1点左方，应反向后退搜索。,确定初始搜索区间的进退法,x1,x1,x2,x2,x3,x3,h0,2h0,h0,2h0,前进搜索,后退搜索,注意：x1x2互换后再取x3,二、前进搜索 令h h0，并使步长加倍h2h，取得前进方向的x3点，x3 x2+h=x2+2h0，其函数值y3与y2比较有如下情况：1、若y2 y2y3，则继续前进搜索，各点变换如下：x1 x2，y1 y2 x2 x3，y2 y3 然后步长加倍，取新点x3，重复上述比较y2与y3的大小，直至出现y1 y2y3时，令a x1，b x3，从而构成搜索区间a,b,三、后退搜索 令h-h0，并将x1与 x2对调，使步长加倍h2h，取得x3点，x3 x2+h，其函数值y3与y2比较有如下情况：1、若y2 y2y3，则继续后退搜索，各点变换如下：x1 x2，y1 y2 x2 x3，y2 y3 然后步长加倍，取新点x3，重复上述比较y2与y3的大小，直至出现y1 y2y3时，令a x3，b x1，从而构成搜索区间a,b,四、进退法确定搜索区间的流程图,例题3.1：试用进退法确定函数 的一维优化搜索区间a，b，设初始点x1=0，初始步长h0=1。,解：计算过程如下:,hh0=1x2x1+h=1y1=f(x1)=9,y2=f(x2)=4,由于用y2y1，作前进搜索：,h2h=2 x3x2+h=3 y3=f(x3)=0,比较y2，y3有y2y3，再做前进搜索,x1x2=1,y1y2=4x2x3=3,y2y3=0h2h=4x3x2+h=7,y3=F(x3)=16,在比较y2，y3有y2y3，则取,ax1=1，bx3=7搜索区间a，b为1，7搜索过程见下图,3.2 一维搜索的最优化方法,在确定了搜索区间以后，一维优化的任务是采用某种方法将此区间逐步缩小，在满足收敛精度或迭代精度的情况下，使其达到包含极小点的一个很小的邻域，以取得一个近似的最优点。一维优化的方法有如下几种：1、格点法 2、黄金分割法 3、二次插值法,3.2.1 格点法,一、格点法的原理 设一维函数为f(x)，搜索区间为a,b，一维收敛精度为。在区间a,b的内部取n个等分点：x1,x2,xn。区间被分为n+1等分，各分点坐标为 对应各点的函数值为y1,y2,yn。比较其大小，取最小者ym=minyk,k=1,2,n，则在区间xm-1,xm+1内必包含极小点，取xm-1,xm+1为缩短后新区间，若新区间满足收敛条件 xm+1-x m-1，则最优解为x*xm，y*ym 若不能满足精度要求，把当前区间作为初始搜索区间，重复上述步骤直至满足精度为止,格点法,新区间,y1,ym-1,ym,ym+1,yn,x1,a,xm-1,xm,xm+1,xn,b,格点法的区间缩短,格点法流程图,+,-,-,+,+,-,例题3.2：用格点法求一维目标函数 的最优解。给定搜索区间a，b为1，2.2，迭代精度=0.2，内分点数n=4。,解：计算区间端点的函数值,f(a)=2 f(b)=2.96,由上式确定四个内分点的位置，并计算其函数值，计算结果见下页表。其中最小的函数值为：,对应的点,新区间的端点为：,新区间的长度为：，不满足精度要求。,再做第二次区间缩短后，得到区间端点为：,新区间长度，满足迭代精度。,最优解为：,3.2.2 黄金分割法,黄金分割法适用于a,b区间上的任何单峰函数求极小值问题。对函数除要求单峰外不作其它要求，甚至可以不连续。因此，这种方法的适应面相当广。一、黄金分割法的原理在搜索区间a,b内适当插入两点x1,x2，x1x2,且在区间内对称位置，计算其函数值。y1=f(x1)y2=f(x2)1)若y1y2则极小点必在区间a,x2内，令b=x2，新区间为a，x22)若y1y2则极小点必在区间x1,b内，令a=x1，新区间为x1，b经过函数值比较，区间缩短一次。新区间只保留x1，x2中的一个。,黄金分割法内分点选区的原则之一是要对称的、并采取每次区间缩短率都是相等的。设原区间长度为l如图3.8所示，保留区间长度为l，区间缩短率为。进行第二次缩短时，新点为x3,设y1f(x3)则新区间为a,x1为保持相同的区间缩短率，应有（1-）/=故：1-=2 2+-1=0由此可得：=0.618 黄金分割法可使相邻两次搜索区间都具有相同的缩短率0.618。x1=a+0.382(b-a)x2=a+0.618(b-a),二、黄金分割法的搜索过程 1、给出初始搜索区间a,b及收敛精度。2、按坐标点计算公式计算，并计算相应的函数值 3、缩短搜索区间 4、检查是否满足收敛条件 5、若满足收敛条件，则取最后两点的平均值作为极小点的近似解。,三、黄金分割法流程图,+,-,+,-,例题3.3 试用黄金分割法求目标函数 的最优解。给定初始区间1，7，收敛精度=0.4。,解：第一次区间缩短计算过程：,计算两内点及对应函数值：,X1=a+0.382(b-a)=3.292 y1=f(x1)=0.085264X2=a+0.618(b-a)=4.708 y2=f(x2)=2.917264,作数值比较，可见y1y2,再做置换：,用终止准则判断,为第二次区间缩短做准备，做置换：,x2x1=3.292，y2y1=0.085264,各次缩短区间的计算数据见下页表。第六次区间缩短的端点,满足精度要求，终止计算。取最优解为,黄金分割法例题计算数据,3.3.3 二次插值法,一、插值法概念 假定我们给定的问题是在某一确定区间内寻求函数的极小点的位置，但是没有函数表达式，只有若干试验点处的函数值。我们可以根据这些函数值，构成一个与原目标函数相接近的低次插值多项式，用该多项式的最优解作为原函数最优解的近似解，这种方法是用低次插值多项式逐步逼近原目标函数的极小点的近似求解方法，称为插值方法或函数逼近法。二、插值法与试探法的异同点 相同点：都是利用区间消去法原理将初始搜索区间不断缩短，从而求得极小点的数值近似解。,不同点：试验点位置的确定方法不同。在试探法中试验点的位置是由某种给定的规律确定的，并未考虑函数值的分布。例如：黄金分割法是按照等比例0.618缩短率确定的。插值法中，试验点的位置是按函数值近似分布的极小点确定的。试探法仅仅利用了试验点函数值进行大小的比较，而插值法还要利用函数值本身或其导数信息。所以，当函数具有较好的解析性质时，插值方法比试探方法效果更好。,三、二次插值法的概念 利用原目标函数上的三个插值点，构成一个二次插值多项式，用该多项式的最优解作为原函数最优解的近似解，逐步逼近原目标函数的极小点，称为二次插值方法或抛物线法。四、二次插值函数的构成 设一维目标函数的搜索区间为a,b，取三点x1、x2、x3，其中x1、x3取区间的端点，即 x1a，x3 b 而x2为区间内的一个点，开始可以取区间的中点，即 x2=0.5(x1+x3),计算函数值f 1=f(x1)、f 2=f(x2)、f 3=f(x3)过函数曲线上的三点P1(x1,f 1)、P2(x2,f 2)、P3(x3,f 3)作二次插值多项式 p(x)=Ax2+Bx+C 它应满足条件 p(x1)=Ax12+Bx1+C 1=f 1 p(x2)=Ax22+Bx2+C=f 2 p(x3)=Ax32+Bx3+C=f 3 解方程组，得待定系数A、B、C分别为,于是函数p(x)就是一个确定的二次多项式，称二次插值函数 如图所示，虚线部分即为二次插值函数,令插值函数p(x)的一阶导数为0，即 p(x)=2ax+b=0 得p(x)极小点为 xp*=B/2 A 代入A、B得,令,得,注意：若c2=0，则 即 说明三个插值点位于同一条直线上，因此说明区间已经很小，插值点非常接近，故可将x2、f2输出作为最优解。,五、区间的缩短 为求得满足收敛精度要求的最优点，往往需要多次进行插值计算，搜索区间不断缩短，使xp*不断逼近原函数的极小点x*。第一次区间缩短的方法是，计算xp*点的函数值fp*，比较fp*与f2，取其中较小者所对应的点作为新的x2，以此点的左右两邻点作为新的x1和x3，得到缩短后的新区间x1，x3，如图所示。,新区间,x1=a,x2,x3=b,x*,xP*,x1,x2,x3,以后，根据fp*相对于x2的位置，并比较fp*与 f2，区间的缩短可以分为以下四种情况。,x1,x2,x3,xP*,f2,fP*,x1,x1,x1,x2,x2,x2,xP*,xP*,xP*,x3,x3,x3,f2,f2,f2,fP*,fP*,fP*,b,a,c,d,入口,xp*x2?,f2fP*?,f2fP*?,x1 xp*f1 fP*,x3 x2 f3 f2x2 xp*f2 fP*,x1 x2 f1 f2x2 xp*f2 fP*,x3 xp*f3 fP*,出口,Y,Y,Y,N,N,N,a,b,c,d,区间缩短流程图,六、终止准则 当满足给定精度时，计算终止，并令 x*xP*(k),f*f(x*),七、二次插值算法流程图,+,-,-,-,-,+,+,+,例题3.4 试用二次插值法求函数 的最优解，初始区间为1，7，精度=0.01,解：,(1)初始插值节点,x1=a=1,f1=f(x1)=4x2=0.5(a+b)=4,f2=f(x2)=1x3=b=7,f3=f(x3)=16,(2)计算差值函数的极小点与极小值,(3)缩短区间,因有，故有,x1=1,f1=4x3x2=4,f3=1x2=3,f2=0,(4)重复步骤(2),c1=-1,c2=1,(5)检查终止条件,获得最优解,例题3.5 用二次差值法求非二次函数 的最优解。初始区间端点为a=-0.5,b=2.5精度要求=0.005,解：,(1)初始差值结点,x1=a=-0.5,f1=f(x1)=-0.851279x2=0.5(a+b)=1,f2=f(x2)=-2.610944x3=b=2.5,f3=f(x3)=15.615452,(2)计算 与,c1=5.488910,c2=4.441347,(3)缩短区间,因有，故取,x1=-0.5,f1=-0.851279x2=0.382067,f2=-20927209x3=1,f3=-2.610944,(4)对新区间重复步骤二,c1=-1.17311,c2=1.910196,(5)检查终止条件,未满足终止条件，返回步骤（3）,计算结果表,经五次差值计算后，得,得最优解,/搜索区间的确定void find_ab(double x0,double h0,double*a,double*b)double x1,y1,x2,y2,x3,y3,h;h=h0;x1=x0;y1=f(x1);x2=x1+h;y2=f(x2);if(y2y1)h=-h0;x3=x1;x1=x2;x2=x3;y3=y1;y1=y2;y2=y3;for(;)h=2*h;x3=x2+h;y3=f(x3);if(y2y3)break;x1=x2;y1=y2;x2=x3;y2=y3;if(h0)*a=x3;*b=x1;else*a=x1;*b=x3;,一维优化方法的比较,格点法的结构及程序很简单,但效率偏低:黄金分割法的结构简单，使用可靠，但效率也不高，格点法和黄金分割法适于低维优化问题中的一维搜索。二次插值法在同样搜索次数下，其计算精度更高，但程序略复杂，可靠性差些，对高维数的优化问题更适宜，经过某些技术处理，方法的可靠度可大为提高。,
