机械优化设计第三节一维搜索方法

第三节一维搜索方法3.1概述:第三节一维搜索方法3.1概述:一维搜索方法:对任一次迭代，总是从已)(kx知点出发，沿着给定的方向)(ks搜索到目标函数的极小点称为一维搜索法由迭代公式)()()1()(kkksxxk若设)(kx)(ks已知，则目标函数)(xf仅为最优步长)(k的函数，即)()()()()()()1(fsxfxfkkkk对)()(kf求使得)(min)()(min*)()()(fsxffkkk的最优步长*)(k的方法称作一维搜索方法)1(kx2.求*的基本思想及迭代公式(1)基本思想：通过有限次的数值迭代计算，使min)()(kf得*)(k求最优步长(2)迭代公式：设*在ba区间内，则有迭代计算公式kkk1k1，2)n且在前后两次迭代计算中，应保证)()(1kkff当11kk或21)()(kkff(21为很小的正数)则停止迭代计算，且认为1*k3.几何意义:从)(kx出发，沿)(ks方向一维搜索,就是求)(ks方向与等值线的切点此时的步长因子即为最优步长因子常有的一维搜索方法：黄金分割法和二次分割法如图所示一维函数图象在[a,e]区间有两个局部极小点和两个局部极大点。无论求哪个极值点，均需将原区间[a,e]划分出若干小区间，即在区间[a,b][c,d]中有局部极小点而区间[b,c][d,e]中有局部极大点。这些子区间的共同特点是都单峰区间。所谓单峰区间，是指函数在区间只有一个极值点abcdexf(x)3.2函数的单峰区间及其确定(1)单峰区间的确定——进退法（试探法）确定单峰区间：目的是寻找一个包含一个有函数极小点*x的区间,也是一维优化方法要解决的问题.基本思想：欲求函数)(xf的单峰区间,先任选一个初始点0x及初始步长h然后进行前进或后退的试探性搜索，找到三个点321xxx其中两端点的函数值大于中间点的函数值。即)()()(321xfxfxf确定搜索区间31xx（2）进退算法步骤：1.设有一维函数)(xf给定初始点0x初始步长h.)(xf1x2x3x0x2.令01xxhxx02计算函数值)(11xff和)(22xff3.比较存在两种情况。1f和2fa)若则说明极小点在的右方，应做前进算法。于是步长加倍，第三个试点hxx313计算)3(13hxff比较32,ffi)若32ff则说明相邻三点的函数值形成了大—小—大的特征；构成初始单峰区间，令hxx313单峰区间即为31,xx)(xf1xhx1hx310x1f2fii）若32ff步长加倍继续作前进算法，即令h=2h，如此重复该过程，直到符合大—小—大的情况为止。21ff32ff21xx32xxhxx23b）若21ff则说明极小点必在1x的左方。则作后退运算即步长改为负值,且缩短一定倍数.如41倍(nn,21)，将x1，x2，f1，f2对调，令,,,,,12211ffxxxxxxhh计算)(33xffhxxffff23221,x2x11）32ff则初始单峰区间以找到即13,xx2）32ff，则步长加倍继续后退，即令h=-2h，反复循环直到出现大—小—大情况为止程序框图如下：21ff32ff21xx32xxhxx23继续比较,开始000,hhh，输入)()(22111110afyaHaafyaa12yy1313,yyaahh32322121,,yyaayyaa)(,3323afyhaa23yyhh2输出321321,yyyaaa结束后退前进是　否3.3黄金分割法（0.618法）1、基本原理：通过不断缩短搜索区间的长度来寻求一维函数)(xf的极小点原理。它是一种等比例缩短区间的直接搜索方法。ax1x2bax1x2b1若21ff极小点在区间bx1内，将1xa新区间[ab]，区间缩短一次121220.618()xxffxaba产生2若21ff极小点在区间2xa内，将2xb产生新区间[ab]，区间缩短一次)(382.011212abaxffxx为单峰函数，区间长设为l在区间内按如下规则对称地取两点1x和)(618.0)(382.021abaxabax)()(2211xffxff比较1f和2f的大小有两种可能2x计算他们的函数值设目标函数在搜索区间[a,b]内)(xfax1x2bax1x2b3.判断新区间长度（b-a）是否达到预先给定的精度即ab时)()(21***xffbax为近似极小点4.若不能满足继续寻优（计算对称点）直到满足迭代精度为止。收缩率bxax21由此可以看出无论删除那一段,保留区间长度相等ax1x2bax1x2b为保证区间收缩率不变。因此必须在搜索区间内对称地取计算点则有21xx每次缩短区间都是取相等的区间收缩率即21每次缩小所得的新区间长度与前区间长度之比称为区间收缩率用表示。也称为缩短率，收缩率。为常数。根据收缩率相等的原则则有618.02150112所以黄金分割法有称0.618法特点：程序结构简单容易理解可靠性好。但计算效率偏低，使用于低维优化的一维搜索。LLLL)1(三、二次插值法（抛物线法）三、二次插值法（抛物线法）(1)基本思想：在寻求目标函数)(xf极小点的区间内取三个点的函数值来构造一个二次插值多项式)(xp用它的极小点近似地作为原目标函数的极小点。若近似程度不满足精度要求时，可反复使用此法随着区间的缩短，二次插值多项式的极小点就逼近原目标函数的极小点。一维函数)(xf在搜索区间[ab]内为单峰函数，在区间内取三点321xxx且321xxx三点的函数值为)()()(332211xfxffxff且321fff即满足函数值是大—小—大变化。原目标函数曲线上的3点)()()(332211fxfxfx作为二次插值多项式cbxaxxp2)(的插值结点。这里abc为待定系数.可用下述线形方程组确定.332332222211211)()()(fcbxaxxpfcbxaxxpfcbxaxxp解此方程组可得给定函数的表达式))()(()()()())()(()()()())()(()()()(13322132112231313223133221322212212312322133221321213112xxxxxxfxxxxfxxxxxxxxcxxxxxxfxxfxxfxxbxxxxxxfxxfxxfxxa2、求二次插值函数)(xp的极小点*px02)(2baxxpcbxaxxp插值多项式)(xp的极小点为222222*2313121232313121233113121121223*1132*2()()()12()()()()()1()2()ppppbxaxxfxxfxxfxxxfxxfxxfffcxxffcxxcxxcxxxcffx当搜索区间满足精度要求时**2ppxxx而可能看作是)(xf在区间[ab]上的近似最优点3、计算步骤ⅰ确定初始搜索区间[ab]和精度（这里可以采用进退法确定一个很小的插值区间)baⅱ在区间内取三点)(2131231321xxxbxaxxxx计算函数值)()()(332211xffxffxffⅲ插值计算*px(a)若分母为零即0)()()(321213132fxxfxxfxx即13131212xxffxxff则说明三个插值点),(),(),(332211fxfxfx在同一条直线上，此时可取中间插值点2x为近似*px其对应的函数值为近似极小值)(*pxf(b)若0))((*31*ppxxxx时，说明*px已在区间之外。这种情况只有当区间已缩小的很小和三个插值点十分接近时，由于计算机的舍入误差才可能性。因而可把2x及其对应的目标函数的)(22xff作为最优解输出)(2*2*xffxx④判断是否满足要求(a)若2*xxp说明搜索区间足够小2*)(fxfp时输出目标函数最优解*px)(*pxf否则2*)(fxfp时输出目标函数最优解)(22xfx(b)若2*xxp则需比较点*px和2x在搜索区间的相对位置及其对应的目标函数值的大小，以便缩短搜索区间得到新的三点。二次插值法区间缩短的4种情况开始)(),(),(5.0,,,,33221123131fyfyfybaba输入)()(3211212213131aaCaayyCaayyC)()(5.02121pPpafyCCaaa22yyyppyy22*2*,yyaappyyaa**,结束0)(2haappyy2pyy2ppyyaayyaa112121,,ppyyaa33ppyyaa11ppyyaayyaa222323,,是否是否是否是否是否