最优化方法课程设计参考模版

1、;黄拉林电彳科被火玲/GUILINUNIVERSITYOFELECTRONICTECHNOLOGY最优化方法课程设计题目：共梯度法算法分析与实现院系：数学与计算科学学院专业：数学与应用数学姓名：梁婷艳学号：学00730103指导教师：李丰兵日期：2015年12月30日摘要在各种优化算法中，共腕梯度法是非常重要的一种。本文主要介绍的共腕梯度法是介于最速下降法与牛顿法之间的一种无约束优化算法，它具有超线性收敛速度，而且算法结构简单，容易编程实现。在本次实验中，我们首先分析共腕方向法、对该算法进行分析，运用基于共腕方向的一种算法一共腕梯度法进行无约束优化问题的求解。无约束最优化方法的核心问题是选择搜

2、索方向。共腕梯度法的基本思想是把共腕性与最速下降方法相结合，利用已知点处的梯度构造一组共腕方向，并沿这组方向进行搜索，求出目标函数的极小点。根据共腕方向的基本性质，这种方法具有二次终止性。再结合该算法编写matlab程序，求解无约束优化问题，再结合牛顿算法的理论知识，编写matlab程序，求解相同的无约束优化问题，进行比较分析，得出共腕梯度法和牛顿法的不同之处以及共腕梯度法的优缺点。共腕梯度法仅需利用一阶导数信息，避免了牛顿法需要存储和计算Hesse矩阵并求逆的缺点，共腕梯度法不仅是解决大型线性方程组最有用的方法之一，也是解大型非线性最优化最有效的算法之一。共腕梯度法是一个典型的共腕方向法，它

3、的每一个搜索方向是互相共腕的，而这些搜索方向仅仅是负梯度方向与上一次迭代的搜索方向的组合，因此，存储量少，计算方便。关键词：共腕梯度法；超线性收敛；牛顿法；无约束优化AbstractInavarietyofoptimizationalgorithms,conjugategradientmethodisaveryimportantone.Inthispaper,theconjugategradientmethodisbetweenthesteepestdescentmethodandNewtonmethodforunconstrainedoptimizationbetweenamethod,it

4、hassuperlinearconvergencerate,andthealgorithmissimpleandeasyprogramming.Inthisexperiment,wefirstanalyzetheconjugatedirectionmethod,thealgorithmanalysis,theuseofaconjugatedirection-basedalgorithm-conjugategradientmethodforunconstrainedoptimizationproblems.Unconstrainedoptimizationmethodistoselectthec

5、oreissueofthesearchdirection.Conjugategradientmethodisthebasicideaoftheconjugatedescentmethodwiththemostcombinedpointsinthegradientusingtheknownstructureofasetofconjugatedirections,andsearchalongthedirectionofthisgroup,findtheminimumpointofobjectivefunction.Accordingtothebasicnatureoftheconjugatedir

6、ection,thismethodhasthequadratictermination.Combinedwiththepreparationofthisalgorithmmatlabprogramforsolvingunconstrainedoptimizationproblems,combinedwithNewtonstheoryofknowledge,writingmatlabprogramtosolvethesameproblemofunconstrainedoptimization,comparisonanalysis,theconjugategradientmethodandNewt

7、onmethoddifferentOfficeandtheadvantagesanddisadvantagesoftheconjugategradientmethod.Conjugategradientmethodusingonlyfirstderivativeinformation,toavoidtheNewtonmethodrequiresstorageandcomputingtheinverseHessematrixandshortcomings,isnotonlytheconjugategradientmethodtosolvelargelinearsystemsoneofthemos

8、tuseful,butalsolarge-scalesolutionnonlinearoptimizationalgorithmisoneofthemosteffective.Conjugategradientmethodisatypicalconjugatedirectionmethod,eachofitssearchdirectionisconjugatetoeachother,andthesearchdirectiondisjustthenegativegradientdirectionwiththelastiterationofthesearchdirectionoftheportfo

9、lio,therefore,storagelesscomputationalcomplexity.Keywords:Conjugategradientmethod;Superlinearconvergence;NewtonmethodUnconstrainedoptimization1、引言5.2、共钝梯度法的描述.5.2.1 共腕方向法5.2.2 共腕梯度法6.2.3 Armijo准则6.3、数值实验7.3.1 代码实现7.3.2 算法测试8.3.3 结果分析104、算法比较104.1 牛顿法的构造1.04.2 算法实现1.14.3 算法测试124.4 算法比较135、总结 总

