第二章 线搜索技术前章知识回顾与本章知识提要2.1精确线搜索及其Matlab实现2.2非精确线搜索及其Matlab实现2.3线搜索法的收敛性前章知识回顾1.无约束优化问题：对于函数hi(x), gj(x)，若集合E=i: hi(x)=0与I=i: gj(x)0构成的指标集EI为空集，则称之为无约束优化问题。2.凸函数：设函数f:D包含于RnR,其中D为凸集。称f是D上的凸函数，是指对任意的x,yD及任意的实数0,1，都有f(x+(1-)y)f(x)+(1-)f(y).当等号不成立时f是严格的凸函数。本章知识提要研究无约束优化问题的数值方法，不仅是出于实际问题的需要，同时也是研究约束优化问题数值方法的基础，本章主要讨论一维线搜索算法及其收敛性分析。我们考虑下面的无约束优化模型通过某种搜索方式确定步长因子 使得 （2.1）这实际上是怒变函数 在一个规定的方向上移动所形成的单变量优化问题，也就是所谓的“线搜索”或“一维搜索”技术。令 （2.2）这样，搜索式(2.1)等价于求步长 使得 线搜索有精确线搜索和非精确线搜索之分，所谓精确线搜索，是指求 使目标函数 沿方向 达到极小，即或若 是连续可微的，那么由精确线搜索得到的步长因子 具有如下性质：亦即 (2.3)上述性质在后面的算法收敛分析中起着很重要的作用。所谓非精确线搜索，是指选取 使目标函数 得到可接受的下降量，即 是可接受的。定义定义13 设 是定义在实数集上的一元函数， 并且 .若存在区间a,b 使 ,则称a,b是极小化问题(2.4)的搜索区间。进一步，若 使得 在 上严格递减，在 上严格递增，则称a,b是 的单峰区间， 是a,b上的单峰函数。下面介绍一种确定搜索区间并保证具有近似单峰性质的数值算法进退法算法算法2（进退法）（进退法）步1 选取 计算 置k=0.步2 令 计算 ， 若 转 步3 否则转步4.步3 加大步长，令 转步2.步4 反向搜索或输出,若k=0,令k=1,转步2，否则停止迭代，令输出a,b.2.1精确线搜索及其Matlab实现 精确线搜索分为两类，一类是使用导数的搜索，如插值法，牛顿法，及抛物线法等；另一类是不用导数的搜索，如0.618法，分数法及成功-失败法等，这里仅介绍0.618法和二次插值法。1.黄金分割法黄金分割法 设 其中 是搜索区间 上的单峰函数，在第i次迭代时的搜索区间为 ,取两个试探点 且 ,计算 ,根据单峰函数的性质，可能会出现如下两种情形之一(1)若则令 (2)若则令我们要求两个试探点 满足下面两个条件：(a) 和的长度相同，即 (b)区间长度的缩短率相同，即从而可得 （2.5）先考虑情形(1),此时，新的搜索区间为为了进一步缩短搜索区间，需取新的试探点由(2.5)得若令 ,t0(2.6)则解方程(2.6)得区间长度缩短率为t= 0.618算法算法3 （0.618法）法）步0 确定搜索区间 和容许误差0,计算初始试探点 及相应的函数值 置i=0.步1 若 转步2，否则，转步3.步2 计算左试探点,若 停算，输出 ，否则，令计算 ,i=i+1,转步1.步3 计算右试探点，若 停算，输出 否 则，令计算 ,i=i+1,转步1.程序程序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);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;endds=abs(b-a); dphi=abs(phib-phia);if(phip.=phiq) s=p; phis=phip;else s=q; phis=phiq;endE=ds,dphi;2.抛物线法抛物线法也叫做二次插值法，其基本思想是：在搜索区间中不断地使用二次多项式去近似目标函数，并逐步用差值多项式的极小点去逼近先搜索问题s0，的极小点.算法算法4 （抛物线法）（抛物线法）步0 由算法2确定三点对应的函数值分别为满足 设定容许误差0.步1 若 ,停算，输出.步2 计算插值点，根据 计算 和, 若 转步4，否则，转步3. 步3 若 ,则 转步1,否则， 转步1.步4 若 ,则 ,转步1，否则， ,转步1.程序程序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); endwhile (kepsilon &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); else if (phi2big|abs(s0).big), cond=5; endendif(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; endif(h=0), h=barh; end if(hbig|abs(bars)big), cond=5; endif(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; endends=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)。2.Armijo准则准则Armijo准则是指：给定的 , ,令步长因子 ,其中 是满足下列不等式的最小非负整数：(2.13)可以证明，若 是连续可微的且满足 ,则Armijo准则是有限终止的，即存在正数 ，使得对于充分大的正整数m,(2.13)式成立。算法算法5 (Armijo准则准则)步0 给定 ， ,令m=0.步1 若不等式 成立，置 ,停算，否则，转步2.步2 令m=m+1,转步1.线搜索的收敛性所谓“线搜索法”是指线搜索技术求步长因子的无约束优化问题下降类算法的简称，其一般算法框架是：算法算法6 (线搜索算法框架线搜索算法框架)步0 初始化，选取有关参数及初始化迭代点 ,设定容许误 差 ，令k=0.步1 检验终止判别准则，计算，若，输出 ，停算.步2 确定下降方向 ，使满足步3 确定步长因子 ，可在下列“精确”与“非精确”两种线 搜索技术中选用其一：(1)用前面介绍的0.618法或者二次插值法等精确线搜索技 术求：(2.14)(2) 用前面介绍的Wolfe准则或Armijo准则等非确定先搜 索技术求步4 更新迭代点，令，k=k+1,转步1.搜索方向 与 的夹角 满足(2.15)显然，夹角 的余弦为(2.16)