结构优化设计 3.一维搜索方法.ppt

1、第三章 一维搜索方法,概述 搜索区间的确定 一维搜索的试探方法 黄金分割法 一维搜索的插值方法 牛顿法(切线法) 二次插值法,2,概述,直接搜索法更适合于工程实践 对于单个变量（一维问题）的直接搜索，通常称为一维搜索或线性搜索 多维问题转化为一维问题求解,3,多维和一维间的转换,多维目标函数的极值问题，通常采用数值迭代的方法求解 每一步的格式都是从某一定点xk出发沿着某一使函数值下降的规定方向dk，找出在此方向的极值点xk+1。 在任何一次迭代计算过程中，当起步点和方向确定之后，就把求多维问题的目标函数的极小值这个多维问题，转变成求一个变量即步长ak的最优值的一维问题 沿着规定方向求ak的最优

2、值以使f(xk+akdk)得到极小值的过程，就是一维搜索或一维最优化问题，而ak则称为一维搜索的最优化步长 多维问题就转换为一系列的一维搜索问题,4,一维搜索方法,第一是初始点的x0选取，x0应尽量选择靠近极值点，这样就能较快找到极值点 第二是搜索方向的dk确定。从xk出发沿什么方向很快找到f(x)的极小点？以不同的原则选取dk就构成了优化方法中各种不同的方法 第三在确定了搜索方向dk后，关键的问题是如何进行沿dk方向的一维搜索,5,一维搜索方法,采用数值解法代替解析解法 第一步是确定搜索区间，即最优步长ak所在的区间a,b，搜索区间应为单峰区间，区间内目标函数应只有一个极小值 第二步是在此区

3、间内求最优步长ak，使目标函数f(xk+ak)达到极小，即通过某种原理不断缩小搜索区间，从而获得最优步长a*的数值近似解。,6,确定初始搜索区间的进退算法,前进计算,后退计算,试探后作前进或后退计算。,一）基本思路,7,给定x1、h0,y2y3,二) 迭代步骤,8,9,10,进退法的计算机程序框图,t0, h,t1=t0; t2=t0+h,f1=f(t1); f2=f(t2),f2f1,h=2ht2=t2+hf1=f2; f2=f(t2),h=-h/4,是,否,f2f1,t1=t2-h,t1=t1+h f2=f1f1=f(t1),f2f1,t2=t1-h h=2h,否,a=t1b=t2,是,是

4、,否,结束,11,一维搜索方法的分类,为了每次缩短区间，只需要在区间内再插入一点并计算其函数值。然而，对于插入点的位置，是可以用不同的方法来确定的。 一类称作试探法：区间内插入点位置的确定仅仅按照区间缩短如何加快，而不顾及函数值的分布关系 黄金分割法等 一类称作插值法或函数逼近法：构造一个插值函数来逼近原来函数，用插值函数的极小点作为区间的插入点 牛顿法、二次插值法等,12,一维搜索的试探方法黄金分割法,是最常用的一维搜索试探方法，又称作0.618法 适用于区间上的任何单谷函数求极小值问题 对函数除要求“单谷”外不作其他要求，甚至可以不连续 基本思路：在搜索区间内适当插入两点，并计算其函数值。

5、将区间分成三段。应用函数的单谷性质，通过函数值大小的比较，删去其中一段，使搜索区间得以缩短。然后再在保留下来的区间上作同样的处置，如此迭代下去，使搜索区间无限缩小，从而得到极小点的数值近似解。,13,黄金分割法,黄金分割法要求插入点1、2的位置相对于原区间a,b的两端点具有对称性，即 黄金分割法还要求在保留下来的区间内再插入一点所形成的区间新三段，与原来区间的三段具有相同的比例分布,14,黄金分割法的搜索过程,给出初始搜索区间a,b及收敛精度，将赋以0.618 按前页中坐标点比例公式计算1和2 ，并计算其对应的函数值f(1)和f(2)。 比较函数值，利用进退法缩短搜索区间 检查区间是否缩短到足

6、够小和函数值是否收敛到足够近，如果条件不满足则返回到步骤 如果条件满足则取最后两试验点的平均值作为极小点的数值近似值,15,黄金分割法程序框图,给定 a, b, 0.618,a1=b-(b-a); y1=f(a1); a2=a+(b-a); y2=f(a2);,y1y2,a=a1; a1=a2; y1=y2; a2=a+(b-a); y2=f(a2),b=a2; a2=a1; y2=y1; a1=b-(b-a); y1=f(a1),a*=(a+b)/2,结束,是,否,是,否,16,二次插值法（一）,又称抛物线法。利用y=f(x)在单谷区间中的三点x1f(x2)f(x3)，作出如下的二次插值多项

7、式 多项式的极值点可以从极值的必要条件求得,17,二次插值法（二）P(x)的系数确定与极小点的计算,18,二次插值法（三）缩短搜索区间,(1)如果搜索区间足够小，则可用P(x)的极小点x4作为f(x)的极小值x*的近似解 (2)否则，必须缩短搜索区间（利用单谷函数的性质）重复进行二次插值法 (1)当x2f(x4)则取x2,x4,x3。 (2)当x2x4时， 如果f(x2)f(x4)则取x1,x4,x2。,19,二次插值法（四）计算步骤,(1)确定搜索区间x1,x2,x3，给定计算精度0 (2)计算f(xk)，置fk=f(xk)，k=1,2,3 (3)按公式计算x4，并计算f4=f(x4) (4

8、)检验|x4-x2|否。如果满足，则停止计算，取x*=x4，否则转(5) (5)如果x2x4，转(6)，否则当f2f4时，x1=x4，f1=f4，转(3)；当f2f4时，x3=x2，f3=f2，x2=x4，f2=f4，转(3) (6)当x2x4，当f2f4时，x3=x4，f3=f4，转(3)；当f2f4时，x1=x2，f1=f2，x2=x4，f2=f4，转(3),20,二次插值法（四）计算机流程图,给定x1, x2, x3, 计算f1,f2,f3,c1=(y2-y1)/(x3-x1); C2=(y2-y1)/x2-x1)-c1)/(x2-x3),x4=0.5*(x1+x3-c1/c2); f4=f(x4),|(f4-f2)/f2|,x*=x4,x2x4,f2f4,x3=x4; f3=f4,x1=x2; f1=f2; x2=x4 f2=f4,f2f4,x1=x4; f1=f4,x3=x2; f3=f2; x2=x4 f2=f4,结束,是,否,是,是,是,否,否,否,21,例题：黄金分割法（一）,对函数f(x)x2+2x，给定搜索区间-3x5时，用黄金分割法求极小点x*,此时a=-3，b