一维搜索方法.ppt

《一维搜索方法.ppt》由会员分享，可在线阅读，更多相关《一维搜索方法.ppt（55页珍藏版）》请在得力文库 - 分享文档赚钱的网站上搜索。

1、一维搜索方法一维搜索方法一一维优化一般可分化一般可分为两大步两大步骤：图图3.1当迭代初始点当迭代初始点 及搜索及搜索方向方向 确定后，确定后，迭代所得迭代所得的新点的新点 取决于步取决于步长 ，不同的，不同的 会得到不同的会得到不同的目目标函数函数值 。确定初始搜索区确定初始搜索区间a,b;该区区间应为包含一包含一维优化目化目标函数的极小点在内的函数的极小点在内的单峰区峰区间。在搜索区在搜索区间a,b内内寻找极小点。找极小点。优化算法的基本迭代公式：化算法的基本迭代公式：2在多在多维优化化问题中，一中，一维优化的目的是：化的目的是：在既定的在既定的 和和 下下寻求最求最优步步长 ，使迭代，使

2、迭代产生的新生的新点点 的函数的函数值为最小，即：最小，即：u常用的一常用的一维搜索方法搜索方法l试探法探法黄金分割法黄金分割法fibonacci方法方法平分法平分法格点法格点法l插插值类方法方法牛牛顿法法抛物抛物线法（二次插法（二次插值法）法）此此处介介绍的均的均为一一维的无的无约束束优化方法化方法。3u本本节的假的假设：函数在区函数在区间a,b上是凸函数，且上是凸函数，且连续。1 2 30F()F(2)F(1)F(3)图图3.2于是在区于是在区间a,b上有上有唯一的极小唯一的极小值；如；如图3.2所示所示,在区在区间 1,3上，函数上，函数值满足足高高-低低-高高(或大或大-小小-大大)的

3、特征。的特征。在极小点的左在极小点的左边函数函数值应一直下降；而在极小一直下降；而在极小点的右点的右边函数函数值应严格上升。格上升。4由由单峰函数性峰函数性质可知，在极可知，在极小点左小点左边函数函数值应严格下降，格下降，而在极小点而在极小点 右右边函数函数值应严格上升。格上升。从某一从某一给定的初始点定的初始点 出出发，以初始步，以初始步长h0沿着目沿着目标函数函数值的下降方向，逐步前的下降方向，逐步前进（或后退），（或后退），直至找到相直至找到相继的的3个个试点的函数点的函数值按按“大小大大小大”变化化为止。止。u进退法的基本思路退法的基本思路 3.2 确定最确定最优解所在区解所在区间的的

4、进退法退法*0f()f(*)5 (1)给定初始点定初始点0和初始步和初始步长h0;u进退法确定搜索区退法确定搜索区间的步的步骤：(2)令令1 0,h=h0，2 1+h,得：得：两两试点点1，2，计算算 f1 f(1),f2 f(2);(3)比比较 f1 和和 f2，存在以下两种情况：，存在以下两种情况：1)若若f1 f2，如右如右图所示所示,取取h=2h,作作前前进运算运算。1.1.方法一方法一11 6 2)若若f1 f2，如下，如下图所示所示,则作作后退后退计算算。令令h=-h,将将1、f1与与2、f2对调，转入第入第3)步。步。7 3)计算算第第3个个试点点3 2+h,计算函数算函数值f3

5、f(3),并并比比较f2 和和 f3，有如下两种情况，有如下两种情况:l 若若 f2f3，如下，如下图所示所示,则找到了相找到了相继3试点点1、2、3的函数的函数值按按“大小大大小大”变化，化，故有故有搜索区搜索区间a,b，a=min1,3;b=max1,3。8l若若 f3 f2，如如图3.3（a）、（）、（b）所示）所示,则作作前前进运算运算。取取第第3个个试点点3 2+h,计算函数算函数值f3f(3),并并比比较f2 和和 f3:2.2.方法二方法二 11图图3.3 进退法进退法(b)(a)12l 若若 f2 f3，如，如图3.3（a）所示）所示,则找找到了相到了相继3试点点1、2、3的函

