第三章 一维搜索方法

1、第三章第三章 一维搜索方法一维搜索方法第三章一维搜索方法第三章一维搜索方法第一节第一节 一维搜索的概念一维搜索的概念第二节第二节 搜索区间的确定与区间消去法原理搜索区间的确定与区间消去法原理第三节第三节 一维搜索的试探方法一维搜索的试探方法黄金分割法黄金分割法第四节第四节 一维搜索的插值方法一维搜索的插值方法第三章第三章 一维搜索方法一维搜索方法第一节第一节 一维搜索的概念一维搜索的概念 当采用数学规划法寻求多元函数的极值点时，一般要进行当采用数学规划法寻求多元函数的极值点时，一般要进行一系列如下格式的迭代计算：一系列如下格式的迭代计算：1(0,1,2)kkkkXXdkkdk当方向当方向给定，

2、求最佳步长给定，求最佳步长就是求一元函数就是求一元函数1kkkkkfxfxd 的极值问题。这一过程被称为的极值问题。这一过程被称为一维搜索一维搜索。 第三章第三章 一维搜索方法一维搜索方法一维搜索是优化搜索方法的基础。一维搜索是优化搜索方法的基础。 f (x (k+1) ) = min. f (x (k) + S (k) ) = f (x (k) + (k) S ( k) )第三章第三章 一维搜索方法一维搜索方法求解一元函数求解一元函数 的极小点的极小点a*a，可用解析法。，可用解析法。 12TTf xadf xadf xadG ad上式求上式求的极值，即求的极值，即求导数为零。导数为零。 2

3、12TTf xdf xd Gd *0TTdf xd Gd则则 *TTdfxd Gd 第三章第三章 一维搜索方法一维搜索方法数值解法数值解法基本思路：基本思路： kk 先确定先确定 所在的搜索区间，然后根据区间消去法原理所在的搜索区间，然后根据区间消去法原理不断缩小此区间，从而获得不断缩小此区间，从而获得 的数值近似解。的数值近似解。 解析解法对于函数关系复杂、求导困难等情况难以解析解法对于函数关系复杂、求导困难等情况难以实现。在实际优化设计中，数值解法的应用更为有效，实现。在实际优化设计中，数值解法的应用更为有效，且适合计算机的运算特点。且适合计算机的运算特点。 一维搜索也称一维搜索也称直线搜

4、索直线搜索。这种方法不仅对于解决一维最优化问。这种方法不仅对于解决一维最优化问题具有实际意义，而且也是求解多维最优化问题的重要支柱。题具有实际意义，而且也是求解多维最优化问题的重要支柱。一维搜索一般分为两大步骤：一维搜索一般分为两大步骤：(1)(1)确定初始搜索区间确定初始搜索区间aa，bb，该区间应是包括一维函数，该区间应是包括一维函数极小点在内的极小点在内的单谷区间单谷区间。(2)(2)在单谷区间在单谷区间a,ba,b内通过缩小区间寻找极小点。内通过缩小区间寻找极小点。第三章第三章 一维搜索方法一维搜索方法第二节第二节 搜索区间的确定与区间消去法原理搜索区间的确定与区间消去法原理1 1、确

5、定搜索区间的外推法、确定搜索区间的外推法（1 1）单谷（峰）区间）单谷（峰）区间 在给定区间内仅有一个谷值（或有唯一的极小点）的在给定区间内仅有一个谷值（或有唯一的极小点）的函数称为函数称为单谷函数单谷函数，其区间称为，其区间称为单谷区间。单谷区间。函数值：函数值：“大大小小大大”图形：图形：“高高低低高高”单谷区间中一定能求得一个极小点。单谷区间中一定能求得一个极小点。第三章第三章 一维搜索方法一维搜索方法f (x)0130f (x)31说明：说明：单谷区间内，函数可以有不可微点，也单谷区间内，函数可以有不可微点，也可以是不连续函数；可以是不连续函数；第三章第三章 一维搜索方法一维搜索方法（

