三章一维化方法

《三章一维化方法》由会员分享，可在线阅读，更多相关《三章一维化方法（48页珍藏版）》请在金锄头文库上搜索。

1、第三章第三章第三章第三章 一维优化方法一维优化方法一维优化方法一维优化方法初始搜索区间的确定初始搜索区间的确定一维搜索的最优化方法一维搜索的最优化方法1 1 1 1、格点法、格点法、格点法、格点法2 2 2 2、黄金分割法、黄金分割法、黄金分割法、黄金分割法3 3 3 3、二次插值法、二次插值法、二次插值法、二次插值法教学要求：教学要求： 1 1、掌握初始搜索区间的确定方法、掌握初始搜索区间的确定方法 2 2、掌握黄金分割法、掌握黄金分割法 3 3、掌握二次插值法、掌握二次插值法一维搜索方法概述一维搜索方法概述一维搜索方法概述一维搜索方法概述 在优化设计的迭代运算中，在搜索方向在优化设计的迭代

2、运算中，在搜索方向s s(k(k) )上寻求最优上寻求最优步长步长 (k)(k) 的方法称一维搜索法。实际上一维搜索法就是一的方法称一维搜索法。实际上一维搜索法就是一元函数极小化的数值迭代算法，其求解过程称为一维搜索。元函数极小化的数值迭代算法，其求解过程称为一维搜索。 一维搜索法是非线性优化方法的基本算法，多元函数一维搜索法是非线性优化方法的基本算法，多元函数的迭代算法都可以归结为在一系列逐步产生的下降方向上的迭代算法都可以归结为在一系列逐步产生的下降方向上的一维搜索。的一维搜索。例如例如例如例如：下图所示的二维优化的例子。：下图所示的二维优化的例子。 二维优化问题的一维搜索方向二维优化问题

