完整版一维搜索的最优方法黄金分割法课件.ppt

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

2、k)(k)?（k)（k)S即确定步长?，就是单变量函数?（?）的搜索问题。称为一维搜索问题。min ?（?）f(X?(k)?（k)（k)S)在极小点附近，函数呈现“大小大”yy? f(x)xyy? f(x)a?bx一维搜索的思路（间1）确定极小点*所在的区现“大小大”变化趋势。a, b，在此区间内，函数呈搜速区间。（2）在a, b内找*将区间长度逐步缩短。0.618决第二个步骤的方法法与二次插值法就是解在极小点附近，函数呈现“大小大”yy? f(x)xyy? f(x)x二、确定搜索区间的进退法? 基本思想从一点出发，按一定的步长，试图确定出函数值呈现出”高低高“的三个点。一个方向不成功，就退回

3、来沿相反方向搜索。具体作法： 给出初始点?0，初始步长h0? 0,若（? ?0h0）?（?0）,则下一步仍然从点?0出发，沿反方向搜索，直到目标函数上升就停止。这样就可以得到一个搜索区间。进退法步骤step1. 给定初始值。给定初始点?step2. 令?(0 )( 0 )，初始步长h ? 0。(1)(2)?，?(1)(1)(1)? h?。计算（f?），（f?）(2)(2) 令（f?） ?f1，（f?） ?f2step3. 若f2? f1，前进运算，? 令（f?） ?f3(3)(2)? h ?。计算（ f?( 3 )），停止计算(1)(3)(1) 若f2? f3，则 a,b=? ?(3)(1),

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

5、2)(3)(1)(3)(1)?，f2?f1，(3)(1)?，f3?f2? h?，计算（ f?），令（ f?） ?f3,( 3 )(2) ?(2)(3) 返回(1)重新开始。例4.1 用进退法确定函数f(a)? a ? 7a?10 的一维优化初始搜索区间 a,b。2设初始点?0? 0,初始步长h?1。解： 按顺序进行计算，有a. ?1?0? 0 f1? f(?1)?10 ?2?1? h?1 f2? f(?2)? 4b. 比较 f2? f1 ?3?2? h? 2 c. 比较 f2? f3 h? 2?1? 2 ?1?21, ?2?32, ?3?2? h 4 作前进运算f3? f(?3)? 0再作前进

6、运算 f1? f(?1)? 4f2? f(?2)? 0f3? f(?3)? ?2 d. 比较 f2? f3 再作前进运算 h? 2?2 ? 4 ?1?22, f1? f(?1)? 0 ?2?34, f2? f(?2)? ?2 ?3?2? h 8 f3? f(?3)?18e. 此时有 f1? f2， f2? f3 ,故a=?1? 2,b?3.即初始搜索区间为2,8.4 42 2 黄金分割法（黄金分割法（0.6180.618法）法）一、消去法的基本原理基本思路：逐步缩小搜索区间，直至最小点存在的区间达到允许的误差范围为止。 设一元函数 f(a) 的起始搜索区间为 a,b,?是函数的极小点。 在搜索