6、2 2）外推方法）外推方法基本思想：基本思想：对对 任选一个初始点任选一个初始点 及初始步长及初始步长 ，通过比较这两点函数值的大小，确定第三点位置，比较这通过比较这两点函数值的大小，确定第三点位置，比较这三点的函数值大小，确定是否为三点的函数值大小，确定是否为“高高低低高高”形态。形态。)(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，向右前进，

7、加大步长，向右前进，加大步长h=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。第三章第三章 一维搜索方法一维搜索方法khx1x2x30h0初始点初始点初始点初始点+ h012h0初始点初

8、始点初始点初始点+ h0初始点初始点+3h024h0初始点初始点+ h0初始点初始点+3h0初始点初始点+7h038h0初始点初始点+3h0初始点初始点+7h0初始点初始点+15h0前前进进搜搜索索步步骤骤表表khx1x2x30h0初始点初始点初始点初始点+ h012h0初始点初始点+ h0初始点初始点初始点初始点-2h024h0初始点初始点初始点初始点-2h0初始点初始点-6h038h0初始点初始点-2h0初始点初始点-6h0初始点初始点-14h0后后退退搜搜索索步步骤骤表表第三章第三章 一维搜索方法一维搜索方法（3 3）搜索区间外推法程序框图）搜索区间外推法程序框图是是否否是是是是否否否否

9、初始进退距初始进退距给定01,hx0hh )(,),(221211xfyhxxxfy21yy hh2)(,3323xfyhxx32yy 0h31,xbxa结束13,xbxa1313yyxxhh32322121,yyxxyyxx3xf2x1xx1x2x3x前进计算前进计算1x2x3xfx1x2x3x后退计算后退计算1x2x1y2y3y第三章第三章 一维搜索方法一维搜索方法. 1 . 0, 0,983)(. 1013hxxxxf初始进退距初始点给定的一维优化初始区间用外推法确定函数例题:解khx1 y1x2 y2x3 y300.10.20 90.1 8.2030.3 6.68110.40.1 8.

10、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 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

11、 . 1, 4 . 0,ba可得初始搜索区间x0.9426最优点为第三章第三章 一维搜索方法一维搜索方法练习练习 确定确定 的初始搜索区间。的初始搜索区间。2)3()( xxf k kh hx x1 1 y y1 1x x2 2 y y2 2x x3 3 y y3 30 01 12 20 9 0 9 1 41 4 3 03 01 14 41 41 43 03 07 167 16得区间得区间 7, 1 ,ba k kh hx x1 1 y y1 1x x2 2 y y2 2x x3 3 y y3 30 01 1-2-25 4 5 4 6 96 96 96 95 45 4 3 03 01 1-4-

12、45 45 43 03 0-1 16-1 16得区间得区间 5, 1,ba1, 501hx 2）取取1,001hx解：解：1 1）取）取第三章第三章 一维搜索方法一维搜索方法2 2、区间消去法原理、区间消去法原理11( )( )f af b极小点必在区间极小点必在区间 内。内。 1, a b11()( )f af b则取则取为为 缩短后的搜索区间。缩短后的搜索区间。 1,ab基本思想：基本思想： ,a b11,a b11ab，搜索区间确定之后，采用区间消去法逐步缩短搜索区间确定之后，采用区间消去法逐步缩短搜索区间，从而找到极小点的数值近似解。搜索区间，从而找到极小点的数值近似解。在搜索区间在搜

13、索区间 内任取两点内任取两点 且且 计算其函数值得如下结论：计算其函数值得如下结论： 第三章第三章 一维搜索方法一维搜索方法缩小的新区间为必在缩小的新区间为必在 。 11( )( )f af b缩小的新区间为必在缩小的新区间为必在 ； 1,a b11()( )f af b1,ab第三章第三章 一维搜索方法一维搜索方法3 3、一维搜索方法分类、一维搜索方法分类根据插入点位置的确定方法，可以把一维搜索根据插入点位置的确定方法，可以把一维搜索法分成两大类：法分成两大类：试探法试探法：即按照某种规律来确定区间内插入点的位：即按照某种规律来确定区间内插入点的位置，如置，如黄金分割法黄金分割法，裴波纳契法

14、等。，裴波纳契法等。裴波纳契数列：裴波纳契数列：1 1、1 1、2 2、3 3、5 5、8 8、1313、2121、3434、5555、8989、144144 插值法（函数逼近法）：插值法（函数逼近法）：通过构造插值函数来逼通过构造插值函数来逼近原函数，用插值函数的极小点作为区间的插入近原函数，用插值函数的极小点作为区间的插入点，如点，如二次插值法二次插值法，三次插值法等。，三次插值法等。第三章第三章 一维搜索方法一维搜索方法第三节一维搜索的试探方法第三节一维搜索的试探方法1 1、前提、前提 函数在区间函数在区间 上是单谷函数。上是单谷函数。 , a b2 2、点的插入原则、点的插入原则（1

15、1）要求插入点）要求插入点 的位置相对于区间的位置相对于区间 ,a b两端点具有对称性。两端点具有对称性。 1()bba2()aba（2 2）要求保留下来的区间内再插入一点所形成）要求保留下来的区间内再插入一点所形成的新三段具有相同的比例分布。的新三段具有相同的比例分布。21,第三章第三章 一维搜索方法一维搜索方法3 3、点位置的确定方法、点位置的确定方法结论：结论：所谓黄金分割所谓黄金分割是指将一线段分成两段的方法，是指将一线段分成两段的方法，使整段长与较长段的长度比值等于较长段与较短段使整段长与较长段的长度比值等于较长段与较短段长度的比值即长度的比值即 。)1 ( :1)(618. 0)(

16、)(618. 0)(21abaabaabbabb两内分点值两内分点值:第三章第三章 一维搜索方法一维搜索方法4 4、黄金分割法的搜索过程、黄金分割法的搜索过程（1）给出初始搜索区间给出初始搜索区间 及收敛精度及收敛精度 ，将，将 赋以赋以 , a b0.618（2）按坐标点计算公式计算按坐标点计算公式计算 并计算其对应的函并计算其对应的函数值数值 12和12,ff（3）根据区间消去法原理缩短搜索区间。为了能用原来的）根据区间消去法原理缩短搜索区间。为了能用原来的坐标点计算公式，进行区间名称的代换，并在保留区间中坐标点计算公式，进行区间名称的代换，并在保留区间中计算一个新的试验点及其函数值。计算

17、一个新的试验点及其函数值。（4）检查区间是否缩短到足够小和函数值收敛到足够近，）检查区间是否缩短到足够小和函数值收敛到足够近，如果条件不满足返回到步骤（如果条件不满足返回到步骤（2）。）。（5）如果条件满足，则取最后两试验点的平均值作为极小）如果条件满足，则取最后两试验点的平均值作为极小点的数值近似解。点的数值近似解。618.0ln)/(lnabk缩短区间的总次数（迭代次数）缩短区间的总次数（迭代次数）:第三章第三章 一维搜索方法一维搜索方法5 5、黄金分割法程序框图、黄金分割法程序框图给定给定,ba)(),(618. 0222xfyabax)(),(382. 0111xfyabax21yy

18、否否否否21211,yyxxxa)(),(618. 0222xfyabax是是)(),(382. 0111xfyabax12122,yyxxxbab是是)()(5 . 0 xffbax止止xfab1x2x1y2y1x2xbxfab1x2x1y2y1x2xa也可采用迭代次数是否大于或等于也可采用迭代次数是否大于或等于 k k 作终止准则。作终止准则。第三章第三章 一维搜索方法一维搜索方法6 6、举例、举例 22f35 对函数对函数，当给定搜索区间，当给定搜索区间时，试用黄金分割法求极小点时，试用黄金分割法求极小点。表表3-1 3-1 黄金分割法的搜索过程黄金分割法的搜索过程迭代序迭代序号号aa1

19、a2by1比较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第三章第三章 一维搜索方法一维搜索方法四、一维搜索的插值方法四、一维搜索的插值方法 在某一确定的区间内寻求函数的极小点位置，在某一确定的区间内寻求函数的极小点位置，虽然没有函数表达式，但能够给出若干点处的函虽然没有函数表达式，但能够给出若干点处的函数值。可以根据这些点处的函数值，利用插值方数值。可以根据这些点处的函数值，利用插值方法建立函数的某种

20、近似表达式，进而求出函数的法建立函数的某种近似表达式，进而求出函数的极小点，并用它作为原来函数极小点的最小值，极小点，并用它作为原来函数极小点的最小值，这种方法称作插值方法，又叫函数逼近法。这种方法称作插值方法，又叫函数逼近法。第三章第三章 一维搜索方法一维搜索方法试探法试探法（如黄金分割法）与（如黄金分割法）与插值法插值法的比较：的比较：相同点相同点：两种方法都是利用区间消去法原理将初始搜索区：两种方法都是利用区间消去法原理将初始搜索区间不断缩短，求得极小值的数值近似解。间不断缩短，求得极小值的数值近似解。试探法试探法：试验点是按照某种个特定的规律确定；不考：试验点是按照某种个特定的规律确定

21、；不考虑函数值的分布；虑函数值的分布；不同点不同点：表现在试验点（插入点）位置的确定方法不同。：表现在试验点（插入点）位置的确定方法不同。插值法插值法：试验点是按照函数值近似分布的极小点确定；：试验点是按照函数值近似分布的极小点确定；利用了函数值本身及其导数信息。利用了函数值本身及其导数信息。第三章第三章 一维搜索方法一维搜索方法1、牛顿法（切线法）、牛顿法（切线法） 对于一维搜索函数对于一维搜索函数 ，假定已经给出，假定已经给出极小点的一个较好的近似点极小点的一个较好的近似点 ，在，在 点附近用点附近用一个二次函数一个二次函数 来逼近函数来逼近函数 yf00 f 20000012ffff 然

22、后以该二次函数然后以该二次函数 的极小点作为的极小点作为 极小极小点的一个新的近似点点的一个新的近似点 。根据极值必要条件：。根据极值必要条件： f1 0 0100ff 1(0,1,2 )kkkkfkf第三章第三章 一维搜索方法一维搜索方法牛顿法的几何解释：牛顿法的几何解释：在上图中，在在上图中，在 处用一抛物线处用一抛物线 代替曲线代替曲线 ，相当于用一斜线相当于用一斜线 代替代替 。这样各个近似点是。这样各个近似点是通过对通过对 作切线求得与作切线求得与 轴的交点找到，故牛顿法轴的交点找到，故牛顿法又称为切线法。又称为切线法。)(f0)()()(f)(f1(0,1,2)kkkkfkf第三章

23、第三章 一维搜索方法一维搜索方法牛顿法的计算步骤：牛顿法的计算步骤：1 1）给定初始点）给定初始点 0，控制误差，控制误差 ，并令，并令 0k 2 2）计算）计算 ,kkff3 3）求）求 1kkkkff4 4）若）若 1kk，则求得近似解则求得近似解 ，1k停止计算，否则作停止计算，否则作5 5）。）。 5 5）令）令 1kk转转2 2）。）。 第三章第三章 一维搜索方法一维搜索方法例题：例题： 给定给定 43246164f，试用，试用牛顿法求其极小点牛顿法求其极小点 。 解：解：1 1）给定初始点）给定初始点 03，控制误差控制误差 0.001 324(334)f 212(21)f0100

24、1331366ff31133662 2）3 3）4 4）第三章第三章 一维搜索方法一维搜索方法重复上边的过程，进行迭代，直到重复上边的过程，进行迭代，直到 10.001kk为止。可得到计算结果如下表为止。可得到计算结果如下表: : 表表3-2 3-2 牛顿法的搜索过程牛顿法的搜索过程k k0 01 12 23 34 4值值a ak k3 35.166675.166674.334744.334744.03964.03964.000664.00066f(af(ak k) )-52-52153.35183153.3518332.3019932.301993.382993.382990.005510.

25、00551f(af(ak k) )-24-24184.33332184.33332109.44586109.4458686.8699286.8699284.0472084.04720a ak+1k+15.166675.166674.334744.334744.039604.039604.000664.000664.000594.00059第三章第三章 一维搜索方法一维搜索方法优点：收敛速度快。优点：收敛速度快。缺点：每一点都要进行二阶导数，工作量大；缺点：每一点都要进行二阶导数，工作量大； 当用数值微分代替二阶导数，由于舍入误差当用数值微分代替二阶导数，由于舍入误差会影响迭代速度；会影响迭代速度； 要求初始点离极小点不太远，否则有可能使要求初始点离极小点不太远，否则有可能使极小化发散或收敛到非极小点。极小化发散或收敛到非极小点。牛顿法的特点：牛顿法的特点：第三章第三章 一维搜索方法一维搜索方法、二次插值法（抛物线法）、二次插值法（抛物线法）基本思想：基本思想：利用目标函数在不同利用目标函数在不同3点的函数值构成一个与点的函数值构成一个与原函数原函数 相近似的二次多项式相近似的二次