第三章一维优化方法

1、 一维搜索方法概述一维搜索方法概述 初始搜索区间的确定初始搜索区间的确定 一维搜索的最优化方法一维搜索的最优化方法1、格点法、格点法2、黄金分割法、黄金分割法3、二次插值法、二次插值法教学要求：教学要求： 1、掌握初始搜索区间的确定方法、掌握初始搜索区间的确定方法 2、掌握黄金分割法、掌握黄金分割法 3、掌握二次插值法、掌握二次插值法 在优化设计的迭代运算中，在搜索方向在优化设计的迭代运算中，在搜索方向s(k)上寻求最优步长上寻求最优步长 (k) 的方法称一维搜索法。实的方法称一维搜索法。实际上一维搜索法就是一元函数极小化的数值迭际上一维搜索法就是一元函数极小化的数值迭代算法，其求解过程称为一

2、维搜索。代算法，其求解过程称为一维搜索。 一维搜索法是非线性优化方法的基本算一维搜索法是非线性优化方法的基本算法，多元函数的迭代算法都可以归结为在一系法，多元函数的迭代算法都可以归结为在一系列逐步产生的下降方向上的一维搜索。例如：列逐步产生的下降方向上的一维搜索。例如：下图所示的二维优化的例子。下图所示的二维优化的例子。 注意：二维优化问题的一维搜索方向注意：二维优化问题的一维搜索方向s(k)是由具体的优化方法决定的，迭代公式是由具体的优化方法决定的，迭代公式 x(k+1)=x(k)+ (k)s(k) 因此，二维优化问题因此，二维优化问题min f(x1, x2)就可以表就可以表示为一维优化问

