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

1、精选优质文档-倾情为你奉上最 优 化 方 法课 程 设 计题 目： 共轭梯度法算法分析与实现 院 系： 数学与计算科学学院 专 业： 数学与应用数学 姓 名： 梁婷艳 学 号： 指导教师： 李丰兵 日 期： 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 Newton method for unconstrained

4、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 gradient method for unconstra

5、ined 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 of conjugate directions, and

6、 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 unconstrained optimization problems

7、, 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 gradient method.Conjugate gradient

8、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 solution nonlinear optimization al

9、gorithm 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 direction of the portfolio, there

10、fore, storage less computational complexity.Key words: Conjugate gradient method; Superlinear convergence; Newton method Unconstrained optimization目 录1、引言在各种优化算法中，共轭梯度法（Conjugate Gradient）是非常重要的一种。其优点是所需存储量小，具有N步收敛性，稳定性高，而且不需要任何外来参数。共轭梯度法是介于最速下降法与牛顿法之间的一个方法，它仅需利用一阶导数信息，但克服了最速下降法收敛慢的缺点，又避免了牛顿法需要存储和计算

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

12、法的描述2.1 共轭方向法共轭方向法是介于最速下降法与牛顿法之间的一个方法。它仅需利用一阶导数信息，但克服了最速下降法收敛慢的缺点，又避免了存贮和计算牛顿法所需要的二阶导数信息。共轭方向法是从研究二次函数的极小化产生的，但是它可以推广到处理非二次函数的极小化问题。一般共轭方向法步骤如下：算法 2.1.1 （一般共轭方向法）给出的初始点，步1 计算步2 计算，使步3 令步4 计算和，使得步5 计算使得,。步6 令,转步4共轭方向法的一个基本性质是：只要执行精确线性搜索，就能得到二次终止性。这就是下面的共轭方向法基本定理。定理 2.1.1 （共轭方向法基本定理）对于正定二次函数，共轭方向法之多经n

13、步精确线性搜索终止；且每一都是在和方向所张成的线性流行中的极小点。2.2 共轭梯度法共轭梯度法是最着名的共轭方向法，它首先由Hestenes和Stiefel（1952）提出来作为解线性方程组的方法。由于解线性方程组等价于极小化一个正定二次函数，故1964年Fletcher和Reeves提出了无约束极小化的共轭梯度法，它是直接从Hestenes和Stiefel解线性方程组的共轭梯度法发展而来的。共轭方向法基本定理告诉我们，共轭性和精确线性搜索产生二次终止性。共轭梯度法就是使得最速下降方向具有共轭性，从而提高算法的有效性和可靠性。下面针对二次函数情形讨论共轭梯度法，我们先给出共轭梯度法的推导。设

14、(2.2.1)其中是对称正定矩阵，是向量，是实数。的梯度为 (2.2.2)令 (2.2.3)则 (2.2.4)由精确线性搜索性质， (2.2.5)令 (2.2.6)选择，使得. (2.2.7)对（2.2.6）两边同乘以，得. (2.2.8)由共轭方向法基本定理，。利用（2.2.3）和（2.2.6），可知, . (2.2.9)又令, (2.2.10)选择和，使得，。从而有,. (2.2.11)一般地，在第次迭代，令, (2.2.12)选择，使得，。也假定, , , (2.2.13)对(2.2.12)左乘，则, . (2.2.14)由(2.2.13)，, , ,故得,和. (2.2.15)因此，共

15、轭梯度法的公式为, (2.2.16)其中，在二次函数情形，. (2.2.17) 一般地，由精确线性搜索得到，当然也可以由非线性搜索得到， (2.2.18) (Crowder-Wolfe公式) (2.2.19).(Fletcher-Reeves公式) (2.2.20)另两个常用的公式为, (Polak-Ribiere-Polyak公式) (2.2.21).(Dixon公式) (2.2.22)由上面的公式可见，共轭梯度法具有二次终止性（即对于二次函数，算法在有限步终止），所以共轭梯度法是一个很吸引人的方法。共轭梯度法步骤如下：算法2.2.1(共轭梯度法)步0 给定迭代精度和初始点.计算.令.步1

16、若,停算,输出.步2 计算搜索方向:其中当时,确定.步3 利用精确(或非精确)线搜索方法确定搜索步长.步4 令,并计算.步5 令,转步1.下面证明算法2.2.1的收敛性定理。定理 2.2.3 设是由算法 2.2.1 产生的序列, 假定函数一阶连续可微且水平集是有界的。那么算法 2.2.1 或者有限步终止, 或者。证：不是一般性，不放假设是无穷序列，此时有，因 故有，即是下降方向，从而由精度线性搜索规则可知，是单调下降的，故，于是是有界的，因为必有聚点，即存在子列收敛到，由的连续性，有.类似地，也是有界序列，故存在子列收敛到，这里是无穷子序列，于是可得.故有. (2.2.23)下面用反证法证明.

17、如果不然，即，则对于充分小，有.注意到，对任意的，有.对于，令对上式去极限得，这与(2.2.23)式相矛盾，从而证明了. 证毕. 若在算法2.2.1中采用非精度搜索确定的补步长因子，比如Wolfe准则和Armijo 准则，则利用一般下降类算法的全局收敛性定理，可得到非精确搜索下的共轭梯度算法的收敛性定理。定理 2.2.4 设是由算法2.2.1利用Wolfe准则产生的序列，假定函数一阶连续可微且有下界，其梯度函数在上Lipschitz连续，即存在常数，使得, .若选取的搜索方向与的夹角满足条件, .那么算法2.2.1或者有限步终止，或者。证: 不失一般性,不妨假设是无穷序列.由Lipschitz

