3一维搜索法.ppt

第三章常用的一维优化方法§3- 1 概述§3- 2 单峰区间的确定§3- 3 黄金分割法§3- 5 二次插值法§3- 4 i 法作业§3- 1 概述一、问题的提出 1、实际设计工作中会遇到一维优化设计问题在长为 350cm 、宽为 260cm 的长方形不锈钢板的四角,各剪去一个小正方形,做成一个无盖的储水箱,试确定正方形的边长,使储水箱的容积最大。 f x x x x max ( ) (350 2 ) (260 2 ) ? ? ??? s t x . . 0 130 ? ? x 2、多维优化设计转化为一维优化设计问题多维优化问题求解过程: ( 1) ( ) ( ) k k+ k k X X d ? ?? X (1)d (0) 0? d (1) (2)d (3)d (2)X (3)X (4)XX (0) ( ) ( ) min ( ) min ( ) min ( ) k k f X f X d ???? ??二、一维优化方法的分类 ( ) 0 dd ????( ) ( ) ( ) ( ) ( ) 2 ( ) ( ) ( ) ( ) ( ) 1 ( ) ( ) ( ) 2 k k k k T k k T k k f X d f X f X d d H X d ?? ?? ?? ?? ???( ) ( ) ( ) ( ) ( ) ( ) ( ) 0 k T k k T k k f X d d H X d ?? ? ?由( ) ( ) ( ) ( ) ( ) ( ) ( ) k T k k T k k f X d d H X d ?????方程求根法区间收缩法二分法、切线法、割线法等分数( i )法、黄金分割( ) 法、插值法等得§3- 2 单峰区间的确定定义设α*是?(α) 的极小点,若存在闭区间[a, b], 使得α*∈[a, b], 且使函数值呈“高—低—高”的形态,即函数?(α) 在闭区间[a, b]中有唯一极小点,则称[a, b]是?(α)单峰区间. 一、单峰区间的定义非单峰区间单峰区间二、单峰区间的确定确定搜索区间的一种简单的方法是进退法,其基本思想是从某一点出发,按一定的步长,确定函数值呈“高—低—高”的三点。如果一个方向不成功,就退回来,再沿相反的方向寻找。具体算法步骤如下: (4) 如果 k=1, 则置μ 2=μ,? 2= ? ,和 h=-h, 转(2); 否则置μ 1=μ 2 , ? 1= ? 2,μ 2= μ 3, ? 2= ? 3 , μ 3= μ, ? 3= ?, 并令 a=min{ μ 1,μ 3 }, b=max{ μ 1,μ 3 }, 停止计算. (1) 取初始步长 h, 置初始值μ 3=0 , ? 3= ?(μ 3),并置 k=0. (2) 置μ=μ 3+h ,?= ? (μ)和 k=k+1. (3) 如果?<? 3, 则置μ 2=μ 3 , ? 2=? 3 , μ 3=μ, ? 3=?和 h=2h,k=k+1, 转(2);??3? h2h 4h 1? 2?二、单峰区间的确定?? 3? h2h 4h 1? 2? 4? h ab??h ha b 开始输入: h置μ 3=0 ,? 3= ?(μ 3), k=0 置μ=μ 3+h ,?= ? (μ),k=k+1 μ 2=μ 3 , ? 2=? 3 , μ 3=μ,? 3=?, h=2h,k=k+1 ?<? 3? k=1? μ 2=μ,? 2 = ? , h=-h, μ 1=μ 2 , ? 1= ? 2,μ 2= μ 3, ? 2= ? 3,μ 3= μ,? 3= ?, a=min{ μ 1,μ 3}, b=max{ μ 1,μ 3}结束 yes no yes no 三、算法框图四、区间收缩原则与区间收缩率 1???ab 1a 2? 2a ? 1>? 2? yes no a=a 1b=b a=a b = a 2 1 2 a b aa ab ab ??新区间长旧区间= 长= 黄金分割法(Golden Section Method) 又称为 法, 是用于在单峰函数区间上求极小的一种方法。其基本思想是通过取试探点和进行函数值比较,使包含极小点的搜索区间不断减少,当区间长度缩短到一定程度时,就得到函数