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

1、 一元函数的极小值问题，就是一维最优化问题，其数值迭代方法亦称为一维搜索方法。 一维搜索最优化是优化方法中最简单、最基本的方法。 主要方法有：0.618法、牛顿法、二次插值法等。迭代计算的基本格式迭代计算的基本格式( )(1)( )( )kkkkXXS4 41 1 一维搜索的搜索区间一维搜索的搜索区间一、一维搜索的概念一、一维搜索的概念k)k) S（显然，搜索方向和步长因子构成决定了每最优一次迭代化算法好的修正量，它们是坏的重要因素。k)k)k)k)(1)( )k)k)( )( )k)k)k) SXS ()()() ()kkkkffff （假定给定了搜索方向，从点出发沿方向进行搜索，要确定步长

2、，使得记（ ）即确定步长，就是单变量函数 （ ）的搜索问题。称为一维搜索问题。XXSXXS( )k)k)min ()kf （ ）XS在极小点附近，函数呈现在极小点附近，函数呈现“大小大大小大”xy( )yf xxy( )yf x一维搜索的思路一维搜索的思路（1）确定极小点）确定极小点*所在的区所在的区间间a, b，在此区间内，函数呈，在此区间内，函数呈现现“大小大大小大”变化趋势。变化趋势。搜速区间搜速区间。ab（2）在）在a, b内找内找*将区将区间长度逐步缩短。间长度逐步缩短。0.618法与二次插值法就是解法与二次插值法就是解决第二个步骤的方法决第二个步骤的方法在极小点附近，函数呈现在极小

3、点附近，函数呈现“大小大大小大”xy( )yf xxy( )yf x 基本思想 从一点出发，按一定的步长，试图确定出函数值呈现出”高低高“的三个点。一个方向不成功，就退回来沿相反方向搜索。 具体作法：二、确定搜索区间的进退法二、确定搜索区间的进退法00000000000 0,hhhh 给出初始点，初始步长若（ ）（）,则下一步仍然从点出发，沿反方向搜索，直到目标函数上升就停止。这样就可以得到一个搜索区间。进退法步骤0step1. 0()h给定初始值。给定初始点，初始步长。(1)(2)(1)(2)0112step2. ()( )( )()2hffffff1令，。计算（），（）令（），（）3(3)

4、3(3)2123232132step3. ()()f,f ,ffhffffffffffhff33若，。计算（）令（）(1) 若，则a,b=，(2) 若，则 2hh前进运算， ，计算（），令（止算返停计）(2)(3)(1)(3)(2)(1)(3)(2)(2)(3)1( )回重新开始。进退试算法步骤进退试算法步骤3(3)2113213231step4. -; ()hh,;,;fffffffffhffff3若在步2中，后退运算 以为起始点，重排顺序+。计算（），令（）(1) 若，步长反号，反方向a,搜索。则(1)(1)(3)(2)(1)(3)(2)(2)(3)3(3)312132 1(),f ,(

5、)ffffffhff3b=，(2) 若，则 2hh， ，计算（），令（）停止计算。返回重新开始。(3)(2)(2)(1)(3)(2)(2)(3)例4.1 用进退法确定函数2710 01(),f aaah0的一维优化初始搜索区间a,b。设初始点初始步长。12122133231 a. 0 10 1 4b. 2 0 2 12 1 ()()()., ffhffffhffcffh1012232解： 按顺序进行计算，有比较作前进运算比较再作前进运算132323 4 2 0 2(),()() ffffhff12234 231132323122313 2 24 0 2 18 ,=2.,(),()().,.df

