一维搜索方法和区间消去法原理

《一维搜索方法和区间消去法原理》由会员分享，可在线阅读，更多相关《一维搜索方法和区间消去法原理（34页珍藏版）》请在装配图网上搜索。

1、一维搜索方法和区间消去法原理 第三章 一维搜索方法3.3 一维搜索的试探法3.1 搜索区间的确定3.2 区间消去法原理3.4 一维搜索的插值法一维搜索方法和区间消去法原理求解求解最优解的过程，称为最优解的过程，称为(一维一维搜索搜索)，所使用的方法称为，所使用的方法称为。)(Xf由前由前可知，求某目标函数的最优值时，迭代过可知，求某目标函数的最优值时，迭代过程每一步的格式都是从某一定点程每一步的格式都是从某一定点 出发，沿着某一使目出发，沿着某一使目标函数下降的规定方向标函数下降的规定方向 搜索，以找出此方向的极小点搜索，以找出此方向的极小点 。这一过程是各种最优化方法的一种。这一过程是各种最

2、优化方法的一种。)(kS)1(kX)(kX一般一般：首先确定一个包含函数极小点的初始区间，即确定首先确定一个包含函数极小点的初始区间，即确定 函数的搜索区间，该区间必须是单峰区间；函数的搜索区间，该区间必须是单峰区间；然后采用缩小区间或插值逼近的方法得到最优步长，然后采用缩小区间或插值逼近的方法得到最优步长，最终求出该搜索区间内的一维极小点。最终求出该搜索区间内的一维极小点。3.1 3.1 搜索区间的确定搜索区间的确定一维搜索方法和区间消去法原理根据函数的变化情况，可将根据函数的变化情况，可将分为单峰区间和多峰区间。分为单峰区间和多峰区间。所谓所谓，就是在该区间内的函数变化只有一个峰值，就是在

3、该区间内的函数变化只有一个峰值，即函数的极小值。即函数的极小值。即在即在内的内的的左侧：函数呈的左侧：函数呈，而在而在内的极小值点内的极小值点X*的右侧：函数呈上升趋势。的右侧：函数呈上升趋势。也就是说，也就是说，的函数值呈的函数值呈的变化特征的变化特征。3.1 3.1 搜索区间的确定搜索区间的确定O f(a)b x*x a 一维搜索方法和区间消去法原理目前在一维优化搜索中确定单峰区间常用的方法目前在一维优化搜索中确定单峰区间常用的方法是进退试算法。是进退试算法。为：为：1)1)按照一定的规律给出若干试算点，按照一定的规律给出若干试算点，2)2)依次比较各试算点的函数值的大小，依次比较各试算点

4、的函数值的大小，3)3)直到找到相邻三点函数值按直到找到相邻三点函数值按“高高-低低-高高”变化的单峰区间为止变化的单峰区间为止3.1 3.1 搜索区间的确定搜索区间的确定一维搜索方法和区间消去法原理进退试算法的进退试算法的如下：如下：(2)将将0及及0+h 代入目标函数代入目标函数 f(x)进行计算并比较大小进行计算并比较大小(1)给定初始点给定初始点0和初始步长和初始步长h3.1 3.1 搜索区间的确定搜索区间的确定一维搜索方法和区间消去法原理 若若 ，则所计算的相邻三点，则所计算的相邻三点 的函数值已具的函数值已具“高高-低低-高高”特征，这时可确定特征，这时可确定 搜索区间搜索区间(3

5、)若若 ，则表明极小点在试算点，则表明极小点在试算点 的右侧，需做前进试算。的右侧，需做前进试算。00()()ffh00()(3)fhfh00,3abh否则，将步长再加倍，并重复上述运算。否则，将步长再加倍，并重复上述运算。3.1 3.1 搜索区间的确定搜索区间的确定 在做前进运算时，为加速计算，可将步长在做前进运算时，为加速计算，可将步长h 增加增加2倍，并取计算新点为倍，并取计算新点为0+h+2h=0+3h一维搜索方法和区间消去法原理(4)若若 ，则表明极小点在试算点，则表明极小点在试算点 的左侧，需做后退试算。的左侧，需做后退试算。在做后退运算时，应将步长变为在做后退运算时，应将步长变为