6、数的函数值按按“大小大大小大”变化，故有化，故有搜索区搜索区间a,b=1,3;图图3.3 进退法进退法13l若若 f2 f3，如，如图3.3（b）所示）所示,则将将步步长加倍加倍，即令，即令h=2h，1 2,2 3,3 2+h。如此重复如此重复该过程，程，总能找到相能找到相继3试点的函数点的函数值符合符合“大小大大小大”变化的要求。左端点化的要求。左端点为a,右端点右端点为b，从而找到了搜索区从而找到了搜索区间a,b。图图3.3 进退法进退法14 2)若若f2 f1，如，如图3.3（c）、（）、（d）所示）所示,则作作后退后退计算算。令令h=-h,将将1、f1与与2、f2对调，并取第，并取第3

7、个个试点点3 2+h,计算函数算函数值f3f(3),比比较对调后的后的f2 与与 f3:图图3.3 进退法进退法15l若若 f2 f3，如，如图3.3（c）所示）所示,则搜索区搜索区间a,b=3,1;图图3.3 进退法进退法16l若若 f2 f3，如，如图3.3（d）所示）所示,则将将步步长加倍，加倍，继续作后作后退运算退运算，即令，即令h=2h，1 2,2 3,3 2+h。继续比比较f2 与与 f3，直至找到相，直至找到相继3试点的函数点的函数值按按“大大小大小大”变化化为止。相止。相应的区的区间为 3,1。图图3.3 进退法进退法17图图3.4u进退法的退法的程序框程序框图18193.3

8、一一维搜索的区搜索的区间消去法消去法l基本原理基本原理黄金分割法是通黄金分割法是通过不断不断缩短搜索短搜索区区间的的长度来度来寻求一求一维函数函数f()的极小点，其基本原理如下：的极小点，其基本原理如下：图3.53.3.1 黄金分割法（黄金分割法（0.618法）法）在搜索区在搜索区间a,b内按如下内按如下规则对称地取两点称地取两点1,2，并，并计算算它它们的函数的函数值f1 f(1),f2 f(2)。20比较f1 与与f2的大小，有以下两种可能：的大小，有以下两种可能：图图3.5 黄金分割法区间收缩黄金分割法区间收缩（1）若）若f1 f2，如如图3.5（a）所示，极小点必在）所示，极小点必在1

9、,b 内，内，消去区消去区间a，1，令，令a1，产生新区生新区间a,b。至此，至此，区区间收收缩了一次。了一次。注意：注意：新区新区间的的1点点与原区与原区间的点的点2重合重合，可令，可令12，f1f2,这样可可少找一个新点和少找一个新点和节省一省一次函数次函数值计算。算。21（2）若）若f1 f2，如，如图3.5（b）所）所示，极小点必在示，极小点必在a，2 内，内，消消去区去区间2，b，令，令b2，产生新区生新区间a,b，至此，区，至此，区间收收缩了一次。了一次。同同样，新区，新区间2点点与原区与原区间1点重合点重合，令，令2 1，f2 f1。当当缩短的新区短的新区间长度小于等于某一精度度

10、小于等于某一精度，即，即b-a 时，取，取*为近似极小点。近似极小点。*（b+a）/222l黄金分割法的区黄金分割法的区间收收缩率率即即每次每次缩小所得的新区小所得的新区间长度度与与缩小前区小前区间长度度之比。之比。区区间收收缩率率的推的推导：为加快区加快区间收收缩应保保证区区间收收缩率不率不变，即在搜索区，即在搜索区间a,b内内对称取称取计算点算点1,2。设初始区初始区间长度度为L,则第一次第一次和第二次收和第二次收缩得到的新区得到的新区间长度度分分别为：L 和和(1)L。根据收根据收缩率相等的原率相等的原则，可得：，可得：L：L(1)L：L 该方程的正根方程的正根为：23图图3.6l黄金分

11、割法程序框黄金分割法程序框图24l特点：特点：黄金分割法程序黄金分割法程序结构构简单，容易理解，可，容易理解，可靠性好。但靠性好。但计算效率偏低，适用于低算效率偏低，适用于低维优化化的一的一维搜索。搜索。253.3.2 斐波斐波纳契契 Fibonacci方法方法除去黄金分割法外，在生除去黄金分割法外，在生产上，上，还常使用一些其他常使用一些其他区区间消去的搜索方法，消去的搜索方法，如：斐波如：斐波纳契契Fibonacci法。法。n01234567891011121314151617181920Fn1123581321345589144233377610987159725844181676510

12、946该方法是方法是构造一个数列构造一个数列，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法相比，没有本法相比，没有本质的提高，故在生的提高，故在生产中的中的应用已用已经较少。少。26l黄金分割法与黄金分割法与Fibonacci方法比方法比较 也就是也就是说，当，当n时黄金分割法的黄金分割法的总缩短率的短率的值比比Fibona

