最优化课件9一维搜索

1、2022-4-28最优化理论1最优化理论与算法9， 一维搜索2022-4-28最优化理论2第九章 一维搜索 一维搜索的基本概念 试探法 函数逼近法2022-4-28最优化理论39. 一维搜索一维搜索-概念1最优化方法的基本结构：给定初始点x0 (a) 确定搜索方向dk，即按照一定规则，构造f在xk点处的下降方向 作为搜索方向;(b)确定步长因子 k，使目标函数值有某种意义下的下降;(c)令 xk+1 = xk + kdk 若xk+1满足某种终止条件 则停止迭代，得到近似最优解xk+1， 否则，重复上述步骤。9.1 一维搜索概念一维搜索概念,(),().kkkkf xd 注意到上述迭代算法中当方

2、向确定后 涉及到求一个步长使得目标函数值减小 极小化问题 这就是在一直线上求目标函数的极小点,即极小化这称维搜索问题为 对变量的一,或称为搜索.线2022-4-28最优化理论49. 9. 一维搜索一维搜索-概念2( )( )( )( )( )( ),(9.1.1)( ) |,- ( )( (9.1.2).)kkkkkkf xxdf xLx xxdf xdL 设目标函数为过点沿方向的直线可用点集来表示: 求在直线 上的极小点就转化为求的极小点 ( )kk(1)( )( )( ),( ) (9.1.3)kkkkkdf xLxxd设的极小点为称为沿方向的于是在直线 上的极小点为步长因子 2022-4

