一维搜索的最优方法(黄金分割法).ppt

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,第四章 一维搜索的最优化方法,一元函数的极小值问题，就是一维最优化问题，其数值迭代方法亦称为一维搜索方法。,一维搜索最优化是优化方法中最简单、最基本的方法。,主要方法有：,0.618,法,、牛顿法、,二次插值法,等。,迭代计算的基本格式,4,1,一维搜索的搜索区间,一、一维搜索的概念,在极小点附近，函数呈现“大小大”,一维搜索的思路,（,1,）确定极小点,*,所在的区间,a,b,，在此区间内，函数呈现“大小大”变化趋势。,搜速区间,。,a,b,（,2,）在,a,b,内找,*,将区,间长度逐步缩短。,0.618,法与二次插值法就是解决第二个步骤的方法,在极小点附近，函数呈现“大小大”,基本思想,从一点出发，按一定的步长，试图确定出函数值呈现出”高低高“的三个点。一个方向不成功，就退回来沿相反方向搜索。,具体作法：,二、确定搜索区间的进退法,进退法步骤,进退试算法步骤,例,4.1,用进退法确定函数,基本思路：逐步缩小搜索区间，直至最小点存在的区,间达到允许的误差范围为止。,一、消去法的基本原理,4,2,黄金分割法（,0.618,法）,二、,0.618,的由来,L,a,b,L,1,=,L,L,1,=,L,L,1,=,L,L,2,=(,),L,a,b,L,2,=(,),L,L,a,b,L,1,=,L,L,1,=,L,L,1,=,L,L,2,=(,),L,b,L,2,=(,),L,数学家华罗庚运用黄金分割法提出一种可以尽可能减少做试,验次数、尽快地找到最优方案的方法,优选法,三、,0.618,法的迭代过程及算法框图,黄金分割法计算框图,例,用,0.618,法求一元函数,4-3,牛顿法,基本思想：,在极小点附近，将目标函数做二阶,Taylor,展开，,得二次多项式，用该多项式的极小点近似原问题的极小点。,注意点：初始迭代点的选择很重要，要靠近极小点，否则可,能不收敛。,需计算一、二阶导数，计算两增大，实用可能不方便。,思考,：,实际问题如何得到初始迭代点？,割线法：,导数的近似计算。,割线法,4-3,二次插值法,注意点,比较,f,4,与,f,2,的大小,一般，函数在其极小点附近，可用一元二次函数很好地,逼近。故二次插值法有高的收敛速度。,三个点,(1),，,(2),和,(3),逐渐逼近极小点。,本章小结,序列消去法,进退法确定搜索区间，,0.618,法,缩短搜索区间,函数逼近法,牛顿法，二次插值法，如何设定,初始点？,