第三章 一维搜索方法.ppt

第三章 一维搜索方法第三章一维搜索方法第一节 一维搜索的概念第二节 搜索区间的确定与区间消去法原理第三节 一维搜索的试探方法黄金分割法第四节 一维搜索的插值方法第三章 一维搜索方法第一节 一维搜索的概念 当采用数学规划法寻求多元函数的极值点时，一般要进行一系列如下格式的迭代计算：当方向给给定，求最佳步长长就是求一元函数的极值问题这一过程被称为一维搜索 第三章 一维搜索方法一维搜索是优化搜索方法的基础 f (x (k+1) ) = min. f (x (k) + S (k) ) = f (x (k) + (k) S ( k) )第三章 一维搜索方法求解一元函数 的极小点，可用解析法上式求的极值，即求导数为零则第三章 一维搜索方法数值解法基本思路： 先确定 所在的搜索区间，然后根据区间消去法原理不断缩小此区间，从而获得 的数值近似解 解析解法对于函数关系复杂、求导困难等情况难以实现在实际优化设计中，数值解法的应用更为有效，且适合计算机的运算特点 一维搜索也称直线搜索这种方法不仅对于解决一维最优化问题具有实际意义，而且也是求解多维最优化问题的重要支柱一维搜索一般分为两大步骤：(1)确定初始搜索区间a，b，该区间应是包括一维函数极小点在内的单谷区间。

2)在单谷区间a,b内通过缩小区间寻找极小点第三章 一维搜索方法第二节 搜索区间的确定与区间消去法原理1、确定搜索区间的外推法（1）单谷（峰）区间 在给定区间内仅有一个谷值（或有唯一的极小点）的函数称为单谷函数，其区间称为单谷区间函数值：“大小大”图形：“高低高”单谷区间中一定能求得一个极小点第三章 一维搜索方法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）继续探测；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 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第三章 一维搜索方法练习 确定 的初始搜索区间。

khx1 y1x2 y2x3 y30120 9 1 4 3 0141 43 07 16得区间 khx1 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、144 插值法（函数逼近法）：通过构造插值函数来逼近原函数，用插值函数的极小点作为区间的插入点，如二次插值法，三次插值法等第三章 一维搜索方法第三节一维搜索的试探方法1、前提 函数在区间 上是单谷函数 2、点的插入原则（1）要求插入点 的位置相对于区间 两端点具有对称性。

（2）要求保留下来的区间内再插入一点所形成的新三段具有相同的比例分布第三章 一维搜索方法3、点位置的确定方法结论：所谓黄金分割是指将一线段分成两段的方法，使整段长与较长段的长度比值等于较长段与较短段长度的比值即 两内分点值:第三章 一维搜索方法4、黄金分割法的搜索过程（1）给出初始搜索区间 及收敛精度 ，将 赋以 （2）按坐标点计算公式计算 并计算其对应的函数值 （3）根据区间消去法原理缩短搜索区间为了能用原来的坐标点计算公式，进行区间名称的代换，并在保留区间中计算一个新的试验点及其函数值4）检查区间是否缩短到足够小和函数值收敛到足够近，如果条件不满足返回到步骤（2）5）如果条件满足，则取最后两试验点的平均值作为极小点的数值近似解缩短区间的总次数（迭代次数）:第三章 一维搜索方法5、黄金分割法程序框图给定否否是是止也可采用迭代次数是否大于或等于 k 作终止准则第三章 一维搜索方法6、举例对对函数，当给给定搜索区间间时时，试试用黄金分割法求极小点表3-1 黄金分割法的搜索过程迭代序号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第三章 一维搜索方法四、一维搜索的插值方法 在某一确定的区间内寻求函数的极小点位置，虽然没有函数表达式，但能够给出若干点处的函数值。

可以根据这些点处的函数值，利用插值方法建立函数的某种近似表达式，进而求出函数的极小点，并用它作为原来函数极小点的最小值，这种方法称作插值方法，又叫函数逼近法第三章 一维搜索方法试探法（如黄金分割法）与插值法的比较：相同点：两种方法都是利用区间消去法原理将初始搜索区间不断缩短，求得极小值的数值近似解试探法：试验点是按照某种个特定的规律确定；不考虑函数值的分布；不同点：表现在试验点（插入点）位置的确定方法不同插值法：试验点是按照函数值近似分布的极小点确定；利用了函数值本身及其导数信息第三章 一维搜索方法1、牛顿法（切线法） 对于一维搜索函数 ，假定已经给出极小点的一个较好的近似点 ，在 点附近用一个二次函数 来逼近函数 然后以该二次函数 的极小点作为 极小点的一个新的近似点 根据极值必要条件：第三章 一维搜索方法牛顿法的几何解释：在上图中，在 处用一抛物线 代替曲线 ，相当于用一斜线 代替 这样各个近似点是通过对 作切线求得与 轴的交点找到，故牛顿法又称为切线法第三章 一维搜索方法牛顿法的计算步骤：1）给定初始点 ，控制误差 ，并令 2）计算 3）求 4）若 ，则求得近似解 ，停止计算，否则作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）如果不满足，必须缩小区间 ，根据区间消取法原理不断缩小区间。

结论第三章 一维搜索方法第三章 一维搜索方法二次插值法程序框图第三章 一维搜索方法例： 用二次插值法求 上的极小点 表3-4 二次插值值法计计算过过程示例12a144.5a24.54.705120a355y1-0.756802 -0.977590y2-0.977590-0.999974y3-0.958924 -0.958924ap4.7051204.710594yp-0.999974-0.999998。