第3章一维搜索方法

1、机械优化设计第三章第三章 一维搜索方法一维搜索方法机械优化设计 当采用数学规划法寻求多元函数的极值点时，一般要进行当采用数学规划法寻求多元函数的极值点时，一般要进行一系列如下格式的迭代计算：一系列如下格式的迭代计算：1(0,1,2)kkkkXXdkkdk当方向当方向给定，求最佳步长给定，求最佳步长就是求一元函数就是求一元函数1kkkkkfxfxd 的极值问题。这一过程被称为的极值问题。这一过程被称为一维搜索一维搜索。 机械优化设计v求多元函数极值点，需要进行一系列的一维搜索。求多元函数极值点，需要进行一系列的一维搜索。可见可见一维搜索是优化搜索方法的基础一维搜索是优化搜索方法的基础。v求解一元

2、函数求解一元函数 的极小点的极小点 ，可采用，可采用解析解法解析解法，即利用一元函数的极值条件即利用一元函数的极值条件 求求在用函数在用函数 的导数求的导数求 时，所用的函数时，所用的函数 是仅以步长因子是仅以步长因子 为变量的一元函数，而不是为变量的一元函数，而不是以设计点以设计点 x x 为变量的多元函数为变量的多元函数 。)(*0)(*)(*)()(xf机械优化设计为了直接利用为了直接利用 的函数式求解最佳步长因子的函数式求解最佳步长因子 。可把。可把 或它的简写形式或它的简写形式 进行泰勒展开，取进行泰勒展开，取到二阶项，即到二阶项，即 将上式对将上式对 进行微分并令其等于零，给出进行

3、微分并令其等于零，给出 极值点极值点 应满足的条件应满足的条件 从而求得从而求得机械优化设计 这里是直接利用函数这里是直接利用函数 而不需要把它化成步长因而不需要把它化成步长因子子 。的函数。的函数 。不过，此时需要计算。不过，此时需要计算 点点处的梯度处的梯度 和海赛矩阵和海赛矩阵 。解析解法的缺点解析解法的缺点需要进行求导计算。需要进行求导计算。v对于函数关系复杂、求导困难或无法求导的情况，使对于函数关系复杂、求导困难或无法求导的情况，使用解析法将是非常不便的。用解析法将是非常不便的。v因此，在优化设计中，求解最佳步长因子因此，在优化设计中，求解最佳步长因子 主要采用主要采用数值数值解法解

4、法，利用计算机通过反复迭代计算求得最佳步长因子的近，利用计算机通过反复迭代计算求得最佳步长因子的近似值。似值。数值解法的基本思路是：首先确定数值解法的基本思路是：首先确定 所在的搜索区间，所在的搜索区间，然后根据区间消去法原理不断缩小此区间，从而获得然后根据区间消去法原理不断缩小此区间，从而获得 的数值近似解。的数值近似解。机械优化设计一维搜索是优化搜索方法的基础。一维搜索是优化搜索方法的基础。机械优化设计0)(* 一维搜索方法解析法高等数学已学过，一维搜索方法解析法高等数学已学过，即利用一维函数的极值条件：即利用一维函数的极值条件： 一维搜索也称直线搜索。这种方法不仅对一维搜索也称直线搜索。

5、这种方法不仅对于解决一维最优化本身具有实际意义，而且也于解决一维最优化本身具有实际意义，而且也是解多维最优化问题的重要支柱。是解多维最优化问题的重要支柱。求求*一维搜索方法数值解法分类一维搜索方法数值解法分类试探法插值法机械优化设计1. 解析法：解析法： 步骤步骤: : f(X f(X(k)(k) + S + S(k) (k) ) ) 沿沿S S(k)(k) 方向在方向在x x(k)(k) 点点进行泰勒展开；进行泰勒展开； 取二次近似：取二次近似： ( )( )( )( )( )2( )( )( )1() ()()2kkkkTkk Tkkf xSf xf xSSGxS1()()()kkkkkf

6、fs xx机械优化设计0)()()(kkSxfdd对对求导，令其为零。求导，令其为零。 ( )( )( )( )( )()()0kTkkTkkf xSSG xS( )( )( )( )( )( )()()kTkkkTkkf xSSG xS 求得最优步长求得最优步长机械优化设计数值解法数值解法基本思路：基本思路： kk 先确定先确定 所在的搜索区间，然后根据区间消去法原理所在的搜索区间，然后根据区间消去法原理不断缩小此区间，从而获得不断缩小此区间，从而获得 的数值近似解。的数值近似解。 解析解法对于函数关系复杂、求导困难等情况难以解析解法对于函数关系复杂、求导困难等情况难以实现。在实际优化设计中

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

8、小点。内通过缩小区间寻找极小点。机械优化设计1 1、确定搜索区间的外推法、确定搜索区间的外推法 在给定区间内仅有一个谷值（或有唯一的极小点）的在给定区间内仅有一个谷值（或有唯一的极小点）的函数称为函数称为单谷函数单谷函数，其区间称为，其区间称为单谷区间。单谷区间。函数值：函数值：“大大小小大大”图形：图形：“高高低低高高”单谷区间中一定能求得一个极小点。单谷区间中一定能求得一个极小点。机械优化设计v从从 开始，以初始步长开始，以初始步长 向前试探。向前试探。如果函数值上升，则步长变号，即改变试探方向。如果函数值上升，则步长变号，即改变试探方向。如果函数值下降，则维持原来的试探方向，并将步长加倍

9、。如果函数值下降，则维持原来的试探方向，并将步长加倍。区间的始点、中间点依次沿试探方向移动一步。区间的始点、中间点依次沿试探方向移动一步。此过程一直进行到函数值再次上升时为止，即可找到搜索区此过程一直进行到函数值再次上升时为止，即可找到搜索区间的终点。间的终点。最后得到的三点即为搜索区间的始点、中间三点和终点，形最后得到的三点即为搜索区间的始点、中间三点和终点，形成函数值的成函数值的“高低高高低高”趋势。趋势。单谷区间机械优化设计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=

11、2hh=2h0 0，转（，转（3 3）向前；）向前；b 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 2yy3 3，则初始区间得到：，则初始区间得到：a=minaa=mina1 1,a,a3 3,b=maxa,b=maxa1 1,a,a3 3 ，函数最小值所在区间为，函数最小值所在区间为a,ba,b。机械优化设计v右图表示沿右图表示沿 的正向试探。的正向试探。每走一步都将区间的始点、每走一步都将区间的始点、中间点沿试探方向移动一中间点沿试

12、探方向移动一步（进行换名）。经过三步（进行换名）。经过三步最后确定搜索步最后确定搜索间间 ，并且得到区，并且得到区间始点、中间点和终点间始点、中间点和终点 所对应的函数所对应的函数值值 。31,321321yyyy1y3y2y2y1a3a2a2a1a1Oaa3h0h02h0图图3-2 3-2 正向搜索的外推法正向搜索的外推法机械优化设计v右图所表示的情况是：开右图所表示的情况是：开始是沿始是沿 的正方向试探，的正方向试探，但由于函数值上升而改变但由于函数值上升而改变了试探方向，最后得到始了试探方向，最后得到始点，中间点和终点点，中间点和终点 及它们的对应函数及它们的对应函数值值 ，从而形成单，

13、从而形成单谷区间为一维搜索区谷区间为一维搜索区间间 。y1y2a2a3a1a2a1Oaa32h0h0h0y3y1y2y1y2y3a1a2图图3-3 3-3 反向搜索的外推法反向搜索的外推法机械优化设计机械优化设计khx1x2x30h0初始点初始点+ h012h0初始点初始点+ h0初始点+3h024h0初始点+ h0初始点+3h0初始点+7h038h0初始点+3h0初始点+7h0初始点+15h0前进搜索步骤表前进搜索步骤表机械优化设计khx1x2x30h0初始点初始点+ h012h0初始点+ h0初始点初始点-2h024h0初始点初始点-2h0初始点-6h038h0初始点-2h0初始点-6h0

14、初始点-14h0后退搜索步骤表后退搜索步骤表机械优化设计. 1 . 0, 0,983)(. 1013hxxxxf初始进退距初始点给定的一维优化初始区间用外推法确定函数例题:解khx1 y1x2 y2x3 y300.10.20 90.1 8.2030.3 6.68110.40.1 8.2030.3 6.6810.7 4.42920.80.3 6.6810.7 4.4291.5 7.125.5 .1, 3 .0,ba可得初始搜索区间机械优化设计. 1 . 0, 8 . 1,983)(. 2013hxxxxf初始进退距初始点给定的一维优化初始区间用外推法确定函数例题:解khx1 y1x2 y2x3

15、y300.1-0.21.8 12.096 1.9 14.3771.9 14.3771.8 12.0961.6 8.488 1-0.41.8 12.0961.6 8.4881.2 4.5842-0.81.6 8.4881.2 4.5840.4 5.992 .6 . 1, 4 . 0,ba可得初始搜索区间x0.9426最优点为机械优化设计基本思想：基本思想： ,a b11,a b11ab，搜索区间确定之后搜索区间确定之后，采用区间消去法逐步缩短，采用区间消去法逐步缩短搜索区间，从而找到极小点的数值近似解。搜索区间，从而找到极小点的数值近似解。在搜索区间在搜索区间 内任取两点内任取两点 且且 计算其

16、函数值得如下计算其函数值得如下于是将有下列三种可能情形：于是将有下列三种可能情形：机械优化设计v(1)f（a1）f（b1）, 则极小点必在区间则极小点必在区间1，b内内;v(3)f（a1）=f（b1）, 则极小点必在区间则极小点必在区间1，b1内内f(a1)f(b1)f(a1)f(b1)f(a1)f(b1)a1a1 a1b1baabab b1 b1机械优化设计根据以上所述，只要在区间根据以上所述，只要在区间 a,b a,b 内取两个点，算内取两个点，算出它们的函数值并加以比较，就可以把搜索区间出它们的函数值并加以比较，就可以把搜索区间 a,b a,b 缩短成缩短成a,ba,b1 1 ，1 1，

17、bb 或或 1 1，b b1 1 。对于第一种情况，我们已算出区间对于第一种情况，我们已算出区间a,ba,b1 1 内内 1 1点的函数值，如果要把搜索区间点的函数值，如果要把搜索区间a,ba,b1 1 进一步缩短，只需在其内再取一点算出函数值进一步缩短，只需在其内再取一点算出函数值并与并与f（1） 加以比较，即可达到目的。加以比较，即可达到目的。对于第二种情况，同样只需再计算一点函数值就对于第二种情况，同样只需再计算一点函数值就可以把搜索区间继续缩短。可以把搜索区间继续缩短。机械优化设计v第三种情形与前面两种情形不同，因为在区间第三种情形与前面两种情形不同，因为在区间 1 1，b b1 1

18、内缺少已算出的函数值。要想把区内缺少已算出的函数值。要想把区间间 1 1，b b1 1 进一步缩短，需在其内部取两个进一步缩短，需在其内部取两个点（而不是一个点）计算出相应的函数值再加点（而不是一个点）计算出相应的函数值再加以比较才行。以比较才行。v如果经常发生这种情形，为了缩短搜索区间，如果经常发生这种情形，为了缩短搜索区间，需要多计算一倍数量的函数值，这就增加了计需要多计算一倍数量的函数值，这就增加了计算工作量。算工作量。机械优化设计若若 则取则取 为缩短后的搜索区间。为缩短后的搜索区间。若若 则取则取 为缩短后的搜索区间。为缩短后的搜索区间。11( )( )f af b1 ,a b11(

19、)()f af b1 , a b机械优化设计3 3、一维搜索方法分类、一维搜索方法分类根据插入点位置的确定方法，可以把一维搜索根据插入点位置的确定方法，可以把一维搜索法分成两大类：法分成两大类：试探法试探法：即按照某种规律来确定区间内插入点的位：即按照某种规律来确定区间内插入点的位置，置，此点位置的确定仅仅按照区间缩短如何加快，此点位置的确定仅仅按照区间缩短如何加快，而不顾及函数值的分布关系。而不顾及函数值的分布关系。如黄金分割法，裴波如黄金分割法，裴波纳契法等。纳契法等。裴波纳契数列：裴波纳契数列：1 1、1 1、2 2、3 3、5 5、8 8、1313、2121、3434、5555、898

20、9、144144 插值法（函数逼近法）：插值法（函数逼近法）：通过构造插值函数来逼通过构造插值函数来逼近原函数，用插值函数的极小点作为区间的插入近原函数，用插值函数的极小点作为区间的插入点，点，如如牛顿法（切线法）、二次插值法（抛物线牛顿法（切线法）、二次插值法（抛物线法）、三次插值法等。法）、三次插值法等。机械优化设计v概述概述在实际计算中，最常用的在实际计算中，最常用的一维搜索试探方法是黄金分割法一维搜索试探方法是黄金分割法，又称作又称作0.6180.618法法。我们可以通过学习黄金分割法来了解一维。我们可以通过学习黄金分割法来了解一维搜索试探方法的基本思想。搜索试探方法的基本思想。在搜索

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

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

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

24、间的 位置应相当于在保位置应相当于在保留区间的留区间的 位置。故有位置。故有 取方程正数解，得取方程正数解，得机械优化设计ab2111a213(1)2图2-5 黄金分割法)(618. 0)()(618. 0)(21abaabaabbabb两内分点值两内分点值:结论：结论：所谓黄金分割所谓黄金分割是指将一线段分成两段的方法，是指将一线段分成两段的方法，使整段长与较长段的长度比值等于较长段与较短段使整段长与较长段的长度比值等于较长段与较短段长度的比值即长度的比值即 。215 10.6182 机械优化设计（1）给出初始搜索区间给出初始搜索区间 及收敛精度及收敛精度 ，将，将 赋以赋以 , a b0.

25、618（2）按坐标点计算公式计算按坐标点计算公式计算 并计算其对应的函并计算其对应的函数值数值 12和12,ff（3）根据区间消去法原理缩短搜索区间。为了能用原来的）根据区间消去法原理缩短搜索区间。为了能用原来的坐标点计算公式，进行区间名称的代换，并在保留区间中坐标点计算公式，进行区间名称的代换，并在保留区间中计算一个新的试验点及其函数值。计算一个新的试验点及其函数值。（4）检查区间是否缩短到足够小和函数值收敛到足够近，）检查区间是否缩短到足够小和函数值收敛到足够近，如果条件不满足返回到步骤（如果条件不满足返回到步骤（2）。）。（5）如果条件满足，则取最后两试验点的平均值作为极小）如果条件满足

26、，则取最后两试验点的平均值作为极小点的数值近似解。点的数值近似解。618.0ln)/(lnabk缩短区间的总次数（迭代次数）缩短区间的总次数（迭代次数）:机械优化设计给定给定,ba)(),(618. 0222xfyabax)(),(382. 0111xfyabax21yy 否否否否21211,yyxxxa)(),(618. 0222xfyabax是是)(),(382. 0111xfyabax12122,yyxxxbab是是)()(5 . 0 xffbax止止xfab1x2x1y2y1x2xbxfab1x2x1y2y1x2xa也可采用迭代次数是否大于或等于也可采用迭代次数是否大于或等于 k k

27、作终止准则。作终止准则。机械优化设计 22f35 对函数对函数，当给定搜索区间，当给定搜索区间时，试用黄金分割法求极小点时，试用黄金分割法求极小点。迭代序号ab0 0-3-30.0560.0561.9441.9445 50.1150.115 7.6677.6671 1-3-3-1.111-1.1110.0560.0561.9441.944-0.987-0.987-0.987-0.9873 3-1.832-1.832-1.111-1.111-0.665-0.6650.0560.056-0.987-0.987-0.987-0.9875 5-1.386-1.386-1.111-1.111-0.940

28、-0.940-0.66511()( 1.3860.665)1.025522ab 机械优化设计例例 3-1 用黄金分割法求函数用黄金分割法求函数f(x)=3x3-4x+2的极小点，给的极小点，给定定 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）用黄金分割法缩小区间）用

29、黄金分割法缩小区间 第一次缩小区间：第一次缩小区间： a1=0+0.382(2-0)=0.764, f1=0.282 a2=0+0.618 (2-0)=1.236, f2=2.72 f10.2机械优化设计第二次缩小区间：第二次缩小区间：v令令 x2=x1=0.764, f2=f1=0.282v x1=0+0.382X X(1.236-0)=0.472, f1=0.317v由于由于f1f2, 故新区间故新区间a,b=x1,b=0.472, 1.236v因为因为 b-a=1.236-0.472=0.7640.2, 应继续缩小区间。应继续缩小区间。 第三次缩小区间：第三次缩小区间：l令令 x1=x2

30、=0.764, f1=f2=0.282l x2=0.472+0.618X X(1.236-0.472)=0.944, f2=0.747l由于由于f10.2, 应继续缩小区间。应继续缩小区间。机械优化设计 第四次缩小区间：第四次缩小区间：v令令 x2=x1=0.764, f2=f1=0.282v x1=0.472+0.382X X(0.944-0.472)=0.652, f1=0.223v由于由于f10.2, 应继续缩小区间。应继续缩小区间。第五次缩小区间：第五次缩小区间：l令令 x2=x1=0.652, f2=f1=0.223l x1=0.472+0.382X X(0.764-0.472)=0

31、.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 X(0.584+0.764)=0.674, f(x*)=0.222机械优化设计机械优化设计试探法试探法（如黄金分割法）与（如黄金分割法）与插值法插值法的比较：的比较：不同点不同点：表现在试验点（插入点）位置的确定方法不同。：表现在试验点（插入点）位置的确定方法不同。机械优化设计多项式是函数逼近的一种常用工具。多项式是函数逼近的一种常用工具。v在搜索区间内可以利

32、用若干试验点处的函数在搜索区间内可以利用若干试验点处的函数值来构造低次多项式，用它作为函数的近似值来构造低次多项式，用它作为函数的近似表达式，并用这个多项式的极小点作为原函表达式，并用这个多项式的极小点作为原函数极小点的近似。数极小点的近似。常用的插值多项式为常用的插值多项式为二次多项式。二次多项式。v牛顿法（切线法）牛顿法（切线法） 利用一点的函数值、一利用一点的函数值、一阶导数值和二阶导数值来构造二次函数。阶导数值和二阶导数值来构造二次函数。1.1.二次插值法（抛物线法）二次插值法（抛物线法） 利用三个点的函利用三个点的函数值形成一个抛物线来构造二次函数。数值形成一个抛物线来构造二次函数。

33、机械优化设计1、牛顿法（切线法）、牛顿法（切线法） 对于一维搜索函数对于一维搜索函数 ，假定已经给出，假定已经给出极小点的一个较好的近似点极小点的一个较好的近似点 ，在，在 点附近用点附近用一个二次函数一个二次函数 来逼近函数来逼近函数 yf00 f 20000012ffff 然后以该二次函数然后以该二次函数 的极小点作为的极小点作为 极小极小点的一个新的近似点点的一个新的近似点 。根据极值必要条件：。根据极值必要条件： f1 0 0100ff 1(0,1,2 )kkkkfkf机械优化设计牛顿法的几何解释：牛顿法的几何解释：在上图中，在在上图中，在 处用一抛物线处用一抛物线 代替曲线代替曲线

34、，相当于用一斜线相当于用一斜线 代替代替 。这样各个近似点是。这样各个近似点是通过对通过对 作切线求得与作切线求得与 轴的交点找到，故牛顿法轴的交点找到，故牛顿法又称为切线法。又称为切线法。)(f0)()()(f)(f1(0,1,2)kkkkfkf机械优化设计牛顿法的计算步骤：牛顿法的计算步骤：1 1）给定初始点）给定初始点 0，控制误差，控制误差 ，并令，并令 0k 2 2）计算）计算 ,kkff3 3）求）求 1kkkkff4 4）若）若 1kk，则求得近似解则求得近似解 ，1k停止计算，否则作停止计算，否则作5 5）。）。 5 5）令）令 1kk转转2 2）。）。 机械优化设计例题：例题

35、： 给定给定 43246164f，试用，试用牛顿法求其极小点牛顿法求其极小点 。 解：解：1 1）给定初始点）给定初始点 03，控制误差控制误差 0.001 324(334)f 212(21)f01001331366ff31133662 2）3 3）4 4）机械优化设计重复上边的过程，进行迭代，直到重复上边的过程，进行迭代，直到 10.001kk为止。可得到计算结果如下表为止。可得到计算结果如下表: : 表3-2 牛顿法的搜索过程k01234值ak35.166674.334744.03964.00066f(ak)-52153.3518332.301993.382990.00551f(ak)-2

36、4184.33332109.4458686.8699284.04720ak+15.166674.334744.039604.000664.00059机械优化设计优点：收敛速度快。优点：收敛速度快。缺点：每一点都要进行二阶导数，工作量大；缺点：每一点都要进行二阶导数，工作量大； 当用数值微分代替二阶导数，由于舍入误差当用数值微分代替二阶导数，由于舍入误差会影响迭代速度；会影响迭代速度； 要求初始点离极小点不太远，否则有可能使要求初始点离极小点不太远，否则有可能使极小化发散或收敛到非极小点。极小化发散或收敛到非极小点。牛顿法的特点：牛顿法的特点：机械优化设计、二次插值法（抛物线法）、二次插值法（抛

37、物线法）p机械优化设计（1）二次插值多项式的构成及其极值点）二次插值多项式的构成及其极值点 yf x设设 在单谷区间中的三点在单谷区间中的三点 123的相应函数值的相应函数值 123()fff，则可以做出，则可以做出如下的二次插值多项式：如下的二次插值多项式： 2012Paaa21011211Paaaf22012222Paaaf23013233Paaaf机械优化设计多项式多项式 P的极值点可从极值的必要条件求得的极值点可从极值的必要条件求得1220ppPaa，即，即 12/2paa ， n为了确定这个极值点，只需计算出系数为了确定这个极值点，只需计算出系数a a1 1和和a a2 2 。其方法

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

39、间消去法原理，需要已根据区间消去法原理，需要已知区间内两点的函数值。其中知区间内两点的函数值。其中点点2的函数值的函数值y2=f（2） 已知，另外一点可取已知，另外一点可取p点并计点并计算其函数值算其函数值yp=f（p）。当当 y20h0）或反向搜索（）或反向搜索（h0h0）的不同，具体换名有如下）的不同，具体换名有如下表所示的八种情况。（表所示的八种情况。（P56)P56)机械优化设计机械优化设计n上表中的中的上表中的中的 h h 就是在进行外推法时求初始就是在进行外推法时求初始搜索区间过程中所形成的最后步长，搜索区间过程中所形成的最后步长，h h 可正可可正可负，分别对应于沿负，分别对应于

