最优化方法第三次

第三次自学、讨论的内容1.有哪几类常用一维搜索方法?2.如何确定初始搜索区间?3.Fibonacci法和0.618法的基本原理与算法步骤。4.最速下降法的基本思想与算法步骤。5.最速下降法的特点(优缺点)及适用范围。书面作业与编程作业1.证明最速下降法相邻两次搜索方向相互垂直。2.用0.618法求单峰函数在区间内的极小值。(可用数学软件或C编程)xxxfsin)(21,0Ch2.常用无约束最优化算法在基本迭代格式中，若已知当前点和迭代方向，则迭代步长可由的极小值确定，即。这种确定的方法称为一维搜索，其实质就是求一元函数的极小值。一维搜索方法分为两类：一类是不需要求导运算、只利用的函数值、适用于单峰函kkkkptxx1kxkpktkktpxft)(kkkfxtpmin()tkt)(t)(t§1.一维搜索方法数的直接法，主要有Fibonacci法和黄金分割法(0.618法)；另一类是需要求导运算的解析法，例如插值方法等。直接法能适应不可微的情况，而解析法的效率相对较高。一、直接法1.确定搜索区间的进退算法在区间中任取一点，若，(两头大中间小)，则为搜索区间。ba,ba,c)()(ca)()(bcba,①取定初始点及初始步长；②令，计算和；③若，转④，否则缩短步长，比如（后退运算），转②；④加大步长，比如(前进运算)，令;⑤若，则得到，否则，转④。tt3ttcb)()(cbba,bcca,0attac)(a)(c)()(cat3tt2.直接法的基本原理假设为单峰函数，即有唯一的极小点，且搜索区间已知。因为在内单减，在内单增，故若在内任取二点，则仅有如下两种情形：)(xf)(xf*xba,)(xf),(*xa),(*bxba,,①，由于为单峰，所以极小点必在内；②，则极小点必在内。可见，只要在当前搜索区间内取二点，比较其函数值，即可将搜索区间缩短。自然地，我们会提出下列两个问题：问题1：计算个函数值可获得的区间最大缩短率即缩短后的区间长度与原区间长度之比为多少？)()(ff,a)()(ffb,n问题2：要将区间缩短到规定的程度，怎样选取试验点才能使计算次数最少？问题1等价于“计算个函数值能把多长的区间缩短为长度为1的区间？”用表示所能取得的最大区间长度，这个区间经计算个函数值能够缩成单位区间。显然，。因为不计算函数值或只计算1个函数值无法缩短区间，只有原区间长度本来就是1才行。nFn011,1FFn现考虑两个点情形：在区间内取两个相异点，缩短后的区间为或。这两个区间的长度和必大于的长度，故其中至少有一个子区间的长度大于的一半，即计算两个函数值一般无法把长度大于2的区间缩成单位区间。但是，对于长度为2的区间，可以如图所示选取试验点,缩短后的区间长度为1+，其中为任意小的正数。因为可任意选取，所以缩短后的区间ba,,ab,ba,ba,长度接近1，因此。同理可知，，一般地，有递推公式这就是著名的Fibonacci序列。综上所述，计算个函数值可获得的区间最大缩短率为。对于问题2，既然个试点的最大缩短率为，要想把的长度缩短为原来的倍，22F,8,5,3543FFF)2(12110nFFFFFnnnnnF1nnF1ba,称为相对缩短精度，只要满足即可，试点的具体位置可以根据每次的缩短率确定。3.Fibonacci法和0.618法若按上述方法选取试点，则对当前搜索区间，，，若在搜索区间内取个点，则各次缩短率分别为，nF1nkkba,kkkkkabFFb1kkkkkabFFa1n12112,,,nnnnFFFFFF其中为Fibonacci序列。这种方法称为菲波那什(Fibonacci)法。理论上讲，Fibonacci法是缩短搜索区间的最优方法，但实际计算时要用到Fibonacci数列，且每次缩短率不同，这就增加了计算上的困难。为了计算上的方便，通常采用等速缩短方法。缩短率取的极限,此方法称为0.618法，也称黄金分割法。nFnnFF1618.0若当前搜索区间为，则。显然，取个点后，缩短率为，若要求相对精度为，则。0.618法的计算步骤如下：求在区间上的最小值，相对精度为。kkba,kkkabbkkkaban1N1lnlnNba,)(xf①给定，记，，；②，，若，转③，否则转④；③，转⑤；④，转⑤；618.01lnlnNbbaakkk,,01,(),kkkkkkbbaffaba21ff1112111,,,,kkkkkkabbffaba1121111,,,,kkkkkkaabffbba2()ff1()ff2()ff⑤若，置，转②，否则转⑥；⑥取最优点，最优值为。注：①Fibonacci法和0.618法仅适用于单峰函数；②若初始搜索区间未知，要用进退算法先确定。2*kkbax)(*xfba,Nk1kk二、插值法多项式是逼近函数的一种常用工具。在搜索区间上，我们可以利用在若干点处的函数值来构成低次插值多项式，用它作为函数的近似表达式，并用这个多项式的极小点作为原函数极小点的近似，而低次多项式的极小点是比较容易计算的。常用的插值多项式为二次或三次，一般说来三次插值公式的收敛性较好，但在导数不便计算时，二次插值多项式也是常用的一种方法。1.二次插值方法设函数在点处的值为，利用这三点作二次插值公式，很容易得到它的极小点为)(xf321xxx321,,fff2210)(xaxaaxp321213132322212212312322*21fxxfxxfxxfxxfxxfxxx若三点等距，相邻两点距离为，则。2.三次插值方法在二次插值方法中，极小点不一定在区间中，即插值可能为外插，这就使得二次插值方法的误差可能较大，不易控制。321,,xxxx321312*22fffxffxx*x31,xx因为一般情况下在搜索区间上满足，所以若利用在两点的函数值以及一阶导数值作三次插值，则插值法为内插，精度较高。经过计算，可得三次插值多项式的极小点为)(xfba,0)(,0)(bfaf)(xfba,)(),(bfaf)(),(bfaf)(2)()()(*abuafbfafvuax2()(),()()uvfafbvwfafb()()3fbfawba§2.共轭梯度法一、最速下降法柯西于1947年提出的最速下降法是求无约束极值最早的数值方法。其基本思想是：从迭代点出发，沿目标函数值的负梯度方向进行一维搜索，求出新的迭代点，直到找到局部极小点或满足精度要求。1.最速下降法的计算步骤①给定初始点、控制误差，置；②计算梯度，若，则，停机，否则令，由一维搜索求步长，使；③令，，转②。0X0k)(kXf)(kXfkXX*)(kkXfpktminkkkftfXtpkkkkptXX11kk定理2.1从出发沿任意下降方向执行一维搜索，得新迭代点，则与垂直，即。kXkp)(min)(kkktpXft1kX1()kfXkp0)(1kTkXfp2.最速下降法的特点①由于负梯度的方向仅仅在附近才具有“最速下降”性质,因此最速下降法不一定具有较高的收敛速度；②由定理2.1，，即相邻两次搜索方向是相互正交的。可见，最速下降法逼近最小点的路线是锯齿形的，并且越靠近极小点步长越小，即越走越慢。)(kXf0)(11kTkkTkXfpppkX③最速下降法是基本方法，但不是有效的实用方法，一般适宜于其它方法结合用于早期搜索。例2.2用最速下降法求Rosenbrock函数的极小值。222)1(100),(xxyyxf解在函数优化问题中，目标函数等高面内经常出现“超山谷”。对于二维函数，在由目标函数等值线绘出的曲线图中则表现为“山谷”。对一个成功的最优化方法的要求之一就是能够沿着狭长的山谷迅速逼近极值。本例中的就是由Rosenbrock设计用以考察最优化方法这一方面性能的典型函数，也称香蕉函数。下面给出的三条等高线。),(yxf(,)8,4,0.01fxy从图中可以看出，Rosenbrock函数的等值线是一条条弯曲而又狭长的山谷，山谷中点的最速下降方向几乎与通向极小值的最好方向垂直，因此最速下降法收敛得极慢（主要是x方向收敛太慢），甚至在合理的时间内完全不收敛。