第三章一维搜索(线性搜索)

1、第三章第三章 一维搜索方一维搜索方法法3.1 概述概述3.2 确定初始区间确定初始区间3.3 缩小区间缩小区间3.4 黄金分割法（黄金分割法（0.618法）法）3.5 一维搜索的插值方法一维搜索的插值方法2()0f X12(,)TnXx xx第3章 一维搜索方法3.1 概述3.1.1 一维问题是多维问题的基础 求目标函数 f (X)的极小点，从理论上说需要求解方程：其中那么如何来求 f (X)的极小点呢？基本思想:011,kkXXXX011()() ,()()kkf Xf Xf Xf X 这种方法是逐次迭代的方法，在电子计算机上很容易实现，这种方法是逐次迭代的方法，在电子计算机上很容易实现，因

2、此它在优化设计中被广泛地采用。因此它在优化设计中被广泛地采用。3kkkSXfkkkSXfmin:kkkkSaXX1()f X这个过程称为一维搜索过程。kkkSXf52128)(212221xxxxXF如：如：52202521282212221xxxxF则则000 0 ,1 1TTXd1100X当当Sk方向上的任何一点可以表示为其中是步长因子，为实系数，此时 Sk 方向上任何一点的目标函数值为 ，它是参数的一元函数。那么在沿 Sk 方向求的极小点，这就是求一元函数 的极小问题，它可表示为：)2 , 1 , 0(1kSXXkkk一维搜索示意图一维搜索示意图 求多元函数极值点，需要进行一系列的一维搜

3、索。可见求多元函数极值点，需要进行一系列的一维搜索。可见一一维搜索是优化搜索方法的基础维搜索是优化搜索方法的基础。 求解一元函数求解一元函数 的极小点的极小点 ，可采用，可采用解析解法解析解法，即利用一元函数的极值条件即利用一元函数的极值条件 求求n在用函数在用函数 的导数求的导数求 时，所用的函数时，所用的函数 是仅以步长因子是仅以步长因子 为变量的一元函数，而不是以为变量的一元函数，而不是以设计点设计点 x x 为变量的多元函数为变量的多元函数 。)(*0)(*)(*)()(xf3.1.2 的确定方法的确定方法为了直接利用为了直接利用 的函数式求解最佳步长因子的函数式求解最佳步长因子 。把

4、把 或它的简写形式或它的简写形式 进行泰勒展开，进行泰勒展开，取到二阶项，即取到二阶项，即 将上式对将上式对 进行微分并令其等于零，给出进行微分并令其等于零，给出 极值点极值点 应满足的条件应满足的条件 从而求得从而求得这里是直接利用函数这里是直接利用函数 而不需要把它化成步长因而不需要把它化成步长因子子 。的函数。的函数 。不过，此时需要计算。不过，此时需要计算 点处点处梯度梯度 和海赛矩阵和海赛矩阵 H H 。n 解析解法的缺点解析解法的缺点需要进行求导计算。需要进行求导计算。o 对于函数关系复杂、求导困难或无法求导的情况，使用对于函数关系复杂、求导困难或无法求导的情况，使用解析法将是非常

5、不便的。解析法将是非常不便的。 因此，在优化设计中，求解最佳步长因子因此，在优化设计中，求解最佳步长因子 主要采用主要采用数数值解法值解法，利用计算机通过反复迭代计算求得最佳步长因子，利用计算机通过反复迭代计算求得最佳步长因子的近似值。的近似值。n 数值解法的基本思路是：首先确定数值解法的基本思路是：首先确定 所在的搜索区间，所在的搜索区间，然后根据区间消去法原理不断缩小此区间，从而获得然后根据区间消去法原理不断缩小此区间，从而获得 的数的数 值近似解。值近似解。 解析法解析法: : f(X f(X(k)(k) + S + S(k) (k) ) ) 沿沿S S(k)(k) 方向在方向在x x(

6、k)(k) 点泰勒展开；点泰勒展开； 取二次近似：取二次近似： ( )( )( )( )( )2( )( )( )1()()()2kkkkTkkTkkf xSf xf xSSG xS 0)()()(kkSxfdd对对求导，令其为零。求导，令其为零。 ()()()()()()()0kTkkTkkfxSSG xS()()()()()()()()kTkkkTkkfxSSGxS 求得最优步长求得最优步长1()()()kkkkkffs xx数值解法数值解法基本思路：基本思路： kk 解析解法对于函数关系复杂、求导困难等情况难以解析解法对于函数关系复杂、求导困难等情况难以实现。在实际优化设计中，数值解法的

7、应用更为有效，实现。在实际优化设计中，数值解法的应用更为有效，且适合计算机的运算特点。且适合计算机的运算特点。 一维搜索也称一维搜索也称直线搜索直线搜索。这种方法不仅对于解决。这种方法不仅对于解决一维最优化问题具有实际意义，而且也是求解多维最优一维最优化问题具有实际意义，而且也是求解多维最优化问题的重要支柱。化问题的重要支柱。一维搜索一般分为两大步骤：一维搜索一般分为两大步骤：(1)(1)确定初始搜索区间确定初始搜索区间aa，bb，该区间应是包括一维函数，该区间应是包括一维函数极小点在内的极小点在内的单谷区间单谷区间。(2)(2)在单谷区间在单谷区间a,ba,b内通过缩小区间寻找极小点。内通过

8、缩小区间寻找极小点。 先确定先确定 在的搜索区间，然后根据区间消去法原理在的搜索区间，然后根据区间消去法原理不断缩小此区间所，从而获得不断缩小此区间所，从而获得 的数值近似解。的数值近似解。1、确定搜索区间的外推法 在给定区间内仅有一个谷值（或有唯一的极小点）的函数称为单谷函数，其区间称为单谷区间。函数值：“大小大”图形：“高低高”单谷区间中一定能求得一个极小点。3.2 确定初始区间确定初始区间o 从从 开始，以初始步长开始，以初始步长 向前试探。向前试探。n 如果函数值上升，则步长变号，即改变试探方向。如果函数值上升，则步长变号，即改变试探方向。n 如果函数值下降，则维持原来的试探方向，并将

9、步长加倍。如果函数值下降，则维持原来的试探方向，并将步长加倍。n 区间的始点、中间点依次沿试探方向移动一步。区间的始点、中间点依次沿试探方向移动一步。n 此过程一直进行到函数值再次上升时为止，即可找到搜索此过程一直进行到函数值再次上升时为止，即可找到搜索区间的终点。区间的终点。n 最后得到的三点即为搜索区间的始点、中间三点和终点，最后得到的三点即为搜索区间的始点、中间三点和终点，形成函数值的形成函数值的“高低高高低高”趋势。趋势。单谷区间单谷区间f (x)0130f (x)31说明：单谷区间内，函数可以有不可微点，也可以是不连续函数；基本思想：基本思想：对对 任选一个初始点任选一个初始点 及初

10、始步长及初始步长 ，通过比较这两点函数值的大小，确定第三点位置，比较这通过比较这两点函数值的大小，确定第三点位置，比较这三点的函数值大小，确定是否为三点的函数值大小，确定是否为“高高低低高高”形态。形态。)(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）如果）如果y y1 1yy2 2，向右前进，加大步长，向右前进，加大步长h=2hh=2h0 0，转（，转（3 3）向前；）向前；b

11、 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 ,a b11,a b， 搜索区间确定之后，采用区间消去法逐步缩短搜索区间，从而找到极小点的数值近似解。 假定在搜索区间 内任取两点 ，且 )(2)(111bffaff3.3 区间消去方法区间消去方法(1)(1)f f（a a1 1） f f（b b1 1）, , 则

12、极小点必在区间则极小点必在区间aa，b b1 1 内内; ;)(2)(111bffaff(1)(1)f f（a a1 1） f f（b b1 1）, , 则极小点必在区间则极小点必在区间 1 1，bb内内; ;)(2)(111bffaff(1)(1)f f（a a1 1） f f（b b1 1）, , 则极小点必在区间则极小点必在区间 1 1，bb内内; ;(3)(3)f f（a a1 1）= =f f（b b1 1）, , 则极小点必在区间则极小点必在区间 1 1，b b1 1 内内)(2)(111bffaff可以总结为两种情况：若 ， 则取a,b1为缩小后的搜索区间。若 ，则取a1,b为缩

13、小后的搜索区间。)()(11bfaf)()(11bfaf试探法 黄金分割法插值法 二次插值法3 一维搜索方法分类 从前面的分析可知，每次缩短区间，只需要在区间内再插入一点并计算其函数值。 而插入点的位置，可以由不同的方法来确定。就形成了不同的一维搜索方法。一维搜索方法分类3.4 黄金分割法（0.618法）黄金分割法黄金分割法的搜索过程 概述概述n 在实际计算中，最常用的在实际计算中，最常用的一维搜索试探方法是黄金分割法一维搜索试探方法是黄金分割法，又称作又称作0.6180.618法法。我们可以通过学习黄金分割法来了解一。我们可以通过学习黄金分割法来了解一维搜索试探方法的基本思想。维搜索试探方法

14、的基本思想。n 在搜索区间在搜索区间 a,ba,b内适当插入两点内适当插入两点1 1、2 2，并计算其函，并计算其函数值。数值。1 1、2 2将区间分成三段。应用函数的单谷性质，将区间分成三段。应用函数的单谷性质，通过函数值大小的比较，删去其中一段，使搜索区间得以通过函数值大小的比较，删去其中一段，使搜索区间得以缩短。然后再在保留下来的区间上作同样的处置，如此迭缩短。然后再在保留下来的区间上作同样的处置，如此迭代下去，使搜索区间无限缩小，从而得到极小点的数值近代下去，使搜索区间无限缩小，从而得到极小点的数值近似解。似解。3.4 黄金分割法（0.618法）黄金分割法是建立在区间消去法原理基础上的

15、试探方法。黄金分割法是建立在区间消去法原理基础上的试探方法。o 适用于适用于a,ba,b区间上的任何单谷函数求极小值问题。区间上的任何单谷函数求极小值问题。对函数除要求对函数除要求“单谷单谷”外不作其它要求，甚至可以不连外不作其它要求，甚至可以不连续。因此，这种方法的适应面相当广。续。因此，这种方法的适应面相当广。n 黄金分割法对插入点的要求：黄金分割法对插入点的要求： 1 1）要求插入点）要求插入点1 1、2 2 的位置相对于区间的位置相对于区间a,ba,b两端两端点具有对称性点具有对称性，即，即 其中其中 为待定常数。为待定常数。1()bba2()aba1.黄金分割法黄金分割法2 2）黄金

16、分割法还要求黄金分割法还要求在保留下来的区间内再插入一点所在保留下来的区间内再插入一点所形成的区间新三段，与原来区间的三段具有相同的比形成的区间新三段，与原来区间的三段具有相同的比例分布例分布。 即每次缩小所得的新区间长度与缩小前区间长度即每次缩小所得的新区间长度与缩小前区间长度之比（即：区间收缩率）为定值。之比（即：区间收缩率）为定值。o 设原区间设原区间a,ba,b长度为长度为1 1如下图所示，保留下来的区间如下图所示，保留下来的区间 a,a,2 2 长度为长度为 ，区间缩短率为，区间缩短率为 。为了保持相。为了保持相同的比例分布，新插入点同的比例分布，新插入点 3 3应在应在 位位置上，

17、置上，1 1 在原区间的在原区间的 位置应相当于在保位置应相当于在保留区间的留区间的 位置。故有位置。故有 取方程正数解，得取方程正数解，得ab2111a213(1)2图2-5 黄金分割法)(618. 0)()(618. 0)(21abaabaabbabb两内分点值两内分点值:结论：结论：所谓黄金分割是指将一线段分成两段的方法，使整段长与较长段的长度所谓黄金分割是指将一线段分成两段的方法，使整段长与较长段的长度比值等于较长段与较短段长度的比值即比值等于较长段与较短段长度的比值即 。215 10.6182 黄金分割法要求插入两点：)(618. 0)()(618. 0)(21abaabaabbab

18、b黄金分割法区间消去示意图：3.4 黄金分割法（黄金分割法（0.6180.618法）法）（1）给出初始搜索区间 及收敛精度 ，将 赋以 。 , a b0.618（2）按坐标点计算公式计算 并计算其对应的函数值 12和12,ff3.4 黄金分割法（黄金分割法（0.6180.618法）法）（3）根据区间消去法原理缩短搜索区间。为了能用原来的坐标点计算公式，进行区间名称的代换，并在保留区间中计算一个新的试验点及其函数值。3.4 黄金分割法（黄金分割法（0.6180.618法）法）（4）检查区间是否缩短到足够小和函数值收敛到足够精度，如果收敛条件满足，则取最后两试验点的平均值作为极小点的数值近似解。如

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

20、a也可采用迭代次数是否大于或等于 k 作终止准则。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解：abaabb2139*1()21( 1.3860.665)21.0255ab *()1.0007f 解析解：1,( )1f 例例 3-1 用黄金分割法求函数用黄金分割法求函数f(x)=3x3-4x+2的极小点，给的

21、极小点，给定定 x0=0, h=1, =0.2。解：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=0+0.382(2-0)=0.764, f1=0.282 a2=0+0.618 (2-0)=1.236, f2=2.72 f10.2第二次缩小区间：第二次缩小区间： 令令 x2=x1=0.764, f2=f1=0.282 x1=0+0

22、.382X X(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, 应继续缩小区间。应继续缩小区间。 第三次缩小区间：l令 x1=x2=0.764, f1=f2=0.282l x2=0.472+0.618X(1.236-0.472)=0.944, f2=0.747l由于f10.2, 应继续缩小区间。 第四次缩小区间：第四次缩小区间： 令令 x2=x1=0.764, f2=f1=0.282 x1=0.472+0.382X X(0.944-0.472)=0.6

23、52, f1=0.223 由于由于f10.2, 应继续缩小区间。应继续缩小区间。第五次缩小区间：l令 x2=x1=0.652, f2=f1=0.223l x1=0.472+0.382X(0.764-0.472)=0.584, f1=0.262l由于f1f2, 故新区间a,b=x1,b=0.584, 0.764l因为 b-a=0.764-0.584=0.180.2, 停止迭代。极小点与极小值：x*=0.5X(0.584+0.764)=0.674, f(x*)=0.2223.5 一维搜索的二次插值法一维搜索的二次插值法试探法试探法（如黄金分割法）与（如黄金分割法）与插值法插值法的比较：的比较：不同

24、点不同点：表现在试验点（插入点）位置的确定方法不同。：表现在试验点（插入点）位置的确定方法不同。n多项式是函数逼近的一种常用工具。多项式是函数逼近的一种常用工具。o 在搜索区间内可以利用若干试验点处的函数在搜索区间内可以利用若干试验点处的函数值来构造低次多项式，用它作为函数的近似值来构造低次多项式，用它作为函数的近似表达式，并用这个多项式的极小点作为原函表达式，并用这个多项式的极小点作为原函数极小点的近似。数极小点的近似。n常用的插值多项式为常用的插值多项式为二次多项式。二次多项式。o 牛顿法（切线法）牛顿法（切线法） 利用一点的函数值、一利用一点的函数值、一阶导数值和二阶导数值来构造二次函数

25、。阶导数值和二阶导数值来构造二次函数。1.1. 二次插值法（抛物线法）二次插值法（抛物线法） 利用三个点的函利用三个点的函数值形成一个抛物线来构造二次函数。数值形成一个抛物线来构造二次函数。1、牛顿法（切线法）、牛顿法（切线法） 对于一维搜索函数对于一维搜索函数 ，假定已经给出极小点的一个较，假定已经给出极小点的一个较好的近似点好的近似点 ，在，在 点附近用一个二次函数点附近用一个二次函数 来逼近函数来逼近函数 。 yf00 f 20000012ffff 然后以该二次函数然后以该二次函数 的极小点作为的极小点作为 极小点的一个新的极小点的一个新的近似点近似点 。根据极值必要条件：。根据极值必要

26、条件： f1 0 0100ff 1(0,1,2 )kkkkfkf牛顿法的几何解释：牛顿法的几何解释：1(0,1,2)kkkkfkf在上图中，在在上图中，在 处用一抛物线处用一抛物线 代替曲线代替曲线 ，相当于用一斜线相当于用一斜线 代替代替 。这样各个近似点是。这样各个近似点是通过对通过对 作切线求得与作切线求得与 轴的交点找到，故牛顿法轴的交点找到，故牛顿法又称为切线法。又称为切线法。)(f0)()()(f)(f牛顿法的计算步骤：牛顿法的计算步骤：1 1）给定初始点）给定初始点 0，控制误差，控制误差 ，并令，并令 0k 2 2）计算）计算 ,kkff3 3）求）求 1kkkkff4 4）若

27、）若 1kk，则求得近似解，则求得近似解 ，1k停止计算，否则作停止计算，否则作5 5）。）。 5 5）令）令 1kk转转2 2）。）。 例题：例题： 给定给定 43246164f，试用，试用牛顿法求其极小点牛顿法求其极小点 。 解：解：1 1）给定初始点）给定初始点 03，控制误差，控制误差 0.001 324(334)f 212(21)f01001331366ff31133662 2）3 3）4 4）重复上边的过程，进行迭代，直到重复上边的过程，进行迭代，直到 10.001kk为止。可得到计算结果如下表为止。可得到计算结果如下表: : 表3-2 牛顿法的搜索过程k01234值ak35.16

28、6674.334744.03964.00066f(ak)-52153.3518332.301993.382990.00551f(ak)-24184.33332109.4458686.8699284.04720ak+15.166674.334744.039604.000664.00059优点：收敛速度快。优点：收敛速度快。缺点：每一点都要进行二阶导数，工作量大；缺点：每一点都要进行二阶导数，工作量大； 当用数值微分代替二阶导数，由于舍入误当用数值微分代替二阶导数，由于舍入误差会影响迭代速度；差会影响迭代速度； 要求初始点离极小点不太远，否则有可能要求初始点离极小点不太远，否则有可能使极小化发散或

29、收敛到非极小点。使极小化发散或收敛到非极小点。牛顿法的特点：牛顿法的特点：、二次插值法（抛物线法）、二次插值法（抛物线法）p p（1）二次插值多项式的构成及其极值点）二次插值多项式的构成及其极值点 yf x设 在单谷区间中的三点 123的相应函数值 123()fff，则可以做出如下的二次插值多项式： 2012Paaa21011211Paaaf22012222Paaaf23013233Paaaf多项式多项式 P的极值点可从极值的必要条件求得的极值点可从极值的必要条件求得1220ppPaa，即，即 12/2paa， n为了确定这个极值点，只需计算出系数为了确定这个极值点，只需计算出系数a a1 1

30、和和a a2 2 。其。其方法法是利用方法法是利用a a0 0、a a1 1、a a2 2的联立方程组中相邻两个方程的联立方程组中相邻两个方程消去消去a a0 0 ，从而得到关于，从而得到关于a a1 1、a a2 2的方程组的方程组n 解得解得n 所以所以113212pcac31131ffc21121223ffccf() *p ）如果区间长度 31足够小，则由 31p便得出我们所要求的近似极小点 p2 2）如果不满足，必须缩小区间）如果不满足，必须缩小区间 13, ，根据区间消取法，根据区间消取法原理不断缩小区间。原理不断缩小区间。根据区间消去法原理，需要已知根据区间消去法原理，需要已知区间

31、内两点的函数值。其中点区间内两点的函数值。其中点2 2的函数值的函数值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 为缩短后为缩短后的搜索区间。的搜索区间。 二二次次插插值值法法程程序序框框图图例1： 用二次插值法求 sin45f在上的极小点。 12144.524.54.705120355y1-0.756802 -0.977590y2

32、-0.977590-0.999974y3-0.958924 -0.958924p4.7051204.710594yp-0.999974-0.999998例例 2 2 用二次插值法求函数用二次插值法求函数f f( (x x)=3)=3x x3 3-4-4x x+2+2的极小点，的极小点，给定给定 x x0 0=0, =0, =0.2=0.2。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. =

33、18. 代入公式：代入公式：222222*2313121232313121231 ()()()2 ()()()pxxfxxfxxfxxxfxx fxxfx xp p* *0.555, f0.555, fp p=0.292=0.292解解 : : 1 1）确定初始区间）确定初始区间初始区间初始区间 a a, , b b=0, 2, =0, 2, 中间点中间点x x2 2=1, =1, f f( (x x2 2)=1)=1。由于由于f fp p f f2 2, , x xp p * * 0.2, |=1-0.555=0.4450.2, 应继续迭代。应继续迭代。在新区间，相邻三点的函数值在新区间，相

34、邻三点的函数值: : 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=1, =1, 代入代入x xp p* *公式计算得：公式计算得：x xp p* *0.607, f0.607, fp p=0.243=0.243 由于由于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

35、.555-0.607|=0.0520.2, 迭代终止。迭代终止。 x xp p* *0.607, f0.607, f* *=0.243=0.243例例 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=19=19，f f2 2=-96.9375=-96.9375，f f3 3=124=124。可见函数值满足。可见函数值满足“高低高高低高”形态。形态。2130.5 ()2.5xxx以以x x1 1, , x x2 2, , x x3 3为插值点构造二次曲线。为插值点构造二次曲线。求第一次近似的二次曲线求第一次近似的二次曲线p p(