一维搜索线性搜索PPT学习教案

1、会计学1一维搜索线性搜索一维搜索线性搜索2()0f X12(,)TnXx xx第3章 一维搜索方法3.1 概述3.1.1 一维问题是多维问题的基础 求目标函数 f (X)的极小点，从理论上说需要求解方程：其中那么如何来求 f (X)的极小点呢？基本思想:011,kkXXXX011()() ,()()kkf Xf Xf Xf X 这种方法是逐次迭代的方法，在电子计算机上很容易实这种方法是逐次迭代的方法，在电子计算机上很容易实现，因此它在优化设计中被广泛地采用。现，因此它在优化设计中被广泛地采用。第1页/共66页3kkkSXfkkkSXfmin:kkkkSaXX1()f X这个过程称为一维搜索过程

2、。kkkSXf52128)(212221xxxxXF如：如：52202521282212221xxxxF则则000 0 ,1 1TTXd1100X当当Sk方向上的任何一点可以表示为其中是步长因子，为实系数，此时 Sk 方向上任何一点的目标函数值为 ，它是参数的一元函数。那么在沿 Sk 方向求的极小点，这就是求一元函数 的极小问题，它可表示为：第2页/共66页)2 , 1 , 0(1kSXXkkk一维搜索示意图一维搜索示意图第3页/共66页)(*0)(*)(*)()(xf3.1.2 的确定方法的确定方法第4页/共66页第5页/共66页第6页/共66页 解析法解析法: : f(X f(X(k)(k

3、) + S + S(k) (k) ) ) 沿沿S S(k)(k) 方向在方向在x x(k)(k) 点泰勒展开点泰勒展开； 取二次近似：取二次近似： ( )( )( )( )( )2( )( )( )1()()()2kkkkTkkTkkf xSf xf xSSG xS 0)()()(kkSxfdd对对求导，令其为零。求导，令其为零。 ()()()()()()()0kTkkTkkfxSSG xS()()()()()()()()kTkkkTkkfxSSGxS 求得最优步长求得最优步长1()()()kkkkkffs xx第7页/共66页数值解法数值解法基本思路：基本思路： kk 解析解法对于函数关系复

4、杂、求导困难等情况难以解析解法对于函数关系复杂、求导困难等情况难以实现。在实际优化设计中，数值解法的应用更为有效，实现。在实际优化设计中，数值解法的应用更为有效，且适合计算机的运算特点。且适合计算机的运算特点。 一维搜索也称一维搜索也称直线搜索直线搜索。这种方法不仅对于解决。这种方法不仅对于解决一维最优化问题具有实际意义，而且也是求解多维最优一维最优化问题具有实际意义，而且也是求解多维最优化问题的重要支柱。化问题的重要支柱。一维搜索一般分为两大步骤：一维搜索一般分为两大步骤：(1)(1)确定初始搜索区间确定初始搜索区间aa，bb，该区间应是包括一维函数，该区间应是包括一维函数极小点在内的极小点

5、在内的单谷区间单谷区间。(2)(2)在单谷区间在单谷区间a,ba,b内通过缩小区间寻找极小点。内通过缩小区间寻找极小点。 先确定先确定 在的搜索区间，然后根据区间消去法原理在的搜索区间，然后根据区间消去法原理不断缩小此区间所，从而获得不断缩小此区间所，从而获得 的数值近似解。的数值近似解。第8页/共66页1、确定搜索区间的外推法 在给定区间内仅有一个谷值（或有唯一的极小点）的函数称为单谷函数，其区间称为单谷区间。函数值：“大小大”图形：“高低高”单谷区间中一定能求得一个极小点。3.2 确定初始区间确定初始区间第9页/共66页单谷区间单谷区间第10页/共66页f (x)0130f (x)31说明

6、：单谷区间内，函数可以有不可微点，也可以是不连续函数；第11页/共66页基本思想：基本思想：对对 任选一个初始点任选一个初始点 及初始步长及初始步长 ，通过比较这两点函数值的大小，确定第三点位置，比较这通过比较这两点函数值的大小，确定第三点位置，比较这三点的函数值大小，确定是否为三点的函数值大小，确定是否为“高高低低高高”形态。形态。)(xf1ah步骤：步骤： 1 1）选定初始点）选定初始点a a1 1，初始步长，初始步长h=hh=h0 0，计算，计算y y1 1=f(a=f(a1 1) )和和y y2 2=f(a=f(a1 1+h)+h)2 2）比较）比较y y1 1和和y y2 2；a a

7、）如果）如果y y1 1yy2 2，向右前进，加大步长，向右前进，加大步长h=2hh=2h0 0，转（，转（3 3）向前；）向前；b b）如果）如果y y1 1yyy3 3 ，加大步长，加大步长h=2hh=2h，a a1 1=a=a2 2,a,a2 2=a=a3 3, ,转（转（3 3）继）继续探测；续探测；b b）如果）如果y y2 2y0h0否否初始进退距初始进退距3xf2x1xx1x2x3x前进计算1x2x3xfx1x2x3x后退计算1x2x1y2y3y第20页/共66页 ,a b11,a b， 搜索区间确定之后，采用区间消去法逐步缩短搜索区间，从而找到极小点的数值近似解。 假定在搜索区

8、间 内任取两点 ，且 )(2)(111bffaff3.3 区间消去方法区间消去方法第21页/共66页)(2)(111bffaff第22页/共66页)(2)(111bffaff第23页/共66页)(2)(111bffaff可以总结为两种情况：若 ， 则取a,b1为缩小后的搜索区间。若 ，则取a1,b为缩小后的搜索区间。)()(11bfaf)()(11bfaf第24页/共66页试探法 黄金分割法插值法 二次插值法3 一维搜索方法分类 从前面的分析可知，每次缩短区间，只需要在区间内再插入一点并计算其函数值。 而插入点的位置，可以由不同的方法来确定。就形成了不同的一维搜索方法。一维搜索方法分类第25页

9、/共66页3.4 黄金分割法（法）黄金分割法黄金分割法的搜索过程第26页/共66页3.4 黄金分割法（法）第27页/共66页1()bba2()aba1.黄金分割法黄金分割法第28页/共66页第29页/共66页第30页/共66页ab2111a213(1)2图2-5 黄金分割法)(618. 0)()(618. 0)(21abaabaabbabb两内分点值两内分点值:结论：结论：所谓黄金分割是指将一线段分成两段的方法，使整段长与较长段的长度比值等于较长段与较短段长度的比值即所谓黄金分割是指将一线段分成两段的方法，使整段长与较长段的长度比值等于较长段与较短段长度的比值即 。215 10.6182 第3

10、1页/共66页黄金分割法要求插入两点：)(618. 0)()(618. 0)(21abaabaabbabb黄金分割法区间消去示意图： 黄金分割法（法）黄金分割法（法）第32页/共66页（1）给出初始搜索区间 及收敛精度 ，将 赋以 。 , a b0.618（2）按坐标点计算公式计算 并计算其对应的函数值 12和12,ff 黄金分割法（法）黄金分割法（法）第33页/共66页（3）根据区间消去法原理缩短搜索区间。为了能用原来的坐标点计算公式，进行区间名称的代换，并在保留区间中计算一个新的试验点及其函数值。 黄金分割法（法）黄金分割法（法）第34页/共66页（4）检查区间是否缩短到足够小和函数值收敛

11、到足够精度，如果收敛条件满足，则取最后两试验点的平均值作为极小点的数值近似解。如果条件不满足则转向步骤5。（5）产生新的插入点：如N0=0，则取（5）如果条件满足，则取最后两试验点的平均值作为极小点的数值近似解。 黄金分割法（法）黄金分割法（法）618.0ln)/(lnabk缩短区间的总次数（迭代次数）:第35页/共66页给定,ba)(),(618. 0222xfyabax)(),(382. 0111xfyabax21yy 否否21211,yyxxxa)(),(618. 0222xfyabax是)(),(382. 0111xfyabax12122,yyxxxbab是)()(5 . 0 xffb

12、ax止xfab1x2x1y2y1x2xbxfab1x2x1y2y1x2xa也可采用迭代次数是否大于或等于 k 作终止准则。第36页/共66页38迭代序号aby1比较y20-30.0561.94450.1157.6671-3-1.1110.0561.944-0.987-0.9873-1.832-1.111-0.6650.056-0.987-0.9875-1.386-1.111-0.940-0.665例3-3：用黄金分割法求 的极小值 ，搜索区间是2( )2f35 *12解：abaabb21第37页/共66页39*1()21( 1.3860.665)21.0255ab *()1.0007f 解析解

13、：1,( )1f 第38页/共66页解：1）确定初始区间a1=x0=0, f1=f(a1)=2a2=x0+h=0+1=1, f2=f(a2)=1由于f1f2, 应加大步长继续向前探测。a3= x0+2h=0+2=2, f3=f(a3)=18由于f2f3,可知初始区间已经找到，即a,b=a1,a3=0,22）用黄金分割法缩小区间 第一次缩小区间： a1(2-0)=0.764, f1 a2=0+0.618 (2-0)=1.236, f2 f1f2, 新区间a,b=a,a2=0, 1.236, b-a第39页/共66页 第三次缩小区间：l令 x1=x2l x2Xl由于f10.2, 应继续缩小区间。第

14、40页/共66页第五次缩小区间：l令 x2=x1l x1Xl由于f1f2, 故新区间a,b=x1,b=0.584, 0.764l因为 b-a=0.764-0.584=0.180.2, 停止迭代。极小点与极小值：xX(0.584+0.764)=0.674, f(x第41页/共66页 一维搜索的二次插值法一维搜索的二次插值法第42页/共66页试探法试探法（如黄金分割法）与（如黄金分割法）与插值法插值法的比较：的比较：不同点不同点：表现在试验点（插入点）位置的确定方法不同。：表现在试验点（插入点）位置的确定方法不同。第43页/共66页第44页/共66页1、牛顿法（切线法）、牛顿法（切线法） 对于一维

15、搜索函数对于一维搜索函数 ，假定已经给出极小点的一个较，假定已经给出极小点的一个较好的近似点好的近似点 ，在，在 点附近用一个二次函数点附近用一个二次函数 来逼近函数来逼近函数 。 yf00 f 20000012ffff 然后以该二次函数然后以该二次函数 的极小点作为的极小点作为 极小点的一个新的极小点的一个新的近似点近似点 。根据极值必要条件：。根据极值必要条件： f1 0 0100ff 1(0,1 ,2 )kkkkfkf第45页/共66页牛顿法的几何解释：牛顿法的几何解释：1(0,1,2)kkkkfkf在上图中，在在上图中，在 处用一抛物线处用一抛物线 代替曲线代替曲线 ，相当于用一斜线相

16、当于用一斜线 代替代替 。这样各个近似点是。这样各个近似点是通过对通过对 作切线求得与作切线求得与 轴的交点找到，故牛顿法轴的交点找到，故牛顿法又称为切线法。又称为切线法。)(f0)()()(f)(f第46页/共66页牛顿法的计算步骤牛顿法的计算步骤：1 1）给定初始点）给定初始点 0，控制误差，控制误差 ，并令，并令 0k 2 2）计算）计算 ,kkff3 3）求）求 1kkkkff4 4）若）若 1kk，则求得近似解，则求得近似解 ，1k停止计算，否则作停止计算，否则作5 5）。）。 5 5）令）令 1kk转转2 2）。）。 第47页/共66页例题：例题： 给定给定 43246164f，试

17、用，试用牛顿法求其极小点牛顿法求其极小点 。 解：解：1 1）给定初始点）给定初始点 03，控制误差，控制误差 0.001 324(334)f 212(21)f01001331366ff31133662 2）3 3）4 4）第48页/共66页重复上边的过程，进行迭代，直到重复上边的过程，进行迭代，直到 10.001kk为止。可得到计算结果如下表为止。可得到计算结果如下表: : 表3-2 牛顿法的搜索过程k01234值ak35.166674.334744.03964.00066f(ak)-52153.3518332.301993.382990.00551f(ak)-24184.33332109.

18、4458686.8699284.04720ak+15.166674.334744.039604.000664.00059第49页/共66页优点：收敛速度快。优点：收敛速度快。缺点：每一点都要进行二阶导数，工作量大；缺点：每一点都要进行二阶导数，工作量大； 当用数值微分代替二阶导数，由于舍入误当用数值微分代替二阶导数，由于舍入误差会影响迭代速度；差会影响迭代速度； 要求初始点离极小点不太远，否则有可能要求初始点离极小点不太远，否则有可能使极小化发散或收敛到非极小点。使极小化发散或收敛到非极小点。牛顿法的特点：牛顿法的特点：第50页/共66页、二次插值法（抛物线法）、二次插值法（抛物线法）p p第

19、51页/共66页（1）二次插值多项式的构成及其极值点）二次插值多项式的构成及其极值点 yf x设 在单谷区间中的三点 123的相应函数值 123()fff，则可以做出如下的二次插值多项式： 2012Paaa21011211Paaaf22012222Paaaf23013233Paaaf第52页/共66页多项式多项式 P的极值点可从极值的必要条件求得的极值点可从极值的必要条件求得1220ppPaa，即，即 12/2paa， n 为了确定这个极值点，只需计算出系数为了确定这个极值点，只需计算出系数a a1 1和和a a2 2 。其方法法是利用其方法法是利用a a0 0、a a1 1、a a2 2的联

20、立方程组中相邻两个的联立方程组中相邻两个方程消去方程消去a a0 0 ，从而得到关于，从而得到关于a a1 1、a a2 2的方程组的方程组第53页/共66页第54页/共66页113212pcac31131ffc21121223ffccf() *p ）如果区间长度 31足够小，则由 31p便得出我们所要求的近似极小点 p第55页/共66页2 2）如果不满足，必须缩小区间）如果不满足，必须缩小区间 13, ，根据区间消取法，根据区间消取法原理不断缩小区间。原理不断缩小区间。根据区间消去法原理，需要已知根据区间消去法原理，需要已知区间内两点的函数值。其中点区间内两点的函数值。其中点2 2的函数值的

21、函数值y y2 2=f=f（2 2）已知，另外已知，另外一点可取一点可取p p点并计算其函数值点并计算其函数值y yp p=f=f（p p）。）。当当 y y2 2yyp p 时取时取 1 1，p p 为缩短后的搜索区间（如为缩短后的搜索区间（如右图）。右图）。当当y y2 2yyp p 时取时取 2 2，3 3 为缩短为缩短后的搜索区间。后的搜索区间。 第56页/共66页二二次次插插值值法法程程序序框框图图第57页/共66页例1： 用二次插值法求 sin45f在上的极小点。 12144.524.54.705120355y1-0.756802 -0.977590y2-0.977590-0.99

22、9974y3-0.958924 -0.958924p4.7051204.710594yp-0.999974-0.999998第58页/共66页2 2）用二次插值法逼近极小点）用二次插值法逼近极小点相邻三点的函数值相邻三点的函数值: : x x1 1=0, =0, x x2 2=1, =1, x x3 3=2; =2; f f1 1=2, =2, f f2 2=1, =1, f f3 3=18. =18. 代入公式：代入公式：222222*2313121232313121231 ()()()2 ()()()pxxfxxfxxfxxxfxxfxxfx xp p* *0.555, f0.555, f

23、p p解解 : : 1 1）确定初始区间）确定初始区间初始区间初始区间 a a, , b b=0, 2, =0, 2, 中间点中间点x x2 2=1, =1, f f( (x x2 2)=1)=1。第59页/共66页由于由于f fp p f f2 2, , x xp p * * 0.2, |=1-0.555=0.4450.2, 应继续迭代。应继续迭代。在新区间，相邻三点的函数值在新区间，相邻三点的函数值: : x x1 1=0, =0, x x2 2=0.555, =0.555, x x3 3=1; =1; f f1 1=2, =2, f f2 2=0.292, =0.292, f f3 3=

24、1, =1, 代入代入x xp p* *公式计算得：公式计算得：x xp p* *0.607, f0.607, fp p 由于由于f fp p x x2 2, , 新区间新区间 a a, , b b=x x2 2, , b b=0.555, 1=0.555, 1| |x x2 2- -x xp p * * |=|0.555-0.607|=0.0520.2, |=|0.555-0.607|=0.0520.2, 迭代终止。迭代终止。 x xp p* *第60页/共66页例例 3 用二次插值法求用二次插值法求 的极值点的极值点。初始搜索区间。初始搜索区间 ， 。432( )46164f xxxxx13 1 6x x 0.05解：取解：取x x2 2点为区间点为区间 x x1 1, , x x3 3 的中点的中点 ， 计算计算x x1 1, , x x2 2, , x x3 3 3 3点处的函数值点处的函数值f f1 1=1