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

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

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

3、之一。共轭梯度法是一个典型的共轭方向法，它的每一个搜索方向是互相共轭的，而这些搜索方向仅仅是负梯度方向与上一次迭代的搜索方向的组合，因此，存储量少，计算方便。关键词关键词：共轭梯度法；超线性收敛；牛顿法；无约束优化 AbstractIn a variety of optimization algorithms, conjugate gradient method is a very important one. In this paper, the conjugate gradient method is between the steepest descent method and Newt

4、on method for unconstrained optimization between a method, it has superlinear convergence rate, and the algorithm is simple and easy programming.In this experiment, we first analyze the conjugate direction method, the algorithm analysis, the use of a conjugate direction-based algorithm - conjugate g

5、radient method for unconstrained optimization problems. Unconstrained optimization method is to select the core issue of the search direction. Conjugate gradient method is the basic idea of the conjugate descent method with the most combined points in the gradient using the known structure of a set

6、of conjugate directions, and search along the direction of this group, find the minimum point of objective function. According to the basic nature of the conjugate direction, this method has the quadratic termination. Combined with the preparation of this algorithm matlab program for solving unconst

7、rained optimization problems, combined with Newtons theory of knowledge, writing matlab program to solve the same problem of unconstrained optimization, comparison analysis, the conjugate gradient method and Newton method different Office and the advantages and disadvantages of the conjugate gradien

8、t method.Conjugate gradient method using only first derivative information, to avoid the Newton method requires storage and computing the inverse Hesse matrix and shortcomings, is not only the conjugate gradient method to solve large linear systems one of the most useful, but also large-scale soluti

9、on nonlinear optimization algorithm is one of the most effective. Conjugate gradient method is a typical conjugate direction method, each of its search direction is conjugate to each other, and the search direction d is just the negative gradient direction with the last iteration of the search direc

10、tion of the portfolio, therefore, storage less computational complexity.Key words: Conjugate gradient method; Superlinear convergence; Newton method Unconstrained optimization目目 录录1、引言引言.12、共轭梯度法的描述共轭梯度法的描述.12.1 共轭方向法.12.2 共轭梯度法.22.3 Armijo 准则.63、数值实验数值实验.73.1 代码实现.73.2 算法测试.83.3 结果分析.104、算法比较算法比较.1

11、04.1 牛顿法的构造.104.2 算法实现.114.3 算法测试.124.4 算法比较.135、总结总结.135.1 总结概括.135.2 个人感言.146、参考文献、参考文献：.16最优化方法课程设计51 1、引言引言在各种优化算法中，共轭梯度法（Conjugate Gradient）是非常重要的一种。其优点是所需存储量小，具有 N 步收敛性，稳定性高，而且不需要任何外来参数。共轭梯度法是介于最速下降法与牛顿法之间的一个方法，它仅需利用一阶导数信息，但克服了最速下降法收敛慢的缺点，又避免了牛顿法需要存储和计算 Hesse 矩阵并求逆的缺点，共轭梯度法不仅是解决大型线性方程组最有用的方法之一

12、，也是解大型非线性最优化最有效的算法之一。 共轭梯度法最早是又 Hestenes 和 Stiefle（1952）提出来的，用于解正定系数矩阵的线性方程组，在这个基础上， Fletcher 和 Reeves（1964）首先提出了解非线性最优化问题的共轭梯度法。由于共轭梯度法不需要矩阵存储，且有较快的收敛速度和二次终止性等优点，现在共轭梯度法已经广泛地应用与实际问题中。 共轭梯度法是一个典型的共轭方向法，它的每一个搜索方向是互相共轭的，而这些搜索方向仅仅是负梯度方向与上一次迭代的搜索方向的组合，因此，存储量少，计算方便。2 2、共轭梯度法的描述共轭梯度法的描述2.1 共轭方向法共轭方向法共轭方向法