6、-h，并从，并从 点出点出 发，得到后退点为发，得到后退点为 若若 ，则搜索区间可取为，则搜索区间可取为00()()ffh00()()fhf00,ahbh00h否则，将步长加倍，继续后退，重复上述步否则，将步长加倍，继续后退，重复上述步骤，直到满足单峰区间条件为止。骤，直到满足单峰区间条件为止。3.1 3.1 搜索区间的确定搜索区间的确定一维搜索方法和区间消去法原理f(b1)f(a1)f(b1)f(a1)f(b1)af(a1)搜索区间确定之后，采用区间消去法逐步缩短搜索区间，搜索区间确定之后，采用区间消去法逐步缩短搜索区间，找到极小点的数值近似解。找到极小点的数值近似解。假定在搜索区间内假定在

7、搜索区间内a,b 任取两点任取两点a1、b1,且且a1f2 f1f2 f1=f2 f(x)f(x)f(x)一维搜索方法和区间消去法原理f(a1)f(b1)f(a1)f(b1)f(a1)f(b1)a1a1 a1b1baabab b1 b1(1)f1f2,新区间为新区间为a1,b;(3)如如f1=f2,新区间为新区间为a1,b112ff1,a b对于上述缩短后的新区间，可在其内再取一个新点，然后对于上述缩短后的新区间，可在其内再取一个新点，然后将此点和该区间内剩下的那一点进行函数值大小的比较，将此点和该区间内剩下的那一点进行函数值大小的比较，以再次按照上述方法，进一步缩短区间，这样不断进行下以再次

8、按照上述方法，进一步缩短区间，这样不断进行下去，直到所保留的区间缩小到给定的误差范围内，而得到去，直到所保留的区间缩小到给定的误差范围内，而得到近似最优解。近似最优解。新区间为新区间为一维搜索方法和区间消去法原理111222(1)(),()(),()aabaff aaabaff aab a2a1 a2a a1f(a1)f(a2)f(a2)f(a1)b一、适用范围一、适用范围 适用于适用于a,b区间上的任何单谷函数求极小值问题。对区间上的任何单谷函数求极小值问题。对函数除要求函数除要求“单谷单谷”外不作其他要求，甚至可以不连外不作其他要求，甚至可以不连续。适应面相当广。基本原理为区间消去法续。适

9、应面相当广。基本原理为区间消去法3.3 3.3 黄金分割法黄金分割法黄金分割法插入两点：黄金分割法插入两点：一维搜索方法和区间消去法原理ab2111a213(1)221510.61823.3 3.3 黄金分割法黄金分割法一维搜索方法和区间消去法原理ab黄金分割法程序框图黄金分割法程序框图 开开 始始输入输入a,b,120.382()0.618()xabaxaba12()()f xf x22121111,0.382(),()bx xx ffxabaff x11212222,0.618(),()ax xxffxabaff x*0.5(),()xabff x结结 束束一维搜索方法和区间消去法原理例例

10、 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,x3=0,23.3 3.3 黄金分割法黄金分割法一维搜索方法和区间消去法原理2）用黄金分割法缩小区间）用黄金分割法缩小区间 第一次缩小区间

