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

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