论文资料机械优化设计第三章一维搜索方法

《论文资料机械优化设计第三章一维搜索方法》由会员分享，可在线阅读，更多相关《论文资料机械优化设计第三章一维搜索方法（38页珍藏版）》请在装配图网上搜索。

1、机械优化设计第三章一维搜索方法第三章一维搜索方法一、一维搜索的概念一、一维搜索的概念二、搜索区间的确定与区间消去法原理二、搜索区间的确定与区间消去法原理三、一维搜索的试探方法三、一维搜索的试探方法黄金分割法黄金分割法四、一维搜索的插值方法四、一维搜索的插值方法机械优化设计一、一维搜索的概念一、一维搜索的概念 当采用数学规划法寻求多元函数的极值点时，一般要进行当采用数学规划法寻求多元函数的极值点时，一般要进行一系列如下格式的迭代计算：一系列如下格式的迭代计算：当方向当方向给给定，求最佳步定，求最佳步长长就是求一元函数就是求一元函数的极值问题。这一过程被称为的极值问题。这一过程被称为一维搜索一维搜

2、索。机械优化设计一维搜索是优化搜索方法的基础。一维搜索是优化搜索方法的基础。f(x(k+1)=min.f(x(k)+S(k)=f(x(k)+(k)S(k)机械优化设计求解一元函数求解一元函数 的极小点的极小点，可用解析法。，可用解析法。上式求上式求的极值，即求的极值，即求导数为零。导数为零。则则机械优化设计数值解法数值解法基本思路：基本思路：先确定先确定 所在的搜索区间，然后根据区间消去法原理所在的搜索区间，然后根据区间消去法原理不断缩小此区间，从而获得不断缩小此区间，从而获得 的数值近似解。的数值近似解。解析解法对于函数关系复杂、求导困难等情况难以解析解法对于函数关系复杂、求导困难等情况难以

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

4、内通过缩小区间寻找极小点。内通过缩小区间寻找极小点。机械优化设计二、搜索区间的确定与区间消去法原理二、搜索区间的确定与区间消去法原理1 1、确定搜索区间的外推法、确定搜索区间的外推法（1 1）单谷（峰）区间）单谷（峰）区间 在给定区间内仅有一个谷值（或有唯一的极小点）的在给定区间内仅有一个谷值（或有唯一的极小点）的函数称为函数称为单谷函数单谷函数，其区间称为，其区间称为单谷区间。单谷区间。函数值：函数值：“大大小小大大”图形：图形：“高高低低高高”单谷区间中一定能求得一个极小点。单谷区间中一定能求得一个极小点。机械优化设计f(x)0130f(x)31说明：说明：单谷区间内，函数可以有不可微点，

5、也单谷区间内，函数可以有不可微点，也可以是不连续函数；可以是不连续函数；机械优化设计（2 2）外推方法）外推方法基本思想：基本思想：对对 任选一个初始点任选一个初始点 及初始步长及初始步长 ，通过比较这两点函数值的大小，确定第三点位置，比较这通过比较这两点函数值的大小，确定第三点位置，比较这三点的函数值大小，确定是否为三点的函数值大小，确定是否为“高高低低高高”形态。形态。步骤：步骤：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和和

6、y y2 2；a a）如果）如果y y1 1yy2 2，向右前进，加大步长，向右前进，加大步长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初始点初始点初始

7、点初始点+h012h0初始点初始点初始点初始点+h0初始点初始点+3h024h0初始点初始点+h0初始点初始点+3h0初始点初始点+7h038h0初始点初始点+3h0初始点初始点+7h0初始点初始点+15h0前进搜索步骤表前进搜索步骤表khx1x2x30h0初始点初始点初始点初始点+h012h0初始点初始点+h0初始点初始点初始点初始点-2h024h0初始点初始点初始点初始点-2h0初始点初始点-6h038h0初始点初始点-2h0初始点初始点-6h0初始点初始点-14h0后退搜索步骤表后退搜索步骤表机械优化设计（3 3）搜索区）搜索区间间外推法程序框外推法程序框图图是是否否是是是是否否否否初始

8、进退距初始进退距前进计算前进计算后退计算后退计算机械优化设计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机械优化设计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机械优化设计练习练习 确定确定

9、的初始搜索区间。的初始搜索区间。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得区间得区间 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-45 45 43 03 0-1 16-1 16得区间得区间 2）取取解：解：1 1）取）取机械优化设计2 2、区间消去法原理、区间消去法原理极小点必在区间极小点必在

10、区间 内。内。则则取取为为 缩短后的搜索区间。缩短后的搜索区间。基本思想：基本思想：，搜索区间确定之后，采用区间消去法逐步缩短搜索区间确定之后，采用区间消去法逐步缩短搜索区间，从而找到极小点的数值近似解。搜索区间，从而找到极小点的数值近似解。在搜索区间在搜索区间 内任取两点内任取两点 且且 计算其函数值得如下结论：计算其函数值得如下结论：机械优化设计缩小的新区间为必在缩小的新区间为必在 。缩小的新区间为必在缩小的新区间为必在 ；机械优化设计3 3、一维搜索方法分类、一维搜索方法分类根据插入点位置的确定方法，可以把一维搜索根据插入点位置的确定方法，可以把一维搜索法分成两大类：法分成两大类：试探法

11、试探法：即按照某种规律来确定区间内插入点的位：即按照某种规律来确定区间内插入点的位置，如置，如黄金分割法黄金分割法，裴波纳契法等。，裴波纳契法等。裴波纳契数列：裴波纳契数列：1 1、1 1、2 2、3 3、5 5、8 8、1313、2121、3434、5555、8989、144144 插值法（函数逼近法）：插值法（函数逼近法）：通过构造插值函数来逼近通过构造插值函数来逼近原函数，用插值函数的极小点作为区间的插入点，原函数，用插值函数的极小点作为区间的插入点，如如二次插值法二次插值法，三次插值法等。，三次插值法等。机械优化设计三、一维搜索的试探方法三、一维搜索的试探方法黄金分割法黄金分割法1 1

12、、前提、前提 函数在区间函数在区间 上是单谷函数。上是单谷函数。2 2、点的插入原则、点的插入原则（1 1）要求插入点）要求插入点 的位置相对于区间的位置相对于区间 两端点具有对称性。两端点具有对称性。（2 2）要求保留下来的区间内再插入一点所形成的）要求保留下来的区间内再插入一点所形成的新三段具有相同的比例分布。新三段具有相同的比例分布。机械优化设计3 3、点位置的确定方法、点位置的确定方法结论：结论：所谓黄金分割所谓黄金分割是指将一线段分成两段的方法，是指将一线段分成两段的方法，使整段长与较长段的长度比值等于较长段与较短段使整段长与较长段的长度比值等于较长段与较短段长度的比值即长度的比值即

13、 。两内分点值两内分点值:机械优化设计4 4、黄金分割法的搜索过程、黄金分割法的搜索过程（1）给出初始搜索区间给出初始搜索区间 及收敛精度及收敛精度 ，将，将 赋以赋以（2）按坐标点计算公式计算按坐标点计算公式计算 并计算其对应的函并计算其对应的函数值数值（3）根据区间消去法原理缩短搜索区间。为了能用原来的）根据区间消去法原理缩短搜索区间。为了能用原来的坐标点计算公式，进行区间名称的代换，并在保留区间中坐标点计算公式，进行区间名称的代换，并在保留区间中计算一个新的试验点及其函数值。计算一个新的试验点及其函数值。（4）检查区间是否缩短到足够小和函数值收敛到足够近，）检查区间是否缩短到足够小和函数

14、值收敛到足够近，如果条件不满足返回到步骤（如果条件不满足返回到步骤（2）。）。（5）如果条件满足，则取最后两试验点的平均值作为极小）如果条件满足，则取最后两试验点的平均值作为极小点的数值近似解。点的数值近似解。缩短区间的总次数（迭代次数）缩短区间的总次数（迭代次数）:机械优化设计5 5、黄金分割法程序框图、黄金分割法程序框图给定给定否否否否是是是是止止也可采用迭代次数是否大于或等于也可采用迭代次数是否大于或等于 k k 作终止准则。作终止准则。机械优化设计6 6、举例、举例对对函数函数，当，当给给定搜索区定搜索区间间时时，试试用黄金分割法求极小点用黄金分割法求极小点。表表3-1 3-1 黄金分

15、割法的搜索过程黄金分割法的搜索过程迭代序迭代序号号aa1a2by1比较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机械优化设计四、一维搜索的插值方法四、一维搜索的插值方法 在某一确定的区间内寻求函数的极小点位置，在某一确定的区间内寻求函数的极小点位置，虽然没有函数表达式，但能够给出若干点处的函虽然没有函数表达式，但能够给出若干点处的函数值。可以根据这些点处的函数值，利用插值方数值。可以根据这些点处的函数值

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

17、定；不考虑函数值的分布；虑函数值的分布；不同点不同点：表现在试验点（插入点）位置的确定方法不同。：表现在试验点（插入点）位置的确定方法不同。插值法插值法：试验点是按照函数值近似分布的极小点确定；：试验点是按照函数值近似分布的极小点确定；利用了函数值本身及其导数信息。利用了函数值本身及其导数信息。机械优化设计1、牛顿法（切线法）、牛顿法（切线法）对于一维搜索函数对于一维搜索函数 ，假定已经给出，假定已经给出极小点的一个较好的近似点极小点的一个较好的近似点 ，在，在 点附近用点附近用一个二次函数一个二次函数 来逼近函数来逼近函数 然后以该二次函数然后以该二次函数 的极小点作为的极小点作为 极小极小

18、点的一个新的近似点点的一个新的近似点 。根据极值必要条件：。根据极值必要条件：机械优化设计牛顿法的几何解释：牛顿法的几何解释：在上图中，在在上图中，在 处用一抛物线处用一抛物线 代替曲线代替曲线 ，相，相当于用一斜线当于用一斜线 代替代替 。这样各个近似点是通过。这样各个近似点是通过对对 作切线求得与作切线求得与 轴的交点找到，故牛顿法又称为轴的交点找到，故牛顿法又称为切线法。切线法。机械优化设计牛顿法的计算步骤：牛顿法的计算步骤：1 1）给定初始点）给定初始点，控制误差，控制误差，并令，并令 2 2）计算）计算 3 3）求）求 4 4）若）若，则求得近似解则求得近似解 ，停止计算，否则作停止

19、计算，否则作5 5）。）。5 5）令）令 转转2 2）。）。机械优化设计例题：例题：给定给定，试用，试用牛顿法求其极小点牛顿法求其极小点 。解：解：1 1）给定初始点）给定初始点，控制误差控制误差 2 2）3 3）4 4）机械优化设计重复上边的过程，进行迭代，直到重复上边的过程，进行迭代，直到 为止。可得到计算结果如下表为止。可得到计算结果如下表:表表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-52

20、153.35183153.3518332.3019932.301993.382993.382990.005510.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机械优化设计优点：收敛速度快。优点：收敛速度快。缺点：每一点都要进行二阶导数，工作量大；缺点：每一点都要进行二阶导数，工作量大；当用数值微分代替二阶导

21、数，由于舍入误差当用数值微分代替二阶导数，由于舍入误差会影响迭代速度；会影响迭代速度；要求初始点离极小点不太远，否则有可能使要求初始点离极小点不太远，否则有可能使极小化发散或收敛到非极小点。极小化发散或收敛到非极小点。牛顿法的特点：牛顿法的特点：机械优化设计、二次插值法（抛物线法）、二次插值法（抛物线法）基本思想：基本思想：利用目标函数在不同利用目标函数在不同3点的函数值构成一个与点的函数值构成一个与原函数原函数 相近似的二次多项式相近似的二次多项式 ，以函数，以函数 的极的极值点值点 （即（即 的根）作为目标函数的根）作为目标函数 的近似极的近似极值点。值点。机械优化设计（1）二次插值多项式

22、的构成及其极值点）二次插值多项式的构成及其极值点设设 在单谷区间中的三点在单谷区间中的三点 的相应函数值的相应函数值，则可以做出，则可以做出如下的二次插值多项式：如下的二次插值多项式：机械优化设计多项式多项式 的极值点可从极值的必要条件求得的极值点可从极值的必要条件求得，即，即，机械优化设计）如果区间长度）如果区间长度 足够小，则由足够小，则由 便得出我们所要求的近似极小点便得出我们所要求的近似极小点 2 2）如果不满足，必须缩小区间）如果不满足，必须缩小区间，根据区间消取法，根据区间消取法原理不断缩小区间。原理不断缩小区间。结论结论机械优化设计机械优化设计机械优化设计二二次次插插值值法法程程序序框框图图机械优化设计例：例：用二次插值法求用二次插值法求 上的极小点。上的极小点。表表3-4 3-4 二次插二次插值值法法计计算算过过程示例程示例12a144.5a24.54.705120a355y1-0.756802-0.977590y2-0.977590-0.999974y3-0.958924-0.958924ap4.7051204.710594yp-0.999974-0.999998