3、-28最优化理论59. 9. 一维搜索一维搜索-概念3函数逼近法/插值法试探法一维搜索 一维搜索算法的闭性一维搜索算法的闭性假设一维搜索是以x为起点,沿方向为d的进行的,并定义为算法映射算法映射M0:RRR ( , ) |,9.1.1 (9.1.4()min()nnnMM x dy yxdf xxDdfdf满足 算法映射 义 定为2022-4-28最优化理论69. 9. 一维搜索一维搜索- -概念4( )( )( )( )0,0,(9.1.5) (9. 1.6)kkkkkdyddxk由当 充分大时 必有于是由( )( )( )( )( )( )( )( )( )( )(,(,: ( , ) ,

4、 ,0 , (,)( , ); (9.1 ) .)5 kkkkkkkkkkkkkxdx dyxdyM xy yxkyxMddd证 设序列和满足 下证 注意到 对每个 ,使Th9.1.1 设f是定义在Rn的连续函数,d0,则(9.1.4)定义的算法映射M在(x,d)处是闭的2022-4-28最优化理论79. 9. 一维搜索一维搜索- -概念5( )( )( )k, (9.1.7)(9.1.5)k(9.1.7), (9.1.8)M,0 , ( )() (9.1.9),k,(9.1.9) kkkkkkyxdyxdkfyf xdf 令则中令并注意到有根据的定义 对每个 及有由于 连续 令则由得0( )

5、() ()min() ( , ) fyf xdf xdf xdyM x d故 即知 2022-4-28最优化理论89. 9. 一维搜索一维搜索- -试探法19.2.1, 0.618法法(1)(2)(1)(2)(2)(1)(2)(1)(1)(2) , , , , , ,()()()() , 9.2.1fa bxfa bxxa bxxxxf xf xxxf xf xfafbD设 是定义在闭区间上的一元实函数是 在上的极小点 且对有 当时 当时则称 是在闭区间上的单峰函数.2022-4-28最优化理论99. 9. 一维搜索一维搜索- -试探法试探法2 单峰函数具有一些很有用的性质:如果f是a,b上单

6、峰函数,则可通过计算此区间内两不同点的函数值,就能确定一个包含极小点的子区间,从而缩小了搜索区间.单峰函数的一个等价定义：:, , ,* , ( ) , *, *, , , ( ),( ) , .fRR a bRa bf xaba bf xf xa b 设若，使得在上严格递减 在上严格递增 则称是函数的是上的单峰区间单峰函数2022-4-28最优化理论109. 一维搜索一维搜索-试探法试探法3(1)(2)(1)(2)(1)(2)(1)(2)(1)(2)(2)(1) , , , .,(1)()(), ,( )()(2)()(), ,( )(),9.2.1fa bxxa bxxf xf xxa x

7、f xf xf xf xxxbxhxTff 设 是区间上的单峰函数且则 若则若则2022-4-28最优化理论119. 一维搜索一维搜索-试探法试探法4 4证明:仅证(1),反证,如若不然,存在点x*a, x(1),使(2)(1)(1)(1)(1)(1)(2)(1)*(1)(2) ( *)(). , . ,()(),.,b,()()(),.f xf xxxa xxxbxa xf xf xxxf xf xf x显然不是极小点此时要么极小点要么若则矛盾若则矛盾(1)(2)(1)(1)(2)(2),: (1)()(),b;(2)()(), ,.根据以上定理 只需选择两个点就可缩短包含极小点的区间 若则

8、极小点 若则极小点f xf xxxf xf xxa x2022-4-28最优化理论129. 一维搜索一维搜索-试探法试探法5 50.618法的基本思想:通过取试探点使包含极小点的区间(不确定区间)不断缩小,当区间长度小到一定程度时,区间上各点的函数值均接近极小值,此时该区间内任一点都可以作为极小点的近似值.111111 ( ) , ,.,.()(),1(1),()(), (2.1)(2),()(), (2:.2) kkkkkkkkkkkkkkkkkkkkkkaaba bkabba bTha b 设是搜索区间上的单峰函数.设在第 次迭代时搜索区间为取两个试探点计算令和根据若令若2022-4-28

9、最优化理论139. 一维搜索一维搜索-试探法试探法6 6由( 2.3)和(2.4)得到11 , (2.3:(1),)(2),), (2.4,)kkkkkkkkkkkkkkbabar ba ba我们要求两个试探点和满足下列条件和到搜索区间的端点等距 即 每次迭代 搜索区间长度的缩短率相同即 (1r)() , (2.5)(), (2.6)kkkkkkkkabaar ba 2022-4-28最优化理论149. 一维搜索一维搜索-试探法试探法7 7今考虑( 2.1)的情形,此时新的搜索区间为111111112 (2.7)2() =r() =r(r(), , (2.8) =r ()kkkkkkkkkkk

10、kkkkkkkkkkabaar baaaaabaaaba为进一步缩短区间.需取试探点和.由( .6) 2022-4-28最优化理论159. 一维搜索一维搜索-试探法试探法8 82111) -15= (2.9) (2.10)2,.(2.9) 0, 21-1+ 5=0. 6182 kkkkkkkkkaba 若令 则 这样新的试探点就不用重新计算只要取,于是每次迭代中(除第一次)只需取一个试探点.类似的,如考虑( .2)的情形,新的试探点=它也不需重新计算解方程立得区间长度缩短率由于=+(1- )(故取 (2.11)2022-4-28最优化理论169. 一维搜索一维搜索-试探法试探法9 9这样,计算

11、公式(2.5)(2.6)可写为-111112,(),0.618 0.618,1- ,101 由于每次函数计算后极小区间的缩短率为 故若初始区间为则最终区间长度为因此可知法是线性收敛的。法也叫黄金分割法 因为缩短率 叫黄金分割数，它满足比率 即 。nra brbarrrr0.382() , (2.12)0.618(), (2.13)kkkkkkkkabaaba 2022-4-28最优化理论179. 一维搜索一维搜索-试探法试探法10其几何意义:黄金分割率对应的点在单位长区间0,1中的位置相当于其对称点1-在区间0,中的位置ak+lbk+lk+lk+lk+lk+lbk+lak+lakbkkkSte

12、p 2Step 32022-4-28最优化理论189. 一维搜索一维搜索-试探法试探法11算法算法(0.618法法)111111111111111:,a ,b 0. 0.382() 0.618()().abaaba 步 选取初始数据 确定初始搜索区间和精度要求计算最初两试探点 ， ：， 计算和 (2:.()(),3()()4kkkk 步比较函数值若则转步 ， 否则，转步2022-4-28最优化理论199. 一维搜索一维搜索-试探法试探法12k+1k+11k+1k+1k+1k+1k+113,;,:,:,:,()(),0.618()()5kkkkkkkkkbabbaba 步 :若停止计算 输出否则

13、令 ，计算转步5:k:k1,2步转步 。k+1k+11k+1k+1k+1k+1k+114:,;,:,:,:,():(),0.382()(),5kkkkkkkkkaaababa 步 若停止计算 输出否则令 ，计算转步2022-4-28最优化理论209. 一维搜索一维搜索-试探法试探法132.2 Fibonacci法 Fibonacci法是与0.618法类似的一种分割方法。 它与0.618法的主要区别之一在于：搜索区间 长度的缩短率不是采用黄金分割数，而是采用 Fibonacci数：1101 , 1, 1,2,. nnnFFFFFn1111(1)() (),1,2,.,1(), 1,2,., -1

14、 n kn kn kn kn kn kFkkkkFFkkkFFkkkkFabaabaknabakn Fbinacci法中计算公式为：2022-4-28最优化理论219. 一维搜索一维搜索-试探法试探法14显然, 这里Fn-k /Fn-k+1相当于0.618法(1.5)-(1.6)中的,每次的缩短率满足12-112231111111111 (), ( ) .()() nnnn kkkkkn knnFnnnnFFFFFFFFFbabaFnnbababababa 这里 时计算函数值的次数 即要求经过 次计算函数值后 最后区间的长度不超过即由于2022-4-28最优化理论229. 一维搜索一维搜索-试

15、探法试探法1511111111 ()(1.20),1151522551lim2nnnnkknkkkbabaFFFibonacciFFnnFFF故（1.20）给出最终区间长度得的上界 ，由求出数再跟据确定出从而搜索一直进行到第 个搜索点为止. 注意到从而2022-4-28最优化理论239. 一维搜索一维搜索-试探法试探法16算法算法(Fibonacci法法)1111211111111, , .,0.(),()nnnnnStepa bLbanFLFFabaabaFF1111给定初始区间和最终区间长度 求计算函数值的次数使得置辨别常数计算试探点 和 ：上式表明当上式表明当n 趋于无穷时趋于无穷时,F

16、inonacci法与法与0.618法的区间缩短法的区间缩短率相同率相同,因而也是以收敛比因而也是以收敛比r线性收敛。可以证明线性收敛。可以证明Fibonacci法法是分割方法求一维极小化问题的最优策略，而是分割方法求一维极小化问题的最优策略，而0.618法是近法是近似最优的。似最优的。2022-4-28最优化理论249. 一维搜索一维搜索-试探法试探法17计算函数值(1 ) , (1).置k=1kkkk1k1k1kk11111k12,3,.().2,6kkkn kkkkn kStepStepabbFabaFkn k+1若 () (),转3；若 ()(),转4。令计算试探点若转 ，否则，计算 (

17、)，转5。1k1k1kk12111k14,.().2,6kkkn kkkkn kStepabFabaFkn k+1令计算试探点若转 ，否则，计算 ()，转5。2022-4-28最优化理论259. 一维搜索一维搜索-试探法试探法18Step 5, 置k:=k+1,转2.n-1n1kknn1kkn-1n6,.),.nnnnnnnnnnStepabbaaba b 令计算 ()。若 () (),则令；若 ()(),则令。停止计算，极小点含于2022-4-28最优化理论269. 一维搜索-试探法试探法192.3 进退法进退法2022-4-28最优化理论279. 一维搜索-试探法试探法20算法算法( (进

18、退法进退法) )输出a,b2022-4-28最优化理论289. 一维搜索-函数逼近法函数逼近法11.1.牛顿法牛顿法考虑问题 min f(x), xR1 (3.1)( )( )( )( )( )21( )()()()()()2kkkkkxf xfxxxfxxx令( )( )( )( )()()()kkkxfxfxxx又令得到(x)的驻点，记做x(k1)，则( )(1)( )( )() (3.2)()kkkkfxxxfx2022-4-28最优化理论299. 一维搜索-函数逼近法函数逼近法2在点x(k)附近，f(x)(x)，因此可用(x)的极小点作为目标函数f(x)的极小点的估计。如果x(k)是f

19、(x)的极小点,则利用(3.2)可以得到极小点的一个进一步的估计.于是得到一个序列x(k).(1)( )3.1( ) ( )0,( )0,2.kThf xxfxfxxxxx设存在连续三阶导数, 满足初始点充分接近则牛顿法产生的序列至少以 阶收敛速率收敛于2022-4-28最优化理论309.一维搜索-函数逼近法函数逼近法3( ) ( )- (3.3)( ),( )fxA xxfxxxxxA证明:牛顿法可定义为算法映射设解集合 定义函数 下证 是关于解集合 和算法 的下降函数2022-4-28最优化理论319.一维搜索-函数逼近法函数逼近法4( )( )( )( )(1)( )( )( )( )(

20、 )( )( )( )( )( )( )( )().( )0,()()1 ()()()()1 ( )()()()() kkkkkkkkkkkkkkkkkxxxA xfxfxxxxxxfxxfxfxxfxfxfxfxxxfxfx设，由有（）- -( )2( )( )11 ()( ) (3.4)2() kkkxxffxxx其中 在 与之间。2022-4-28最优化理论329.一维搜索-函数逼近法函数逼近法5( )( )1212(1)( )221(1)21( )( ) ( )0,0 ( ),( ) (3.5)(3.4)() (3.6)2, 2kkkkfxfxfxxxk kxxxfxkfxkkxxxx

21、kxxkk由于和连续，故当接近 时 必存在使得在包含和 的闭区间上的每一点 处有代入，则 取初始点充分接近使得(1)1xx( )(1)(1)( ) (3.7) kkkxXx xxxxxxxx由此推得 且 2022-4-28最优化理论339. 9. 一维搜索一维搜索- -函数逼近法函数逼近法6( )( )8.2.1,.3.62.kAXA xXThxx由此知， 是关于解集合 和算法 的下降函数。且 为紧集，在 上连续.根据收敛于 由()知收敛阶为(0)( )( )(1)( )(1)( )( )S1,0,0;S2,(),S3,() 1.2()kkkkkkktepxktepfxxtepxfxxxkkf

22、x给定初始点允许误差置若停止，得。计算点：置转算法算法(牛顿法牛顿法)2022-4-28最优化理论349.一维搜索-函数逼近法函数逼近法7 7基本思想：用割线逼近目标函数的导函数的曲线y=f (x)把割线的零点作为目标函数的驻点的估计。(1)kx( )kx(1)kx-3.2. 割线法割线法( )(1)( )(1)( )(1)( )(1)(1)( )( )( )( )( )1)(1)()()()()( )()()0 (3.8()()().kkkkkkkkkkkkkkkkkkxxfxfxxxxfxfxxfxfxxfxxxxxfxx设在点和处的导数分别为和。令-用公式(3.8)进行迭代，得到序列-2

23、022-4-28最优化理论35(1)(2)( )3.2( ) ( )0,( )0,.1.618.kThf xxfxfxxxxxx 设存在连续三阶导数, 满足若和充分接近则割线法产生的序列收敛于收敛阶为(1)(2)( )(1)( )(1)( )( )( )(1),( )0,.,()()( )()()kkkkkkkkx xxxxfxxxxxfxfxxfxxxxx证明：设 是包含 的某个充分小的闭区间，使得对每一个有取以为节点构造插值多项式- (3.9)9.一维搜索-函数逼近法函数逼近法8在一定的条件下，这个序列收敛于解：2022-4-28最优化理论369.一维搜索-函数逼近法函数逼近法9( )(1

24、)11()( )( )()() (3.10)2kkffxxxxxx插值余项其中。11( )(1)1(k)( )0(3.10)() ( ) (3.11)2 , (3.8)()0,(3.9)k kkkkkfxfxe eexx exxx由于 ，因此由得到另一方面，由知由知2022-4-28最优化理论37由(3.11)和(3.12)得到9.一维搜索-函数逼近法函数逼近法10( )(1)( )(1)(1)(1)2( )(1)(1)(1)3( )(1)31()() ( )( )( )()()()() ()(), (kkkkkkkkkkkkkfxfxxxxxxxxxfxfxxxfxxxxfe +-) -)=

25、) =-(1)( )(1)1333.12),()0.kkkkexxxxf+其中在和之间1113() (3.13)2()kk kfee ef2022-4-28最优化理论38上式两端取绝对值，则9.一维搜索-函数逼近法函数逼近法111113111() (3.14)2()max( ) M=2min( )M (3.15). 1 (3.16)MkkkxxkkkkfeeeffxfxeeeMe令则 取充分小的 使得 则 ( )(1)(1)(1)(2)( )( ), k,(3.15).kkkkkxxxxxxxx 于是,进而由由收敛于2022-4-28最优化理论39下面考虑收敛速率，考虑k取充分大的情形。根据（

