第三章-一维搜索方法.ppt

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、称为单谷函数，其区间称为单谷区间。,函数值：“大小大”,图形：“高低高”,单谷区间中一定能求得一个极小点。,说明：单谷区间内，函数可以有不可微点，也可以是不连续函数；,（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，

4、则初始区间得到： a=mina1,a3,b=maxa1,a3，函数最小值所在区间为a,b。,前进搜索步骤表,后退搜索步骤表,（3）搜索区间外推法程序框图,是,否,是,是,否,练习 确定 的初始搜索区间。,得区间,得区间,2）取,解：1）取,2、区间消去法原理,基本思想：,3、一维搜索方法分类,根据插入点位置的确定方法，可以把一维搜索法分成两大类：,试探法：即按照某种规律来确定区间内插入点的位置，如黄金分割法，裴波纳契法等。 裴波纳契数列：1、1、2、3、5、8、13、21、34、55、89、144,插值法（函数逼近法）：通过构造插值函数来逼近原函数，用插值函数的极小点作为区间的插入点，如二次插

5、值法，三次插值法等。,第三节一维搜索的试探方法,1、前提,函数在区间 上是单谷函数。,2、点的插入原则,（1）要求插入点 的位置相对于区间,两端点具有对称性。,（2）要求保留下来的区间内再插入一点所形成的新三段具有相同的比例分布。,3、点位置的确定方法,结论：所谓黄金分割是指将一线段分成两段的方法，使整段长与较长段的长度比值等于较长段与较短段长度的比值即 。,两内分点值:,4、黄金分割法的搜索过程,（1）给出初始搜索区间 及收敛精度 ，将 赋以,（2）按坐标点计算公式计算 并计算其对应的函数值,（3）根据区间消去法原理缩短搜索区间。为了能用原来的坐标点计算公式，进行区间名称的代换，并在保留区间

6、中计算一个新的试验点及其函数值。 （4）检查区间是否缩短到足够小和函数值收敛到足够近，如果条件不满足返回到步骤（2）。 （5）如果条件满足，则取最后两试验点的平均值作为极小点的数值近似解。,缩短区间的总次数（迭代次数）:,5、黄金分割法程序框图,给定,也可采用迭代次数是否大于或等于 k 作终止准则。,6、举例,对函数,，当给定搜索区间,时，试用黄金分割法求极小点,。,四、一维搜索的插值方法,在某一确定的区间内寻求函数的极小点位置，虽然没有函数表达式，但能够给出若干点处的函数值。可以根据这些点处的函数值，利用插值方法建立函数的某种近似表达式，进而求出函数的极小点，并用它作为原来函数极小点的最小值

7、，这种方法称作插值方法，又叫函数逼近法。,试探法（如黄金分割法）与插值法的比较：,相同点：两种方法都是利用区间消去法原理将初始搜索区间不断缩短，求得极小值的数值近似解。,试探法：试验点是按照某种个特定的规律确定；不考虑函数值的分布；,不同点：表现在试验点（插入点）位置的确定方法不同。,插值法：试验点是按照函数值近似分布的极小点确定；利用了函数值本身及其导数信息。,1、牛顿法（切线法）,对于一维搜索函数 ，假定已经给出极小点的一个较好的近似点 ，在 点附近用一个二次函数 来逼近函数,然后以该二次函数 的极小点作为 极小点的一个新的近似点 。根据极值必要条件：,牛顿法的几何解释：,在上图中，在 处

8、用一抛物线 代替曲线 ，相当于用一斜线 代替 。这样各个近似点是通过对 作切线求得与 轴的交点找到，故牛顿法又称为切线法。,牛顿法的计算步骤：,例题：,给定,，试用,牛顿法求其极小点 。,解：1）给定初始点,，控制误差,2）,3）,4）,重复上边的过程，进行迭代，直到,为止。可得到计算结果如下表:,优点：收敛速度快。,缺点：每一点都要进行二阶导数，工作量大；,当用数值微分代替二阶导数，由于舍入误差会影响迭代速度； 要求初始点离极小点不太远，否则有可能使极小化发散或收敛到非极小点。,牛顿法的特点：,、二次插值法（抛物线法）,基本思想：利用目标函数在不同3点的函数值构成一个与原函数 相近似的二次多项式 ，以函数 的极值点 （即 的根）作为目标函数 的近