3、的一维搜索方向s s(k(k) )是由具体的优化方法是由具体的优化方法决定的，迭代公式决定的，迭代公式 x x(k+1)(k+1)= =x x(k)(k)+ + (k)(k)s s(k(k) ) 因此，二维优化问题因此，二维优化问题minminF F(x(x1 1, x, x2 2) )就可以表示为一维优化就可以表示为一维优化问题问题min min f( f( ) )x2x1o (k)S(k)S(k)x(k+1)x(k)x*F(x(k)F(x(k+1)二维优化问题中的一维搜索二维优化问题中的一维搜索二维优化问题中的一维搜索二维优化问题中的一维搜索3.1 3.1 初始搜索区间的确定初始搜索区间的

4、确定初始搜索区间的确定初始搜索区间的确定 在一维搜索时，需要确定一个搜索区间a,b，此区间必须包含函数的极小点 x*，因此搜索区间必须是单峰区间单峰区间，即该区间内的函数值呈现“高-低-高”的趋势。如图所示，通过将搜索区间a,b逐渐缩小，直至足够小，就可以得到近似最优点。 在一维搜索时，需要确定一个搜索区间在一维搜索时，需要确定一个搜索区间 a,ba,b，此此区间必须包含函数的极小点区间必须包含函数的极小点 x x* *，因此搜索区间必须是因此搜索区间必须是单峰区间单峰区间单峰区间单峰区间，即该区间内的函数值呈现，即该区间内的函数值呈现“ “高高- -低低- -高高” ”的的趋势。如图所示，通

5、过将搜索区间趋势。如图所示，通过将搜索区间 a,ba,b逐渐缩小，直逐渐缩小，直至足够小，就可以得到近似最优点。至足够小，就可以得到近似最优点。f(x)f(x)xxaax*x*bb确定初始搜索区间的进退法确定初始搜索区间的进退法确定初始搜索区间的进退法确定初始搜索区间的进退法一、试探搜索极小点位置一、试探搜索极小点位置 设函数为设函数为 y=y=f(xf(x) ) , ,给定初始点为给定初始点为x x1 1 ，选定的初始步长选定的初始步长为为h h0 0。 由初始点由初始点x x1 1沿沿x x轴正向取轴正向取x x2 2点，点，x x2 2=x=x1 1+h+h0 0，计算计算x x1 1

6、、x x2 2的函数值的函数值y y1 1 、y y2 2 ，比较，比较y y1 1 、y y2 2 的大小，则极小点的位置的大小，则极小点的位置有如图所示两种情况有如图所示两种情况 1 1、若、若y y2 2 y y1 1 ，则极小点位于则极小点位于x x1 1点左方，应反向后退搜点左方，应反向后退搜索。索。确定初始搜索区间的进退法确定初始搜索区间的进退法确定初始搜索区间的进退法确定初始搜索区间的进退法x1x1x2x2x3x3h02h0h02h0前进搜索前进搜索后退搜索后退搜索注意：注意：x1x2互换后互换后再取再取x3二、前进搜索二、前进搜索二、前进搜索二、前进搜索 令令h h h h0

7、0，并使步长加倍并使步长加倍h h2 2h h，取得前进方向的取得前进方向的x x3 3点，点，x x3 3 x x2 2+h=x+h=x2 2+2h+2h0 0，其函数值其函数值y y3 3与与y y2 2比较比较有如下情况：有如下情况： 1 1、若若y y2 2 y y2 2 y y3 3，则继续前进搜索，各点变换如下：则继续前进搜索，各点变换如下： x x1 1 x x2 2 ，y y1 1 y y2 2 x x2 2 x x3 3 ，y y2 2 y y3 3 然后然后步长加倍，取新点步长加倍，取新点x x3 3，重复上述比较重复上述比较y y2 2与与y y3 3的大的大小，直至出现

8、小，直至出现y y1 1 y y2 2 y y3 3时，令时，令a a x x1 1，b b x x3 3，从而构成从而构成搜索区间搜索区间 a,ba,b 三三、后退搜索、后退搜索、后退搜索、后退搜索 令令h h - -h h0 0，并将并将x x1 1与与 x x2 2对调，对调，使步长加倍使步长加倍h h2 2h h，取得取得x x3 3点，点，x x3 3 x x2 2+h+h，其函数值其函数值y y3 3与与y y2 2比较比较有如下情况：有如下情况： 1 1、若、若y y2 2 y y2 2 y y3 3，则继续后退搜索，各点变换如下：则继续后退搜索，各点变换如下： x x1 1 x

9、 x2 2 ，y y1 1 y y2 2 x x2 2 x x3 3 ，y y2 2 y y3 3 然后然后步长加倍，取新点步长加倍，取新点x x3 3，重复上述比较重复上述比较y y2 2与与y y3 3的大的大小，直至出现小，直至出现y y1 1 y y2 2 y y3 3时，令时，令a a x x3 3，b b x x1 1，从而构从而构成搜索区间成搜索区间 a,ba,b 四四四四、进进进进退退退退法法法法确确确确定定定定搜搜搜搜索索索索区区区区间间间间的的的的流流流流程程程程图图图图例题例题3.13.1：试用进退法：试用进退法确定函数确定函数 的一维优化搜索区间的一维优化搜索区间aa，

10、bb，设初始点设初始点x x1 1=0=0，初始步长初始步长h h0 0=1=1。解：解：计算过程如下计算过程如下: :hhhh0 0=1=1x x2 2xx1 1+h=1+h=1y y1 1=f(x=f(x1 1)=9 ,y)=9 ,y2 2=f(x=f(x2 2)=4)=4 由于用由于用y y2 2y y1 1，作前进搜索，作前进搜索：h2h=2 h2h=2 x x3 3xx2 2+h=3 y+h=3 y3 3=f(x=f(x3 3)=0)=0 比较比较y y2 2，y y3 3有有y y2 2y y3 3，再做前进搜索，再做前进搜索x x1 1xx2 2=1, y=1, y1 1yy2

11、2=4=4x x2 2xx3 3=3, y=3, y2 2yy3 3=0=0h2h=4h2h=4x x3 3xx2 2+h=7, y+h=7, y3 3=F(x=F(x3 3)=16)=16在比较y2，y3有y2y3，则取axax1 1=1=1，bxbx3 3=7=7搜索区间搜索区间a a，b b为为11，77搜索过程见下图搜索过程见下图3.2 3.2 一维搜索的最优化方法一维搜索的最优化方法一维搜索的最优化方法一维搜索的最优化方法 在确定了搜索区间以后，一维优化的任务是采用某在确定了搜索区间以后，一维优化的任务是采用某种方法将此区间逐步缩小，在满足收敛精度或迭代精度种方法将此区间逐步缩小，在

12、满足收敛精度或迭代精度的情况下，使其达到包含极小点的一个很小的邻域，以的情况下，使其达到包含极小点的一个很小的邻域，以取得一个近似的最优点。取得一个近似的最优点。 一维优化的方法有如下几种一维优化的方法有如下几种一维优化的方法有如下几种一维优化的方法有如下几种： 1 1、格点法、格点法 2 2、黄金分割法、黄金分割法 3 3、二次插值法、二次插值法3.2.1 3.2.1 格点法格点法格点法格点法 一、格点法的原理一、格点法的原理一、格点法的原理一、格点法的原理 设一维函数为f(x)，搜索区间为a,b，一维收敛精度为。 在区间a,b的内部取n个等分点： x1 , x2 , , xn。区间被分为n

13、+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 若不能满足精度要求，把当前区间作为初始搜索区间，重复上述步骤直至满足精度为止格点法格点法格点法格点法 新区间新区间y1ym-1ymym+1ynx1axm-1xmxm+1xnb格点法的区间缩短格格点点法法流流程程图图+-+-例题例题3.23.2：用格点法求一维目标函数：用格点法求一维目标函数 的最的

14、最优解。给定搜索区间优解。给定搜索区间aa，bb为为11，2.22.2，迭代精度，迭代精度 =0.2=0.2，内分点数内分点数n=4n=4。解：计算区间端点的函数值解：计算区间端点的函数值f(af(a)=2 )=2 f(bf(b)=2.96)=2.96由上式确定四个内分点的位置，并计算其函数值，计算结果由上式确定四个内分点的位置，并计算其函数值，计算结果见下页表。其中最小的函数值为：见下页表。其中最小的函数值为：对应的点对应的点区间缩短次数xkykxmabb-a第一次1.241.481.721.961.27041.00161.19361.8461.481.241.720.48第二次1.3361

15、.4321.5281.6241.1075841.0184961.0031361.0615041.5281.4321.6240.192新区间的端点为：新区间的端点为：新区间的长度为：新区间的长度为： ，不满足精度要求。，不满足精度要求。再做第二次区间缩短后，得到区间端点为：再做第二次区间缩短后，得到区间端点为：新区间长度新区间长度 ，满足迭代精度。，满足迭代精度。最优解为：最优解为： 3.2.2 3.2.2 黄金分割法黄金分割法黄金分割法黄金分割法 黄金分割法适用于黄金分割法适用于 a,ba,b 区间上的任何单峰函数求极区间上的任何单峰函数求极小值问题。对函数除要求单峰外不作其它要求，甚至可以小

16、值问题。对函数除要求单峰外不作其它要求，甚至可以不连续。因此，这种方法的适应面相当广。不连续。因此，这种方法的适应面相当广。一、黄金分割法的原理一、黄金分割法的原理一、黄金分割法的原理一、黄金分割法的原理在搜索区间在搜索区间 a,ba,b 内适当插入两点内适当插入两点x x1 1,x,x2 2 ，x x1 1xx2 2, ,且在区间内且在区间内对称位置，对称位置，计算其函数值。计算其函数值。 y y1 1=f(x=f(x1 1) y) y2 2=f(x=f(x2 2) )1)1)若若y y1 1yy2 2则极小点必在区间则极小点必在区间a,xa,x2 2 内，令内，令b=xb=x2 2，新区间

