一维搜索方法.ppt

1,一维优化方法是优化方法中最基本的方法。该类方法不仅用来解决一维目标函数的求优问题，而且更常用于多维优化问题中在既定方向上寻求最优步长的一维搜索。,一维无约束优化问题：求解一维目标函数的极小点和极小值的数值迭代方法即为一维搜索方法。,第3章一维搜索方法3.1引言,2,一维优化一般可分为两大步骤：,图3.1,当迭代初始点及搜索方向确定后，迭代所得的新点取决于步长，不同的会得到不同的目标函数值。,确定初始搜索区间a,b;该区间应为包含一维优化目标函数的极小点在内的单峰区间。在搜索区间a,b内寻找极小点。,优化算法的基本迭代公式：,3,在多维优化问题中，一维优化的目的是：在既定的和下寻求最优步长，使迭代产生的新点的函数值为最小，即：,常用的一维搜索方法,试探法黄金分割法fibonacci方法平分法格点法,插值类方法牛顿法抛物线法（二次插值法）,此处介绍的均为一维的无约束优化方法。,4,本节的假设：函数在区间a,b上是凸函数，且连续。,于是在区间a,b上有唯一的极小值；如图3.2所示,在区间1,3上，函数值满足高-低-高(或大-小-大)的特征。在极小点的左边函数值应一直下降；而在极小点的右边函数值应严格上升。,5,由单峰函数性质可知，在极小点左边函数值应严格下降，而在极小点右边函数值应严格上升。,从某一给定的初始点出发，以初始步长h0沿着目标函数值的下降方向，逐步前进（或后退），直至找到相继的3个试点的函数值按“大小大”变化为止。,进退法的基本思路,3.2确定最优解所在区间的进退法,6,(1)给定初始点0和初始步长h0;,进退法确定搜索区间的步骤：,(2)令10,h=h0，21+h,得：两试点1，2，计算f1f(1),f2f(2);,(3)比较f1和f2，存在以下两种情况：1)若f1f2，如右图所示,取h=2h,作前进运算。,1.方法一1,7,2)若f1f2，如下图所示,则作后退计算。令h=-h,将1、f1与2、f2对调，转入第3)步。,8,3)计算第3个试点32+h,计算函数值f3f(3),并比较f2和f3，有如下两种情况:,若f2f3，如下图所示,则找到了相继3试点1、2、3的函数值按“大小大”变化，故有搜索区间a,b，a=min1,3;b=max1,3。,9,若f3f2，如图3.3（a）、（b）所示,则作前进运算。取第3个试点32+h,计算函数值f3f(3),并比较f2和f3:,2.方法二,12,图3.3进退法,(b),(a),13,若f2f3，如图3.3（a）所示,则找到了相继3试点1、2、3的函数值按“大小大”变化，故有搜索区间a,b=1,3;,图3.3进退法,14,若f2f3，如图3.3（b）所示,则将步长加倍，即令h=2h，12,23,32+h。如此重复该过程，总能找到相继3试点的函数值符合“大小大”变化的要求。左端点为a,右端点为b，从而找到了搜索区间a,b。,图3.3进退法,15,2)若f2f1，如图3.3（c）、（d）所示,则作后退计算。令h=-h,将1、f1与2、f2对调，并取第3个试点32+h,计算函数值f3f(3),比较对调后的f2与f3:,图3.3进退法,16,若f2f3，如图3.3（c）所示,则搜索区间a,b=3,1;,图3.3进退法,17,若f2f3，如图3.3（d）所示,则将步长加倍，继续作后退运算，即令h=2h，12,23,32+h。继续比较f2与f3，直至找到相继3试点的函数值按“大小大”变化为止。相应的区间为3,1。,图3.3进退法,18,图3.4,进退法的程序框图,19,20,3.3一维搜索的区间消去法,基本原理黄金分割法是通过不断缩短搜索区间的长度来寻求一维函数f()的极小点，其基本原理如下：,图3.5,3.3.1黄金分割法（0.618法）,在搜索区间a,b内按如下规则对称地取两点1,2，并计算它们的函数值f1f(1),f2f(2)。,21,比较f1与f2的大小，有以下两种可能：,图3.5黄金分割法区间收缩,（1）若f1f2，如图3.5（a）所示，极小点必在1,b内，消去区间a，1，令a1，产生新区间a,b。至此，区间收缩了一次。,注意：新区间的1点与原区间的点2重合，可令12，f1f2,这样可少找一个新点和节省一次函数值计算。,22,（2）若f1f2，如图3.5（b）所示，极小点必在a，2内，消去区间2，b，令b2，产生新区间a,b，至此，区间收缩了一次。同样，新区间2点与原区间1点重合，令21，f2f1。,当缩短的新区间长度小于等于某一精度，即b-a时，取*为近似极小点。*（b+a）/2,23,黄金分割法的区间收缩率即每次缩小所得的新区间长度与缩小前区间长度之比。,区间收缩率的推导：,为加快区间收缩应保证区间收缩率不变，即在搜索区间a,b内对称取计算点1,2。,设初始区间长度为L,则第一次和第二次收缩得到的新区间长度分别为：L和(1)L。,根据收缩率相等的原则，可得：L：L(1)L：L,该方程的正根为：,24,图3.6,黄金分割法程序框图,25,特点：黄金分割法程序结构简单，容易理解，可靠性好。但计算效率偏低，适用于低维优化的一维搜索。,26,3.3.2斐波纳契Fibonacci方法除去黄金分割法外，在生产上，还常使用一些其他区间消去的搜索方法，如：斐波纳契Fibonacci法。,该方法是构造一个数列，f0=1,f1=1,fn=fn-1+fn-2,按照下列条件，构造搜索点：X1=a+fn-2(b-a)/fn,X2=a+fn-1(b-a)/fn,各搜索点同样可满足上述区间消去要求。,由于该法需要存储斐波纳契数列，计算速度与0.618法相比，没有本质的提高，故在生产中的应用已经较少。,27,黄金分割法与Fibonacci方法比较,也就是说，当n时黄金分割法的总缩短率的值比Fibonacci法的总缩短率的值大1.17倍，故其效果虽然稍差些，但计算简便也是很好的。,当计算点总数n时，Fibonacci分数Fn-1/Fn(即缩短率)的极限就是0.6180339887418948。实际上当n8,即有Fn-1/Fn0.618。,用n个计算点计算时或经过n-1次迭代后，黄金分割法的总缩短率为n-1,当n时此两者之比为：,28,当n=211时，两种方法总缩短率的比较：,29,取具有极小点的单峰函数的搜索区间a,b的坐标中点作为计算点，计算目标函数在该点处的导数；,基本原理,3.3.3平分法,利用函数在极小点处的导数为零，而在其左侧为负、右侧为正的原理，来判断极小点所在的那一半搜索区间，以消掉另一半区间。,这样逐次迭代下去，总能将搜索区间收敛到一个局部极小点附近，求得极小点的近似解。,特点：其收敛速度虽慢，但缩短率也达到0.5，特别是每次迭代计算量较少，可靠性较好，故其仍然是一个受欢迎的方法。,30,平分法的迭代计算步骤,31,3.3.4格点法,图3.7格点法的内等分计算点,32,33,格点法的计算程序框图：,格点法的特点：计算程序简单，且当变量为离散值时，也可作为内分点，使离散变量求优方便；但当迭代精度要求高时，内分点的数目要增大而使计算工作量增大，效率低。,34,3.4一维搜索的插值类方法该类方法又称函数逼近法，即利用插值方法建立目标函数的某种近似表达式，进而求出插值函数的极小点，并用它作为原来函数极小点的近似值。,插值类方法与试探方法比较:,共同点：均利用区间消去法原理将初始搜索区间不断缩短，从而求得极小点的数值解。,35,不同点：试验点位置的确定方法不同。,试探方法：试验点位置是由某种给定的规律确定的，它不考虑函数值的分布。如：黄金分割法是按等比例0.618缩短率确定的。,插值类方法：试验点位置是按函数值近似分布的极小点确定的。,试探法仅仅利用试验点函数值的大小进行比较，而插值类方法则利用了函数值本身或者其导数信息。,当函数具有较好的解析性质时（如连续可微性），插值类方法比试探方法效果更好。,36,多项式插值方法多项式是函数逼近的一种常用工具。多项式插值方法利用若干试验点处的函数值来构造低次多项式，用它作为函数的近似表达式，并用这个多项式的极小点作为原函数极小点的近似。,常用的插值多项式为二次多项式。常用的二次多项式插值方法如下：,牛顿法（切线法）牛顿法是利用一点的函数值、一阶导数值和二阶导数值来构造此二次函数的。,抛物线法（二次插值法）抛物线法是利用三个点的函数值形成一个抛物线来构造此二次函数的。,37,3.4.1牛顿法,基本原理,38,图3-9一维搜索的切线法,39,牛顿法的计算步骤：,40,牛顿法的特点收敛速度快；但计算工作量较大，因在每一点均需计算函数的二阶导数，此外当用数值微分代替二阶导数时，舍入误差会影响牛顿法的收敛速度，当f()很小时这个问题更严重；要求初始点选得比较好，即离极小点不太远，否则有可能使极小化序列发散或收敛到非极小点。,41,4,4.00066,0.00551,84.04720,4.00059,42,二次插值法的基本原理即在寻求目标函数f()极小点的搜索区间内，取三个点的函数值来构造一个二次插值多项式p()，用它的极小点近似地作为原目标函数的极小点。若近似程度不满足精度要求，可反复使用此法，随着区间缩短，二次插值多项式的极小点就逼近原目标函数的极小点。,3.4.2抛物线法（二次插值法）,图3.10二次插值法基本