第3章 一维搜索方法.ppt

1、第三章 一维搜索方法,3-1 引言 3-2 确定最优解所在区间的进退法 3-3 一维搜索的区间消去方法 3-4 一维搜索的插值类方法,3-1 引言,当采用数学规划法寻求多元函数的极值点时，一般要进行一系列如下格式的迭代计算:,当方向 给定，求最佳步长 就是求一元函数 :,的极值问题，这一过程被称为一维搜索.,一维搜索也称直线搜索。这种方法不仅对于解决一维最优化本身具有实际意义，而且也是解多维最优化问题的重要支柱。（搜索步长求解）,一维搜索方法解析法高等数学已学过，即利用一维函数的极值条件：,一维搜索方法数值解法使讲解的重点!,一维搜索方法数值解法分类,1、单谷(峰）区间 在给定区间内仅有一个谷

2、值的函数称为单谷数，其区间称为单谷区间。,3-2 确定最优解所在区间的进退法,一、 一维搜索的基本思想,函数值：“大小大” 图形：“高低高”,单谷区间中一定能求得一个极小点,2. 找初始单谷区间是一维搜索的第一步； 第二步使区间缩小。,二、确定初始单谷区间的进退法,基本思想： 对f(x)任选一个初始点a1及初始步长h， 通过比较这两点函数值的大小，确定第三点位置，比较这三点的函数值大小，确定是否为 “高低高” 形态。,步骤：,（1）选定初始点a1, 初始步长hh0 0，计算 y1f(a1)， y2f(a1h)。 （2）比较y1和y2。 （a）如y1y2, 向右前进；加大步长 h2 h ，转（3

3、）向前； （b）如y1y2, 向左后退；h h0， 将a1与a2，y1与y2的 值互换。转（3）向后探测； （c）如y1y2，极小点在a1和a1h之间。,(3）产生新的探测点a3a2h，y3f(a3); (4) 比较函数值 y2与y3： （b）如y2y3, 加大步长 h2 h(也可不变) ， a1=a2, a2=a3, 转（3）继续探测。 （a）如y2y3, 则初始区间得到： a=mina1,a3， b=maxa3,a1，函数最小值所在的区间为a， b 。,确定初始单谷区间进退法示意图,进退法程序框图,搜索区间确定之后，采用区间消去法逐步缩短搜索区间，从而找到极小点的数值近似解。 假定在搜索区

4、间内a,b 任取两点a1,b1;,f1f（a1）， f2f（b1）,3-3 一维搜索的区间消去方法,一、基本思想,f1f（a1）， f2f（b1） (1)如f1f2, 则缩小的新区间为a1,b; (3)如f1=f2, 则缩小的新区间为a1,b1,综合为两种情况： 若 则取 为缩短后的搜索区间。 若 则取 为缩短后的搜索区间。,一些照片：,如下图是一个五角星图案，如何找点C把AB分成两段AC和BC，使得画出的图形匀称美观？,在线段AB上，点C把线段AB分成两条线段AC和BC，如果 ，那么称线段AB被点C黄金分割(golden section)，点C叫做线段AB的黄金分割点，AC与AB的比叫做黄金

5、比，其中 0618。,黄金分割,由于五角星的顶角是36度，这样也可以得出黄金分割的数值为2Sin18 。,黄金分割由来,黄金分割是公元前六世纪古希腊数学家毕达哥拉斯所发现，后来古希腊美学家柏拉图将此称为黄金分割。这其实是一个数字的比例关系，即把一条线分为两部分，此时长段与短段之比恰恰等于整条线与长段之比，其数值比为1.618 : 1或 1 : 0.618，也就是说长段的平方等于全长与短段的乘积。 千百年来，它被广泛运用于几何学、建筑设计、绘画艺术、舞台艺术、音乐艺术、管理等方面，甚至也存在于自然界中。17世纪欧洲著名科学家开普勒说过：“几何学有两个宝藏，一个是勾股定理，一个是黄金分割。”,黄金

6、分割具有严格的比例性、艺术性、和谐性，蕴藏着丰富的美学价值。,人体的黄金分割点,0.618,1,面部的黄金分割,0.618,1,建筑中的黄金分割,古希腊时期的巴台农神庙，它被公认为现存古代建筑中最具均衡美感的伟大杰作 。,绘画艺术中的黄金分割,黄金分割广泛用在建筑设计、美术、音乐、艺术等方面。如在设计工艺品或日用品的宽和长时，常设计成宽与长的比近似为0.618，这样易引起美感；在拍照时，常把主要景物摄在接近于画面的黄金分割点处，会显得更加协调、悦目；舞台上报幕员报幕时总是站在近于舞台的黄金分割点处，这样音响效果就比较好，而且显得自然大方，等等。,气温在人体正常体温的黄金分割点上23左右时，恰是

7、人的身心最适度的温度；,植物界也有采用黄金分割的地方，如果从一棵嫩枝的顶端向下看，就会看到叶子是按照黄金分割的规律排列着的。,黄金分割与优选法,数学上最优化问题的解决方法大致分为两类：间接最优化方法和直接最优化方法。间接最优化方法是把研究对象用数学方程表示出来，再用数学方法求最优解。但在许多情况下，对象本身处理不清楚，间接最优化方法就无法使用，于是人们就通过大量试验来寻找最优解。 优选法也叫快速优选法，它是用最快的速度把最优的方案选出来。如果将实验点定在区间的0.618左右，那么实验的次数将大大减少。实验统计表明，对于一个因素问题，用“0.618法”做16次实验，就可以取得“对分法”做2500

8、次试验所达的效果。它可以使我们合理地安排较少的试验次数找到合理的配方和合适的工艺条件。因而“优选法”又被称为“黄金分割法”。 20世纪50、60年代华罗庚在全国推广“0.618法”，在生产中获得大量应用，特别在工程设计方面应用最多，成效最佳。,在搜索区间内a,b适当插入两点 ，将区间分成三段；,二、黄金分割法,黄金分割法适用于a,b区间上的任何单谷函数求极小值问题。对函数除要求“单谷”外不作其他要求，甚至可以不连续。因此，这种方法的适应面相当广。 黄金分割法也是建立在区间消去法原理基础上的试探方法。,利用区间消去法，使搜索区间缩小，通过迭代计算，使搜索区间无限缩小，从而得到极小点的数值近似解。

9、,黄金分割法还要求在保留下来的区间内再插入一点所形成的区间新三段，与原来区间的三段具有相同的比例分布 。,将区间分成三段,黄金分割法要求插入两点：,黄金分割法区间消去示意：,黄金分割法的搜索过程： 1）给出初始搜索区间及收敛精度 ，将 赋以0.618。,2）按坐标点计算公式计算 , ；并计算其对应的函数值。,3）根据区间消去法原理缩短搜索区间。为了能用原来的坐标点计算公式，需进行区间名称的代换，并在保留区间中计算一个新的试验点及其函数值。 如果 ，则新区间 令 记N0=0； 如果 ，则新区间 ， 令 ，记N0=1；,4）检查区间是否缩短到足够小和函数值收敛到足够精度，如果收敛条件满足，则取最后

10、两试验点的平均值作为极小点的数值近似解。如果条件不满足则转向步骤5）。,如N0=0，则取,如N0=1，则取,5）产生新的插入点：,转向3）进行新的区间缩小。,黄金分割法程序框图,例 3-1 用黄金分割法求函数f(x)=3x3-4x+2的极小点，给定 x0=0, h=1, =0.2。,解： 1）确定初始区间 x1=x0=0, f1=f(x1)=2 x2=x0+h=0+1=1, f2=f(x2)=1 由于f1f2, 应加大步长继续向前探测。,x3= x0+2h=0+2=2, f3=f(x3)=18 由于f2f3,可知初始区间已经找到，即a,b=x1,x2=0,2,2）用黄金分割法缩小区间 第一次缩

11、小区间： x1=0+0.382X(2-0)=0.764, f1=0.282 x2=0+0.618 X(2-0)=1.236, f2=2.72 f10.2,第二次缩小区间： 令 x2=x1=0.764, f2=f1=0.282 x1=0+0.382X(1.236-0)=0.472, f1=0.317 由于f1f2, 故新区间a,b=x1,b=0.472, 1.236 因为 b-a=1.236-0.472=0.7640.2, 应继续缩小区间。,第三次缩小区间： 令 x1=x2=0.764, f1=f2=0.282 x2=0.472+0.618X(1.236-0.472)=0.944, f2=0.7

12、47 由于f10.2, 应继续缩小区间。,第四次缩小区间： 令 x2=x1=0.764, f2=f1=0.282 x1=0.472+0.382X(0.944-0.472)=0.652, f1=0.223 由于f10.2, 应继续缩小区间。,第五次缩小区间： 令 x2=x1=0.652, f2=f1=0.223 x1=0.472+0.382X(0.764-0.472)=0.584, f1=0.262 由于f1f2, 故新区间a,b=x1,b=0.584, 0.764 因为 b-a=0.764-0.584=0.180.2, 停止迭代。,极小点与极小值： x*=0.5X(0.584+0.764)=0

13、.674, f(x*)=0.222,例3-2 对函数 ，当给定搜索区间 时，试用黄金分割法求极小点。,一、牛顿法,3-4 一维搜索的插值类方法,设f(x)为一个连续可微的函数，则在x0附近，该函数应该与一个二次函数接近，即可在点x0附近用一个二次函数(x)来逼近函数f(x) ，即：,用二次函数的(x)极小点x1作为f(x)极小点的一个近似点。根据极值必要条件:,即,依次继续下去，可得牛顿迭代公式：,牛顿法所作的几何解释,在图中，在x0处用一抛物线(x)代替曲线f(x)，相当于用一斜直线(x)代替曲线f(x) 。这样各个近似点是通过对作f(x)切线求得与轴的交点找到的，所以，有时，牛顿法又称作切

14、线法。,牛顿法的优点是收敛速度快。缺点是要计算函数的一阶和二阶导数，因而增加了每次迭代的工作量。如果用数值微分计算函数的二阶导数，其舍入误差将严重影响牛顿法的收敛速度， f(x)的值越小，这个问题就越严重。另外，牛顿法要求初始点选的比较好，也就是说应离极小点不太远，否则有可能使极小化序列发散或收敛到非极小点。,例3-3 给定 ，试用牛顿法计算其极小点。,给定初始点0=3，=0.001，计算结果如下：,函数的二阶导数：,解： 函数的一阶导数：,二、抛物线法（二次插值法）,二次插值的基本思想是利用目标函数在不同3点的函数值构成一个与原函数f(x)相近似的二次多项式p(x)，以函数p(x)的极值点

15、(即p(x*p)=0的根)作为目标函数f(x)的近似极值点。,1. 二次多项式p(x)的构成及其极小点 设原目标函数的初始单峰区间为。函数在x1, x2, x3 3点处函数值分别为f1, f2, f3，,求待定系数a0, a1和a2, 并代入上式，得：,令：,则上式可简化为：,如果 ，以x2,xp* 中函数值较小的点作为最优点x*。,2 缩短区间,假若f(x)本身为二次函数，则在理论上按前式一次求值就可找到最优点 。 若f(x)为高于二次的函数或为其他函数 ,可采用区间消去法逐步缩小区间 。 根据xp* ，x2，f(xp* )和f(x2)的相互关系，分4种情况进行区间缩小。 在已有的四x1,x

16、2,x3,xp* 中选择新的三个点x1,x2,x3，再进行二次插值。 选点要求： x1f2, f2f3 （高低高形态）,二次插值法的程序框图,（1）二次插值法只要求f(x)连续，不要求其一阶可微； （2）收敛速度比黄金分割法快，但可靠性不如黄金分割法 好，程序也较长。,二次插值法的特点：,例 34 用二次插值法求函数f(x)=3x3-4x+2的极小点，给定 x0=0, =0.2。,解 1）确定初始区间 初始区间a,b=0,2, 中间点x2=1。,2）用二次插值法逼近极小点 相邻三点的函数值: x1=0, x2=1, x3=2; f1=2, f2=1, f3=18. 代入公式：,xp*0.555, fp=0.292,在新区间，相邻三点的函数值: x1=0, x2=0.555, x3=1; f1=2, f2=0.292, f3=1. xp*0.607, fp=0.243 由于fpx2, 新区间a,b=x2, b=0.555,1 |x2-xp * |=|0.555-0.607|=0.0520.2, 迭代终止。 xp*0.607, f*=0.243,由于fp0.2, 应继续迭代。,例 3-5用二次插值法求 的极值点。初始搜索