26、3.14）9.一维搜索-函数逼近法函数逼近法121111212 (3.17)( ) M=2( )/M (3.18) (3.17).1015151.618,0.61822kkkkykkkkeM eefxfxeayyy 其中令 代入于是可考虑差分方程 它的特征方程是其两个根是2022-4-28最优化理论409.一维搜索-函数逼近法函数逼近法131 12 21 111 11111111(1) (3.19)1 (1) (3.20) (1) kkkkccckckkkeaakMMeakMeMke于是 2022-4-28最优化理论419.一维搜索-函数逼近法函数逼近法14 基本思想：在极小点附近用二次三项式

27、x逼近目标函数f(x), 令x与f(x)在三点x (1) x(2) f (x(2) , f (x(2) 0 的点.(1) 2(1)(1)(1) 2(1)(1)( )3 ()2 () (3.35)( )6 ()2 , (3.36); ( )0 ()2 ()0, (3.37)(1)0), (3.38); 2(2)0 xa xxb xxcxa xxbxa xxb xxccaxxbaxx 令解此方程21)3) (3.33)3bbaca 2022-4-28最优化理论479. 一维搜索-函数逼近法函数逼近法202(1)222,( )20(3.24)( ),(3.36)3( )6 ()262323( )03c (3.40)33xbxxbbacxa xxbababacxbbacxabbac 第一种情形 有由假设及(可得故 是的极小点.第二种情形 将方程的根代入要