一维搜索方法[网搜]-工程优化-西电课件.ppt

第三章第三章 一维搜索方法一维搜索方法一维搜索可用于：求一元函数的最优解（一般指：极小点、极小值）；多维优化设计时，在第k次迭代中，求最优步长。即把目标函数看成是步长的一元函数。一维搜索的2个步骤：确定fmin所在的区间，即找出“高低高”单峰区间。单峰区间是指函数在该区间内只有1个极值点，；缩小搜索区间，当区间足够小时得到最优点。图a的函数具有“高-低-高”变化特点，而图b和图c可以看成是图a的特例。一维搜索方法属于无约束规划问题的直接法。常用解法有成功失败法，黄金分割法，二次插值法，等等。其基本思想都是确保搜索区间是一个单峰区间，并通过重复不断缩小单峰区间。确定单峰区间的步骤如下：确定单峰区间的步骤如下：1、给定初始点1和初始步长h,令2=1+h.2、记f1=f(1),f2=f(2),比较f1和f2的大小。3、若f1f2(如下图a、b)，则前进h，即前进到3，得f3。比较f2与f3：若f2f3(如图a)，则找到了三个点满足“两头大，中间小”的特点。若f2f3(如图b)，则将步长加倍，前进到3+2h位置，然后对第2步的试探点重新编号：1=2，2=3，3=3+2h，检查新一轮搜索中的三点是否满足“两头大，中间小”的特点，若不，则重复这一过程。若f1f2(如下图c、d)，则作后退计算。后退到图中第3点，然后对调1、2点。比较f2与f3：若f2f3(如图c)，则找到了“两头大，中间小”的区间：3,1。若f2f3(如图d)，则将步长加倍，即加倍后退到图d中第三行的3位置，然后对第2步的试探点重新编号，检查新一轮搜索中的三点是否满足“两头大，中间小”的特点，若不，则重复这一过程。以上两种搜索过程中试点1、2、3的排列顺序有什么特点？向前搜索时，试点1、2、3为单调递增顺序排列。向后搜索时，试点1、2、3为单调递减顺序排列。(2)比较发现，f2f3，符合图b的情况,则步长加倍，即前进两步(h=?),重新编号后得：3.2成功失败法这种方法可以简单概括为：大步前进，小步后退。该法可使已知的单峰区间逐渐缩小。以x0点为初始点，以h为初始步长，到达x0+h点，1）：若目标函数值下降，即f(x0)f(x0+h)，则称搜索成功。下一次就以x0+h为起点，以2h为步长前进到新点，这个过程称为大步前进。2）到达x0+h点，若目标函数值不下降，即f(x0)f(x0+h)，则称搜索失败。下一次就以x0+h为起点，以-h/4为步长，即改变搜索方向并缩小步长，这个过程称为小步后退。当步长足够小（小于允许误差）时，搜索停止，得到问题的近似解。,失败，退回到x1,下一步反向，改变步长。，失败，仍回到x1,下一步再反向，再改变步长，迭代失败，回到x5，下一步实际工程中，函数的形态可能并不清楚，但只要是一维函数，通过成功失败法就可以找到其最小值点。这个过程可以通过计算机程序来实现。以下是一个matlab程序。%用成功-失败法求x2+2*x的最小值h=3;x0=4;n=1;f0=x0*x0+2*x0;fprintf(初始点x0=%d 步长h=%d 目标函数f0=%dn,x0,h,f0)while abs(h)1e-4 x=x0+h;f=x2+2*x;fprintf(第%d步，从x=%d出发，经过步长%d，到达点x=%d,目标函数为f=%d;,n,x0,h,x,f)n=n+1;if ff2，保留区间为1，b，下一步又在保留区间确定两个黄金分割点图（b）1、2为黄金分割点，f2f1,保留区间为a，2，下一步又在保留区间确定两个黄金分割点问题：1.总结以上两图，指出保留区间有什么共同特点？2黄金分割法新区间长度与旧区间长度的比值有什么特点？黄金分割法的渊源公元前300多年，毕达哥拉斯学派的大算学家攸道克斯有句名言“凡是美的东西，都具有一个共同特征，这就是部分与部分之间，以及部分与整体之间固有的协调一致”。2000多年前，Euclid发现，对一直线段进行分割，使分割线段的“小部/大部大部/全部”的那个分割点，在任一线段的0.618处。如：芭蕾舞演员的腰高/身高0.618；法国埃菲尔铁塔的第二层平台，位于整个塔高的0.618处；五星红旗的宽度/长度0.618；日常所见到的书本杂志、纸张、桌面、门窗、衣柜等等，其宽度/长度0.618时，看起来就觉得和谐悦目。例：用黄金分割法求 的最优解。迭代精度为0.35。实际工程中目标函数往往不能用简单的函数来表示，很难通过函数求导来解上述问题。由前面例题知，单峰区间为2,8.（通过excel求解）以下进行二次插值公式的推导：设原函数为f(x),与某一搜索区间相对应的插值函数为p(x)=ax2+bx+c，其中a、b、c为待定系数，求这三个系数需要知道三个插值点处的函数值。若搜索区间发生变化，则a、b、c的值也不一样。若原函数在某区间内x1、x2、x3处的函数值为f1、f2、f3，则插值函数在这三点的值也应为f1、f2、f3。于是有如下方程组：解方程可得系数a、b、c的表达式。近似解可能还不到精度要求，为此需缩短区间，进行多次插值计算，以使近似解逼近原函数的极小点。现在的问题是，如何确定下一个区间？为方便起见，初始迭代时一般取区间为x1、x3，区间中点为x2，求出一个极值点x4后，在以上4个点中选出3个点，使它们构成的新区间比上一步短，同时3个点的函数值在新区间内呈现“两头大中间小”的特点。具体说来，要区分如图所示4种情况：问题：观察上述四图，总结保留区间有何特点？由图可知缩短搜索区间的原则是：比较f2与f4,以较小值所对应的点为新区间的x2点,并此点左右邻点作为新区间的端点。可用下图来说明。我们发现，如果原函数本来就是二次函数，则只需要一次迭代即可得最优解。若继续迭代，则x4报错，为什么？作业：上机编制黄金分割法和二次插值法的matlab程序，并求解本章习题1、2。用excel实现成功失败法的求解过程。