三 一维搜索方法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）单谷（峰）区间,在给定区间内仅有一个谷值（或有唯一的极小点）的函数称为单谷函数，其区间称为单谷区间。,函数值：“大小大”,图形：“高低高”,单谷区间中一定能求得一个极小点。,说明：单谷区间内，函数可以有不可微点，也可以是不连续函数；,（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。,前进搜索步骤表,后退搜索步骤表,（3）搜索区间外推法程序框图,是,否,是,是,否,练习确定的初始搜索区间。,得区间,得区间,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、举例,对函数,，当给定搜索区间,时，试用黄金分割法求极小点,。,四、一维搜索的插值方法,在某一确定的区间内寻求函数的极小点位置，虽然没有函数表达式，但能够给出若干点处的函数值。可以根据这些点处的函数值，利用插值方法建立函数的某种近似表达式，进而求出函数的极小点，并用它作为原来函数极小点的最小值，这种方法称作插值方法，又叫函数逼近法。,试探法（如黄金分割法）与插值法的比较：,相同点：两种方法都是利用区间消去法原理将初始搜索区间不断缩短，求得极小值的数值近似解。,试探法：试验点是按照某种个特定的规律确定；不考虑函数值的分布；,不同点：表现在试验点（插入点）位置的确定方法不同。,插值法：试验点是按照函数值近似分布的极小点确定；利用了函数值本身及其导数信息。,1、牛顿法（切线法）,对于一维搜索函数，假定已经给出极小点的一个较好的近似点，在点附近用一个二次函数来逼近函数,然后以该二次函数的极小点作为极小点的一个新的近似点。根据极值必要条件：,牛顿法的几何解释：,在上图中，在处用一抛物线代替曲线，相当于用一斜线代替。这样各个近似点是通过对作切线求得与轴的交点找到，故牛顿法又称为切线法。,牛顿法的计算步骤：,例题：,给定,，试用,牛顿法求其极小点。,解：1）给定初始点,，控制误差,2）,3）,4）,重复上边的过程，进行迭代，直到,为止。可得到计算结果如下表:,优点：收敛速度快。,缺点：每一点都要进行二阶导数，工作量大；,当用数值微分代替二阶导数，由于舍入误差会影响迭代速度；要求初始点离极小点不太远，否则有可能使极小化发散或收敛到非极小点。,牛顿法的特点：,、二次插值法（抛物线法）,基本思想：利用目标函数在不同3点的函数值构成一个与原函数相近似的二次多项式，以函数的极值点（即的根）作为目