第三章 一维搜索方法3.3 一维搜索的试探法3.1 搜索区间的确定3.2 区间消去法原理3.4 一维搜索的插值法一维搜索方法和区间消去法原理求解求解一维目标函数一维目标函数一维目标函数一维目标函数最优解的过程，称为最优解的过程，称为一维优化一维优化一维优化一维优化( (一维一维搜索搜索) )，所使用的方法称为，所使用的方法称为一维优化方法一维优化方法一维优化方法一维优化方法。 由前由前数值迭代法数值迭代法数值迭代法数值迭代法可知，求某目标函数的最优值时，迭代过可知，求某目标函数的最优值时，迭代过程每一步的格式都是从某一定点程每一步的格式都是从某一定点 出发，沿着某一使目标出发，沿着某一使目标函数下降的规定方向函数下降的规定方向 搜索，以找出此方向的极小点搜索，以找出此方向的极小点 。这一过程是各种最优化方法的一种。这一过程是各种最优化方法的一种基本过程基本过程基本过程基本过程。一维搜索方法一维搜索方法一维搜索方法一维搜索方法一般一般分两步进行分两步进行分两步进行分两步进行： 首先确定一个包含函数极小点的初始区间，即确定首先确定一个包含函数极小点的初始区间，即确定 函数的搜索区间，该区间必须是单峰区间；函数的搜索区间，该区间必须是单峰区间； 然后采用缩小区间或插值逼近的方法得到最优步长，然后采用缩小区间或插值逼近的方法得到最优步长， 最终求出该搜索区间内的一维极小点。最终求出该搜索区间内的一维极小点。3.1 3.1 搜索区间的确定搜索区间的确定一维搜索方法和区间消去法原理根据函数的变化情况，可将根据函数的变化情况，可将区间区间区间区间分为单峰区间和多峰区间。分为单峰区间和多峰区间。所谓所谓单峰区间单峰区间单峰区间单峰区间，就是在该区间内的函数变化只有一个峰值，就是在该区间内的函数变化只有一个峰值，即函数的极小值。即函数的极小值。即在即在单峰区间单峰区间单峰区间单峰区间内的内的极小值点极小值点极小值点极小值点X X* * 的左侧：函数呈的左侧：函数呈下降趋势下降趋势下降趋势下降趋势，而在而在单峰区间单峰区间单峰区间单峰区间内的极小值点内的极小值点X* 的右侧：函数呈上升趋势。的右侧：函数呈上升趋势。也就是说，也就是说，单峰区间单峰区间单峰区间单峰区间的函数值呈的函数值呈“ “高高高高- -低低低低- -高高高高” ”的变化特征的变化特征。3.1 3.1 搜索区间的确定搜索区间的确定O f (a) b x* x a 一维搜索方法和区间消去法原理目目前前在在一一维维优优化化搜搜索索中中确确定定单单峰峰区区间间常常用用的的方方法法是进退试算法。是进退试算法。 进退试算法的基本思想进退试算法的基本思想进退试算法的基本思想进退试算法的基本思想为：为： 1)1) 按照一定的规律给出若干试算点，按照一定的规律给出若干试算点， 2)2) 依次比较各试算点的函数值的大小，依次比较各试算点的函数值的大小， 3) 3) 直到找到相邻三点函数值按直到找到相邻三点函数值按“高高- -低低- -高高” 变化的单峰区间为止变化的单峰区间为止3.1 3.1 搜索区间的确定搜索区间的确定一维搜索方法和区间消去法原理进退试算法的进退试算法的运算步骤运算步骤运算步骤运算步骤如下：如下：(2)将将0及及0+h 代入目标函数代入目标函数 f(x) 进行计算并比较大小进行计算并比较大小(1)给定初始点给定初始点0和初始步长和初始步长h3.1 3.1 搜索区间的确定搜索区间的确定一维搜索方法和区间消去法原理 若若 ，则所计算的相邻三点，则所计算的相邻三点 的函数值已具的函数值已具“高高-低低-高高”特征，这时可确定特征，这时可确定 搜索区间搜索区间(3)若若 ，则表明极小点在试算点，则表明极小点在试算点 的右侧，需做前进试算。的右侧，需做前进试算。否则，将步长再加倍，并重复上述运算。否则，将步长再加倍，并重复上述运算。3.1 3.1 搜索区间的确定搜索区间的确定 在做前进运算时，为加速计算，可将步长在做前进运算时，为加速计算，可将步长h 增加增加2倍，并取计算新点为倍，并取计算新点为0+h+2h=0+3h一维搜索方法和区间消去法原理(4)若若 ，则表明极小点在试算点，则表明极小点在试算点 的左侧，需做后退试算。的左侧，需做后退试算。 在做后退运算时，应将步长变为在做后退运算时，应将步长变为-h ，并从，并从 点出点出 发，得到后退点为发，得到后退点为 若若 ，则搜索区间可取为，则搜索区间可取为否则，将步长加倍，继续后退，重复上述步骤，否则，将步长加倍，继续后退，重复上述步骤，直到满足单峰区间条件为止。直到满足单峰区间条件为止。3.1 3.1 搜索区间的确定搜索区间的确定一维搜索方法和区间消去法原理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) 一维搜索方法和区间消去法原理f(a1)f(b1)f(a1)f(b1)f(a1)f(b1)a1a1 a1b1baabab b1 b1(1)f1f2, 新区间为新区间为a1,b;(3)如如f1=f2, 新区间为新区间为a1,b1对于上述缩短后的新区间，可在其内再取一个新点，然后对于上述缩短后的新区间，可在其内再取一个新点，然后将此点和该区间内剩下的那一点进行函数值大小的比较，将此点和该区间内剩下的那一点进行函数值大小的比较，以再次按照上述方法，进一步缩短区间，这样不断进行下以再次按照上述方法，进一步缩短区间，这样不断进行下去，直到所保留的区间缩小到给定的误差范围内，而得到去，直到所保留的区间缩小到给定的误差范围内，而得到近似最优解。近似最优解。新区间为新区间为一维搜索方法和区间消去法原理ab a2a1 a2a a1f(a1)f(a2)f(a2)f(a1)b一、适用范围一、适用范围 适适用用于于a,b区区间间上上的的任任何何单单谷谷函函数数求求极极小小值值问问题题。对对函函数数除除要要求求“单单谷谷”外外不不作作其其他他要要求求，甚甚至至可可以以不不连连续续。适应面相当广。基本原理为区间消去法适应面相当广。基本原理为区间消去法3.3 3.3 黄金分割法黄金分割法黄金分割法插入两点：黄金分割法插入两点：一维搜索方法和区间消去法原理黄金分割法还要求在保留下来的区间内再插入一点所形成黄金分割法还要求在保留下来的区间内再插入一点所形成黄金分割法还要求在保留下来的区间内再插入一点所形成黄金分割法还要求在保留下来的区间内再插入一点所形成的区间新三段，与原来区间的三段具有相同的比例分布的区间新三段，与原来区间的三段具有相同的比例分布的区间新三段，与原来区间的三段具有相同的比例分布的区间新三段，与原来区间的三段具有相同的比例分布 。3.3 3.3 黄金分割法黄金分割法一维搜索方法和区间消去法原理黄金分割法程序框图黄金分割法程序框图 开开 始始输入输入a, b, , Y YN NY YN N结结 束束一维搜索方法和区间消去法原理例例 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）用黄金分割法缩小区间）用黄金分割法缩小区间 第一次缩小区间：第一次缩小区间： 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, 应继续缩小区间应继续缩小区间一维搜索方法和区间消去法原理 第三次缩小区间：第三次缩小区间： 令令 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 (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 插值方法插值方法利用一点的函数值、利用一点的函数值、一阶导数以及二阶一阶导数以及二阶导数构造二次多项导数构造二次多项式。用构造的二次式。用构造的二次多项式的极小点作多项式的极小点作为原函数极小点的为原函数极小点的近似。近似。一维搜索方法和区间消去法原理一、牛顿法一、牛顿法设设f(a)为一个连续可微的函数，则在点为一个连续可微的函数，则在点a0附近附近进行泰勒展开并保留到二次项：进行泰勒展开并保留到二次项：用二次函数用二次函数(a)的极小点的极小点a1作为作为f(a)极小点的一个近似极小点的一个近似点。根据极值必要条件点。根据极值必要条件:3.4 3.4 插值方法插值方法一维搜索方法和区间消去法原理即即依此类推可得牛顿迭代公式：依此类推可得牛顿迭代公式：一、牛顿法一、牛顿法3.4 3.4 插值方法插值方法一维搜索方法和区间消去法原理在在a0处处用用一一抛抛物物线线(a)代代替替曲曲线线f(a)，相相当当于于用用一一斜斜直直线线(a)代代替替曲曲线线f(a) 。这这样样各各个个近近似似点点是是通通过过对对作作f(a)切切线线求求得得与与轴轴的的交交点点找找到到的的，所所以以，有有时时，牛牛顿顿法法又又称称作作切线法。切线法。一维搜索方法和区间消去法原理牛顿法牛顿法程序框图程序框图程序框图程序框图 开开 始始计算计算 ，Y YN N给定初始点给定初始点 ，误差，误差 ,令令k=0计算计算 ，结结 束束一维搜索方法和区间消去法原理数值数值 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.00007例例例例3-2 3-2 给定给定给定给定 ，试用牛顿法计算其极小点。，试用牛顿法计算其极小点。，试用牛顿法计算其极小点。，试用牛顿法计算其极小点。给定初始点给定初始点x0=3，=0.001，计算公式：，计算公式：函数的二阶导数：函数的二阶导数：解：解： 函数的一阶导数：函数的一阶导数：3.4 3.4 插值方法插值方法一维搜索方法和区间消去法原理 优点：优点：1）收敛速度快。）收敛速度快。 缺点：缺点：1）要计算函数的一阶和二阶导数，增加每次）要计算函数的一阶和二阶导数，增加每次 迭代的工作量。迭代的工作量。 2）数值微分计算函数二阶导数，舍入误差将）数值微分计算函数二阶导数，舍入误差将 严重影响牛顿法的收敛速度，严重影响牛顿法的收敛速度， f (x)的值越的值越 小问题越严重。小问题越严重。 3）牛顿法要求初始点离极小点不太远，否则）牛顿法要求初始点离极小点不太远，否则 可能使极小化序列发散或收敛到非极小点。可能使极小化序列发散或收敛到非极小点。一、牛顿法一、牛顿法3.4 3.4 插值方法插值方法一维搜索方法和区间消去法原理二、二次插值法（二、二次插值法（抛物线法抛物线法）a1af(a)2a3a1ff23fa*在给定的单峰区间中，利用目标函数上的三个点来构造在给定的单峰区间中，利用目标函数上的三个点来构造一个二次插值函数，以近似地表达原目标函数，并求一个二次插值函数，以近似地表达原目标函数，并求这个插值函数的极小点近似作为原目标函数的极小点。这个插值函数的极小点近似作为原目标函数的极小点。ap3.4 3.4 插值方法插值方法一维搜索方法和区间消去法原理y0aap1a1a2apa3ay0a*y1y2ypy3a1a2apa*y1y2ypyp1一维搜索方法和区间消去法原理apap1a1a2apa3ay0a*y1y2ypy3a2a3ay0a*y2ypy3yp1一维搜索方法和区间消去法原理构造的构造的二次插值函数曲线通过原函数二次插值函数曲线通过原函数二次插值函数曲线通过原函数二次插值函数曲线通过原函数上的三个点上的三个点: : 解得系数解得系数 可求得可求得可求得可求得二、二次插值法（二、二次插值法（抛物线法抛物线法）3.4 3.4 插值方法插值方法一维搜索方法和区间消去法原理二次插值法二次插值法程序框图程序框图程序框图程序框图 开开 始始计算计算 ，Y YN N给定给定 ,缩短区间缩短区间名称置换名称置换结结 束束一维搜索方法和区间消去法原理a1a2apa3ay0a*y1y2ypy3a1a2apa3a0a*yy1y2ypy3一维搜索方法和区间消去法原理二次插值法程序编制换名方法二次插值法程序编制换名方法(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的极小点，的极小点， 给定给定 x0=0, =0.2。解解 1）确定初始区间）确定初始区间:a,b=0,22）用二次插值法逼近极小点）用二次插值法逼近极小点 相邻三点的函数值相邻三点的函数值: x1=0, x2=1, x3=2; f1=2, f2=1, f3=18. 代入公式：代入公式：xp0.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, 应继续迭代。应继续迭代。一维搜索方法和区间消去法原理