1、第三次自学、讨论的内容第三次自学、讨论的内容 1.有哪几类常用一维搜索方法?2.如何确定初始搜索区间?3.Fibonacci法和0.618法的基本原理与算法步骤。4.最速下降法的基本思想与算法步骤。5.最速下降法的特点(优缺点)及适用范围。书面作业与编程作业书面作业与编程作业 1.证明最速下降法相邻两次搜索方向相互垂直。2.用0.618法求单峰函数 在区间 内的极小值。(可用数学软件或C编程)xxxfsin)(21,0Ch2.常用无约束最优化算法常用无约束最优化算法 在基本迭代格式 中，若已知当前点 和迭代方向 ，则迭代步长 可由 的极小值确定，即 。这种确定 的方法称为一维搜索，其实质就是求
2、一元函数 的极小值。一维搜索方法分为两类：一类是不需要求导运算、只利用 的函数值、适用于单峰函 kkkkptxx1kxkpktkktpxft)(kkkf xt pmin()tkt)(t)(t1.一维搜索方法一维搜索方法数的直接法，主要有Fibonacci 法和黄金分割法(0.618法)；另一类是需要求导运算的解析法，例如插值方法等。直接法能适应不可微的情况，而解析法的效率相对较高。一、直接法一、直接法1.确定搜索区间确定搜索区间 的进退算法的进退算法 在区间 中任取一点 ，若 ，(两头大中间小)，则 为搜索区间。ba,ba,c)()(ca)()(bcba,取定初始点 及初始步长 ；令 ，计算
3、和 ；若 ，转，否则缩短步长 ，比如 （后退运算），转；加大步长，比如 (前进运算)，令 ;若 ，则得到 ，否则 ，转。tt3ttcb)()(cbba,bcca,0attac)(a)(c)()(cat3tt 2.直接法的基本原理直接法的基本原理 假设 为单峰函数，即 有唯一的极小点 ，且搜索区间 已知。因为 在 内单减，在 内单增，故若在 内任取二点 ，则仅有如下两种情形：)(xf)(xf*xba,)(xf),(*xa),(*bxba,，由于为单峰，所以极小点必在 内；，则极小点必在 内。可见，只要在当前搜索区间内取二点，比较其函数值，即可将搜索区间缩短。自然地，我们会提出下列两个问题：问题1
4、：计算 个函数值可获得的区间最大缩短率即缩短后的区间长度与原区间长度之比为多少？)()(ff,a)()(ffb,n 问题2：要将区间缩短到规定的程度，怎样选取试验点才能使计算次数最少？问题1等价于“计算 个函数值能把多长的区间缩短为长度为1的区间？”用 表示所能取得的最大区间长度，这个区间经计算 个函数值能够缩成单位区间。显然，。因为不计算函数值或只计算1个函数值无法缩短区间，只有原区间长度本来就是1才行。nFn011,1FFn 现考虑两个点情形：在区间内 取两个相异点，缩短后的区间为 或 。这两个区间的长度和必大于 的长度，故其中至少有一个子区间的长度大于 的一半，即计算两个函数值一般无法把
5、长度大于2的区间缩成单位区间。但是，对于长度为2的区间，可以如图所示选取试验点,缩短后的区间长度为1+，其中 为任意小的正数。因为 可任意选取，所以缩短后的区间 ba,ab,ba,ba,长度接近1，因此 。同理可知，一般地，有递推公式这就是著名的Fibonacci序列。综上所述，计算 个函数值可获得的区间最大缩短率为 。对于问题2，既然 个试点的最大缩短率为 ，要想把 的长度缩短为原来的 倍，22F,8,5,3543FFF)2(12110nFFFFFnnnnnF1nnF1ba,称为相对缩短精度，只要 满足 即可，试点的具体位置可以根据每次的缩短率确定。3.Fibonacci法和法和0.618法
6、法 若按上述方法选取试点，则对当前搜索区间 ，若在搜索区间内取 个点，则各次缩短率分别为 ，nF1nkkba,kkkkkabFFb1kkkkkabFFa1n12112,nnnnFFFFF F其中 为Fibonacci序列。这种方法称为菲波那什(Fibonacci)法。理论上讲，Fibonacci法是缩短搜索区间的最优方法，但实际计算时要用到Fibonacci数列，且每次缩短率不同，这就增加了计算上的困难。为了计算上的方便，通常采用等速缩短方法。缩短率取 的极限 ,此方法称为0.618法，也称黄金分割法。nFnnFF1618.0 若当前搜索区间为 ，则 。显然，取 个点后，缩短率为 ，若要求相对
7、精度为 ，则 。0.618法的计算步骤如下：求 在区间 上的最小值，相对精度为 。kkba,kkkabbkkkaban1N1lnlnNba,)(xf 给定 ，记 ，；，若 ，转，否则转；，转；，转；618.01lnlnNbbaakkk,01,(),kkkkkkbbaffaba21ff 1112111,kkkkkkabbffaba1121111,kkkkkkaabffbba2()ff1()ff2()ff 若 ，置 ，转，否则转；取最优点 ，最优值为 。注：注：Fibonacci法和0.618法仅适用于单峰函数；若初始搜索区间 未知，要用进退算法先确定。2*kkbax)(*xfba,Nk 1 kk
8、二、插值法二、插值法 多项式是逼近函数的一种常用工具。在搜索区间上，我们可以利用在若干点处的函数值来构成低次插值多项式，用它作为函数的近似表达式，并用这个多项式的极小点作为原函数极小点的近似，而低次多项式的极小点是比较容易计算的。常用的插值多项式为二次或三次，一般说来三次插值公式的收敛性较好，但在导数不便计算时，二次插值多项式也是常用的一种方法。1.二次插值方法二次插值方法 设函数 在点 处的值为 ，利用这三点作二次插值公式 ，很容易得到它的极小点为)(xf321xxx321,fff2210)(xaxaaxp321213132322212212312322*21fxxfxxfxxfxxfxxf
9、xxx 若 三点等距，相邻两点距离为 ，则 。2.三次插值方法三次插值方法 在二次插值方法中，极小点 不一定在区间 中，即插值可能为外插，这就使得二次插值方法的误差可能较大，不易控制。321,xxxx321312*22fffxffxx*x31,xx 因为一般情况下 在搜索区间 上满足 ，所以若利用 在 两点的函数值 以及一阶导数值 作三次插值，则插值法为内插，精度较高。经过计算，可得三次插值多项式的极小点为)(xfba,0)(,0)(bfaf)(xfba,)(),(bfaf)(),(bfaf)(2)()()(*abuafbfafvuax2()(),()()uvfa fbvwfafb()()3f
10、 bf awba2.共轭梯度法共轭梯度法一、最速下降法一、最速下降法 柯西于1947年提出的最速下降法是求无约束极值最早的数值方法。其基本思想是：从迭代点出发，沿目标函数值的负梯度方向进行一维搜索，求出新的迭代点，直到找到局部极小点或满足精度要求。1.最速下降法的计算步骤最速下降法的计算步骤 给定初始点 、控制误差 ，置 ；计算梯度 ，若 ，则 ，停机，否则令 ，由一维搜索求步长 ，使 ；令 ，转。0X0k)(kXf)(kXfkXX*)(kkXfpkt minkkkf tfXtpkkkkptXX11 kk 定理定理2.1 从 出发沿任意下降方向 执行一维搜索 ，得新迭代点 ，则 与 垂直，即
11、。kXkp)(min)(kkktpXft1kX1()kf Xkp0)(1kTkXfp2.最速下降法的特点最速下降法的特点 由于负梯度 的方向仅仅在 附近才具有“最速下降”性质,因此最速下降法不一定具有较高的收敛速度；由定理2.1，即相邻两次搜索方向是相互正交的。可见，最速下降法逼近最小点的路线是锯齿形的，并且越靠近极小点步长越小，即越走越慢。)(kXf0)(11kTkkTkXfpppkX 最速下降法是基本方法，但不是有效的实用方法，一般适宜于其它方法结合用于早期搜索。例例2.2 用最速下降法求Rosenbrock函数的极小值。222)1(100),(xxyyxf 解解 在函数优化问题中，目标函数等高面内经常出现“超山谷”。对于二维函数，在由目标函数等值线绘出的曲线图中则表现为“山谷”。对一个成功的最优化方法的要求之一就是能够沿着狭长的山谷迅速逼近极值。本例中的 就是由Rosenbrock设计用以考察最优化方法这一方面性能的典型函数，也称香蕉函数。下面给出 的三条等高线。),(yxf(,)8,4,0.01f x y 从图中可以看出，Rosenbrock 函数的等 值线是一条条弯曲而又狭长的山谷，山谷中点的最速下降方向几乎与通向极小值的最好方向垂直，因此最速下降法收敛得极慢（主要是 x 方向收敛太慢），甚至在合理的时间内完全不收敛。
