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

1、单击此处编辑母版标题样式单击此处编辑母版文本样式第二级第三级第四级第五级*机械优化设计第三章一维搜索方法一、一维搜索的概念二、搜索区间的确定与区间消去法原理三、一维搜索的试探方法黄金分割法四、一维搜索的插值方法一、一维搜索的概念 当采用数学规划法寻求多元函数的极值点时，一般要进行一系列如下格式的迭代计算：当方向给定，求最佳步长就是求一元函数的极值问题。这一过程被称为一维搜索。 一维搜索是优化搜索方法的基础。 f (x (k+1) ) = min. f (x (k) + S (k) ) = f (x (k) + (k) S ( k) )求解一元函数 的极小点，可用解析法。上式求的极值，即求导数为

2、零。则数值解法基本思路： 先确定 所在的搜索区间，然后根据区间消去法原理不断缩小此区间，从而获得 的数值近似解。 解析解法对于函数关系复杂、求导困难等情况难以实现。在实际优化设计中，数值解法的应用更为有效，且适合计算机的运算特点。 一维搜索也称直线搜索。这种方法不仅对于解决一维最优化问题具有实际意义，而且也是求解多维最优化问题的重要支柱。一维搜索一般分为两大步骤：(1)确定初始搜索区间a，b，该区间应是包括一维函数极小点在内的单谷区间。(2)在单谷区间a,b内通过缩小区间寻找极小点。二、搜索区间的确定与区间消去法原理1、确定搜索区间的外推法（1）单谷（峰）区间 在给定区间内仅有一个谷值（或有唯

3、一的极小点）的函数称为单谷函数，其区间称为单谷区间。函数值：“大小大”图形：“高低高”单谷区间中一定能求得一个极小点。f (x)0130f (x)31说明：单谷区间内，函数可以有不可微点，也可以是不连续函数；（2）外推方法基本思想：对 任选一个初始点 及初始步长 ，通过比较这两点函数值的大小，确定第三点位置，比较这三点的函数值大小，确定是否为“高低高”形态。步骤： 1）选定初始点a1，初始步长h=h0，计算y1=f(a1)和y2=f(a1+h)2）比较y1和y2；a）如果y1y2，向右前进，加大步长h=2h0，转（3）向前；b）如果y1y3 ，加大步长h=2h，a1=a2,a2=a3,转（3）

4、继续探测；b）如果y2y3，则初始区间得到：a=mina1,a3,b=maxa1,a3，函数最小值所在区间为a,b。khx1x2x30h0初始点初始点+ h012h0初始点初始点+ h0初始点+3h024h0初始点+ h0初始点+3h0初始点+7h038h0初始点+3h0初始点+7h0初始点+15h0前进搜索步骤表khx1x2x30h0初始点初始点+ h012h0初始点+ h0初始点初始点-2h024h0初始点初始点-2h0初始点-6h038h0初始点-2h0初始点-6h0初始点-14h0后退搜索步骤表（3）搜索区间外推法程序框图是否是是否否初始进退距前进计算后退计算khx1 y1x2 y2x

5、3 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.125khx1 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练习 确定 的初始搜索区间。 khx1 y1x2 y2x3 y30120 9 1 4 3 0141 43 07 16得区间 khx

6、1 y1x2 y2x3 y301-25 4 6 96 95 4 3 01-45 43 0-1 16得区间 2）取解：1）取2、区间消去法原理极小点必在区间 内。 则取为 缩短后的搜索区间。 基本思想： ，搜索区间确定之后，采用区间消去法逐步缩短搜索区间，从而找到极小点的数值近似解。在搜索区间 内任取两点 且 计算其函数值得如下结论： 缩小的新区间为必在 。 缩小的新区间为必在 ； 3、一维搜索方法分类根据插入点位置的确定方法，可以把一维搜索法分成两大类：试探法：即按照某种规律来确定区间内插入点的位置，如黄金分割法，裴波纳契法等。裴波纳契数列：1、1、2、3、5、8、13、21、34、55、89

