拟牛顿法的研究现状文献综述

拟牛顿法的研究现状文献综述姓名:孟媛媛学号：112111215指导老师：肖伟前言求解非线性方程组F(x)=0的方法有很多，最速下降法具有结构简单，计算量小的优点，但是它的收敛速度较慢；牛顿法及其改进牛顿法，虽然收敛速度快，但在迭代过程中的每一步构造搜索方向时，首先要计算目标函数的Hessian矩阵，然后需要解一个线性方程组，计算工作量很大，这就抵消了牛顿法收敛速度快的优点。为了克服牛顿法的缺点，人们提出了拟牛顿法，拟牛顿法在构造搜索方向时，只需要利用目标函数及其一阶导数的信息，避免了Hessian矩阵的计算，减少了计算量，并且具有超线性收敛的优点，经理论证明和实践检验，拟牛顿法已经成为一类公认的比较有效的算法.拟牛顿法一、求解非线性方程组的拟牛顿法设F：RntRn是连续可微映射•考虑下面的非线性方程组：F(x)=0(1.1)牛顿法是求解方程组(1.1)的经典的方法之一，其迭代格式为：x=X+d,d=—Ff(x)-1F(x),k+1kkkkkkkkkkk其中F比x)是F在x处的Jacobian阵•牛顿法的一个显著优点就是具有局部的超kk线性甚至二阶收敛速度，由于牛顿法这一优点，使其成为颇受欢迎的算法之一，然而，当Jacobian矩阵F，(X)奇异时，牛顿方向可能不存在.克服牛顿法的这一k缺陷的一个主要途径就是采用拟牛顿法，其基本思想是利用某个矩阵B作为kF(X)的近似取代F(X).拟牛顿法的一般格式为：kkTOC\o"1-5"\h\zX=X+«d,(1.2)k+1kkkd=—B_1F(X),(1.3)kkk其中d是步长，通常由某种线性搜索确定.B是F'(X)的近似尼满足下面的kkk拟牛顿方程：Bs=(y),(1.4)k+1kk其中y=F(X)-F(X),s=X-X.注意到y沁F'(X)s，因此，B与kk+1kkk+1kkk+1kk+1F'(X)沿方向s很接近•拟牛顿矩阵B的不同的校正公式导致不同的拟牛顿k+1kk+1法.著名的拟牛顿校正公式有Broyden秩一校正公式，对称秩一校正公式，DFP校正公式，BFGS校正公式，PSB校正公式等，它们分别由下面这些公式定义：Bdfp=B+k+1kBpsb-B+k+1k(y-Bs)Bdfp=B+k+1kBpsb-B+k+1k(y-Bs)TsyyT一kkkkyyT;(yTs)2kkkk(y-Bs)TskkkkSSt；

(sTs)2kkkkkk_kkkkk_k一yTskk(y-Bs)sT+s(y-Bs)TkkkkkkkkkkstskkBssBTyyTBbFGS—B———k_kkk+k——k—；k+1ksTBsyTsBri=B+k+1k（y-bs）（y-bs）Bri=B+k+1k（y-bs）ts

kkkk容易看到，DFP,PSB,BFGS,SRI校正公式都是对称的，他们适合求解对称问题，而BroydenR1校正公式是不对称的，因此它常被用来求非对称问题•如果丁丁s>0，则DFP和BFGS公式保持迭代矩阵b的对称正定性，而其它几种kkk方法不具有这种性质.PSB校正公式在非线性最小二乘问题中经常被采用.BFGS公式是颇受欢迎的拟牛顿公式，它具有DFP校正所具有的各种性质•此外，当采用Wolfe线性搜索时，BFGS算法对凸极小化问题具有全局收敛性质，这个性质对于DFP方法是否成立尚不清楚.大量的数据结果表明，BFGS方法的数值效果优于其它的拟牛顿方法.拟牛顿法不需要明显计算Jacobian阵伺时保持牛顿法的快速收敛速度启20世纪60年代Broyden第一次提出求解非线性方程组的拟牛顿法后，因其深邃丰富的理论知识和实际计算中的有效性，很快受到最优化工作者和计算数学家的特别青睐.特别是拟牛顿法的局部收敛性得到了广泛的研究.此外，人们对拟牛顿法求解无约束问题的全局收敛性分析进行了相当的努力并且取得了巨大进展．尽管拟牛顿法的局部收敛性结果十分丰富，但是其求解非线性方程组的全局收敛性结果却很少•全局化方法X=X+«d需要采用某种搜索计算步«，但是此k+1kkkk时拟牛顿方向一般不再是某个度量函数的下降方向，从而使得线性搜索难以实现或考说缺少一种有效的线性搜索.Griewank在1986年研究了解非线性方程组的Broyden秩一方法的全局收敛性，并在文献［2］中提出了一种无导数的线性搜索，同时证明了Broyden方法在该搜索下的全局收敛性.Li和Fukushima在文献［3］中构造了一个反例表明Griewank在文献［2］中的线性搜索在计算中可能会产生某些困难，即该搜索不是