3、题示为一维优化问题min f( )x2x1o (k)S(k)S(k)x(k+1)x(k)x*F(x(k)F(x(k+1)二维优化问题中的一维搜索二维优化问题中的一维搜索 在一维搜索时，需要确定一个搜索区间在一维搜索时，需要确定一个搜索区间a,b，此区间必须包含函数的极小点此区间必须包含函数的极小点 x*，因此搜索区间因此搜索区间必须是必须是单峰区间单峰区间，即该区间内的函数值呈现，即该区间内的函数值呈现“高高-低低-高高”的趋势。如图所示，通过将搜索的趋势。如图所示，通过将搜索区间区间a,b逐渐缩小，直至足够小，就可以得到近似逐渐缩小，直至足够小，就可以得到近似最优点。最优点。一、试探搜索极小

4、点位置一、试探搜索极小点位置 设函数为设函数为 y=f(x) ,给定初始点为给定初始点为x1 ，选定选定的初始步长为的初始步长为h0。 由初始点由初始点x1沿沿x轴正向取轴正向取x2点，点，x2=x1+h0，计算计算x1 、x2的函数值的函数值y1 、y2 ，比较，比较y1 、y2 的的大小，则极小点的位置有如图所示两种情况大小，则极小点的位置有如图所示两种情况 1、若、若y2 y1 ，则极小点位于则极小点位于x1点左方，点左方，应反向后退搜索。应反向后退搜索。二、前进搜索二、前进搜索 令令h h0，并使步长加倍并使步长加倍h2h，取得前取得前进方向的进方向的x3点，点，x3 x2+h=x2+

5、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比较比较有如下情况：有如下

6、情况： 1、若、若y2 y2y3，则继续后退搜索，各点变换则继续后退搜索，各点变换如下：如下： x1 x2 ，y1 y2 x2 x3 ，y2 y3然后然后步长加倍，取新点步长加倍，取新点x3，重复上述比较重复上述比较y2与与y3的大小，直至出现的大小，直至出现y1 y2f(x3)则则新区间为新区间为a,x1为保持相同的区间缩短率，应为保持相同的区间缩短率，应有（有（1- ）/ = 故：故：1- = 2 2 + -1=0由此可得：由此可得： =0.618黄金分割法可使相邻两次搜索区间都具有相同黄金分割法可使相邻两次搜索区间都具有相同的缩短率的缩短率0.618。x1=a+ 0.382(b-a)x2

7、=a+ 0.618(b-a)二、黄金分割法的搜索过程二、黄金分割法的搜索过程 1、给出初始搜索区间、给出初始搜索区间a,b及收敛精度及收敛精度 。 2、按坐标点计算公式计算，并计算相应的函数值、按坐标点计算公式计算，并计算相应的函数值 3、缩短搜索区间、缩短搜索区间 4、检查是否满足收敛条件、检查是否满足收敛条件 5、若满足收敛条件，则取最后两点的平均值作为、若满足收敛条件，则取最后两点的平均值作为极小点的近似解。极小点的近似解。三、黄金分割法的流程图三、黄金分割法的流程图四、例题四、例题 一、插值法概念一、插值法概念 假定我们给定的问题是在某一确定区间假定我们给定的问题是在某一确定区间内寻求

8、函数的极小点的位置，但是没有函数表内寻求函数的极小点的位置，但是没有函数表达式，只有若干试验点处的函数值。我们可以达式，只有若干试验点处的函数值。我们可以根据这些函数值，构成一个与原目标函数相接根据这些函数值，构成一个与原目标函数相接近的低次插值多项式，用该多项式的最优解作近的低次插值多项式，用该多项式的最优解作为原函数最优解的近似解，这种方法是用低次为原函数最优解的近似解，这种方法是用低次插值多项式逐步逼近原目标函数的极小点的近插值多项式逐步逼近原目标函数的极小点的近似求解方法，称为插值方法或函数逼近法。似求解方法，称为插值方法或函数逼近法。二、插值法与试探法的异同点二、插值法与试探法的异同

9、点 相同点：相同点：都是利用区间消去法原理将初都是利用区间消去法原理将初始搜索区间不断缩短，从而求得极小点的数值始搜索区间不断缩短，从而求得极小点的数值近似解。近似解。 不同点：不同点：试验点位置的确定方法不同。在试探法试验点位置的确定方法不同。在试探法中试验点的位置是由某种给定的规律确定的，并未考中试验点的位置是由某种给定的规律确定的，并未考虑函数值的分布。例如：黄金分割法是按照等比例虑函数值的分布。例如：黄金分割法是按照等比例0.618缩短率确定的。而在插值法中，试验点的位置缩短率确定的。而在插值法中，试验点的位置是按函数值近似分布的极小点确定的。试探法仅仅利是按函数值近似分布的极小点确定

10、的。试探法仅仅利用了试验点函数值进行大小的比较，而插值法还要利用了试验点函数值进行大小的比较，而插值法还要利用函数值本身或其导数信息。所以，当函数具有较好用函数值本身或其导数信息。所以，当函数具有较好的解析性质时，插值方法比试探方法效果更好。的解析性质时，插值方法比试探方法效果更好。三、二次插值法的概念三、二次插值法的概念 利用原目标函数上的三个插值点，构成利用原目标函数上的三个插值点，构成一个二次插值多项式，用该多项式的最优解作一个二次插值多项式，用该多项式的最优解作为原函数最优解的近似解，逐步逼近原目标函为原函数最优解的近似解，逐步逼近原目标函数的极小点，称为二次插值方法或抛物线法。数的极

11、小点，称为二次插值方法或抛物线法。四、二次插值函数的构成四、二次插值函数的构成 设一维目标函数的搜索区间为设一维目标函数的搜索区间为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) 作作二次插

12、值多项式二次插值多项式 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分别分别为为 )()()()()(133221321213132xxxxxxfxxfxxfxxA)()()()()(133221322212212312322xxxxxxfxxfxxfxxB)()()()()(133221321122313113223xxxxxxfxxxxfxxxxfxxxxC 于是函数于是函数p(x)就是一个确定

13、的二次多项式，称二次插就是一个确定的二次多项式，称二次插值函数，如图所示，虚线部分即为二次插值函数值函数，如图所示，虚线部分即为二次插值函数 令插值函数令插值函数p(x)的一介导数为的一介导数为0，即，即 p(x)=2ax+b=0 得得p(x)极小点为极小点为 xp* = B / 2 A 代入代入A、B得得 则则 321213132322212212312322*)()()()()()(21fxxfxxfxxfxxfxxfxxxp13131xxffc32112122)/()(xxcxxffc令令)2131(21*ccxxxP注意：注意： 若若c2=0， 则则 即即 说明三个插值点位于同一条直线

14、上，因此说明区间说明三个插值点位于同一条直线上，因此说明区间已经很小，插值点非常接近，故可将已经很小，插值点非常接近，故可将x2、y2输出作为输出作为最优解。最优解。0)/()(32112122xxcxxffc131311212xxffcxxff五、区间的缩短五、区间的缩短 为求得满足收敛精度要求的最优点，往往需为求得满足收敛精度要求的最优点，往往需要多次进行插值计算，搜索区间不断缩短，使要多次进行插值计算，搜索区间不断缩短，使xp*不断逼近原函数的极小点不断逼近原函数的极小点x*。 第一次区间缩短的方法是，计算第一次区间缩短的方法是，计算xp*点的函点的函数值数值fp*，比较比较fp*与与f

15、2，取其中较小者所对应的点取其中较小者所对应的点作为新的作为新的x2，以此点的左右两邻点作为新的以此点的左右两邻点作为新的x1和和x3，得到缩短后的新区间得到缩短后的新区间x1，x3，如图所示。如图所示。 以后，根据以后，根据fp*相对于相对于x2的位置，并比较的位置，并比较fp*与与 f2 ，区间的缩短可以分为以下四种情况。区间的缩短可以分为以下四种情况。入口入口xp*x2?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;