1、 第三章 一维搜索方法3.3 一维搜索的试探法3.1 搜索区间的确定3.2 区间消去法原理3.4 一维搜索的插值法求解求解最优解的过程，称为最优解的过程，称为(一一维搜索维搜索)，所使用的方法称为，所使用的方法称为。由前由前可知，求某目标函数的最优值时，可知，求某目标函数的最优值时，迭代过迭代过程程每一步的格式都是从每一步的格式都是从某一定点某一定点X(k)出发，沿着某一使目出发，沿着某一使目标函数下降的规定标函数下降的规定方向方向 S(k)搜索，以找出此方向的搜索，以找出此方向的极小点极小点X(k+1)。这一过程是各种最优化方法的一种。这一过程是各种最优化方法的一种。一般一般：首先首先确定确
2、定一个包含函数极小点的一个包含函数极小点的初始区间初始区间，即，即确定确定 函数的搜索区间，该区间必须是函数的搜索区间，该区间必须是单峰区间单峰区间；然后采用缩小区间或插值逼近的方法然后采用缩小区间或插值逼近的方法得到得到最优步长最优步长，最终求出该搜索区间内的最终求出该搜索区间内的一维极小点一维极小点。3.1 3.1 搜索区间的确定搜索区间的确定根据函数的变化情况，可将根据函数的变化情况，可将分为分为单峰区间单峰区间和和多峰区间多峰区间。所谓所谓，就是在该区间内的函数变化只有一个峰值，就是在该区间内的函数变化只有一个峰值，即函数的极小值。即函数的极小值。即在即在内的内的的的左侧左侧：函数呈：
3、函数呈，而在而在内的内的极小值点极小值点X*的的右侧右侧：函数呈：函数呈上升趋势上升趋势。也就是说，也就是说，的函数值呈的函数值呈的变化特征的变化特征。3.1 3.1 搜索区间的确定搜索区间的确定x*abx0f(x)目前在一维优化搜索中确定目前在一维优化搜索中确定单峰区间单峰区间常用的方法常用的方法是是进退试算法进退试算法。为：为：1)1)按照一定的规律给出按照一定的规律给出若干试算点若干试算点，2)2)依次比较各依次比较各试算点的函数值试算点的函数值的大小，的大小，3)3)直到找到直到找到相邻三点相邻三点函数值按函数值按“高高-低低-高高”变化的变化的单峰区间单峰区间为止为止3.1 3.1
4、搜索区间的确定搜索区间的确定进退试算法的进退试算法的如下：如下：(2)将将0及及0+h 代入目标函数代入目标函数 f(x)进行计算并比较大小进行计算并比较大小(1)给定给定初始点初始点0和和初始步长初始步长h3.1 3.1 搜索区间的确定搜索区间的确定f(x)x0aba0f(a0)a0+hf(a0+h)a0+3hf(a0+3h)f(x)x0aba0-hf(a0-h)a0f(a0)a0+hf(a0+h)若若f(0+h)f(0+3h)，则所计算的相邻三点，则所计算的相邻三点 的函数值已具的函数值已具“高高-低低-高高”特征，这时可确定特征，这时可确定 搜索区间搜索区间(3)若若f(0)f(0+h)
5、，则表明极小点在试算点，则表明极小点在试算点 的右侧，需做的右侧，需做前进试算前进试算。00,3abh否则，将步长再加倍，并重复上述运算。否则，将步长再加倍，并重复上述运算。3.1 3.1 搜索区间的确定搜索区间的确定 在做在做前进运算前进运算时，为加速计算，可将步长时，为加速计算，可将步长h 增加增加2倍，并取计算新点为倍，并取计算新点为0+h+2h=0+3h(4)若若 f(0)f(0)，则，则搜索区间搜索区间可取为可取为00,ahbh否则，将步长加倍，继续后退，重复否则，将步长加倍，继续后退，重复上述步上述步骤骤，直到满足，直到满足单峰区间单峰区间条件为止。条件为止。3.1 3.1 搜索区
6、间的确定搜索区间的确定f(b1)f(a1)f(b1)f(a1)f(b1)af(a1)搜索区间确定搜索区间确定之后，采用区间消去法逐步之后，采用区间消去法逐步缩短搜索区间缩短搜索区间，找到极小点的数值近似解。找到极小点的数值近似解。假定在搜索区间内假定在搜索区间内a,b 任取两点任取两点a1、b1,且且a1f2 f1f2 f1=f2 f(x)f(x)f(x)(1)f1f2,新区间为新区间为a1,b(3)f1=f2,新区间为新区间为a1,b1对于上述对于上述缩短后的新区间缩短后的新区间，可在其内再取一个，可在其内再取一个新点新点，然后，然后将此点和该区间内剩下的那一点进行函数值大小的比较，将此点和
7、该区间内剩下的那一点进行函数值大小的比较，以再次按照以再次按照上述方法上述方法，进一步，进一步缩短区间缩短区间，这样不断进行下，这样不断进行下去，直到去，直到所保留的区间所保留的区间缩小到给定的误差范围内，而得到缩小到给定的误差范围内，而得到近似最优解近似最优解。12ff新区间为新区间为a1,bf(b1)af(a1)a1 b1bf(b1)f(a1)a1ab b1f(b1)f(a1)a1bab1111222(1)(),()(),()aabaff aaabaff a一、适用范围一、适用范围 适用于适用于a,b区间上的任何区间上的任何单谷函数单谷函数求极小值问题。对求极小值问题。对函数除要求函数除要
8、求“单峰单峰”外不作其他要求，甚至可以外不作其他要求，甚至可以不连不连续续。适应面相当广。基本原理为。适应面相当广。基本原理为区间消去法区间消去法3.3 3.3 黄金分割法黄金分割法黄金分割法插入两点：黄金分割法插入两点：f(a2)af(a1)a1 a2bf(a2)af(a1)a1b a221510.61823.3 3.3 黄金分割法黄金分割法212ab11-13(1-)2aab黄金分割法程序框图黄金分割法程序框图 开开 始始输入输入a,b,120.382()0.618()xabaxaba12()()f xf x22121111,0.382(),()bx xx ffxabaff x112122
9、22,0.618(),()ax xxffxabaff x结结 束束*0.5(),()xabff xaf(x2)f(x1)b x1 x2b x2f(x2)x1例例 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,可知初始区间已经找到，即可知初始区间已经找到
10、，即 a,b=x1,x3=0,23.3 3.3 黄金分割法黄金分割法f(x1)=2x1=0f(x2)=1x2=1f(x3)=18x3=2ab2）用黄金分割法缩小区间用黄金分割法缩小区间 第一次缩小区间：第一次缩小区间：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 黄金分割法黄金分割法f(x1)=0.282x1=0.764f(x2)=2.72x2=1.236abb3.3 3.3 黄金分割法黄金分割法第二次缩小区间：第二次缩小区间：令令 x2=x1=0.764
11、,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,应继续缩小区间应继续缩小区间f(x1)=0.282x1=0.764f(x2)=2.72x2=1.236abbx2f(x2)x1f(x1)a 第三次缩小区间：第三次缩小区间：令令 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.
12、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(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,停止迭代。停止迭代。黄金分割法黄金分割法求
13、的的极小点与极小值：求的的极小点与极小值：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 插值方法插值方法利用一点的利用一点的函数值函数值、一阶导数一阶导数以及以及二阶二阶导数导数构造二次多项构造二次多项式。用构造的二次式。用构造的二次多项式的极小点作多项式的极小点作为原函数极小点的为原函数极小点的近似。近似。x*xf(x)x20(x)x0f(x)1(x)x1一、牛顿法一、牛顿法设设f(x)为一个连续可微的函数
14、，则在点为一个连续可微的函数，则在点x0附近附近进行泰勒展开并保留到二次项：进行泰勒展开并保留到二次项：2000001()()()()()()()2f xxf xfxxxfxxx1()0 x用二次函数用二次函数(x)的极小点的极小点x1作为作为f(x)极小点的一个近似极小点的一个近似点。根据极值必要条件点。根据极值必要条件:3.4 3.4 插值方法插值方法xf(x)x1x20(x)x*f(x)1(x)x00010()()()0fxfxxx即即0100()()fxxxfx依此类推可得依此类推可得牛顿迭代公式：牛顿迭代公式：1()()kkkkfxxxfx一、牛顿法一、牛顿法3.4 3.4 插值方法
15、插值方法x2x1x0 x*f(x)f(x)0(x)1(x)在在x0处用一抛物线处用一抛物线(x)代替曲线代替曲线 f(x)，相当于用一斜直线相当于用一斜直线(x)代替曲线代替曲线 f(x)。这样各个近似点。这样各个近似点是通过对作是通过对作f(x)切切线求得与轴的交点线求得与轴的交点找到的，所以有时找到的，所以有时牛顿法又称作切线牛顿法又称作切线法。法。x2x1x0 x*f(x)f(x)0(x)1(x)f (x)f (x)x*x0 1(x)x2x11kkxx牛顿法牛顿法开开 始始计算计算 ，*1kxx给定初始点给定初始点 ，误差，误差 ,令令k=00 x(),()kkf xf x计算计算 ，1
16、()()kkkkfxxxfx1kk结结 束束数值数值 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.00007kxkfxkfx给定初始点给定初始点x0=3，=0.001，计算公式：，计算公式：1()()kkkkfxxxfx 2122412fxxx函数的
17、二阶导数：函数的二阶导数：32()4121216fxxxx解：解：函数的一阶导数：函数的一阶导数：3.4 3.4 插值方法插值方法1kx1kkxx=优点优点：1）收敛速度快。）收敛速度快。缺点缺点：1）要计算函数的一阶和二阶导数，增加每次）要计算函数的一阶和二阶导数，增加每次 迭代的工作量。迭代的工作量。2）数值微分计算函数二阶导数，舍入误差将）数值微分计算函数二阶导数，舍入误差将 严重影响牛顿法的收敛速度，严重影响牛顿法的收敛速度，f (x)的值越的值越 小问题越严重。小问题越严重。3）牛顿法要求）牛顿法要求初始点离极小点不太远初始点离极小点不太远，否则，否则 可能使极小化序列发散或收敛到非
18、极小点。可能使极小化序列发散或收敛到非极小点。一、牛顿法一、牛顿法3.4 3.4 插值方法插值方法1()()kkkkfxxxfx(1)()()()kkKkXXd二、二次插值法（二、二次插值法（）在给定的在给定的单峰区间单峰区间中，利用目标函数上的中，利用目标函数上的三个点三个点来来构构造造一个一个二次插值函数二次插值函数，以近似地表达，以近似地表达原目标函数原目标函数 f(a)，并，并求这个插值函数的求这个插值函数的极小点极小点近似作为原目标函数的近似作为原目标函数的极小点极小点。3.4 3.4 插值方法插值方法2()=ABCp xxxB=-2Cpxf(x)xf1x1f2x2f3x3xpx*y
19、0 xxp1x1x2xpx3xy0 x*y1y2ypy3x1x2xpx*y1y2ypyp1xpxp1x1x2xpx3xy0 x*y1y2ypy3x2x3xy0 x*y2ypy3yp1211112222223333p()ABCp()ABCp()ABCxxxfxxxfxxxf构造的构造的上的三个点上的三个点:解得解得系数系数222222231312123122331231312123122331()()()()()()()()()()()()xxfxxfxxfBxxxxxxxxfxxfxxfCxxxxxx 222222231312123231312123()()()122()()()pxxfxxf
20、xxfBCxxfxxfxxf 二、二次插值法（二、二次插值法（）3.4 3.4 插值方法插值方法2pxx二次插值法二次插值法开开 始始计算计算 ，*2min,pyyy给定给定 ,123123x x x y y y,ppx y缩短区间缩短区间名称置换名称置换结结 束束x1x2xpx3xy0 x*y1y2ypy3x1x2xpx3x0 x*yy1y2ypy3*2min,pyy y二次插值法程序编制换名方法二次插值法程序编制换名方法(1)(1)1)x2xp y2yp y2xp y2 ypyp y2y2y3xpx1x2x3xx3x2 y2ypypy1y2xpx1x2x3xx1（1 1）二次插值法只要求）
21、二次插值法只要求f(x)连续，不要求其一阶可微；连续，不要求其一阶可微；（2 2）收敛速度比黄金分割法快，但可靠性不如黄金分割）收敛速度比黄金分割法快，但可靠性不如黄金分割 法好，程序也较长。法好，程序也较长。特点：特点：3.4 3.4 插值方法插值方法二、二次插值法（二、二次插值法（）例例 3-3 用二次插值法求函数用二次插值法求函数f(X)=3x3-4x+2的极小点，的极小点，给定给定 x0=0,=0.2。解解 1）确定初始区间确定初始区间:a,b=0,22）用二次插值法逼近极小点用二次插值法逼近极小点 相邻三点的函数值相邻三点的函数值:x1=0,x2=1,x3=2;f1=2,f2=1,f
22、3=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,应继续迭代。应继续迭代。yp y2y2y3xpx3x2x1x2x3xx2x3xp
