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

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

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

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

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

5、邻三点，则所计算的相邻三点 的函数值已具的函数值已具“高高-低低-高高”特征，这时可确定特征，这时可确定 搜索区间搜索区间 (3)若若 ，则表明极小点在试算点，则表明极小点在试算点 的右侧，需做前进试算。的右侧，需做前进试算。 00 ()()ffh 00 ()(3 )fhfh 00 , 3abh 否则，将步长再加倍，并重复上述运算。否则，将步长再加倍，并重复上述运算。 3.1 3.1 搜索区间的确定搜索区间的确定 在做前进运算时，为加速计算，可将步长在做前进运算时，为加速计算，可将步长h 增加增加2倍，并取计算新点为倍，并取计算新点为0+h+2h=0+3h 一维搜索方法和区间消去法原理 (4)

6、若若 ，则表明极小点在试算点，则表明极小点在试算点 的左侧，需做后退试算。的左侧，需做后退试算。 在做后退运算时，应将步长变为在做后退运算时，应将步长变为-h ，并从，并从 点出点出 发，得到后退点为发，得到后退点为 若若 ，则搜索区间可取为，则搜索区间可取为 00 ()()ffh 00 ()()fhf 00 , ahbh 0 0 h 否则，将步长加倍，继续后退，重复上述步否则，将步长加倍，继续后退，重复上述步 骤，直到满足单峰区间条件为止。骤，直到满足单峰区间条件为止。 3.1 3.1 搜索区间的确定搜索区间的确定 一维搜索方法和区间消去法原理 f(b1)f(a1) f(b1) f(a1)f

7、(b1) a f(a1) 搜索区间确定之后，采用区间消去法逐步缩短搜索区间，搜索区间确定之后，采用区间消去法逐步缩短搜索区间， 找到极小点的数值近似解。找到极小点的数值近似解。 假定在搜索区间内假定在搜索区间内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) a1 a1 a1b1 ba a b a b b1 b1 (1)f1f2, 新区间为新区间为a1,b; (3)如如f1=f2, 新区间为新区间为a1,b1 12 ff 1 , a b 对于

8、上述缩短后的新区间，可在其内再取一个新点，然后对于上述缩短后的新区间，可在其内再取一个新点，然后 将此点和该区间内剩下的那一点进行函数值大小的比较，将此点和该区间内剩下的那一点进行函数值大小的比较， 以再次按照上述方法，进一步缩短区间，这样不断进行下以再次按照上述方法，进一步缩短区间，这样不断进行下 去，直到所保留的区间缩小到给定的误差范围内，而得到去，直到所保留的区间缩小到给定的误差范围内，而得到 近似最优解。近似最优解。 新区间为新区间为 一维搜索方法和区间消去法原理 111 222 (1)(),( ) (),() aabaff a aabaff a ab a2a1 a2a a1 f(a1

9、) f(a2) f(a2) f(a1) b 一、适用范围一、适用范围 适用于适用于a,b区间上的任何单谷函数求极小值问题。对区间上的任何单谷函数求极小值问题。对 函数除要求函数除要求“单谷单谷”外不作其他要求，甚至可以不连外不作其他要求，甚至可以不连 续。适应面相当广。基本原理为区间消去法续。适应面相当广。基本原理为区间消去法 3.3 3.3 黄金分割法黄金分割法 黄金分割法插入两点：黄金分割法插入两点： 一维搜索方法和区间消去法原理 ab 2 1 1 1 a 2 1 3 (1) 2 2 1 51 0.618 2 3.3 3.3 黄金分割法黄金分割法 一维搜索方法和区间消去法原理 ab 黄金分

10、割法程序框图黄金分割法程序框图 开开 始始 输入输入a, b, , 1 2 0.382() 0.618() xaba xaba 12 ( )()f xf x 22121 111 , 0.382(),( ) bx xx ff xabaff x 11212 222 , 0.618(),() ax xxff xabaff x * 0.5(),()xabff x 结结 束束 一维搜索方法和区间消去法原理 例例 3-1 用黄金分割法求函数用黄金分割法求函数f(x)=3x3-4x+2的极小点，的极小点， 初始点初始点 x0=0, 步长步长h=1,精度精度 =0.2。 解：解： 1）确定初始区间）确定初始区

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

12、小区间应继续缩小区间 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, 应继续缩小区间应继续缩小区间 一维搜索方法和区间消去法原理 第三次缩小区间：第三次缩小区间： 令令 x1=x2=0.764, f1=f2=0.282 x2=0.472+0.618 (1.236-0.472)=0.944, f2=0.7