13、cci法的法的总缩短率的短率的值大大1.17倍，故其倍，故其效果效果虽然稍差些，但然稍差些，但计算算简便也是很好的。便也是很好的。当当计算点算点总数数n时，Fibonacci分数分数Fn-1/Fn(即即缩短率短率)的极限就是的极限就是0.6180339887418948。实际上上当当n8,即有即有Fn-1/Fn0.618。用用n个个计算点算点计算算时或或经过n-1次迭代后，黄金分割次迭代后，黄金分割法的法的总缩短率短率为n-1,当当n时此两者之比此两者之比为：27当当n=211时，两种方法，两种方法总缩短率的比短率的比较：黄金分割法与黄金分割法与Fibonacci法的法的缩短率短率计算点数算点

14、数n23456Fibonacci法法0.50.330.20.1250.077黄金分割法黄金分割法0.6180.380.230.140.083计算点数算点数n7891011Fibonacci法法0.0480.0290.0180.0100.0069黄金分割法黄金分割法0.0540.0340.0210.0130.008128l取具有极小点的取具有极小点的单峰函数的搜索区峰函数的搜索区间a,b的坐的坐标中点中点 作作为计算点，算点，计算目算目标函数函数在在该点点处的的导数数 ；u基本原理基本原理3.3.3 平分法平分法l利用函数在极小点利用函数在极小点处的的导数数为零，而在其左零，而在其左侧为负、右、

15、右侧为正的原理正的原理，来判断极小点所在的那，来判断极小点所在的那一半搜索区一半搜索区间，以消掉另一半区，以消掉另一半区间。这样逐次迭代下去，逐次迭代下去，总能将搜索区能将搜索区间收收敛到到一个局部极小点附近，求得极小点的近似解。一个局部极小点附近，求得极小点的近似解。特点：特点：其收其收敛速度速度虽慢，但慢，但缩短率也达到短率也达到0.5，特特别是每次迭代是每次迭代计算量算量较少，可靠性少，可靠性较好，故其好，故其仍然是一个受仍然是一个受欢迎的方法。迎的方法。29u平分法的迭代平分法的迭代计算步算步骤303.3.4 格点法格点法图图3.7格点法的内等分计算点格点法的内等分计算点3132格点法

16、的格点法的计算程序框算程序框图：图3.8给定：n,a,b,ym?k=n?b-a?格点法的特点：格点法的特点：计算程序算程序简单，且当，且当变量量为离散离散值时，也可作，也可作为内分点，内分点，使离散使离散变量求量求优方便；方便；但当迭代精度要求高但当迭代精度要求高时，内，内分点的数目要增大而使分点的数目要增大而使计算算工作量增大，效率低。工作量增大，效率低。333.4 一一维搜索的插搜索的插值类方法方法该类方法又称方法又称函数逼近法函数逼近法，即，即利用插利用插值方法建立目方法建立目标函数的某种函数的某种近似表达式近似表达式，进而求出插而求出插值函数的极小点，函数的极小点，并用它作并用它作为原

17、来函数极小点的近似原来函数极小点的近似值。l插插值类方法与方法与试探方法比探方法比较:共同点共同点：均利用均利用区区间消去法原理消去法原理将初始搜索区将初始搜索区间不断不断缩短，从而求得极小点的数短，从而求得极小点的数值解。解。34不同点不同点：试验点位置的确定方法不同。点位置的确定方法不同。试探方法：探方法：试验点位置是由某种点位置是由某种给定的定的规律确律确定的，它不考定的，它不考虑函数函数值的分布。如：黄金分割法的分布。如：黄金分割法是按等比例是按等比例0.618缩短率确定的。短率确定的。插插值类方法：方法：试验点位置是按函数点位置是按函数值近似分布近似分布的极小点确定的。的极小点确定的

18、。试探法探法仅仅利用利用试验点函数点函数值的大小的大小进行比行比较，而插而插值类方法方法则利用了函数利用了函数值本身或者其本身或者其导数信数信息。息。当函数具有当函数具有较好的解析性好的解析性质时（如（如连续可微性），可微性），插插值类方法比方法比试探方法效果更好。探方法效果更好。35l多多项式插式插值方法方法多多项式是函数逼近的一种常用工具。式是函数逼近的一种常用工具。多多项式式插插值方法利用若干方法利用若干试验点点处的函数的函数值来构造低次来构造低次多多项式，式，用它作用它作为函数的近似表达式，函数的近似表达式，并用并用这个个多多项式的极小点作式的极小点作为原函数极小点的近似原函数极小点的