17、为，新区间为aa，x x2 2 2)2)若若y y1 1 yf(xf(x3 3) )则则新区间为新区间为 a,xa,x1 1 为保持相同的区间缩短率，应有为保持相同的区间缩短率，应有 （1- 1- ）/ / = = 故：故：1- 1- = = 2 2 2 2 + + -1=0 -1=0由此可得：由此可得： =0.618 =0.618 黄金分割法可使相邻两次搜索区间都具有相同的缩短率黄金分割法可使相邻两次搜索区间都具有相同的缩短率黄金分割法可使相邻两次搜索区间都具有相同的缩短率黄金分割法可使相邻两次搜索区间都具有相同的缩短率0.6180.618。x x1 1=a+ =a+ 0.3820.382(

18、b-a)(b-a)x x2 2=a+ 0.618(b-a)=a+ 0.618(b-a)二、黄金分割法的搜索过程二、黄金分割法的搜索过程二、黄金分割法的搜索过程二、黄金分割法的搜索过程 1 1、给出初始搜索区间、给出初始搜索区间 a,ba,b 及收敛精度及收敛精度 。 2 2、按坐标点计算公式计算，并计算相应的函数值、按坐标点计算公式计算，并计算相应的函数值 3 3、缩短搜索区间、缩短搜索区间 4 4、检查是否满足收敛条件、检查是否满足收敛条件 5 5、若满足收敛条件，则取最后两点的平均值作为极、若满足收敛条件，则取最后两点的平均值作为极小点的近似解。小点的近似解。三三三三、黄黄黄黄金金金金分分

19、分分割割割割法法法法流流流流程程程程图图图图+-+-例题例题3.3 3.3 试用黄金分割法求目标函数试用黄金分割法求目标函数 的最的最优解。给定初始区间优解。给定初始区间11，77，收敛精度，收敛精度 =0.4=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 作数值比较，可见作数值比较，可见y y1 1yx2?f2fP*?f2y1) 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;一维优化方法的比较一维优化方法的比较格点法的结构及程序很简单,但效率偏低:黄金分割法的结构简单，使用可靠，但效率也不高，格点法和黄金分割法适于低维优化问题中的一维搜索。二次插值法在同样搜索次数下，其计算精度更高，但程序略复杂，可靠性差些，对高维数的优化问题更适宜，经过某些技术处理，方法的可靠度可大为提高。