10、结概括135.2 个人感言146、参考文献：161、引言在各种优化算法中，共腕梯度法(ConjugateGradient是非常重要的一种。其优点是所需存储量小，具有N步收敛性，稳定性高，而且不需要任何外来参数。共腕梯度法是介于最速下降法与牛顿法之间的一个方法，它仅需利用一阶导数信息，但克服了最速下降法收敛慢的缺点，又避免了牛顿法需要存储和计算Hesse矩阵并求逆的缺点，共腕梯度法不仅是解决大型线性方程组最有用的方法之一，也是解大型非线性最优化最有效的算法之一。共腕梯度法最早是又Hestenes和Stiefle(1952)提出来的，用于解正定系数矩阵的线性方程组，在这个基础上，Fletcher和

11、Reeves(1964)首先提出了解非线性最优化问题的共腕梯度法。由于共腕梯度法不需要矩阵存储，且有较快的收敛速度和二次终止性等优点，现在共腕梯度法已经广泛地应用与实际问题中。共腕梯度法是一个典型的共腕方向法，它的每一个搜索方向是互相共腕的，而这些搜索方向仅仅是负梯度方向与上一次迭代的搜索方向的组合，因此，存储量少，计算方便。2、共钝梯度法的描述2.1共腕方向法共腕方向法是介于最速下降法与牛顿法之间的一个方法。它仅需利用一阶导数信息，但克服了最速下降法收敛慢的缺点，又避免了存贮和计算牛顿法所需要的二阶导数信息。共腕方向法是从研究二次函数的极小化产生的，但是它可以推广到处理非二次函数的极小化问题

12、。一般共腕方向法步骤如下：算法2.1.1(一般共腕方向法)给出x的初始点X0,步1计算g0=Vf(xo)步2计算do,使dTgo<0步3令k=0步4计算外和Xk书，使得f(xk-:kdk)=m1nf(xk：dk)axk1=xk,;对步5计算dk书使得dT+Gdj=0,j=0,1，k。步6令k:=k+1,转步4共腕方向法的一个基本性质是：只要执行精确线性搜索，就能得到二次终止性。这就是下面的共腕方向法基本定理。定理2.1.1(共腕方向法基本定理)对于正定二次函数，共腕方向法之多经n步精确线性搜索终止；且每一为中都ji、是f(x)在X0和方向d0,，di所张成的线性流行)XX=X0+

13、3;ctjdj,寸aj中的极LTJ小点。2.2共腕梯度法共腕梯度法是最著名的共腕方向法，它首先由Hestene列Stiefel(1952)提出来作为解线性方程组的方法。由于解线性方程组等价于极小化一个正定二次函数，故1964年Fletcher和Reeves提出了无约束极小化的共腕梯度法，它是直接从Hestenes和Stiefel解线性方程组的共腕梯度法发展而来的。共腕方向法基本定理告诉我们，共腕性和精确线性搜索产生二次终止性。共腕梯度法就是使得最速下降方向具有共腕性，从而提高算法的有效性和可靠性。下面针对二次函数情形讨论共腕梯度法，我们先给出共腕梯度法的推导。设(2.2.1)1If(x)=xG

14、xbxc2其中G是n"对称正定矩阵，b是nx1向量，c是实数。f的梯度为g(x)=Gxb(2.2.2)令d。一go(2.2.3)则X=X。;0d0(2.2.4)由精确线性搜索性质，g1Td0=0(2.2.5)令d1=-g110d0(2.2.6)d；Gdo=0.对(2.2.6)两边同乘以d；G,得giTGdog；(gi-go)g：g1-1.T.doGdodo(gi-g°)gogo由共腕方向法基本定理，g；di=O,i=。,1。利用(2.2.3)gTgo=o,gTgi=o.又令d2-g2-odoidi,选主举Bo和Pi,使得dTGdi=O,i=O,I0从而有O=O,:_gT(g

15、2-gi)_gTg2'i-TTTTt.di(g2-gi)gigi一般地，在第k次迭代，令kJdk=-gk=；idi,i=O选主举Pi,使得dTGdi=O,i=O,I，k-1。也假定gTdi=O,gTgi=O,i=O,i,k-i,Xt(2.2.i2)左乘d：G,j=O,i，ki,则gTGdjgTSri-gj)=dTGd=dT，jWdjGdjdj(gjigj)由(2.2.i3),g：gji=o,j=o,i,k-2,gTgj=o,j=o,i,k-i,故得Pj=O,j=O,i，,k2和gT(gk-g)gTgkk41t八、1te(2.2.(7)(2.2.(8)(2.2.6),可知(2.2.(9)

