第二章-线搜索技术

第二章线搜索技术•前章知识回顾与本章知识提要•2.1精确线搜索及其Matlab实现•2.2非精确线搜索及其Matlab实现•2.3线搜索法的收敛性前章知识回顾1.无约束优化问题：对于函数hi(x),gj(x)，若集合E={i:hi(x)=0}与I={i:gj(x)≥0}构成的指标集E∪I为空集，则称之为无约束优化问题。2.凸函数：设函数f:D包含于Rn→R,其中D为凸集。称f是D上的凸函数，是指对任意的x,y∈D及任意的实数λ∈[0,1]，都有f(λx+(1-λ)y)≤λf(x)+(1-λ)f(y).当等号不成立时f是严格的凸函数。本章知识提要研究无约束优化问题的数值方法，不仅是出于实际问题的需要，同时也是研究约束优化问题数值方法的基础，本章主要讨论一维线搜索算法及其收敛性分析。我们考虑下面的无约束优化模型通过某种搜索方式确定步长因子使得（2.1）这实际上是怒变函数在一个规定的方向上移动所形成的单变量优化问题，也就是所谓的“线搜索”或“一维搜索”技术。令（2.2）)()(kkdxfnRx)(minxf)()(kkkkxfdxf)(xf这样，搜索式(2.1)等价于求步长使得线搜索有精确线搜索和非精确线搜索之分，所谓精确线搜索，是指求使目标函数沿方向达到极小，即或若是连续可微的，那么由精确线搜索得到的步长因子具有如下性质：亦即(2.3)上述性质在后面的算法收敛分析中起着很重要的作用。k)0()(kkdk)(xf)(min)(kkkkkdxfdxf0)(min)(k)(xfk0)(kTkkkddaxf01kTkdgkd所谓非精确线搜索，是指选取使目标函数得到可接受的下降量，即是可接受的。定义13设是定义在实数集上的一元函数，并且.若存在区间[a,b]使,则称[a,b]是极小化问题(2.4)的搜索区间。进一步，若使得在上严格递减，在上严格递增，则称[a,b]是的单峰区间，是[a,b]上的单峰函数。下面介绍一种确定搜索区间并保证具有近似单峰性质的数值算法—进退法算法2（进退法）k)(xf0)()(kkkkkdxfxff),0[*)(min*)(),0[),(*ba*)(*],[a]*,[b)()(步1选取计算置k=0.步2令计算，若转步3否则转步4.步3加大步长，令转步2.步4反向搜索或输出,若k=0,令k=1,转步2，否则停止迭代，令输出[a,b].0,000h)(00kkkh1)(11kkkk11,,,211,1kkhhkkkkkkk0101101,,,hh},max{},,min{11kkba2.1精确线搜索及其Matlab实现•精确线搜索分为两类，一类是使用导数的搜索，如插值法，牛顿法，及抛物线法等；另一类是不用导数的搜索，如0.618法，分数法及成功-失败法等，这里仅介绍0.618法和二次插值法。1.黄金分割法•设其中是搜索区间上的单峰函数，在第i次迭代时的搜索区间为,取两个试探点且,计算,根据单峰函数的性质，可能会出现如下两种情形之一(1)若则令①)(s][0,0baiiqp)(),(iiqp)()(iiqpiiiiqbaa1,1],[,iiiibaqp][,iiba)()(iiqp)()(kksdxfs(2)若则令②我们要求两个试探点满足下面两个条件：(a)和的长度相同，即③(b)区间长度的缩短率相同，即④从而可得（2.5）先考虑情形(1),此时，新的搜索区间为为了进一步缩短搜索区间，需取新的试探点由(2.5)得)()(iiqpiiiibbpa1,1iiqp,][,iiqa][,iibpiiiiaqpb)(11iiiiabtab))(1(iiiiabtap)(iiiiabtaq],[],[11iiiiqaba11,iiqp)()()(21111iiiiiiiiiibataaqtaabtaq若令,t0(2.6)则解方程(2.6)得区间长度缩短率为t=≈0.618算法3（0.618法）步0确定搜索区间和容许误差ε0,计算初始试探点及相应的函数值置i=0.步1若转步2，否则，转步3.步2计算左试探点,若停算，输出，否则，令tt12iiiiipabtaq))(1(121-5],[00ba)(382.00000abap)(618.00000abaq)(),(00qp)()(iiqp||iiaqip)()(,,111iiiiiipqqbaa)(382.0,1111iiiiiiabappq计算,i=i+1,转步1.步3计算右试探点，若停算，输出否则，令计算,i=i+1,转步1.)(1ip||iipbiq)()(,,111iiiiiiqpbbpa)(618.0,11111iiiiiiabaqqp)(1iq程序1(0.618法程序)用0.618法求单变量函数𝜑在单峰区间[a,b]上的近似极小点.•function[s,phis,k,G,E]=golds(phi,a,b,delta,epsilon)•%输入:phi是目标函数,a,b是搜索区间的两个端点•%delta,epsilon分别是自变量和函数值的容许误差•%输出:s,phis分别是近似极小点和极小值,G是nx4矩阵,•%其第k行分别是a,p,q,b的第k次迭代值[ak,pk,qk,bk],•%E=[ds,dphi],分别是s和phis的误差限.•t=(sqrt(5)-1)/2;h=b-a;•phia=feval(phi,a);phib=feval(phi,b);•p=a+(1-t)*h;q=a+t*h;•phip=feval(phi,p);phiq=feval(phi,q);)(xf•k=1;G(k,:)=[a,p,q,b];•while(abs(phib-phia).epsilon)—(h.delta)•if(phip.phiq)•b=q;phib=phiq;q=p;phiq=phip;•h=b-a;p=a+(1-t)*h;phip=feval(phi,p);•else•a=p;phia=phip;p=q;phip=phiq;•h=b-a;q=a+t*h;phiq=feval(phi,q);•end•k=k+1;G(k,:)=[a,p,q,b];•end•ds=abs(b-a);dphi=abs(phib-phia);•if(phip.=phiq)•s=p;phis=phip;•else•s=q;phis=phiq;•end•E=[ds,dphi];2.抛物线法抛物线法也叫做二次插值法，其基本思想是：在搜索区间中不断地使用二次多项式去近似目标函数，并逐步用差值多项式的极小点去逼近先搜索问题s0，的极小点.算法4（抛物线法）步0由算法2确定三点对应的函数值分别为满足设定容许误差ε0.步1若,停算，输出.步2计算插值点，根据计算和,若转步4，否则，转步3.)()(minkksdxfs210sss210，，2101，02ss1*sshshss02102100)2(2)43(s)(s1步3若,则转步1,否则，转步1.步4若,则,转步1，否则，,转步1.ss1112112,,,ssss110110,,,ssssss122,ss00,ss)(s],[0sa],[0bs程序2(抛物线法程序)求函数在区间[a,b]上的局部极小值,从初始开始,然后在区间和上进行搜索.•function[s,phis,ds,dphi,S]=qmin(phi,a,b,delta,epsilon)•%输入:phi是目标函数,a和b是搜索区间的端点•%delta,epsilon是容许误差•%输出:s是近似极小点,phis是对应的近似极小值;k是迭代次数%ds是迭代终止时的步长,dphi是—phi(s1)-phi(s)—;S是迭代向量•s0=a;maxj=20;maxk=30;big=1e6;err=1;k=1;•S(k)=s0;cond=0;h=1;ds=0.00001;•if(abs(s0).1e4),h=abs(s0)*(1e-4);end)(s)(s0s],[0sa],[0bs•while(kmaxk&errepsilon&cond˜=5)•f1=(feval(phi,s0+ds)-feval(phi,s0-ds))/(2*ds);•if(f10),h=-abs(h);end•s1=s0+h;s2=s0+2*h;bars=s0;•phi0=feval(phi,s0);phi1=feval(phi,s1);•phi2=feval(phi,s2);barphi=phi0;cond=0;•j=0;%确定h使得phi1.phi0且phi1.phi2•while(j.maxj&abs(h).delta&cond==0)•if(phi0=phi1),•s2=s1;phi2=phi1;h=0.5*h;•s1=s0+h;phi1=feval(phi,s1);•elseif(phi2phi1),•s1=s2;phi1=phi2;h=2*h;•s2=s0+2*h;phi2=feval(phi,s2);•else•cond=-1;•end•end•j=j+1;•if(abs(h)big|abs(s0).big),cond=5;end•end•if(cond==5)•bars=s1;barphi=feval(phi,s1);•else•%二次插值求phis•d=2*(2*phi1-phi0-phi2);•if(d.0),•barh=h*(4*phi1-3*phi0-phi2)/d;•else•barh=h/3;cond=4;•end•bars=s0+barh;barphi=feval(phi,bars);•h=abs(h);h0=abs(barh);•h1=abs(barh-h);h2=abs(barh-2*h);•%确定下一次迭代的h值•if(h0h),h=h0;end•if(h1h),h=h1;end•if(h2h),h=h2;end•if(h==0),h=barh;end•if(hdelta),cond=1;end•if(abs(h)big|abs(bars)big),cond=5;end•if(abs(h)big|abs(bars)big),cond=5;end•err=abs(phi1-barphi);•s0=bars;k=k+1;S(k)=s0;•end•if(cond==2&hdelta),cond=3;end•end•s=s0;phis=feval(phi,s);•ds=h;dphi=err;非精确线搜索及其Matlab实现1.Wolfe准则Wolfe准则是指：给定,,求使得下面两个不等式同时成立：(2.10)(2.11)其中，,条件(2.11)有时也用另一个更强的条件(2.12)来代替，这样，充分小时，可保证(2.12)变成近似精确线搜索。(2.10)和(2.12)也成为强Wolfe准则。定理10设有下界且,令,,则存在一个区间[a,b],0ab,使每一个[a,b],均满足(2.10)和(2.12)。)5.0,0()5.0,(kkTkkkkkkdgxfdxf)()(kTkTkkkdgdxf)()()(kkkxfxggkTkTkkkdgdxf|)(|0)(xf0kTkdg)5.0,0()1,(2