《一维搜索方法.ppt》由会员分享，可在线阅读，更多相关《一维搜索方法.ppt（36页珍藏版）》请在三一文库上搜索。
1、第三章一维搜索方法,采用数学规划法求函数极值点的迭代计算：,K+1次迭代的搜索方向,搜索的最佳步长因子,称为一维搜索。,是优化搜索方法的基础。,求解一元函数 的极小点,，可用解析法。,上式求的极值，即求导数为零。,则,从上式看，需要求导进行计算，对于函数关系复杂的， 解析法十分不便。,数值法的基本思路：确定 的搜索区间，在不断缩小 区间，最终获得近似值。,1、单谷(峰）区间 在给定区间内仅有一个谷值的函数称为单谷函数，其区间称为单谷区间。,第二节 搜索区间的确定和区间消去法原理,一、 确定搜索区间的外推法,函数值：“大小大” 图形：“高低高”,单谷区间中一定能求得一个极小点,2. 找初始单谷区
2、间是一维搜索的第一步； 第二步使区间缩小。,图3-2 正向搜索的外推法,图3-3 反向搜索的外推法,基本思想： 对f(x)任选一个初始点a1及初始步长h， 通过比较这两点函数值的大小，确定第三点位置，比较这三点的函数值大小，确定是否为 “高低高” 形态。,步骤：,（1）选定初始点a, 初始步长hh0，计算 y1f(a1)， y2f(a1h)。 （2）比较y1和y2。 （a）如y1y2, 向右前进；加大步长 h2 h ，转（3）向前； （b）如y1y2, 向左后退；h h0， 将a1与a2，y1与y2的 值互换。转（3）向后探测； （c）如y1y2，极小点在a1和a1h之间。,(3）产生新的探测
3、点a3a1h，y3f(a3); (4) 比较函数值 y2与y3： （b）如y2y3, 加大步长 h2 h ，a1=a2, a2=a3,转（3）继续探测。 （a）如y2y3, 则初始区间得到： a=mina1,a3， b=maxa3,a1，函数最小值所在的区间为a， b 。,进退法程序框图,搜索区间确定之后，采用区间消去法逐步缩短搜索区间，从而找到极小点的数值近似解。 假定在搜索区间内a,b 任取两点a1,b1;,f1f（a1）， f2f（b1）,区间消去法原理,一、基本思想,f1f（a1）， f2f（b1） (1)如f1f2, 则缩小的新区间为a1,b; (3)如f1=f2, 则缩小的新区间为
4、a1,b1,综合为两种情况： 若 则取 为缩短后的搜索区间。 若 则取 为缩短后的搜索区间。,三、一维搜索方法的分类,从前面的分析可知，每次缩短区间，只需要在区间内在插入一 点并计算其函数值。,而插入点的位置，可以由不同的方法来确定。就形成了不同的一维搜索方法。,第三节 一维搜索的试探法,最常用的一维搜索试探法是黄金分割法，又称0.618法。,要求插入点a1、a2的位置相对于区间a,b两端点具有对称性。,除对称要求外，黄金分割法还要求在保留下来的区间再插入一点 所形成的区间新三段，与原来区间的三段具有相同的比例分布。,2,所谓的“黄金分割”是指将一线段分成两段的方法，使整段长 与较长段的长度比
5、值等于较长段与较短段的比值，即,黄金分割法的搜索过程： 1）给出初始搜索区间及收敛精度 ，将 赋以0.618。,2）按坐标点计算公式计算 , ；并计算其对应的函数值。,3）根据区间消去法原理缩短搜索区间。为了能用原来的坐标点计算公式，需进行区间名称的代换，并在保留区间中计算一个新的试验点及其函数值。 如果 ，则新区间 令 记N0=0； 如果 ，则新区间 ， 令 ，记N0=1；,4）检查区间是否缩短到足够小和函数值收敛到足够精度，如果收敛条件满足，则取最后两试验点的平均值作为极小点的数值近似解。如果条件不满足则转向步骤5）。,如N0=0，则取,如N0=1，则取,5）产生新的插入点：,转向3）进行
6、新的区间缩小。,例 3-1 用黄金分割法求函数f(x)=3x3-4x+2的极小点， 给定 x0=0, h=1, =0.2。,解： 1）确定初始区间 x1=x0=0, f1=f(x1)=2 x2=x0+h=0+1=1, f2=f(x2)=1 由于f1f2, 应加大步长继续向前探测。,x3= x0+2h=0+2=2, f3=f(x3)=18 由于f2f3,可知初始区间已经找到，即a,b=x1,x2=0,2,2）用黄金分割法缩小区间 第一次缩小区间： x1=0+0.382X(2-0)=0.764, f1=0.282 x2=0+0.618 X(2-0)=1.236, f2=2.72 f10.2,第二次
7、缩小区间： 令 x2=x1=0.764, f2=f1=0.282 x1=0+0.382X(1.236-0)=0.472, f1=0.317 由于f1f2, 故新区间a,b=x1,b=0.472, 1.236 因为 b-a=1.236-0.472=0.7640.2, 应继续缩小区间。,第三次缩小区间： 令 x1=x2=0.764, f1=f2=0.282 x2=0.472+0.618X(1.236-0.472)=0.944, f2=0.747 由于f10.2, 应继续缩小区间。,第四次缩小区间： 令 x2=x1=0.764, f2=f1=0.282 x1=0.472+0.382X(0.944-0
8、.472)=0.652, f1=0.223 由于f10.2, 应继续缩小区间。,第五次缩小区间： 令 x2=x1=0.652, f2=f1=0.223 x1=0.472+0.382X(0.764-0.472)=0.584, f1=0.262 由于f1f2, 故新区间a,b=x1,b=0.584, 0.764 因为 b-a=0.764-0.584=0.180.2, 停止迭代。,极小点与极小值： x*=0.5X(0.584+0.764)=0.674, f(x*)=0.222,例3-2 对函数 ，当给定搜索区间 时，试用黄金分割法求极小点。,第四节 一维搜索的插值方法,假定要在某一区间内寻找函数的极
9、小点的位置，虽然没有函数 表达式，但能够给出若干试验点处的函数值。,我们可以根据这些点处的函数值，利用插值的方法建立函数的近似表达式，进而求处函数的极小点，作为原来函数的极小点的近似值。这种方法称作插值法，也称函数逼近法。,一、牛顿法（切线法）,函数很接近，因此，在 点附近用一个二次函数 逼近。,即,依次继续下去，可得牛顿法迭代公式：,牛顿法的几何解释：,牛顿法的计算步骤：,给定初始点 ，控制误差 ，并令k=0。,1）计算,2）求,优点：收敛速度快。,缺点：每一点都要进行二阶导数，工作量大；,要求初始点离极小点不太远，否则有可能使极小化 发散或收敛到非极小点。,二、二次插值（抛物线法）,，作出
10、如下的二次插值多项式,它应满足条件,（1）,从极值的必要条件求得,（2）,（3）,要求出系数 和 ，联立方程组（1）、（2）、（3）。,令,所以,则,例 33 用二次插值法求函数f(x)=3x3-4x+2的极小点，给定 x0=0, =0.2。,解 1）确定初始区间 初始区间a,b=0,2, 中间点x2=1。,2）用二次插值法逼近极小点 相邻三点的函数值: x1=0, x2=1, x3=2; f1=2, f2=1, f3=18. 代入公式：,xp*0.555, fp=0.292,在新区间，相邻三点的函数值: x1=0, x2=0.555, x3=1; f1=2, f2=0.292, f3=1.
11、xp*0.607, fp=0.243 由于fpx2, 新区间a,b=x2, b=0.555,1 |x2-xp * |=|0.555-0.607|=0.0520.2, 迭代终止。 xp*0.607, f*=0.243,由于fp0.2, 应继续迭代。,例 3-4 用二次插值法求 的极值点。初始搜索区间 ， 。,解：取x2点为区间x1,x3的中点， , 计算x1,x2,x3 3点处的函数值f1=19，f2=-96.9375，f3=124。可见函数值满足“高低高”形态。,以x1,x2,x3为插值点构造二次曲线， 求第一次近似的二次曲线p(x)的极小值点，由公式得： ， 比较函数值可知,这种情况应消除左边区段 。然后用 作为x1,x2,x3新3点,重新构造二次曲线p(x)，如此反复计算，直到 为止。,整个迭代过程的计算结果列于表。,