《一维搜索的最优方法黄金分割法课件》由会员分享，可在线阅读，更多相关《一维搜索的最优方法黄金分割法课件（46页珍藏版）》请在金锄头文库上搜索。
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) ?（?）
2、f (X（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，则
4、a,b=? ?(3)(1),?(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
5、，? ?(3)(2)(3)(2)(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
6、? f(?3)? 0再作前进运算 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? (
8、3) f(?(1)? f(?( 2).在这种情况下，可以丢掉 a,?(1)(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=()
9、LL1= L?1? 0? 0.618LL1= L(2)a(1)L1= LbL2=()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
10、)( 2 ),b部分，取 a,?( 2)为(1) 新区间 a1,b1,在计算中作置换：? b,?(1)(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
11、 ) ?a( 1 ) f ( a( 1 ) ? f1 a ? 0.618( b ? a ) ?a( 2 ) f ( a( 2 ) ? f2黄黄金金分分割割法法计计算算框框图图否比较函数值。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，取迭
12、代精度?0.15。2解： (1) 在初始区间a,b内取点并计算函数值。 ?b?0.618 (b?a)?0.118, f1f(?( 2)(1)(1) 0.854) 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 f
13、1? f2 ? b? 0.5, a ? 继续缩短 ?0.264， f11.125 新点 ?a ?0.618(b?a)0.354, f2f (? (4) 比较函数值，缩短搜索区间 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
14、.236?(5) 比较函数值，缩短搜索区间 Q f1? f2 ? a ?(1)? 0.208, b? 0.354? 判断迭代终止条件: b-a ? 0.354?0.208? 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 牛顿法牛顿法基本思想：在极小
15、点附近，将目标函数做二阶Taylor展开，得二次多项式，用该多项式的极小点近似原问题的极小点。对初始点（极小点的估计）： x(0)(0)(0)(0)(0)(0)2?(x) = f (x)+ f ? (x)(x- x)?0. 5f ? ? (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)?xx? L(0)(1)? ? ?f (x)f (x)一般迭代格式x(k+1)= x(k)f ? (x)?(k
16、)f ? ? (x)?(k)结论：设f(x)存在连续二阶导数，x 满足 f(x )0；f ? ? (x )? 0 初始点x 接近x，由牛顿法产生的 迭代序列?x(k)(0)?收敛于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 ? (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 ? (
