常用的一维搜索方法

工程优化设计中的数学方法工程优化设计中的数学方法硕士研究生课程硕士研究生课程理学院数学系：穆学文Tel:88207669E-mail:[e-mail]西安电子科技大学穆学文2第三章常用的一维搜索方法一元函数求极小及线性搜索均为一维搜索。常用于求：minf(x(k)+λd(k))=φ(λ)s.t.λ∈SS有3种情况（-∞，+∞）或（0，+∞）或[a,b]。一般地,我们总可以考虑x∈(-∞，+∞),例对问题令：则：min()axbfx≤≤min()axbfx≤≤(),(),fxaxbFxothers≤≤⎧=⎨+∞⎩(),(),fxaxbFxothers≤≤⎧=⎨+∞⎩min()min()axbxfxFx≤≤−∞≤≤+∞=min()min()axbxfxFx≤≤−∞≤≤+∞=西安电子科技大学穆学文3z精确一维搜索方法¾“成功—失败”法¾0.618法（黄金分割法）¾二分法¾牛顿法（Newton）和插值法z非精确搜索算法我们主要介绍如下一些搜索方法：西安电子科技大学穆学文4§1“成功—失败”法以下方法称为“成功—失败”法（进退法）：步骤1：选取初始点x∈R,初始步长h0及精度ε0，步骤2：计算步骤3：若搜索成功,转步骤4；否则，搜索失败，转步骤5。步骤4：令x:=x+h,步骤5：判断若停止迭代，；否则令转步骤2。缺点：效率低。优点：可以求搜索区间注意：初始步长不能选得太小1().fxϕ=1().fxϕ=2().fxhϕ=+2().fxhϕ=+21,ϕϕ21,ϕϕ12:,:2hhϕϕ==12:,:2hhϕϕ==?hε≤?hε≤,hε≤,hε≤*xx=*xx=,4hh=−,4hh=−西安电子科技大学穆学文5例1：设给定初始点为a及初始步长为h,求搜索区间[c,d]1)前进运算首先计算f(a),f(a+h),如果f(a)f(a+h),则步长加倍,计算f(a+3h).若f(a+h)=f(a+3h),则c=a,d=a+3h;否则将步长再加倍，并重复上面运算.2)后退运算如果f(a)f(a+h),则将步长缩为原来的1/4并改变符号，即将步长改为-h/4,如果f(a)f(a-h/4),则c=a-h/4,d=a+h;否则将步长加倍，并继续后退。注意:1.h选择要适当.(太大含多个单峰区间,太小迭代次多)；2.f(x)单调时无结果,(加迭代次数限制)；3.可与中点法结合寻找单调区间(思考)。西安电子科技大学穆学文6§20.618法（黄金分割法）0.618法是求单峰函数极值的一种试探法.所谓的单峰函数是指只有一个峰值的函数,其严格定义有定义1：设f(x)是定义在[a,b]上的函数，如果1）∃x*∈[a,b]是φ在[a,b]上的最小点，2）若对任意x1,x2,a≤x1x2≤b,满足：1º若x2≤x*，则f(x1)f(x2);2º若x1≥x*，则f(x1)f(x2).则称f(x)为[a,b]上的单峰函数。西安电子科技大学穆学文70tfx*0tfx*西安电子科技大学穆学文8定理1：设f：R→R在[a,b]上是单峰函数，a≤x1x2≤b。那么1°若f(x1)≥f(x2)，则x*∈[x1,b],如左下图2°若f(x1)f(x2)，则x*∈[a,x2],如右下图αx1x2bαx1x2b西安电子科技大学穆学文9Proof.1°反证法：设x*∈[a,b]为最小点，z若x*∈[a,x1]，由定义知f(x1)f(x2)，矛盾（假设）；2°若x*∈[x2,b]，由定义知f(x1)f(x2),矛盾（条件）；结论成立。注：上述定理为缩短区间的算法提供了理论根据。西安电子科技大学穆学文10通过上述定理，选二点x1x2,比较f(x1)与f(x2),可去掉[a,x1]或者[x2,b].考虑条件：1°对称：x1–a=b-x2……①（使“坏”的情况去掉，区间长度不小于“好”的情况）2°保持缩减比t=(保留的区间长度／原区间长度)不变。（使每次保留下来的节点，x1或x2，在下一次的比较中成为一个相应比例位置的节点）。推导缩减比t:如图设第一次保留[a,x2](去掉[x2,b]),那么第二次保留的长度为[α,x1],则αx1x2b212(2)xxtbxαααα−−==−−西安电子科技大学穆学文11整理②：x2=a+t(b-α)x1=a+t(x2-α)结合①式：t2+t–1=0故t≈0.618注意:上式有t2=1-t,故有x1=a+(1-t)(b-α)x2=a+t(b-α)（算法框图见下页）)(251舍去负值±−=t西安电子科技大学穆学文12黄金分割法（0.618法）（算法）初始[a,b],ε02/)15(−=tx1=α+（1-t）(b-α)x2=α+t(b-α)b-αε?STOP;x*=(α+b)/2yesf（x1）-f（x2）0?Noα=x1,x1=x2x2=α+t(b–α)yesb=x2,x2=x1x1=α+（1-t）(b-α)Noαx1x2bx2bαx1x2bαx1西安电子科技大学穆学文13优点：不要求函数可微，且每次迭代只需计算一个函数值，计算量小，程序简单缺点：收敛速度慢。黄金分割法（0.618法）的优缺西安电子科技大学穆学文14设f(x)在[a,b]上可微，且当导数为零时是解。取x=(a+b)/2,那么f′(x)=0时,x为最小点,x=x*;f′(x)0时,x在上升段,x*x，去掉[x,b];f′(x)0时,x在下降段,x*x，去掉[a,x].(自己画算法框图)αxbαtgα0f′(x)ααxbtgα0f′(x)§3二分法西安电子科技大学穆学文15我们知道，在极小点处，，且时，递减，即，而当，函数递增，即。若找到一个区间[a,b],满足性质则[a,b]内必有的极小点，且，为找此取，若则在中有极小点，这时用作新的区间[a,b]，继续这个过程，逐步将区间[a,b]缩小，当区间[a,b]的长度充分小时，或者当充分小时，即可将[a,b]的中点取做极小点的近似点，这时有估计：*x()*'0fx=*xx()fx()*'0fx*xx()'0fx()()'0,'0fafb()fx*x()*'0fx=*x02abx+=()0'0fx[]0,ax[]0,ax()0'fx*22abbax+−−西安电子科技大学穆学文16至于区间[a,b]的确定,一般可采用下述方法：首先取初始点，若，则在右方取点,(也是事先给定的步长）；若,则令；若仍然有，则取（或将放大一倍，再取）,若,则以作区间[a,b]；否则继续下去。对于的情况，可类似于上面在左侧取点，此时.优点：计算量较少，而且总能收敛到一个局部极小点。缺点：收敛速度较慢0x()0'0fx0x10xxx=+ΔxΔ()1'0fx01,axbx==()0'0fx21xxx=+ΔxΔ2xxx=+Δ()2'0fx[]12,xx()0'0fx0x0xΔ西安电子科技大学穆学文170.618法和二分法的相同和不同的地方：相同的地方•对单峰函数有效•通过等比收缩原则，不断缩短区间找到极小值点不同的地方•0.618法不要求函数可微，而二分法需要函数的一阶导数。•二分法的收缩比例是0.5，0.618法的收缩比例是0.618倍。二分法的速度要快一些。西安电子科技大学穆学文18§4.1、Newton法：对f(x)在xk点展开：f(x)=f(xk)+f′(xk)(x-xk)+(1/2)f″(xk)(x-xk)2+o||(x-xk)2||取二次式（略去高阶项）g(x)=f(xk)+f′(xk)(x-xk)+(1/2)f″(xk)(x-xk)2§4牛顿法（Newton）和插值法用g(x)作为f(x)的近似，当f″(xk)0时，其驻点为极小点：g′(x)=f′(xk)+f″(xk)(x-xk)=0得xk+1=xk–f'(xk)/f″(xk).取xk+1为新的迭代点。以上过程即Newton法。特点：收敛速度快，二阶收敛。缺点：须计算二次导数，对初始点要求高、局部收敛。西安电子科技大学穆学文19初始x1,ε1,ε20k=1︱f'(xk)︱ε1?停；解xkyNf″(xk)0?N停，失败Yxk+1=xk-f′(xk)／f″(xk)|xk+1-xk|ε2YNk=k+1Newton法算法框西安电子科技大学穆学文20例1：求minf(x)=arctantdt解：f′(x)=arctanx,f″(x)=1／(1+x2)迭代公式：xk+1=xk-(1+xk2)arctanxk取x1=1，计算结果：kxkf′(xk)1／f″(xk)110.785422-0.5708-0.51871.325830.1169-0.11641.01374-0.001095-0.001095x4≈x*=0取x1=2，计算结果如下：0x∫西安电子科技大学穆学文21kxkf′(xk)1／f″(xk)121.107152-3.5357-1.295213.50313.95不收敛。§4.2、插值法用f(x)在2或3个点的函数值或导数值，构造2次或3次多项式作为f(x)的近似值，以这多项式的极小点为新的迭代点。3点2次，2点2次，4点3次，3点3次，2点3次等以3点2次为例：取x1，x2，x3，求出f(x1),f(x2),f(x3)(利用“成功-失败”法)西安电子科技大学穆学文22设二次插值多项式：ax2+bx+c=g(x)ax12+bx1+c=g(x1)ax22+bx2+c=g(x2)ax32+bx3+c=g(x3)解得:a,b123231312122331()()()()()()()()()xxgxxxgxxxgxaxxxxxx−+−+−=−−−−222222123231312122331()()()()()()()()()xxgxxxgxxxgxbxxxxxx−+−+−=−−−2bxa−=−西安电子科技大学穆学文23算法思路：1.寻找满足如下条件的点，成为两头大中间小的点：x1x2x3，f(x1)f(x2),f(x2)f(x3)2.两头大中间小，可得a0,则为g(x)的极小值点，且3.若，则迭代结束，取，否则在点中，选取使f(x)最小的点作为新的x2，并使新的x1，x3各是新的x2近旁的左右两点，继续进行迭代，直到满足终止准则。x[]13,xxx∈2xxε−*xx=123,,,xxxx西安电子科技大学穆学文24注意：1.算法的终止条件可能无法保证算法一定收敛。2.若算法收敛，则在一定条件下，是超线性收敛的收敛阶数为1.33.初始点的产生可由“成功-失败”法产生。4.其他的插值法原理很接近，可自己看西安电子科技大学穆学文25不精确一维搜索：minf(x)考虑从x(k)点出发，沿方向d(k)寻找新迭代点：x(k+1)=x(k)+λkd(k)要求:1°f(x(k)+λkd(k))f(x(k));2°λk0不能太小。总体希望收敛快,每一步不要求达到精确最小,单步速度快,虽然迭代步数增加，但整个收敛达到快速。§5不精确一维搜索西安电子科技大学穆学文26法则1：Goldstein法(1965)为了方便，省去上标：设f:Rn→R。在x取方向d,满足：▽fT(x)d0(即d为下降方向)，求λ使1°f(x+λd)≤f(x)+αλ▽fT(x)d2°f(x+λd)≥f(x)+(1-α)λ▽fT(x)d其中,α∈(0,1／2)为取定参数。实际中常α=0.1。注意：1°表示λ的取值应使f(x+λd)的值在y=f(x)+αλ▽fT(x)d的下方，2°表示λ的取值应使f(x+λd)的值在y=f(x)+(1-α)λ▽fT(x)d的上方两直线的斜率α▽fT(x)d(1-α)▽fT(x)d西安电子科技大学穆学文27f(x(k))西安电子科技大学穆学文28λ=1，α，β1°是否成立？NoYes2°是否成立？Yes停；λk=λNoλ=(3／2)λλ=(1／2)λ算法流程图：注：只需要几步就可以得到步长不少算法利用这个准则可以得到全局收敛的结果