13、是介于最速下降法与牛顿法之间的一个方法。它仅需利用一阶导数信息，但克服了最速下降法收敛慢的缺点，又避免了存贮和计算牛顿法所需要的二阶导数信息。共轭方向法是从研究二次函数的极小化产生的，但是它可以推广到处理非二次函数的极小化问题。一般共轭方向法步骤如下：算法算法 2.1.1 （一般共轭方向法）给出的初始点，*x0 x步 1 计算)(00 xfg步 2 计算，使0d000gdT步 3 令0k步 4 计算和，使得k1kx )(min)(kkkkkdxfdxf kkkkdxx1步 5 计算使得,。1kd01jTkGddkj, 1 , 0最优化方法课程设计6步 6 令,转步 41 : kk共轭方向法的一

14、个基本性质是：只要执行精确线性搜索，就能得到二次终止性。这就是下面的共轭方向法基本定理。定理定理 2.1.1 （共轭方向法基本定理）对于正定二次函数，共轭方向法之多经 n 步精确线性搜索终止；且每一都是在和方向所张成的线性流行中1ix)(xf0 xidd,0jijjjdxxx,00的极小点。2.2 共轭梯度法共轭梯度法共轭梯度法是最著名的共轭方向法，它首先由 Hestenes 和 Stiefel（1952）提出来作为解线性方程组的方法。由于解线性方程组等价于极小化一个正定二次函数，故 1964 年 Fletcher 和 Reeves 提出了无约束极小化的共轭梯度法，它是直接从 Hestenes

15、 和 Stiefel 解线性方程组的共轭梯度法发展而来的。共轭方向法基本定理告诉我们，共轭性和精确线性搜索产生二次终止性。共轭梯度法就是使得最速下降方向具有共轭性，从而提高算法的有效性和可靠性。下面针对二次函数情形讨论共轭梯度法，我们先给出共轭梯度法的推导。设 (2.2.1)cxbGxxxfTT21)(其中是对称正定矩阵，是向量， 是实数。的梯度为Gnnb1ncf (2.2.2)bGxxg)(令 (2.2.3)00gd则 (2.2.4)0001dxx由精确线性搜索性质， (2.2.5)001dgT令 (2.2.6)0011dgd选择，使得0. (2.2.7)001GddT最优化方法课程设计7对

16、（2.2.6）两边同乘以，得GdT0. (2.2.8)001101001100011)()(ggggggdgggGddGdgTTTTTT由共轭方向法基本定理，。利用（2.2.3）和（2.2.6） ，可02iTdg1 , 0i知, . (2.2.9)002ggT012ggT又令, (2.2.10)110022ddgd选择和，使得，。从而有0102iTGdd1 , 0i,00. (2.2.11)11221211221)()(ggggggdgggTTTT一般地，在第次迭代，令k, (2.2.12)10kiiikkdgd选择，使得，。也假定i0iTkGdd1, 1 , 0ki, , , (2.2.13

17、)0iTkdg0iTkgg1, 1 , 0ki对(2.2.12)左乘，则GdTj1, 1 , 0kj, . (2.2.14)()(11jjTjjjTkjTjjTkjggdgggGddGdg1, 1 , 0kj由(2.2.13)，, ,01jTkgg2, 1 , 0kj, ,0jTkgg1, 1 , 0kj故得,和0j2, 1 , 0kj. (2.2.15)111111)()(kTkkTkkkTkkkTkkggggggdggg因此，共轭梯度法的公式为最优化方法课程设计8, (2.2.16)kkkkdxx1其中，在二次函数情形，. (2.2.17) kTkkTkkGdddg一般地，由精确线性搜索得

18、到，当然也可以由非线性搜索得到，k (2.2.18),11kkkkdgd (Crowder-Wolfe 公式) (2.2.19)()(111kkTkkkTkkggdggg.(Fletcher-Reeves 公式) (2.2.20)kTkkTkgggg11另两个常用的公式为, (Polak-Ribiere-Polyak 公式) (2.2.21)kTkkkTkkggggg)(11.(Dixon 公式) (2.2.22)kTkkTkkgdgg11由上面的公式可见，共轭梯度法具有二次终止性（即对于二次函数，算法在有限步终止） ，所以共轭梯度法是一个很吸引人的方法。共轭梯度法步骤如下：算法算法 2.2.

19、1(共轭梯度法)步 0 给定迭代精度和初始点.计算.令.100 x)(00 xfg0 :k步 1 若,停算,输出.kgkxx *步 2 计算搜索方向:kd1, , 0 ,11kdgkgdkkkkk其中当时,确定.1k111kTkkTkkgggg1k步 3 利用精确(或非精确)线搜索方法确定搜索步长.k步 4 令,并计算.kkkkdxx :1)(11kkxfg最优化方法课程设计9步 5 令,转步 1.1 : kk下面证明算法 2.2.1 的收敛性定理。定理定理 2.2.3 设是由算法 2.2.1 产生的序列, 假定函数一阶连续可kx)(xf微且水平集是有界的。那么算法 2.2.1 或者有限步终)

20、()(|)(00 xfxfxxL止, 或者。0)(limkkxg证：不是一般性，不放假设是无穷序列，此时有，因kx0)(kxg 故有11kkkkdgd，0|2112|kkTkkkkTkgdggdg即是下降方向，从而由精度线性搜索规则可知，是单调下降的，故kd)(kxf，于是是有界的，因为必有聚点，即存在子列收)(0 xLxkkx*x:1Kkxk敛到，由的连续性，有*xf.)()()(*) 1() 1(*limlimxfxfxffkKkkKk类似地，也是有界序列，故存在子列收敛到，这里:11Kkxk:21Kkxk*x是无穷子序列，于是可得12KK.)()()(*)2()2(*limlimxfxf

21、xffkKkkKk故有. (2.2.23)*)()(fxfxf下面用反证法证明.如果不然，即，则对于充分小，0)(*xg0)(*xg0有.)()(*xfdxf注意到，对任意的，有0.)()()(1kkkkkkdxfdxfxf对于，令对上式去极限得12KKkk，)()()(*xfdxfxf这与(2.2.23)式相矛盾，从而证明了. 证毕.0)(*xg 若在算法 2.2.1 中采用非精度搜索确定的补步长因子，比如 Wolfe 准则k和 Armijo 准则，则利用一般下降类算法的全局收敛性定理，可得到非精确搜索下的共轭梯度算法的收敛性定理。最优化方法课程设计10定理定理 2.2.4 设是由算法 2.

22、2.1 利用 Wolfe 准则产生的序列，假定函数 kx一阶连续可微且有下界，其梯度函数在上 Lipschitz 连续，即存在)(xf)(xgnR常数，使得0L, .vuLvgug)()(nRvu ,若选取的搜索方向与的夹角满足条件kdkgk, .20k)2, 0(那么算法 2.2.1 或者有限步终止，或者。0)(limkkxg证证: 不失一般性,不妨假设是无穷序列.由 Lipschitz 及连续条件和 Wolfe 准则 kx得kTkkkkkTkkkgdgdxgddL)1 ()( , kkkgdcos)1 ( 即.khkkgLdcos)1 ( 于是利用上式及 Wolfe 准则可得)()(kkk

23、kdxfxf kkkkkTkkgdgdcos kkgL22cos)1 ( .22sin)1 (kgL注意到是有下界的,由上式不难推得)(xf,02kg这蕴含了当时,有.证毕. k0kg2.3 Armijo 准则准则Armijo 准则是指: 给定,令步长因子. 其中 )5 . 0 , 0(),1 , 0(kmkkm是满足下列不等式的最小非负整数: 最优化方法课程设计11 (2.3.1)kTkmkkmkdxfxfdxf)()()(可以证明, 若是连续可微的且满足, 则 Armijo 准则是有限终)(xf0)(kTkdxf止的, 即存在正数, 使得对于充分大的正整数, (2.3.1) 式成立. 也就

24、是说，m目标函数的下降要与步长和下降方向成一定的比例。f为了程序实现的方便, 我们将 Armijo 准则写成下列详细的算法步骤。算法算法 2.3.1 (Armijo 准则)步 0 给定.令.)5 . 0 , 0(),1 , 0(0:m步 1 若不等式kTkmkkmkdxfxfdxf)()()(成立，置，停算，否则，转步 2.kkdmkkkxxmm:,:1步 2 令，转步 1.1: mmk3 3、数值实验、数值实验3.1 代码实现代码实现在共轭梯度法的实际使用中，通常在迭代步或步之后，重新取负梯n1n度方向作为搜索方向，我们称之为再开始共轭梯度法。这是因为对于一般非二次函数而言，步迭代后共轭梯度

25、法产生的搜索方向往往不再具有共轭性。而n对于大规模问题，常常每 (或) 步就进行再开始。此外，当搜mnm nm 索方向不是下降方向时，也插入负梯度方向作为搜索方向。基于Armijo 非精确线性搜索的再开始FR共轭梯度法的Matlab程序如下：(分别新建 frcg.M , fun.M , gfun.M 三个M文件)function x,val,k=frcg(fun,gfun,x0)% 功能: 用 FR 共轭梯度法求解无约束问题: min f(x)%输入: x0 是初始点, fun, gfun 分别是目标函数和梯度%输出: x, val 分别是近似最优点和最优值, k 是迭代次数.maxk=500

26、0; %最大迭代次数rho=0.6;sigma=0.4;k=0; epsilon=1e-4; n=length(x0);while(k=0.0) d=-g; end end if(norm(g)epsilon), break; end %检验终止条件 m=0; mk=0; while(m20) %Armijo 搜索 if(feval(fun,x0+rhom*d)feval(fun,x0)+sigma*rhom*g*d) mk=m; break; end m=m+1; end x0=x0+rhomk*d; val=feval(fun,x0); g0=g; d0=d; k=k+1;endx=x0;

27、val=feval(fun,x);3.2 算法测试算法测试我们通过求解两个无约束优化问题来验证算法的稳定性和准确性。问题一：求解无约束优化问题，该问题的有精确解121222122123)(min2xxxxxxfRx最优化方法课程设计13。1)() 1 , 1 (*xfxT，问题二：求解无约束优化问题，该问题的有精确212221) 1()(100)(min2xxxxfRx解。0)() 1 , 1 (*xfxT，解解：利用程序 3.1 求解以上两个问题，终止准则为，分别修改目4010)(xf标函数和梯度如下：fun.Mfun.M 文件文件function f=fun(x) %目标函数f=(3*x(

28、1)2)/2+x(2)2/2-x(1)*x(2)-2*x(1); %问题一函数%f=100*(x(1)2-x(2)2+(x(1)-1)2; %问题二函数gfun.Mgfun.M 文件文件function gf=gfun(x) %目标函数的梯度函数gf=3*x(1)-x(2)-2,x(2)-x(1); %问题一梯度函数%gf=400*x(1)*(x(1)2-x(2)+2*(x(1)-1), -200*(x(1)2-x(2); %问题二梯度函数分别取不同的起始点的数值结果如下表：表 3.1 问题一 FR 共轭梯度法的数值结果初始点()0 x迭代次数（）k目标函数值（）)(kxf最优解（）kxT)0

29、 , 0(12-1.0000T)9999. 0 ,0000. 1 (T)5 . 0 , 5 . 0(11-1.0000T)9999. 0 ,0000. 1 (T)5 . 2, 2 . 1 (12-1.0000T)0001. 1 ,0000. 1 (T)3, 3( 15-1.0000T)0000. 1 ,0000. 1 (T)3 , 3(13-1.0000T)0001. 1 ,0000. 1 (最优化方法课程设计14表 3.2 问题二 FR 共轭梯度法的数值结果初始点()0 x迭代次数（）k目标函数值（）)(kxf最优解（）kxT)0 , 0(281.8462e-007T)0000. 1 ,00

30、00. 1 (T)5 . 0 , 5 . 0(131.4796e-007T)0001. 1 ,0000. 1 (T)5 . 2, 2 . 1 (153.2749e-007T)0000. 1 ,0000. 1 (T)3, 3( 224.0962e-008T)0000. 1 ,0000. 1 (T)3 , 3(183.5854e-007T)0000. 1 ,0000. 1 (3.3 结果分析结果分析由表 3.1 和表 3.2 可见 FR 共轭梯度法在不同的初始点，求解最优解的迭代次数有所差异，分析可见，在接近精确解的输出点处的迭代次数会相对较少。并且计算结果比较稳定，误差在忽略范围内。4 4、算法

31、比较、算法比较4.1 牛顿法的构造牛顿法的构造牛顿法是一种经典的无约束优化算法, 并且因其收敛速度快以及具有自适应性等优点而至今仍受到科技工作者的青睐.牛顿法也是求解无约束优化问题最早使用的经典算法之一. 其基本思想是用迭代点处的一阶导数(梯度) 和二阶kx导数(Hesse 阵) 对目标函数进行二次函数近似, 然后把二次模型的极小点作为新的迭代点, 并不断重复这一过程, 直至求得满足精度的近似极小点.下面来推导牛顿法的迭代公式. 设的 Hesse 阵连续, )(xf)()(2xfxG截取其在处的泰勒展开式的前三项得kx,)()(21)()(kkTkkTkkkxxGxxxxgfxq最优化方法课程

32、设计15其中,.求二次函数的稳定点，得)(kkxff )(kkxfg)(2kkxfG)(xqk.0)()(kkkkxxGgxq若非奇异，那么解上面的线性方程组即得牛顿法的迭代公式kG.kkkkgGxx11在迭代公式中每步迭代需求 Hesse 阵的逆，在实际计算中可通过先解1kG得，然后令来避免求逆。这样，可以写出基本牛顿法kkgdGkdkkkdxx1的步骤如下：算法算法 4.1.1（基本牛顿法）步 0 给定终止误差,初始点.令.10nRx 00 :k步 1 计算.若,停算，输出.)(kkxfgkgkxx 步 2 计算,并求解线性方程组得:)(2kkxfGkd.kkgdG步 3 令,转第一步.k

33、kkdxx11 : kk牛顿法最突出的优点是收敛速度快，具有局部二阶收敛性。4.2 算法实现算法实现根据牛顿算法，编写 matlab 程序，求解无约束优化问题，代码如下：function x,val,k=grad(fun,gfun,x0)% 功能: 用最速下降法求解无约束问题: min f(x)%输入: x0 是初始点, fun, gfun 分别是目标函数和梯度%输出: x, val 分别是近似最优点和最优值, k 是迭代次数.maxk=5000; %最大迭代次数rho=0.5;sigma=0.4;k=0; epsilon=1e-5;while(kmaxk) g=feral(gfun,x0);

34、 %计算梯度 d=-g; %计算搜索方向 if(norm(d)epsilon), break; end m=0; mk=0;最优化方法课程设计16 while(m20) %Armijo 搜索 if(feral(fun,x0+rhom*d)feral(fun,x0)+sigma*rhom*g*d) mk=m; break; end m=m+1; end x0=x0+rhomk*d; k=k+1;endx=x0;val=feral(fun,x0);4.3 算法测试算法测试使用此牛顿法求解此前的问题一和问题二，取不同的起始点的数值结果分别如下表：问题一：表 4.1 问题一 牛顿法的数值结果初始点()

35、0 x迭代次数（）k目标函数值（）)(kxf最优解（）kxT)0 , 0(23-1.0000T)0000. 1 ,0000. 1 (T)5 . 0 , 5 . 0(23-1.0000T)0000. 1 ,0000. 1 (T)5 . 2, 2 . 1 (25-1.0000T)0000. 1 ,0000. 1 (T)3, 3( 37-1.0000T)0000. 1 ,0000. 1 (T)3 , 3(25-1.0000T)0000. 1 ,0000. 1 (最优化方法课程设计17问题二：表 4.2 问题二 牛顿法的数值结果初始点()0 x迭代次数（）k目标函数值（）)(kxf最优解（）kxT)0 , 0(382.8220e-009T)0000. 1 ,0000. 1 (T)5 . 0 , 5 . 0(281.4429e-011T)0000. 1 ,0000. 1 (T)5 . 2, 2 . 1 (371.3597e-009T)0000. 1 ,0000. 1 (T)3, 3( 392.1601e-009T)0000. 1 ,0000. 1 (T)3 , 3(371.4698e-009T)0000. 1 ,0000. 1 (4.4 算法比较算法比较通过求解问题一和问题二，由上表可以看出, 共轭梯度法的收敛速度是比较令人满意的，在相同初始点处开始求解，使用牛顿法所需