18、及连续条件和Wolfe准则得 , 即.于是利用上式及Wolfe准则可得 .注意到是有下界的,由上式不难推得,这蕴含了当时,有.证毕. 2.3 Armijo 准则Armijo 准则是指: 给定,令步长因子. 其中 是满足下列不等式的最小非负整数: (2.3.1)可以证明, 若是连续可微的且满足, 则Armijo 准则是有限终止的, 即存在正数, 使得对于充分大的正整数, (2.3.1) 式成立. 也就是说，目标函数的下降要与步长和下降方向成一定的比例。为了程序实现的方便, 我们将Armijo 准则写成下列详细的算法步骤。算法 2.3.1 (Armijo准则)步0 给定.令.步1 若不等式成立，置

19、，停算，否则，转步2.步2 令，转步1.3、数值实验3.1 代码实现在共轭梯度法的实际使用中，通常在迭代步或步之后，重新取负梯度方向作为搜索方向，我们称之为再开始共轭梯度法。这是因为对于一般非二次函数而言，步迭代后共轭梯度法产生的搜索方向往往不再具有共轭性。而对于大规模问题，常常每 (或) 步就进行再开始。此外，当搜索方向不是下降方向时，也插入负梯度方向作为搜索方向。基于Armijo 非精确线性搜索的再开始FR共轭梯度法的Matlab程序如下：(分别新建 frcg.M , fun.M , gfun.M 三个M文件)function x,val,k=frcg(fun,gfun,x0)% 功能:

20、用FR共轭梯度法求解无约束问题: min f(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; else beta=(g'*g)/(g0'*g0

21、); d=-g+beta*d0; gd=g'*d; if(gd>=0.0) d=-g; end end if(norm(g)<epsilon), break; end %检验终止条件 m=0; mk=0; while(m<20) %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;val=feval(fu

22、n,x);3.2 算法测试我们通过求解两个无约束优化问题来验证算法的稳定性和准确性。问题一：求解无约束优化问题，该问题的有精确解。问题二：求解无约束优化问题，该问题的有精确解。解：利用程序3.1求解以上两个问题，终止准则为，分别修改目标函数和梯度如下：fun.M文件function f=fun(x) %目标函数f=(3*x(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.M文件function gf=gfun(x) %目标函数的梯度函数gf=3*x(1)-x(2)-2,x(2)-x

23、(1)' %问题一梯度函数%gf=400*x(1)*(x(1)2-x(2)+2*(x(1)-1), -200*(x(1)2-x(2)' %问题二梯度函数分别取不同的起始点的数值结果如下表：表3.1 问题一 FR共轭梯度法的数值结果初始点()迭代次数（）目标函数值（）最优解（）12-1.000011-1.000012-1.000015-1.000013-1.0000表3.2 问题二 FR共轭梯度法的数值结果初始点()迭代次数（）目标函数值（）最优解（）281.8462e-007131.4796e-007153.2749e-007224.0962e-008183.5854e-007

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

25、代公式. 设的Hesse 阵连续, 截取其在处的泰勒展开式的前三项得,其中,.求二次函数的稳定点，得.若非奇异，那么解上面的线性方程组即得牛顿法的迭代公式.在迭代公式中每步迭代需求Hesse阵的逆，在实际计算中可通过先解得，然后令来避免求逆。这样，可以写出基本牛顿法的步骤如下：算法 4.1.1（基本牛顿法）步0 给定终止误差,初始点.令.步1 计算.若,停算，输出.步2 计算,并求解线性方程组得:.步3 令,转第一步.牛顿法最突出的优点是收敛速度快，具有局部二阶收敛性。4.2 算法实现根据牛顿算法，编写matlab程序，求解无约束优化问题，代码如下：function x,val,k=grad(

26、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(k<maxk) g=feral(gfun,x0); %计算梯度 d=-g; %计算搜索方向 if(norm(d)<epsilon), break; end m=0; mk=0; while(m<20) %Armijo搜索 if(feral(fun,x0

27、+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 问题一 牛顿法的数值结果初始点()迭代次数（）目标函数值（）最优解（）23-1.000023-1.000025-1.000037-1.000025-1.0000问题二：表4.2 问题二 牛顿法的数值结果初始点()迭代次数（）目标函数值（）最优解（）3

28、82.8220e-009281.4429e-011371.3597e-009392.1601e-009371.4698e-0094.4算法比较通过求解问题一和问题二，由上表可以看出, 共轭梯度法的收敛速度是比较令人满意的，在相同初始点处开始求解，使用牛顿法所需要的迭代次数共轭梯度法的迭代次数的两倍。虽然在算法设计上比较相似，但是微小的改进，使得共轭梯度法无论是准确性上还是效率上都优于牛顿法。5、总结5.1 总结概括求解最优问题是一个艰难而具有挑战性的过程，最优化方法是近几十年形成的一门运用研究各种系统的优化途径及方案，为决策者提供科学决策的依据的学科，它涵盖了无约束最优化问题、凸集与凸函数、等式约束最优化问题和不等式约束最优化问题等知识点。本次课程设计，我们小组成员通过老师的点拨以及激