适定的•为克服此缺陷丄i和Fukushima提出了一种非单调搜索技术：求步长ak使得||f(x+ad)|<||f(xad||2+H||f(x)||kkkk1kkkk其中b>0是常数，F耳<q在适当条件下，文献［3］证明了求解非线性方程1“k组的Broyden方法的全局收敛性.关于BFGS方法求解非线性方程组的第一个全局收敛性结果属于Li和Fukushima，1999年，他们在文献［4］中提出了一种新的近似范数下降的BFGS方法，称之为Gauss—Newton型BFGS方法，其拟牛顿方向由下面的方程决定:bd+q=0，

kk其中q=kF(Xk+九k"Xk))-卩(二)皑f\X)F(X),B其中q=kkkkk-1正：BsstBYyTB=B———k_kkk+——k,

k+1kSTBSyTskkk其中S=x其中S=xkk+1—X,y二F(x+y)—F(x)，y二F(x)—F(x).这种kkkkkkk+1kGauss-Newton型BFGS公式不同于标准的BFGS公式，尽管它仍满足拟牛顿方Bs二y.k+1kk注意到y沁F'(x)2S因此B沁F'(x)2相应的方法称之为Gauss-Newtonkk+1kk+1k+1型BFGS方法.2003年，GU等人引入了一种范数下降的线性搜索，并利用Li和Fukushima求解无约束优化问题的CBFGS和MBFGS方法的思想，提出了求解对称非线性方程组的范数下降的保守的和修正的Gauss—Newton型BFGS方法，并且证明了这两种方法全局收敛.尽管牛顿法和拟牛顿法都是非常有效的算法，但是它们都需要计算和存储矩阵，这难以用于求解大型问题•最近，Cruz和Raydan在文献⑸提出了一种求解一般的非线性方程组的非单调的谱梯度方法并证明了其全局收敛性．Zhang和Zhou在文献［6］提出了一种求解单调非线性方程组的谱梯度投影方浃法建立了全局收敛性结果.这两种谱梯度方法都适合求大规模问题，察实上，这两种谱梯度方法是求解无约束优化问题的谱梯度方法在非线性方程组中的推广.前面讨论的都是拟牛顿法求解光滑非线性方程组的已有结果。对拟牛顿法求解非光滑方程组的结果目前并不多见，而且大多数研究集中在局部收敛性分析上.通过光滑技术，Li和Fukushima将文献［3］Broyden方法求解光滑方程组的全局收敛性结果推广到了一般的半光滑方程组［8］.二、求解无约束优化问题的拟牛顿法设f:RntR连续可微，g(x)为f在x点处的梯度，求解无约束优化问题minf(x),VxgRn(2.1)的拟牛顿法的迭代与其求解非线性方程的格式相同，只需要将中(1.4)中y的定k义改为y=g-g,kk+1k其中g是g(x)的简写.kk拟牛顿法求解无约束优化问题不仅局部收敛性分析取得丰硕的成果，而且全局收敛性分析也取得了巨大进展.Powell和Dixon证明了Broyden族方法在精确搜索下求解凸极小化问题时的全局收敛性•所谓的精确搜索，即求Q使得满足kf(x+«d)二minf(x+ad).kkkkko》oByrd等人在文献⑻中证明了除DFP方法外的Broyden族方法在Wolfe线性搜索下求解凸极小化问题的全局收敛性•这里的wolfe搜索，指的是求«使得其满k足f(x+ad)<f(x)+sagTd,kkkkkkkdTg(x+ad)>qdTg,kkkkkk其中0v6<Q<1.Byrd和Nocedal证明了BFGS方法在Armijo线性搜索下求解凸极小化问题的全局收敛性•所谓的Armijo搜索很卩求d二maxpi,j二0,1,2,…k满足f(x+dd)<f(x)+6dgTd，kkkkkkk其中0<p<1为常数•为了研究拟牛顿法求解非凸问题的全局收敛性，Li和Fukushima修正了标准的BFGS公式，提出了CBFGS方法和MBFGS方法并证明了这两种方法在Armijo和Wolfe线性搜索下对非凸极小化问题全局收敛.前面都是关于单调的拟牛顿法求解无约束问题(2.1)的工作，所谓的单调方法就是算法产生的函数值序列单调递减很卩使得f(x)<f(x)成立.非单调方法则kk-1不一定要求f(x)<f(x).最早提出非单调线性搜索技术的是Grippo，kk-1Lampariello和Lucidi.1986年，他们在文献⑺中考虑了如下一般格式的非单调线性搜索技术：给定常数d>0,6,pe(0,1)及非负整数M，寻找步长因子d=maxdP。。卩1,…使得kf(x+pmdd)<maxf(x)+6pmdgTd.(2.2)kkk-jkk0<j<M当M二0时,上面的非单调线性搜索变为标准的Armijo线性搜索•非单调技术(2.2)的一个好处就是不要求函数值减少，从而使步长因子的选取更具有弹性，即使得步长a尽可能的大•此外，Panier和Tits在文献[10]中证明了非单调搜索k技术能避免Maratos效应•大量的数值结果表明，非单调搜索比单调搜索数值表现要好得多，特别是非单调方法能求一些比较困难的问题，此外，其数值计算也比较稳定.三、多步拟牛顿法一般的拟牛顿方法在每一步的迭代中，仅利用上一步产生的梯度信息，建立—个拟牛顿方程，进而求得目标函数Hesse阵的近似。如果将前m(m>0)步的梯度值都纳入到计算过程中，是否会取得更好的效果？基于这样的想法Ford和Moghrabi于1993年提出了多步拟牛顿法。多步拟牛顿法的基本思想如下：记X=x(P)(PeR)为Rn中的一条可微路径。对向量g(x(t))应用链式法则，在曲线X上对应*点处，G(x(v*))满足牛顿等式TOC\o"1-5"\h\zdx(T*)dg(x(T*))(31)G(x)=,(31)k+1dTdT利用上式来建立拟牛顿方程.记s=x-x,g=y-y视｛x(t)｝为一条通过x和x两迭代点的kk+1kkk+1kkk+1直线.即x(T)=x+Ts，(3.2)kk则由(3.2)式有x(0)=x,x(1)=x，并且kk+1dx——=s,VTeR.(3.3)dTk由于很难精确求得Hesse阵，用向后差分来近似(3.4)g(x(t))沁g(x(0))+t[g(x(1))-g(x(0))],

(3.4)由(3.4)式可估算导数d(竺))在工*二1处的值drTOC\o"1-5"\h\zdg"1Qg(x(l))-g(x(0))二g(x)-g(x)二y.(3.5)drr=1k+1kk将(3.3)和(3.5)代入(3.1)中取r*=1可得G(x)sQy.(3.6)k+1kk标准拟牛顿打用近似值B来代替Hesse阵g(X)，由上试B满足k+1k+1k+1Bs=y.(3.7)k+1kk这就是标准的拟牛顿方程.多步拟牛顿法是上述单步牛顿法的推广，其多步拟牛顿方程的推导过程与相类似.假设已知前m+1(m>0)个迭代点X,x，…,X,X以及相应的梯度k-m+1k-m+2kk+1值信息。同样记X=x(r)(reR)为rn中的一条可微路径，但此时x(r)不是一条(3.8)直线，可以定义x(r)为一个m次的插值多项式，其插值基点为(3.8)ii=0x(u)=x,i=0,1,…ii=0Uik-m+i+1的取值不同，将得到不同的插值函数.由前面讨论的拟牛顿方程,ii=0的一个很自然的取法是选择等距的r值，即取r=i—m+1,i=0,1,...,m(3.9)i当然除这种取法外,r值还有很多其他的有效取法•标准的拟牛顿方程是取m=1及r=0,r=1得到的.01构造x(r)的Lagrange插值多项式x(r)=区匚(r)x/(3.10)ik-m+i+1这里的:(r)是基于集合r.丿m的标准的m次拉格朗日多项式的第i项，即iii=0:,(T)J二j=o,j知ij将g(X(T))视为T的函数，由标准拟牛顿方程的推导过程及(3.11)(3.10)式，可用Lagrange插值多项式来近似g(x(t))g(X(T))~y:(t)g(X).ik-m+i+1i=0(3.12)由于T=T对应于Xmk+1在(3.1)中令T*=T接下来计算dx(T_mdT丄和dg(X(T丿的dT值.对(3.10)式求导得dx(T)y0=dTi=0(T)xAr,imk-m+i+1—k(3.13