19、近似。常用的插常用的插值多多项式式为二次多二次多项式式。常用的二次。常用的二次多多项式插式插值方法如下：方法如下：牛牛顿法（切法（切线法）法）牛牛顿法是利用一点的函数法是利用一点的函数值、一、一阶导数数值和二和二阶导数数值来构造此二次函数的。来构造此二次函数的。抛物抛物线法（二次插法（二次插值法）法）抛物抛物线法是利用三个点的函数法是利用三个点的函数值形成一个抛物形成一个抛物线来构造此二次函数的。来构造此二次函数的。363.4.1 牛牛顿法法l基本原理基本原理37图3-9一维搜索的切线法38l牛牛顿法的法的计算步算步骤：39l牛牛顿法的特点法的特点收收敛速度快；速度快；但但计算工作量算工作量较

20、大，因在每一点均需大，因在每一点均需计算函数的二算函数的二阶导数，此外当用数数，此外当用数值微分代替二微分代替二阶导数数时，舍入，舍入误差差会影响牛会影响牛顿法的收法的收敛速度，当速度，当f()很小很小时这个个问题更更严重；重；要求初始点要求初始点选得比得比较好，即离极小点不太好，即离极小点不太远，否，否则有有可能使极小化序列可能使极小化序列发散或收散或收敛到非极小点。到非极小点。4044.000660.0055184.047204.0005941l二次插二次插值法的基本原理法的基本原理即在即在寻求目求目标函数函数f()极小点的搜索区极小点的搜索区间内，内，取三个取三个点的函数点的函数值来构造

21、一个二次插来构造一个二次插值多多项式式p()，用它的极小，用它的极小点近似地作点近似地作为原目原目标函数的极小点。函数的极小点。若近似程度不若近似程度不满足精度要求，可反复使用此法，随着足精度要求，可反复使用此法，随着区区间缩短，二次插短，二次插值多多项式的极小点就逼近原目式的极小点就逼近原目标函数的函数的极小点。极小点。3.4.2 抛物抛物线法（二次插法（二次插值法）法）图图3.10二次插值法基本原理二次插值法基本原理42图图3.10二次插值法基本原理二次插值法基本原理4344l二次插二次插值法的迭代法的迭代过程程454647图图3.11二次插值法区间缩短的二次插值法区间缩短的4种情况种情况

22、4849停停50二次插二次插值法程序框法程序框图说明：明：51l二次插二次插值法的特点法的特点该方法收方法收敛速度快、有效性好，但程序速度快、有效性好，但程序较复复杂、可靠性稍差，适用于多、可靠性稍差，适用于多维优化的一化的一维搜索迭代。搜索迭代。52533.5 小结小结各种一维优化方法都有其一定的特点和适用条件，现将常各种一维优化方法都有其一定的特点和适用条件，现将常用的几种方法作一简单比较，以供选用方法时参考。用的几种方法作一简单比较，以供选用方法时参考。方法方法算法特点算法特点适用条件适用条件格点法格点法程序程序简单简单，函数性，函数性态对态对计计算的有效性影响小，算的有效性影响小，可靠

23、性高。但可靠性高。但计计算量大，算量大，搜索效率低。搜索效率低。搜索精度要求不高。允搜索精度要求不高。允许设计变许设计变量量为为稀疏的离散稀疏的离散变变量。量。黄金分黄金分割法割法程序程序简单简单。不用。不用导导数。数。对连续对连续和非和非连续连续函数均函数均能能获获得得较较好的效果。但好的效果。但效率偏低。效率偏低。适用于低适用于低维优维优化化问题问题中的一中的一维维搜搜索，或用于函数不可索，或用于函数不可导导，求，求导导有有困困难难的情况。的情况。低次多低次多项项式插式插值值法法计计算量小，搜索效率算量小，搜索效率较较高，收高，收敛敛速度快。但程速度快。但程序略复序略复杂杂，可靠性不及，可靠性不及黄金分割法。黄金分割法。适用于适用于维维数数较较高高优优化化问题问题中的一中的一维维搜索。搜索。对对于二次两点插于二次两点插值值或三或三次两点插次两点插值值等方法要用到函数的等方法要用到函数的导导数，故函数必数，故函数必须连续须连续可可导导。54结束！结束！