11、：第一次缩小区间：x1=0+0.382(2-0)=0.764,f1=0.282 x2=0+0.618(2-0)=1.236,f2=2.72 由于由于f10.2,应继续缩小区间应继续缩小区间3.3 3.3 黄金分割法黄金分割法第二次缩小区间：第二次缩小区间：令令 x2=x1=0.764,f2=f1=0.282 x1=0+0.382(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,应继续缩小区间应继续缩小区间一维搜索方法和区间消去法原理 第三次缩小区间：第三次缩小

12、区间：令令 x1=x2=0.764,f1=f2=0.282 x2=0.472+0.618(1.236-0.472)=0.944,f2=0.747 由于由于f10.2,应继续缩小区间。应继续缩小区间。3.3 3.3 黄金分割法黄金分割法 第四次缩小区间：第四次缩小区间：令令 x2=x1=0.764,f2=f1=0.282 x1=0.472+0.382(0.944-0.472)=0.652,f1=0.223由于由于f10.2,应继续缩小区间。应继续缩小区间。一维搜索方法和区间消去法原理第五次缩小区间：第五次缩小区间：令令 x2=x1=0.652,f2=f1=0.223 x1=0.472+0.382

13、(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.5(0.584+0.764)=0.674,f(x)=0.2223.3 3.3 黄金分割法黄金分割法求导运算求的极小点与极小值：求导运算求的极小点与极小值：x=0.667,f(x)=0.222一维搜索方法和区间消去法原理一、牛顿法一、牛顿法3.4 3.4 插值方法插值方法利用一点的函数值、利用一点的函数值、一阶导数以及二

14、阶一阶导数以及二阶导数构造二次多项导数构造二次多项式。用构造的二次式。用构造的二次多项式的极小点作多项式的极小点作为原函数极小点的为原函数极小点的近似。近似。一维搜索方法和区间消去法原理一、牛顿法一、牛顿法设设f(a)为一个连续可微的函数，则在点为一个连续可微的函数，则在点a0附近附近进行泰勒展开并保留到二次项：进行泰勒展开并保留到二次项：2000001()()()()()()()2f aaf afaaafaaa1()0a用二次函数用二次函数(a)的极小点的极小点a1作为作为f(a)极小点的一个近似极小点的一个近似点。根据极值必要条件点。根据极值必要条件:3.4 3.4 插值方法插值方法一维搜

15、索方法和区间消去法原理0010()()()0fafaaa即即0100()()faaafa依此类推可得牛顿迭代公式：依此类推可得牛顿迭代公式：1()()kkkkfaaafa一、牛顿法一、牛顿法3.4 3.4 插值方法插值方法一维搜索方法和区间消去法原理在在a0处用一抛物线处用一抛物线(a)代替曲线代替曲线f(a)，相当于用一斜直线相当于用一斜直线(a)代替曲线代替曲线f(a)。这样各个近似点。这样各个近似点是通过对作是通过对作f(a)切切线求得与轴的交点线求得与轴的交点找到的，所以，有找到的，所以，有时，牛顿法又称作时，牛顿法又称作切线法。切线法。一维搜索方法和区间消去法原理1kkaa牛顿法牛顿

16、法开开 始始计算计算 ，*1kaa给定初始点给定初始点 ，误差，误差 ,令令k=00a(),()kkff计算计算 ，1()()kkkkfaaafa1kk结结 束束一维搜索方法和区间消去法原理数值数值 k 0 1 2 3 4 3 5.1667 4.33474 4.03960 4.00066 -52 153.35183 32.30199 3.38299 0.00551 24 184.33332 109.44586 86.86992 84.04720 5.1667 4.33474 4.03960 4.00066 4.00059 2.1667 0.83196 0.29514 0.03894 0.000

17、07 41664234xxxxxFkxkxFkxF 给定初始点给定初始点x0=3，=0.001，计算公式：，计算公式：1()()kkkkF xxxFx 1224122 xxxF函数的二阶导数：函数的二阶导数：161212423xxxxF解：解：函数的一阶导数：函数的一阶导数：3.4 3.4 插值方法插值方法1kx一维搜索方法和区间消去法原理 优点：优点：1）收敛速度快。）收敛速度快。缺点：缺点：1）要计算函数的一阶和二阶导数，增加每次）要计算函数的一阶和二阶导数，增加每次 迭代的工作量。迭代的工作量。2）数值微分计算函数二阶导数，舍入误差将）数值微分计算函数二阶导数，舍入误差将 严重影响牛顿法

18、的收敛速度，严重影响牛顿法的收敛速度，f(x)的值越的值越 小问题越严重。小问题越严重。3）牛顿法要求初始点离极小点不太远，否则）牛顿法要求初始点离极小点不太远，否则 可能使极小化序列发散或收敛到非极小点。可能使极小化序列发散或收敛到非极小点。一、牛顿法一、牛顿法3.4 3.4 插值方法插值方法一维搜索方法和区间消去法原理二、二次插值法（二、二次插值法（）a1af(a)2a3a1ff23fa*在给定的单峰区间中，利用目标函数上的三个点来构在给定的单峰区间中，利用目标函数上的三个点来构造一个二次插值函数，以近似地表达原目标函数，并造一个二次插值函数，以近似地表达原目标函数，并求这个插值函数的极小

19、点近似作为原目标函数的极小点。求这个插值函数的极小点近似作为原目标函数的极小点。()f aap3.4 3.4 插值方法插值方法2()=ABCp aB=-2Cpa一维搜索方法和区间消去法原理y0aap1a1a2apa3ay0a*y1y2ypy3a1a2apa*y1y2ypyp1一维搜索方法和区间消去法原理apap1a1a2apa3ay0a*y1y2ypy3a2a3ay0a*y2ypy3yp1一维搜索方法和区间消去法原理211112222223333p()ABCp()ABCp()ABCfff构造的构造的上的三个点上的三个点:解得系数解得系数22222223131212312233123131212

20、3122331()()()()()()()()()()()()fffBfffC 2222222313121232313121231()()()22()()()pBfffCfff 二、二次插值法（二、二次插值法（）3.4 3.4 插值方法插值方法一维搜索方法和区间消去法原理2pyy二次插值法二次插值法开开 始始计算计算 ，*2min,pyyy给定给定 ,123123a a a y y y,ppy缩短区间缩短区间名称置换名称置换结结 束束一维搜索方法和区间消去法原理a1a2apa3ay0a*y1y2ypy3a1a2apa3a0a*yy1y2ypy3*2min,pyy y一维搜索方法和区间消去法原理

21、二次插值法程序编制换名方法二次插值法程序编制换名方法(1)(1)1)a2ap y2yp y2ap y2 yp y2yp一维搜索方法和区间消去法原理（1 1）二次插值法只要求）二次插值法只要求f(x)f(x)连续，不要求其一阶可微；连续，不要求其一阶可微；（2 2）收敛速度比黄金分割法快，但可靠性不如黄金分割）收敛速度比黄金分割法快，但可靠性不如黄金分割 法好，程序也较长。法好，程序也较长。特点：特点：3.4 3.4 插值方法插值方法二、二次插值法（二、二次插值法（）一维搜索方法和区间消去法原理例例 3-3 用二次插值法求函数用二次插值法求函数f(x)=3x3-4x+2的极小点，的极小点，给定给

22、定 x0=0,=0.2。解解 1）确定初始区间）确定初始区间:a,b=0,22）用二次插值法逼近极小点）用二次插值法逼近极小点 相邻三点的函数值相邻三点的函数值:x1=0,x2=1,x3=2;f1=2,f2=1,f3=18.代入公式：代入公式：2222222313121232313121231()()()2()()()pxxfxxfxxfxxxfxxfxxfxp0.555,fp=0.292一维搜索方法和区间消去法原理 在新区间，相邻三点的函数值在新区间，相邻三点的函数值:x1=0,x2=0.555,x3=1;f1=2,f2=0.292,f3=1.xp=0.607,fp=0.243 由于由于fpx2,新区间新区间a,b=x2,b=0.555,1|x2-xp|=|0.555-0.607|=0.0520.2,迭代终止。迭代终止。x*=0.607,f*=0.243由于由于fpf2,xp 0.2,应继续迭代。应继续迭代。