一维搜索的最优方法(黄金分割法)

一元函数的极小值问题，就是一维最优化问题，其数值迭代方法亦称为一维搜索方法。一维搜索最优化是优化方法中最简单、最基本的方法。主要方法有：0.618法、牛顿法、二次插值法等。迭代计算的基本格式()(1)()()kkkkXXS§4－1一维搜索的搜索区间一、一维搜索的概念k)k)S（（显然，搜索方向和步长因子构成决定了每最优一次迭代化算法好的修正量，它们是坏的重要因素。k)k)k)k)(1)()k)k)()()k)k)k)SXS()()()()kkkkffff（（（（（（（（（假定给定了搜索方向，从点出发沿方向进行搜索，要确定步长，使得记（）＝即确定步长，就是单变量函数（）的搜索问题。称为一维搜索问题。XXSXXS()k)k)min()kf（（（）＝XS◎在极小点附近，函数呈现“大－小－大”xy()yfxxy()yfx一维搜索的思路（1）确定极小点α*所在的区间[a,b]，在此区间内，函数呈现“大－小－大”变化趋势。搜速区间。ab（2）在[a,b]内找α*－将区间长度逐步缩短。0.618法与二次插值法就是解决第二个步骤的方法在极小点附近，函数呈现“大－小－大”xy()yfxxy()yfx•基本思想从一点出发，按一定的步长，试图确定出函数值呈现出”高－低－高“的三个点。一个方向不成功，就退回来沿相反方向搜索。具体作法：二、确定搜索区间的进退法000000000000,hhhh给出初始点，初始步长若（＋）（）,则下一步从新点＋出发，加大步长向前搜索，直到目标函数上升就停止。若（＋）（）,则下一步仍然从点出发，沿反方向搜索，直到目标函数上升就停止。这样就可以得到一个搜索区间。进退法步骤0step1.0()h给定初始值。给定初始点，初始步长。(1)(2)(1)(2)0112step2.()()()()2hffffff1令，。计算（），（）令（），（）3(3)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,,;,;fffffffffhffff3若在步2中，，后退运算以为起始点，，重排顺序+。计算（），令（）(1)若，步长反号，反方向a,搜索。则[(1)(1)(3)(2)(1)(3)(2)(2)(3)3(3)312132]1(),f,()ffffffhff3b]=[，(2)若，则2hh，，，，，计算（），令（）停止计算。返回重新开始。(3)(2)(2)(1)(3)(2)(2)(3)例4.1用进退法确定函数271001(),faaah0的一维优化初始搜索区间[a,b]。设初始点初始步长。12122133231a.01014b.202121()()().,ffhffffhffcffh1012232解：按顺序进行计算，有比较作前进运算比较再作前进运算＝＝1323234202(),()()ffffhff1223＝＝＝＝42311323231223132240218,=2.,(),()().,.dffhffffhffeffffab21223比较再作前进运算＝＝2＝＝4＝＝8此时有，故即初始搜索区间为[2,8].基本思路：逐步缩小搜索区间，直至最小点存在的区间达到允许的误差范围为止。一、消去法的基本原理12121212()()()()()(*()())[,],()()(,)),(ababfffaabff设一元函数的起始搜索区间为是函数的极小点。将在搜索区间内任取两点、。且计算、。与进行比较，可能出现三种情况：()[]§4－2黄金分割法（0.618法）12221][]()()()()()()().(,,ffba这况丢点内在种情下，可以掉部分，而最小必定在。1()a()f()fab*a*1()a2()a2()ab12112()()()()()()().[,)[,]ffab在这种情况下，可以丢掉部分，而最小点必定在内。1()a()f()fab*a*1()a2()a2()ab1212123()()()()()()()()().[,),][,]ffab在这种情况下，可以丢掉部分，也可以丢掉(部分，而最小点必定在内。因此这种情况可以并入上面的任意一种情况。()fab*1()a2()a12212112()()()()()()()()().[,]()()().[,]ffaffb取区间；取区间。二、0.618的由来11.,（）（2）在[a,b]中位置对称2.每次缩短的区间缩短率不变，减少计算量。Lab(1)α(2)αL1=λLL1=λL211LLLLL1=λLL2=(１－λ)L(2)αab’(1)αL2=(１－λ)L12100618.Lab(1)α(2)αL1=λLL1=λL0618.L1=λLL2=(１－λ)L(2)αb(1)αL2=(１－λ)La(1)α@数学家华罗庚运用黄金分割法提出一种可以尽可能减少做试验次数、尽快地找到最优方案的方法——优选法三、0.618法的迭代过程及算法框图1212121212(1)[a,b]06180618()()()()()()()().().()()()(),()bbaabaffffff在初始区间内取两个计算点和，其值分别为＝＝计算和，令22121121211211122a.0618b.()()()()()()()((),,][,][,],,,,.(),(),[,ffbaabbaffbbaffffa则丢掉区间(部分，取为新区间在计算中作置换较数缩区间：则丢掉区间比函值，小搜索11121221220618)()()()()()())[,][,],,,,.(),()babaffabaff部分，取为新区间在计算中作置换：32*()-baab判断迭代终止条件当缩短的区间距离小于某一个预先规定的精度，即时，终止迭代。一般取区间的中点作为最优解。黄金分割法计算框图否停是2*ab11122206180618()()()().()().()()bbaafafabaafaf12?ff比较函数值。121212220618()()()()(),,.()()aaaaffabaafaf,,ab初始条件：-?ba212121110618()()()()(),,.(),()abaaffbbaafaf是否例用0.618法求一元函数2271[a,b]05,0.50.15()fa的极小点。初始搜索区间为[－.]，取迭代精度＝。11122212(1)[a,b]061801180.85406180118109(2)()()()().().,().().,()bbaffabaffffb在初始区间内取点并计算函数值。＝＝＝＝－＝＝＝＝－.比较函数值，解：缩短搜索区间1121222050118050118061801181.090618()()()()().,.-.(.)...()()abafabaff判断迭代终止条件:继续＝＝，＝－新点＝＝0.264,＝＝缩短-1.1251211212(3)050118050118038202641.125()()()().,.-....ffbabaf比较函数值，缩短搜索区间判断迭代终止条件:＝＝，＝－新点继续缩短2212220618(4)01180354035401180236()()()(.()().,.-...abaffffabba＝＝0.354,＝＝-1.103比较函数值，缩短搜索区间判断迭代终止条件:继短＝续缩1211102641.1250618)()()..()()fbbaff＝，＝－新点＝＝0.208,＝＝-1.120121(5)0502810035403540208014562(),.-..()....ffbbaaab比较函数值，缩短搜索区间0.208判断迭代终迭代停止。取止理论解条件:22212E(0)T(0)Tmin()(-3)+(-4)+5[2,3][2,3],XfXxxSX对下列优化问题设例：搜索方向做一维搜索（1）转化为一维搜速问题；（2）用进退法确定初始搜速区间；（3）用0.618法确定初始搜主要步骤：速区间；§4-3牛顿法基本思想：在极小点附近，将目标函数做二阶Taylor展开，得二次多项式，用该多项式的极小点近似原问题的极小点。(0)(0)(0)(0)(0)(0)2()=()+()(05()(xxfxfxx-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)fxxfxfxxxxx设()存在连续二阶导数，满足()＝0；()0初始点接近，由牛顿法产生的迭代序列收敛于结论。：(0)(k)(k)(k)(k+1)(k)(k)00()()1x,k2fxxxfxx=xfxkk21）给定初始点，允许误差）若()，迭代停止，得否则，进行下一步3）计计算步骤算，＋，转步）：注意点：初始迭代点的选择很重要，要靠近极小点，否则可能不收敛。需计算一、二阶导数，计算两增大，实用可能不方便。1432E0min()341212fxxxxx.x（）例＝－－＝－，迭代两次思考：实际问题如何得到初始迭代点？割线法：导数的近似计算。(k)xxy(k-1)x()y=fx切线斜率割线斜率(k)(k1)(k)(k)(k1)()()()fxfxfxxx－－－－(k)(k1)(k)(k)(k1)()()()fxfxfxxx－－－－割线法(k)(k1)(k+1)(k)(k)(k1)()()()()fxfxx=xfxfx－－一般迭代格式－－不需计算导数，但收敛速度较牛顿法慢。1432E0min()341212fxxxxx.x（）例＝－－＝－，迭代两次§4-3二次插值法P()[,][,]xabab基本设函数在内呈现“大－小－大”单峰变化在上以低次（二次或三次）插值多项式来逼近原目标函数，求得多项式的极值点，逐步缩短搜速区间。反复计算，直至给定精度。此法应想。思用较广：(1)xy()y=fxab(2)(3)1f2f3f()y=Px(1)(2)(3)(1)(2)(3)ab在[a,b]中设定三点，和123123f,f,f,fff对应有且P2012xaaxax构造二次多项式P()(1)(1)(1)20121(2)(2)(2)20122(3)(3)(3)20123(i=0,1,2)()()(1)()aaaafaaafaaaf