13、47 由于由于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 (0.764-0.472)=0.584, f1=0.262 由于由于f1f2, 故新区间故新区间a,b=x1,b=

14、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.222 3.3 3.3 黄金分割法黄金分割法 求导运算求的极小点与极小值：求导运算求的极小点与极小值： x=0.667, f(x)=0.222 一维搜索方法和区间消去法原理 一、牛顿法一、牛顿法 3.4 3.4 插值方法插值方法 利用一点的函数值、利用一点的函数值、 一阶导数以及二阶一阶导数以及二阶 导数构造二次多项导数构造二次多项 式。用构造的二次式。用

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

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

17、索方法和区间消去法原理 1kk aa 牛顿法牛顿法 开开 始始 计算计算 ， * 1k aa 给定初始点给定初始点 ，误差，误差 , 令令k=0 0 a ( ),( ) kk ff 计算计算 ， 1 () () k kk k fa aa fa 1kk 结结 束束 一维搜索方法和区间消去法原理 数值数值 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

18、4.00066 4.00059 2.1667 0.83196 0.29514 0.03894 0.00007 41664 234 xxxxxF k x k x F k x F 给定初始点给定初始点x0=3，=0.001，计算公式：，计算公式： 1 () () k kk k F x xx Fx 122412 2 xxxF函数的二阶导数：函数的二阶导数： 1612124 23 xxxxF解：解： 函数的一阶导数：函数的一阶导数： 3.4 3.4 插值方法插值方法 1k x 一维搜索方法和区间消去法原理 优点：优点：1）收敛速度快。）收敛速度快。 缺点：缺点：1）要计算函数的一阶和二阶导数，增加每次

19、）要计算函数的一阶和二阶导数，增加每次 迭代的工作量。迭代的工作量。 2）数值微分计算函数二阶导数，舍入误差将）数值微分计算函数二阶导数，舍入误差将 严重影响牛顿法的收敛速度，严重影响牛顿法的收敛速度， f (x)的值越的值越 小问题越严重。小问题越严重。 3）牛顿法要求初始点离极小点不太远，否则）牛顿法要求初始点离极小点不太远，否则 可能使极小化序列发散或收敛到非极小点。可能使极小化序列发散或收敛到非极小点。 一、牛顿法一、牛顿法 3.4 3.4 插值方法插值方法 一维搜索方法和区间消去法原理 二、二次插值法（二、二次插值法（） a1a f(a) 2 a 3 a 1 f f2 3 f a*

20、在给定的单峰区间中，利用目标函数上的三个点来构在给定的单峰区间中，利用目标函数上的三个点来构 造一个二次插值函数，以近似地表达原目标函数，并造一个二次插值函数，以近似地表达原目标函数，并 求这个插值函数的极小点近似作为原目标函数的极小点。求这个插值函数的极小点近似作为原目标函数的极小点。 ( )f a ap 3.4 3.4 插值方法插值方法 2 ( )=ABCp a B =- 2C p a 一维搜索方法和区间消去法原理 y 0 a ap1 a1 a2 ap a3 a y 0 a* y1 y2 yp y3 a1 a2 apa* y1 y2 yp yp1 一维搜索方法和区间消去法原理 apap1

21、a1a2ap a3 a y 0 a* y1 y2 yp y3 a2a3 a y 0 a* y2 yp y3 yp1 一维搜索方法和区间消去法原理 2 1111 2 2222 2 3333 p()ABC p()ABC p()ABC f f f 构造的构造的上的三个点上的三个点: : 解得系数解得系数 222222 231312123 122331 231312123 122331 ()()() ()()() ()()() ()()() fff B fff C 222222 231312123 231312123 1 ()()() 22 ()()() p Bfff Cfff 二、二次插值法（二、二次插值法（） 3.4 3.4 插值方法插值方法 一维搜索方法和区间消去法原理 2p yy 二次插值法二次插值法 开开 始始 计算计算 ， * 2 min, p yyy 给定给定 , 123123 a a a y y y , pp y 缩短区间缩短区间 名称置换名称置换 结结 束束 一维搜索方法和区间消去法原理 a1a2ap a3 a y 0 a* y1 y2 yp y3 a1a2apa3 a 0 a* y y1 y2 yp y3 * 2 min, p yy y 一维搜索方法和区间消去法原理 二次插值法程序编制换名方法二次插值法程序编制换名方法(1)(1) 1)