16、(2.2.(10)(2.2.(11)(2.2.(12)(2.2.(13)(2.2.(14)(2.2.i5)dk-i(gkgk4)gk-igk-i因此，共腕梯度法的公式为其中，在二次函数情形,-9kdkdTGdk般地，丸由精确线性搜索得到，当然也可以由非线性搜索得到,dk1=-9k1,kdk,丸=g小9k书-9k）（Crowder-Wolfe公式）dT（9ki-9k）T=9kT9k1.（Fletcher-Reeves公式）9k9k另两个常用的公式为pk=9-.（9T.9k）,（poiak-Ribiere-Polyak公式）9k9kT久=999k.3。门公式）dk9k由上面的公式可见，共腕梯度法具

17、有二次终止性（即对于二次函数,有限步终止），所以共腕梯度法是一个很吸引人的方法。共腕梯度法步骤如下：算法2.2.1（共腕梯度法）步0给定迭代精度0E6«1和初始点.计算90=Vf（x°）.令k:=(2.2.(16)(2.2.(17)(2.2.(18)(2.2.(19)(2.2.(20)(2.2.(21)(2.2.(22)算法在0.步1若|9k仔以停算，输出x*划Xk.步2计算搜索方向dk：d9k,k=0,k-9k+Bkjdk，k之1,L_kkk1k1,T其中当k1时，久口=9k9k确定By.9k49y步3利用精确（或非精确）线搜索方法确定搜索步长外步4令Xk41:=Xk+G

18、kdk,并计算9k书=Vf(Xk+).步5令k:=k+1,转步1.下面证明算法2.2.1的收敛性定理。定理2.2.3设xj是由算法2.2.1产生的序列，假定函数f(x)一阶连续可微且水平集L(%)=x|f(x)Wf(%)是有界的。那么算法2.2.1或者有限步终止，或者limg(x。=0。k：证：不是一般性，不放假设xj是无穷序列，此时有g(xk)#0,因dk=gk+Pkdk故有gTdk=-|回|2+PkgTdk_L=|gk|，0,即dk是下降方向，从而由精度线性搜索规则可知，f(xj是单调下降的，故xkuL(x0),于是xB是有界的，因为必有聚点x,即存在子列xjkwKj收敛到x*,由f的连续

19、性，有*f=jm：f(xk)=f(jmxk)=f(x).*类似地，xk书：kwKi也是有界序列，故存在子列xk书：kwK2收敛到x,这里K2二K1是无穷子序列，于是可得*、f'财""回/).故有*f(x)=f(x)=f.(2.2.23)下面用反证法证明g(x*)=0.如果不然，即g(x*)=0,则对于充分小«>0,有_*_*f(x2):f(x).注意到，对任意的a>0,有f(xk1)=f(xk:kdk)-f(xk-dk).对于kWK2UK1,令kT妙对上式去极限得*_._*.*_*f(x)Vf(x+ad)<f(x),、>L-.一&#

20、39;一*.这与(2.2.23)式相矛盾，从而证明了g(x)=0.证毕.若在算法2.2.1中采用非精度搜索确定的补步长因子外，比如Wolfe准则和Armijo准则，则利用一般下降类算法的全局收敛性定理，可得到非精确搜索下的共腕梯度算法的收敛性定理。定理2.2.4设xj是由算法2.2.1利用Wolfe准则产生的序列，假定函数f(x)一阶连续可微且有下界，其梯度函数g(x)在Rn上Lipschitz连续，即存在常数L>0,使得g(u)-g(v)|<L|u-v|,Vu,v=Rn.若选取的搜索方向dk与-gk的夹角或满足条件0£4三一-，J(0,-).22那么算法2.2.1或者有

21、限步终止，或者limg(xk)=0。kf二证：不失一般性，不妨假设小是无穷序列.由Lipschitz及连续条件和Wolfe准则得:kLdk-dT0风:kdk)-gkL-(1-二)dTgk=(1“dk|g/coSk,即«k|dk|(1g)|gh|cos%L.于是利用上式及Wolfe准则可得f(xk)-f(xk：kdk)"-c二kdTgk=?kdk|gkcos%之P(1CT)|gk|2cosflkzp(1-CT)iigki2sin.注意到f(x)是有下界的，由上式不难推得二2一、g2一二，k=0这蕴含了当kTS时，有|gjT0.证毕.2.3Armijo准则Armijo准则是指:

22、给定B(0,1)封口(0,0.5)，令步长因子%=”.其中mk是满足下列不等式的最小非负整数：f(Xkmdk)<f(xk)c-mf(xk)Tdk(2.3.1)可以证明，若f(x)是连续可微的且满足Vf(xk)Tdk<0,则Armijo准则是有限终止的，即存在正数仃，使得对于充分大的正整数m,(2.3.1)式成立.也就是说，目标函数f的下降要与步长和下降方向成一定的比例。为了程序实现的方便，我们将Armijo准则写成下列详细的算法步骤。算法2.3.1(Armijo准则)步0给定Pe(0,1),a(0,0.5).令m:=0.步1若不等式f(xk：mdk)<f(xk)'f(

23、xk)Tdk成立，置mk:=m,x«:=xk+P"dk,停算，否则，转步2.步2令mk:=m+1,转步1.3、数值实验3.1 代码实现在共腕梯度法的实际使用中，通常在迭代n步或n+1步之后，重新取负梯度方向作为搜索方向，我们称之为再开始共腕梯度法。这是因为对于一般非二次函数而言，n步迭代后共腕梯度法产生的搜索方向往往不再具有共腕性。而对于大规模问题，常常每m(m<n或m<<n)步就进行再开始。此外，当搜索方向不是下降方向时，也插入负梯度方向作为搜索方向。基于Armijo非精确线性搜索的再开始F戏腕梯度法的Matlab程序如下：(分别新建frcg.M,fun

24、.M,gfun.M三个Mt件)functionx,val,k=frcg(fun,gfun,x0)%功能：用FR共腕梯度法求解无约束问题：minf(x)%俞入：x0是初始点，fun,gfun分别是目标函数和梯度%俞出：x,val分别是近似最优点和最优值,k是迭代次数.maxk=5000;%最大迭代次数rho=0.6;sigma=0.4;k=0;epsilon=1e-4;n=length(x0);while(k<maxk)g=feval(gfun,x0);%计算梯度itern=k-(n+1)*floor(k/(n+1);itern=itern+1;%计算搜索方向if(itern=1)d=-g

25、;elsebeta=(g*g)/(g0,*g0);d=-g+beta*d0;gd=g'*d;if(gd>=0.0)d=-g;endendif(norm(g)<epsilon),break;end%检验终止条件m=0;mk=0;while(m<20)%Armijo搜索if(feval(fun,x0+rh0Am*d)<feval(fun,x0)+sigma*rh0Am*g,*d)mk=m;break;endm=m+1;endx0=x0+rhoAmk*d;val=feval(fun,x0);g0=g;d0=d;k=k+1;endx=x0;val=feval(fun,x

26、);3.2 算法测试我们通过求解两个无约束优化问题来验证算法的稳定性和准确性。问题一:求解无约束优化问题miRf(x)=：x12+;x；-x1x2-2x1,该问题的有精确解x=(1,1)T,f(x)=1。问题二：求解无约束优化问题miqf(x)=100(x12-x2)2+(x1一1)2,该问题的有精确解x.Rx=(1,1)T,f(x)=0。解:伊仇）|«10,分别修改目标利用程序3.1求解以上两个问题，终止准则为函数和梯度如下：fun.M文件functionf=fun(x)%目标函数f=(3*x(1)A2)/2+x(2)A2/2-x(1)*x(2)-2*x(1);%问题一函数%f=1

27、00*(x(1)A2-x(2)A2+(x(1)-1)A2;%问题二函数gfun.M文件functiongf=gfun(x)%目标函数的梯度函数gf=3*x(1)-x(2)-2,x(2)-x(1)'%问题一梯度函数%gf=400*x(1)*(x(1)A2-x(2)+2*(x(1)-1),-200*(x(1)A2-x(2)'%问题二梯度函数分别取不同的起始点的数值结果如下表:表3.1问题一FR共腕梯度法的数值结果初始点（%）迭代次数（k）目标函数值（f（xk）最优解（xk）(0,0)T12-1.0000(1.000Q0.9999)t(0.5,0,5)T11-1.0000(1.000

28、Q0.9999)t(1.2,-2.5)t12-1.0000(1.000Q1.0001)t(3,-3)T15-1.0000(1.000Q1.0000)t(3,3)T13-1.0000(1.000Q1.0001)t表3.2问题二FR共腕梯度法的数值结果初始点(%)迭代次数(k)目标函数值(f(xj)最优解(Xk)(0,0)T281.8462e-007(1.000Q1.0000)T(0.5,0,5)t131.4796e-007(1.000Q1.0001)t(1.2,-2.5)t153.2749e-007(1.000Q1.0000)t(3,-3)T224.0962e-008(1.000Q1.0000)

29、T(3,3)t183.5854e-007(1.000Q1.0000)T3.3 结果分析由表3.1和表3.2可见FR共腕梯度法在不同的初始点，求解最优解的迭代次数有所差异，分析可见，在接近精确解的输出点处的迭代次数会相对较少。并且计算结果比较稳定，误差在忽略范围内。4、算法比较4.1 牛顿法的构造牛顿法是一种经典的无约束优化算法，并且因其收敛速度快以及具有自适应性等优点而至今仍受到科技工作者的青睐.牛顿法也是求解无约束优化问题最早使用的经典算法之一.其基本思想是用迭代点Xk处的一阶导数(梯度)和二阶导数(Hesse阵)对目标函数进行二次函数近似,然后把二次模型的极小点作为新的迭代点，并不断重复这

30、一过程，直至求得满足精度的近似极小点.下面来推导牛顿法的迭代公式.设f(x)的Hesse阵G(x)=2f(x)连续，截取其在Xk处的泰勒展开式的前三项得_T1T_qk(x)=fkgk(X-Xk)-(x-Xk)Gk(x-Xk),2其中fk=f(Xk),gk=Vf(Xk),Gk=V2f(Xk).求二次函数qk(x)的稳定点，得vqk(x)=gkGk(x-Xk)=0.若Gk非奇异，那么解上面的线性方程组即得牛顿法的迭代公式1Xki*-Gkgk.在迭代公式中每步迭代需求Hesse阵的逆G，在实际计算中可通过先解Gkd=-gk得dk,然后令xk=xk+dk来避免求逆。这样，可以写出基本牛顿法的步骤如下：

31、算法4.1.1(基本牛顿法)步0给定终止误差0工名1,初始点xowRn.令k:=0.步1计算gk7f(x)若修|以，停算,输出x*期xk.步2计算Gk=/f(xk),并求解线性方程组得dk：Gkd=-gk.步3令xk由=xk+dk,k:=k+1,转第一步.牛顿法最突出的优点是收敛速度快，具有局部二阶收敛性。4.2 算法实现根据牛顿算法，编写matlab程序，求解无约束优化问题，代码如下：functionx,val,k=grad(fun,gfun,x0)%功能：用最速下降法求解无约束问题：minf(x)%俞入：x0是初始点，fun,gfun分别是目标函数和梯度%俞出：x,val分别是近似最优点和

32、最优值,k是迭代次数.maxk=5000;%最大迭代次数rho=0.5;sigma=0.4;k=0;epsilon=1e-5;while(k<maxk)g=feral(gfun,x0);%计算梯度d=-g;%计算搜索方向if(norm(d)<epsilon),break;endm=0;mk=0;while(m<20)%Armijo搜索if(feral(fun,x0+rh0Am*d)<feral(fun,x0)+sigma*rh0Am*g'*d)mk=m;break;endm=m+1;endx0=x0+rhoAmk*d;k=k+1;endx=x0;val=fera

33、l(fun,x0);4.3 算法测试使用此牛顿法求解此前的问题一和问题二，取不同的起始点的数值结果分别如下表：问题一:表4.1问题一牛顿法的数值结果初始点（x0）迭代次数（k）目标函数值（f（xj）最优解（xQ(0,0)T23-1.0000(1.0000,1.0000)T(0.5,0.5)t23-1.0000(1.0000,1.0000)T(1.2,-2.5)t25-1.0000(1.0000,1.0000)T(3,-3)T37-1.0000(1.0000,1.0000)T(3,3)T25-1.0000(1.0000,1.0000)T问题二:表4.2问题二牛顿法的数值结果初始点（%）迭代次数（k）目标函数值（f（Xk）最优解（xQ(0,0)T382.8220e-009(1.0000,1.0000)T(0.5,0.5)t281.4429e-011(1.0000,1.0000)T(1.2,-2.5)t371.3597e-009(1.0000,1.0000)T(3,-3)T392.1601e-009(1.0000,1.0000)T(3,3)T371.4698e-009(1.0000,1.0000)T4.4 算法比较通过求解问题一和问题二，由上表可以看出，共腕梯度法的收敛速度是比较令人满意的，在相同初始点处开始求解，使用牛顿法所需要的迭代次数共腕梯度法的迭代次数的两倍。虽然