第三章一维优化方法

1第三章一维优化方法3.1搜索区间的确定进退法3.2一维搜索的最优化方法3.2.1格点法3.2.2黄金分割法3.2.3二次插值法2第三章一维优化方法用数值迭代法求解一元函数的极小点和极小值方法称为一维搜索优化方法。多维优化问题常常是通过一系列的一维优化方法来实现的。因当搜索方向确定后，新设计点总是位于过点的方向上。步长不同,得到的设计点和相应的函数值就不同，即只有一个变量。)()()1(KKKSXX)(KS)(KS)(KX3ox1x2()kX(1)kX*x()kS(1)()()()kkkkX=X+S由前基本迭代公式:()k待求已知(1)()(())minminkkkkFX=FX+Smin()f这种在给定方向上确定最优步长的过程,称一维优化。称为最优步长min()fx()k41x()Fx2x()fo**X()fO*n维问题一系列一维优化问题53.1搜索区间的确定x()fxo单峰函数a*xb用尽量少的计算量,尽快确定包含x*的区间[a,b]关键找三点:“高-低-高”一维搜索最优化过程可分为两步:1、确定极小点所在的初始搜索区间[a，b]2、在区间[a，b]中搜索极小点。采用某种方法将此区间逐步缩小，使其达到包含极小点x*在内的很小邻域（ε）63.1搜索区间的确定（进退法）ox()fx1x2x3x1x3xa2xb函数为y＝f(x),给定初始点x1,选定恰当的初始步长为h0一、试探搜索由于最小点x*的位置是未知的，所以首先要试探最小点x*位于初始点x1的左方或右方，然后再确定是前进还是后退111,()xyfx21022,()xxhyfx比较y1、y2大小21,yy前进21,yy后退二、前进搜索0,2hhhh3233,()xxhyfx比较y2、y3大小：23,yy[a,b]确定23,yy继续前进置换点号12122323,,xxyyxxyy7由前：ox()fx1x2x3x1x3xa2xb三、后退搜索比较y1、y2大小21,yy前进21,yy后退0,2-hhhh3233,()xxhyfx比较y2、y3大小：23,yy[a,b]确定23,yy继续后退12122121,,xxyyxxyy置换点号1x2x置换点号12122323,,xxyyxxyy89例题3.1试用进退法确定函数f(x)=x2-6x+9的一维优化搜索区间[a，b]。设初始点x1＝0，初始步长h0=1。解：按流程图3.4，计算过程如下：由于y2y1，作前进搜索，h←2h=2x3←x2+h=3，y3=f(x3)=0比较y2、y3，有y2y3，再作前进搜索，x1←x2=1，y1←y2=4x2←x3=3，y2←y3=0h←2h=4x3←x2+h=7，y3＝f(x3)=16再比较y2与y3，有y2y3，则取a←x1=1，b←x3=7103.2一维搜索的最优化方法逐渐缩小搜索区间3.2.1格点法x()fxo在区间[a，b]的内部取n个内等分点：x1，x2，…，xn区间[a，b]被分成(n+1)等分，各分点的坐标为:1,2,...,1kbaxakknnab1xnx2x1mxmx1mx1mymy1my1212,,...,,,...,nnxxxyyy计算找出minmin,1,2,...,kyknyab新区间新区间11,,mmaxbx*11:?:mmmyesxxxxno再分格点区间缩短率:λ=新区间长度老区间长度21n11格点法特点：程序简单，但计算效率较低，即在一定精度要求下计算函数值的次数较多，因而不宜用于维数较高的复杂问题中。12(1)(2)()()fafa与(1)(2)aa与(1)(2)()()fafa第一种情况：可丢掉部分(2)(,]ab基本思想:逐步缩小搜索区间,直至最小点存在的范围达到允许的误差范围为止.取中间点为极小点.在[a,b]内任取两点,且计算函数值:进行比较可得:3.2.2黄金分割法(1)(2),aaab13(1)(2)()()fafa(1)(2)()()fafa第二种情况：第三种情况：可丢掉部分(1)[,)aa问题1:λ=?问题2:如何取点?14(1)(2),:.aa在区间中的位置相对边界对称缩小后保留点在新区间中的位置与丢去点在原区间中原的位置相当则LlllL由此得解此方程得两个根取其正根为=0.6180339887…0)(2lLLl01)()(2LlLl01221515问题2:如何取点?0a0b1x2x1y2y1b2x1x1a2a2y1y2b取点规则:120.382()0.618()xabaxaba右图示,第一次区间缩短:120.382()0.618()xabaxaba第二次区间缩短:100.618LL2110.382()xxxaba20100.3820.6180.618LLLL0L100.618LL00.382L200.382LL16终止准则:()()kkba2a0a0b1x2x1y2y1b2x1x1a2y1y2b()()***2()kkabxffx17例题3.3试用黄金分割法求目标函数f(x)=x2-6x+9的最优解。给定初始区间[1，7]，收敛精度ε＝0.4。解：第一次区间缩短：计算两内点及对应函数值：x1=a+0.382(b-a)=3.292，y1=f(x1)=0.085264x2=a+0.618(b-a)=4.708，y2=f(x2)=2.917264作函数值比较，可见y1y2，区间缩短:a=a,b←x2用终止准则判断：b-a＝4.708-1=3.708ε第二次区间缩短:置换：x2←x1=3.292，y2←y1=0.085264增补:x1=a(1)+0.382(b(1)-a(1))＝2.416456，y1=f(x1)=0.3405242a0a0b1x2x1y2y1b2x1x1a2y1y2b18各次缩短区间的计算数据见表3.2。第六次区间缩短的端点a(6)＝2.750917，b(6)＝3.085305，b(6)-a(6)＝0.334388ε，满足精度要求，终止计算。取最优解为:19基本原理:利用一个低次插值多项式来逼近原目标函数,然后求该多项式的极小点,并以此作为目标函数的近似极小点,……反复使用此法,逐次拟合,直到满足给定的精度为止.常用的插值多项式为二次或三次多项式,分别称为二次插值法或三次插值法。一、二次插值函数的构成：p(x)=Ax2+Bx+C式中A、B、C为待定系数，可由P1、P2、P3三个插值结点的信息按下列线性方程组确定3.2.3二次插值法20()fx1P3P2Pa1xb3x2x*xf(x)搜索区间为[a，b]取点x1、x2、x3，构成二次函数2130.5xxx开始时:计算112233(),(),()ffxffxffx得三点:111122133(,),(,),(,)PxfPxfPxf作插值函数p(x)2()pxxAxBC211112111221113()()()pxxxfpxxxABCABCABCfpxxxf解方程组，得待定系数A、B、C*Px()px*Pf求p(x)的极小点x*P，与x2比较→区间缩短1x3x2xx1=ax3=b21一、二次插值函数的构成2()pxxAxBC解方程组，得待定系数A、B、C231312123122331()()()()()()xxfxxfxxfxAxxxxx222222231312123122331()()()()()()xxfxxfxxBfxxxxxx322311313221123122331()()()()()()xxxxfxxxxfxxxCxfxxxxxx22求二次插值函数的极小点：222222231312123231312123*1()()()22()()()PBxxfxxfxxfAxxfxxxfxxf3113121211223()()()()ffcxxffxxccxx令1132*12Pcxxcx'()20pxxAB令23二、区间的缩短**22ppxxff**22ppxxff**22ppxxff**22ppxxff24区间的缩短程序框图25三、终止准则()fx1P3P2Pa1xb3x2x*(1)Px()px*(1)Pf1x3x2x*(1)*(2)*(1)*(*),,...,,,...kkPPPPxxxxx*()*(1)kkPPxx**()kPxx2627在流程图中有两个判别框的内容需稍加说明。其一是c2=0？若成立，即：或写作这说明三个插值结点P1(x1，f1)、P2(x2，f2)、P3(x3，f3)在同一条直线上；其二是(-x1)(x3-)≤0？(3.14)若成立，则说明落在区间[x1，x3]之外。以上两种情况只是在区间已缩得很小，三个插值结点已十分接近的时候，由于计算机的舍人误差才可能导致其发生。因此对这种情况的合理处置就是把中间插值点x2及其函数值f2作为最优解输出*Px*Px*Px282930小结一维优化方法直接法:直接利用原函数f(x)的信息来决定区间的缩短间接法：利用原函数f(x)的信息构造一简单函数p(x)来近似代替原函数f(x)，求得p(x)的极小点，用p(x)的极小点所对应的原函数f(x)的信息来决定区间的缩短直接法：格点法、黄金分割法间接法：二次插值法311、进退法、格点法、黄金分割法、二次插值法的基本原理？2、P52题1和题4