7、、144 插值法（函数逼近法）：通过构造插值函数来逼近原函数，用插值函数的极小点作为区间的插入点，如二次插值法，三次插值法等。三、一维搜索的试探方法黄金分割法1、前提 函数在区间 上是单谷函数。 2、点的插入原则（1）要求插入点 的位置相对于区间 两端点具有对称性。 （2）要求保留下来的区间内再插入一点所形成的新三段具有相同的比例分布。3、点位置的确定方法结论：所谓黄金分割是指将一线段分成两段的方法，使整段长与较长段的长度比值等于较长段与较短段长度的比值即 。两内分点值:4、黄金分割法的搜索过程（1）给出初始搜索区间 及收敛精度 ，将 赋以 （2）按坐标点计算公式计算 并计算其对应的函数值 （

8、3）根据区间消去法原理缩短搜索区间。为了能用原来的坐标点计算公式，进行区间名称的代换，并在保留区间中计算一个新的试验点及其函数值。（4）检查区间是否缩短到足够小和函数值收敛到足够近，如果条件不满足返回到步骤（2）。（5）如果条件满足，则取最后两试验点的平均值作为极小点的数值近似解。缩短区间的总次数（迭代次数）:5、黄金分割法程序框图给定否否是是止也可采用迭代次数是否大于或等于 k 作终止准则。6、举例对函数，当给定搜索区间时，试用黄金分割法求极小点。表3-1 黄金分割法的搜索过程迭代序号aa1a2by1比较y20-30.0561.94450.1157.6671-3-1.1110.0561.94

9、4-0.987-0.9873-1.832-1.111-0.6650.056-0.987-0.9875-1.386-1.111-0.940 -0.665四、一维搜索的插值方法 在某一确定的区间内寻求函数的极小点位置，虽然没有函数表达式，但能够给出若干点处的函数值。可以根据这些点处的函数值，利用插值方法建立函数的某种近似表达式，进而求出函数的极小点，并用它作为原来函数极小点的最小值，这种方法称作插值方法，又叫函数逼近法。试探法（如黄金分割法）与插值法的比较：相同点：两种方法都是利用区间消去法原理将初始搜索区间不断缩短，求得极小值的数值近似解。试探法：试验点是按照某种个特定的规律确定；不考虑函数值的

10、分布；不同点：表现在试验点（插入点）位置的确定方法不同。插值法：试验点是按照函数值近似分布的极小点确定；利用了函数值本身及其导数信息。1、牛顿法（切线法） 对于一维搜索函数 ，假定已经给出极小点的一个较好的近似点 ，在 点附近用一个二次函数 来逼近函数 然后以该二次函数 的极小点作为 极小点的一个新的近似点 。根据极值必要条件：牛顿法的几何解释：在上图中，在 处用一抛物线 代替曲线 ，相当于用一斜线 代替 。这样各个近似点是通过对 作切线求得与 轴的交点找到，故牛顿法又称为切线法。牛顿法的计算步骤：1）给定初始点 ，控制误差 ，并令 2）计算 3）求 4）若 ，则求得近似解 ，停止计算，否则作

11、5）。 5）令 转2）。 例题： 给定 ，试用牛顿法求其极小点 。 解：1）给定初始点 ，控制误差 2）3）4）重复上边的过程，进行迭代，直到 为止。可得到计算结果如下表: 表3-2 牛顿法的搜索过程k01234值ak35.166674.334744.03964.00066f(ak)-52153.3518332.301993.382990.00551f(ak)-24184.33332109.4458686.8699284.04720ak+15.166674.334744.039604.000664.00059优点：收敛速度快。缺点：每一点都要进行二阶导数，工作量大； 当用数值微分代替二阶导数，由于舍入误差会影响迭代速度； 要求初始点离极小点不太远，否则有可能使极小化发散或收敛到非极小点。牛顿法的特点：、二次插值法（抛物线法）基本思想：利用目标函数在不同3点的函数值构成一个与原函数 相近似的二次多项式 ，以函数 的极值点 （即 的根）作为目标函数 的近似极值点。（1）二次插值多项式的构成及其极值点设 在单谷区间中的三点 的相应函数值 ，则可以做出如下的二次插值多项式：多项式 的极值点可从极值的必要条件求得，即 ， ）如果区间长度 足够小，则由 便得出我们所要求的近似极小点 2）如果不满足，必须缩小区间