7、区间 a,b内任取两点?、?。且a ?f(?(1)(1)(2)*?(2)? b,计算f(?(1)、f(?(2)。将f(?(1)与(2)进行比较，可能出现三种情况： (1) f(?(1)? f(?(2 ).在这种情况下，可以丢掉(?(2)(2 ),b部分，而最小点必定在a,?内。f(?)aa(1)?*a(2)bf(?)a?*a(1)a(2)b? (2) f(?(1)? f(?(2).在这种情况下，可以丢掉 a,?(1)(1)部分，而最小点必定在 ?,b内。f(?)aa(1)?*a(2)bf(?)aa(1)a(2)?*b? (3) f(?(1)? f(?(2 ).在这种情况下，可以丢掉 a,?(1

8、)(1)部分，也可以丢掉 (?(2 ),b部分，而最小点必定在 ?,?(2 )内。因此这种情况可以并入上面的任意一种情况。f(?) (1) f (?(1 ) ? f (?( 2 ).取区间 a,?( 2 )； (2 ) f (?(1 ) ? f (?( 2 ).取区间 ?(1 ),b。aa(1)?*a(2)b二、0.618的由来1. ?,?（1）（2）在a,b中位置对称L2. 每次缩短的区间缩短率不变，减少计算量。L1= L(2)a(1)L1= LbL2L1?L1LL2=()L1?(2)a(1)b2?L2=() LL1= L?1? 0? 0.618LL1= L(2)a(1)L1= LbL2=(

9、)La?(1)(2)(1)bL2=() LL1= L? 0.618数学家华罗庚运用黄金分割法提出一种可以尽可能减少做试验次数、尽快地找到最优方案的方法 优选法三、0.618法的迭代过程及算法框图(1) 在初始区间a,b内取两个计算点?和?，其值分别为 ?b?0.618(b?a) ?a?0.618(b?a) 计算f(?(1)(2)(1)(1)(2 )和f(?(2 )，令f(?(1)? f1,f(?(2)? f2(2) 比比较函函数值，值，缩小搜索小搜索区间 a. f1? f2,则丢掉区间(? ?( 2 )(2 ),b部分，取a,?(2 )为(1) 新区间a1,b1,在计算中作置换：? b,?(1

10、)(1)? a(2 ),f1?f2,b?0.618(b?a)?(1), f(?)?f1)部分，取?(1) b. f1? f2,则丢掉区间a,? ?(1),b为(2 ) 新区间a,b,在计算中作置换：? a,?(2 )(2 )?(1),f2?f1,a?0.618(b?a)?, f(?)?f2(3) 判断迭代终止条件 当缩短的区间距离小于某一个预先规定的精 度，即b-a?时，终止迭代。 一般取区间的中点作为最优解。a?b* ?2初始条件：a,b,? b ? 0.618 (b ? a ) ?a(1) f (a(1) ? f1 a ? 0.618 (b ? a ) ?a(2) f (a(2) ? f2

11、黄黄金金分分割割法法计计算算框框图图否比较函数值。f1? f2 ?是a(2)?b,a(1)?a(2), f1?f2b? 0.618(b ? a ) ?a(1),f (a(1)?f1a(1)? a,a(2)? a(1),f2?f1a? 0.618(b? a)? a(2)f(a(2)?f2否b-a? ?是a? b?*2停例 用0.618法求一元函数f (a ) ? 2? 7? 1 的极小点。初始搜索区间为 a, b ? 0. 5,0.5 ，取迭代精度?0.15 。2解： (1) 在初始区间a,b内取点并计算函数值。 ?b?0.618(b?a)?0.118, f1f(?(2)(1)(1) 0.854

12、) 1. 09 ?a? 0.618(b?a)0.118, f2f(? (2) 比较函数值，缩短搜索区间 Q f1? f2 ? b? 0.5, a? 继续缩短 ?0.118， f11.09(1)(2 )(1)(2)? ?0.118 判断迭代终止条件: b-a? 0.5?(?0.118)? 0.618 ? 新点 ?a? 0.618(b?a)0.264, f2f(?(2 )(2) -1.125 (3) 比较函数值，缩短搜索区间 Q f1? f2 ? b? 0.5, a ? 继续缩短 ?0.264， f11.125 新点 ?a? 0.618(b? a)0.354, f2f(? (4) 比较函数值，缩短

13、搜索区间 Q f1? f2 ? a ? 0.118, b? 继续缩短 ?0.264， f21.125 新点 ?(1)b? 0.618(b? a)0.208, f1f(?(1) -1.120 (2)(1)(2)(2)(2)(1)(2)(1)? 0.118 判断迭代终止条件 : b-a ? 0.5? 0.118 ? 0.382 ?) -1.103 ? 0.354 判断迭代终止条件 : b-a ? 0.354 ? 0.118 ? 0.236 ?(5) 比较函数值，缩短搜索区间 Q f1? f2 ? a ?(1)? 0.208, b? 0.354? 判断迭代终止条件: b-a ? 0.354? 0.2

14、08 ? 0.146 ? 迭代停止。取? 0.5(a? b)? 0.281 理论解? 0.25?例： 对下列优化问题min f ( X ) ? ( x - 3)+ ( x - 4)+ 5122X ? E22设 搜索方向 S做一维搜索(0)? 2,3, XT(0)? 2,3T主要步骤：（ 1）转化为一维搜速问题； （ 2）用进退法确定初始搜速区间； （ 3）用 0.618 法确定初始搜速区间；4-3 4-3 牛顿法牛顿法基本思想：在极小点附近，将目标函数做二阶Taylor 展开，得二次多项式，用该多项式的极小点近似原问题的极小点。对初始点（极小点的估计）： x(0)(0)(0)(0)(0)(0)

15、2?(x) = f(x )+ f?(x )(x-x)? 0. 5 f? ?(x )(x-x)(0)(0)(0)? ?令 ?(x)0，有 f (x )? f (x )(x-x )0? 新的极小点 x= x(0)(0)f?(x )?(0)f? ?(x )(1)(0)令 x（1）= x(0)f?(x)f?(x)（2）(1)?x x? L(0)(1)? ? ?f (x)f (x)一般迭代格式x(k+1)= x(k)f?(x )?(k)f? ?(x )?(k)结论：设f(x)存在连续二阶导数，x 满足 f(x )0；f? ?(x )? 0 初始点x 接近x，由牛顿法产生的 迭代序列?x(k)(0)?收敛

16、于x。 ?计算步骤：1） 给定初始点x ，允许误差? 0, 0 ? k2 ） 若 f?(x )?，迭代停止，得x ? x 否则，进行下一步3）计算 x(k+1)(k)?(k)(0)f?(x )= x?，(k)f? ?(x )(k)(k) k1? k，转步2 ）注意点：初始迭代点的选择很重要，要靠近极小点，否则可能不收敛。需计算一、二阶导数，计算两增大，实用可能不方便。例 minf ( x) 3x 4x 12 x1x? E432x（ 0） 1.2，迭代两次思考：实际问题如何得到初始迭代点？割线法：导数的近似计算。yy= f(x)切线斜率割线斜率xx(k)(k-1)x(k)(k)f(x)f(xf?

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

18、f(x)f1f2f3x?(3)a?(1)?(2)?P?b在a,b 中设定三点?，?和?a ?(1)(1)(2)(3)?(2)?(3)? b对应有 f1, f2, f3,且f1? f2? f3y构造二次多项式P(x)? a0? a1x ? a2x2y= P(x)y= f(x)f1f2f3xa?(1)?(2)?(3)b由插值条件确定待定的ai(i=0,1,2)P(?P(?P(?(1)(2)(3)? a0? a1?)? a0? a1?)? a0? a1?(1)(2)(3)? a2(?)? f1?(2)2? a2(?)? f2?L(1)?(3)2? a2(?)? f3?(1)2求P(x)极小点， P(

19、x)? a1? 2a2x ? 0a1? ?2a2?PC1?1?(1)(3)?2?C2?f3? f1其中， C1?(3)(1)?PC2?(f2? f1) /(?(2)?(3)(1)?C1?(2)?（1）?，fP? f2 ?(1)?P(2)?,?y?P(2)?(2),?(2)?(3) f1= fP , f2= f2 , f3= f3 y? f(?)f1f3f2(1)fPx?P?(2)?(3)?(1)?(2)?(3)（3）?，fP? f2 ?(1)?P(2)?(1),?(2)?(2),?(3)?P f1= f1 , f2= f2 , f3= fP yy? f(?)f3f1f2fPx?(1)?(2)?

20、P?(3)?(1)?(2)?(3)比较?与?两点， f(x)的大小；缩短搜索区间。?P(2)（1）?，fP? f2 ?(2)?(2)(1),?(2)?P(2),?(3)（3）?，fP? f2 ?(1)?(1), ?(2)?, ?P(3)注意点1) 三个试探点?(1)?(2)?(3) 且 f1? f2, f2? f3; 大-小-大2) 迭代中止条件 记?与f2是前一次迭代的插值函数极小点与极小值； 记?与f4是本次迭代的插值函数极小点与极小值。 ?1、?2是给定的精度 若 ?（4）（4）（2）-?（2）?1 或 f4-f2?2例. 二次插值法， f( x) =e? x 做一搜索，初始搜索 0,1

21、 , ?=01 .4.543.532.521.510.5-1-0.500.511.52- x2yx初始搜索0, 1解 ( 1)取 ?（ 1）? 0，?（2）? 0.5，?（3）?1f1?1，f2? 0.8565，f3?1.3679f3? f1(2) C1?(3)? 0.3679(1)?f2? f1? C1(2)(1)? C2?1.3096(2)(3)? ?（4）(4)? 0.5(?(2)（ 1）?（3）? C1/C2)=0.3595 ? 0.1405 ? 比较 f4 与 f2的大小 f4? 0.8273(3) Q f4? f2, ? ? ?(3)(2)(4)?(2)?(2)(4)? 0.5; f3? f2? 0.8565? 0.3595; f2? f4? 0.8273 ?(4) 返回第二步 C1=-0.2869； C2=1.3776； ?(4)? 0.3541;(4) Q ?(4)(2)? 0.0054 ? ? ? 0.3541三个点(1)， (2)和(3)逐渐逼近极小点。一般，函数在其极小点附近，可用一元二次函数很好地逼近。故二次插值法有高的收敛速度。yy= P(x)y= f(x)x?P本章小结序列消去法进退法确定搜索区间， 0.618法缩短搜索区间函数逼近法 牛顿法，二次插值法，如何设定初始点？