6、fhffffhffeffffab 21223比较再作前进运算248 此时有，故即初始搜索区间为2,8.基本思路：逐步缩小搜索区间，直至最小点存在的区间达到允许的误差范围为止。一、消去法的基本原理12121212 ( )()( )()( )(*( )() , ,()()(,),(a babfff aa bff设一元函数的起始搜索区间为是函数的极小点。 将在搜索区间内任取两点、。且计算、。与进行比较，可能出现三种情况：( )4 42 2 黄金分割法（黄金分割法（0.6180.618法）法） 1222 1 ( )()()()( )()().(,ffba这况丢点内在种情下，可以掉部分，而最小必定在。1

7、( )a()f()fab*a*1( )a2()a2()ab1211 2 ( )()( )( )()()(). ,), ffab在这种情况下，可以丢掉部分，而最小点必定在内。1( )a()f()fab*a*1( )a2()a2()ab121212 3 ( )()( )()( )()( )()(). ,), ,ffab在这种情况下，可以丢掉部分，也可以丢掉(部分，而最小点必定在内。因此这种情况可以并入上面的任意一种情况。()fab*1( )a2()a122121 1 2 ()()()()()()( )()().,()()().,ffaffb取区间；取区间。二、二、0.618的由来的由来11 .,（

8、 ）（2）在a,b中位置对称2. 每次缩短的区间缩短率不变，减少计算量。Lab(1)(2)L1= LL1= L211LLLLL1= LL 2=()L(2)ab(1)L 2=() L1210 0 618.Lab(1)(2)L1= LL1= L0 618.L1= LL 2=()L(2)b(1)L 2=() La (1)数学家华罗庚运用黄金分割法提出一种可以尽可能减少做试数学家华罗庚运用黄金分割法提出一种可以尽可能减少做试验次数、尽快地找到最优方案的方法验次数、尽快地找到最优方案的方法优选法优选法三、三、0.618法的迭代过程及算法框图法的迭代过程及算法框图1212121212(1) a,b 0 6

9、18 0 618 ( )()( )()( )()( )().().()()()(), ()bbaabaffffff在初始区间内取两个计算点和，其值分别为计算和，令22121121211211122 a. 0 618 b. ()()()( )()( )( )(), ,.(),(), ,ffbaa bbaff bbaffffa则丢掉区间(部分，取为新区间在计算中作置换较数缩区间：则丢掉区间比比函函值值，小小搜搜索索1112122122 0 618 )( )( )()( )()(), , ,.(),()ba baff abaff部分，取为新区间在计算中作置换：3 2*( )-b aab判断迭代终止条

10、件当缩短的区间距离小于某一个预先规定的精度，即时，终止迭代。一般取区间的中点作为最优解。黄金分割法计算框图黄金分割法计算框图否停是2*ab111222 0 618 0 618 ()()()().()().()()bbaafafabaafaf12 ?ff比较函数值。121212220 618( )()( )()(),.()()aa aaffabaaf af, ,a b初始条件： -?b a212121110 618()()()()(),.(),()ab aaffbbaafaf是否例例 用用0.6180.618法求一元函数法求一元函数2271 a,b0 5,0.50.15()fa的极小点。初始搜索

11、区间为 .，取迭代精度 。11122212 (1) a,b 0 6180 118 0.854 0 6180 118 109 (2) ( )( )()().().,().().,()bbaffabaffffb在初始区间内取点并计算函数值。 .比较函数值，解：缩短搜索区间11212220 5 0 1180 50 1180 618 0 118 1.09 0 618 ( )( )()()(). ,.-.(.).()() ab afabaff 判断迭代终止条件: 继续 ，新点0.264,缩短-1.1251211212 (3) 0 5 0 1180 50 1180 382 0 264 1.125 ( )(

12、 )()(). ,.-.ffbab af比较函数值，缩短搜索区间 判断迭代终止条件 : ，新点 继续缩短2212220 618 (4) 0 118 0 3540 3540 1180 236 ()()()(.()().,.-.abaffffabb a0.354,-1.103 比较函数值，缩短搜索区间 判断迭代终止条件: 继短续缩121110 264 1.125 0 618 )( )( ).()()fbbaff，新点0.208,-1.120121(5) 0 50 28 10 0 3540 3540 2080 14562( ),.-. ().ffbb aaab比较函数值，缩短搜索区间0.208 判断

13、迭代终 迭代停止。取 止 理论解条件: 22212E(0)T(0)Tmin()(- 3) + (- 4) + 52,3 2,3,XfXxxSX对下列优化问题设例：搜索方向 做一维搜索 （1）转化为一维搜速问题；（2）用进退法确定初始搜速区间； （3）用0.618法确定初始搜主要步骤：速区间；4-3 4-3 牛顿法牛顿法基本思想：基本思想：在极小点附近，将目标函数做二阶在极小点附近，将目标函数做二阶Taylor展开，展开，得二次多项式，用该多项式的极小点近似原问题的极小点。得二次多项式，用该多项式的极小点近似原问题的极小点。(0)(0)(0)(0)(0)(0)2( ) =()+()(0 5()(

14、xxf xfxx- x)fxx- x)对初始点（极小点的估计）： .(0)(0)(0)(0)(0)(0)( )0()()()() ()xfxfxx- xfxx= xfx令 ，有 0新的极小点(0)(1)1(0)2(1)(0)(1)()() ()()fxfxx= xxxfxfx（ ）（ ）令(k)(k+1)(k)(k)()()fxx= xfx一般迭代格式(0)(k) f xxf xfxxxxx设 ( )存在连续二阶导数， 满足()0； ()0初始点接近 ，由牛顿法产生的 迭代序列收敛于 结论。：(0)(k)(k)(k)(k+1)(k)(k)0 0()() 1x,k2 f xxxfxx= xfxk

15、k21） 给定初始点，允许误差） 若()，迭代停止，得 否则，进行下一步3）计计算步骤算 ，转步 ）：注意点：初始迭代点的选择很重要，要靠近极小点，否则可注意点：初始迭代点的选择很重要，要靠近极小点，否则可 能不收敛。能不收敛。 需计算一、二阶导数，计算两增大，实用可能不方便。需计算一、二阶导数，计算两增大，实用可能不方便。1432E0 m in()34121 2fxxxxx.x（）例 ， 迭 代 两 次思考思考：实际问题如何得到初始迭代点？实际问题如何得到初始迭代点？割线法：割线法：导数的近似计算。导数的近似计算。(k)xxy(k-1)x( )y= f x切线斜率割线斜率(k)(k1)(k)

16、(k)(k1)()()()f xf xfxxx(k)(k1)(k)(k)(k1)()()()fxfxfxxx割线法割线法(k)(k1)(k+1)(k)(k)(k1)()()()()f xf xx= xfxfx一般迭代格式不需计算导数，但收敛速度较牛顿法慢。1432E0 m in()34121 2fxxxxx.x（）例 ， 迭 代 两 次4-3 4-3 二次插值法二次插值法P( ) , , xa ba b基本设函数在内呈现“大小大”单峰变化在上以低次（二次或三次）插值多项式来逼近原目标函数，求得多项式的极值点，逐步缩短搜速区间。反复计算，直至给定精度。此法应想。思用较广：(1)xy( )y= f

17、 xab(2)(3)1f2f3f( )y= P x(1)(2)(3)(1)(2)(3)ab在a,b中设定三点，和123123f , f , f ,fff对应有 且P2012xaa xa x构造二次多项式P( )(1)(1)(1)20121(2)(2)(2)20122(3)(3)(3)20123(i=0,1,2)()()(1)()aaaafaaafaaafi由插值条件确定待定的P()P()P()(1)xy( )y= f xab(2)(3)1f2f3f( )y= P x121(1)(3)1P2P2202C12Cxxaa xaa求P( )极小点，P( )311(3)(1)(2)(1)2112(2)(

18、3)C()()CCffff/其中，(2)PP2(1)(1)(3)(2)(2)P1132 2P 1 ff, f = f , f = f ,f = f（ ），( )fy1fP(1)(2)Pf(3)yx2f3f(1)(2)(3)(2)PP2(1)(2)(2)(3)(3)P1P32 33 3 ff, f = f , f = f ,f = f（ ），( )fy1fP(1)(2)Pf(3)yx2f3f(1)(2)(3)(2)Pf x比较与两点， ( )的大小；缩短搜索区间。(2)PP2(1)(1)(2)(3)(2)P1 ff,（ ），(2)PP2(1)(2)(2)(3)(3)P3 ff,（ ），注意点注意

19、点(1)(2)(3)1223 -; 1- ff , ff) 三个试探点 且大 小 大241242122 2442ffff（ ）（ ）（ ）（ ）) 迭代中止条件 记与 是前一次迭代的插值函数极小点与极小值； 记与 是本次迭代的插值函数极小点与极小值。、是给定的精度 若 - 或 -20,101xf xex- 二次插值法， ( ) =做一搜索，初始搜索 , =例.-1-0.500.511.520.511.522.533.544.5xy0, 1初始搜索123100.51（ ）（ ）（ ） ()取 ，解，12310.85651.3679fff，311(3)(1)211(2)(1)2(2)(3)(2)

20、C0.3679C C1.3096ffff41312(4)(2)40 5(CC )=0.3595 0.14050 8273./ f.（ ）（ ）（ ） 比较比较 f4 与与 f2的大小的大小(4)(2)42(3)(2)32(2)(4)24(3) 0 5; 0 8565 0.3595; 0 8273ff ,.ff.ff.12(4)(4)(2)(4)(4) C =-0.2869 C =1.3776 0.3541; 0.0054 0.3541返回第二步； 一般，函数在其极小点附近，可用一元二次函数很好地一般，函数在其极小点附近，可用一元二次函数很好地逼近。故二次插值法有高的收敛速度。逼近。故二次插值法有高的收敛速度。xy( )y= f x( )y= P xP 三个点三个点(1)， (2)和和(3)逐渐逼近极小点。逐渐逼近极小点。本章小结本章小结序列消去法序列消去法进退法确定搜索区间，进退法确定搜索区间，0.618法法 缩短搜索区间缩短搜索区间函数逼近法函数逼近法牛顿法，二次插值法，如何设定牛顿法，二次插值法，如何设定 初始点？初始点？