40、沿 正向或反向进行的一维正向或反向进行的一维搜索。搜索。n分析上述八种换名情况可知，如果乘积分析上述八种换名情况可知，如果乘积 的符号相同，那么正向搜索和反向的符号相同，那么正向搜索和反向搜索将采取同样的换名方式，从而可将上述八搜索将采取同样的换名方式，从而可将上述八种情况合并成四种情况，从而可将程序框图简种情况合并成四种情况，从而可将程序框图简化。化。机械优化设计二二次次插插值值法法程程序序框框图图机械优化设计例例1 1： 用二次插值法求用二次插值法求 sin45f在上的极小点。上的极小点。 12144.524.54.705120355y1-0.756802 -0.977590y2-0.97

41、7590-0.999974y3-0.958924 -0.958924p4.7051204.710594yp-0.999974-0.999998机械优化设计例例 2 用二次插值法求函数用二次插值法求函数f(x)=3x3-4x+2的极小点，给的极小点，给定定 x0=0, =0.2。2）用二次插值法逼近极小点）用二次插值法逼近极小点相邻三点的函数值相邻三点的函数值: x1=0, x2=1, x3=2; f1=2, f2=1, f3=18. 代入公式：代入公式：222222*2313121232313121231 ()()()2 ()()()pxxfxxfxxfxxxfxx fxxfxp*0.555,

42、 fp=0.292解解 1）确定初始区间）确定初始区间初始区间初始区间a, b=0, 2, 中间点中间点x2=1, f(x2)=1。机械优化设计由于由于fpf2, xp * 0.2, 应继续迭代。应继续迭代。在新区间，相邻三点的函数值在新区间，相邻三点的函数值: x1=0, x2=0.555, x3=1; f1=2, f2=0.292, f3=1, 代入代入xp*公式计算得：公式计算得：xp*0.607, fp=0.243 由于由于fpx2, 新区间新区间a, b=x2, b=0.555, 1 |x2-xp * |=|0.555-0.607|=0.0520.2, 迭代终止。迭代终止。 xp*0.607, f*=0.243机械优化设计例