最优化实验报告最优实验报告.doc

姓 名： 周飞飞（201210020231） 张琳婧（201210020228） 班 级： 信息与计算科学2班 指导教师：刘陶文 2014年11月27日《数值最优化算法与理论》课程实验报告 课程名称 数值最优化算法与理论 班级 信息与计算科学2班 小组成员 周飞飞（201210020231） 张琳婧（201210020228） 实验课题 拟Newton法（BFGS算法）及FR共轭梯度法求解无约束问题 实验目的 通过上机实验掌握最优化的实用算法的结构及性能，并用这些算法解决实际的最优化问题，掌握一些实用的编程技巧。 实验要求 选用你喜欢的无约束优化的某种梯度法 (最速下降法，Newton法，拟牛顿法，共轭梯度法)通过编程，上机实验对所提供的测试问题进行测试、运行，然后提供实验报告。在实验报告中指出你选用的算法、参数设置、终止准则、线性搜索以及实验结果，附加你的实验心得。 实验内容 使用非精确Wolf-Powell线性搜索实现拟牛顿法（BFGS算法）及FR共轭梯度法求解无约束问题，并通过Matlab软件实现算法，观察分析实验过程，对比实验结果来进一步理解两种方法的原理及优点与缺陷。 目 录 实验原理 1 2、实验内容 4 3、实验结果与分析 8 4、实验心得 12 附录 13 实验原理 无约束问题 下降算法是求解无约束优化问题的一类最基本的算法。 其一般步骤为：（已知近似最优解） 首先，计算下降方向满足： 然后计算步长满足： 计算新的近似最优解： 这次实验所运用的拟牛顿法及FR共轭梯度法主要是在下降算法的基础上，求解下降方向的方法上有所不同。 拟牛顿法 （1）拟牛顿法的简述 拟牛顿法(Quasi-Newton Methods)是求解非线性优化问题最有效的方法之一，于20世纪50年代由美国Argonne国家实验室的物理学家W. C. Davidon所提出来。Davidon设计的这种算法在当时看来是非线性优化领域最具创造性的发明之一。不久R. Fletcher和M. J. D. Powell证实了这种新的算法远比其他方法快速和可靠，使得非线性优化这门学科在一夜之间突飞猛进。 拟牛顿法和最速下降法(Steepest Descent Methods)一样只要求每一步迭代时知道目标函数的梯度。通过测量梯度的变化，构造一个目标函数的模型使之足以产生超线性收敛性。这类方法大大优于最速下降法，尤其对于困难的问题。另外，因为拟牛顿法不需要二阶导数的信息，所以有时比牛顿法(Newtons Method)更为有效。如今，优化软件中包含了大量的拟牛顿算法用来解决无约束，约束，和大规模的优化问题。 拟牛顿法的思想 拟牛顿法是对牛顿法的一种改善 保持其优点：快速收敛性 克服其缺陷：需计算Hessian矩阵且要求其正定 方法：构造对称正定矩阵或使其满足 计算搜索方向： 构造的要求如下： 拟牛顿法的BFGS算法 BFGS修正公式： 该公式由：Broyden-Fletcher-Goldfarb-Shanno 提出，是迄今为止最好的拟牛顿修正公式。 BFGS算法： 非线性共轭梯度法（FR算法） （1）共轭梯度法的简述 共轭梯度法是介于最速下降法与牛顿法之间的一个方法，它仅需利用一阶导数信息，但克服了最速下降法收敛慢的缺点，又避免了牛顿法需要存储和计算Hessian矩阵并求逆的缺点，共轭梯度法不仅是解决大型线性方程组最有用的方法之一，也是解大型非线性最优化最有效的算法之一。 共轭梯度法最早是由Hestenes和Stiefle（1952）提出来的，用于解正定系数矩阵的线性方程组，在这个基础上，Fletcher和Reeves（1964）首先提出了解非线性最优化问题的共轭梯度法。由于共轭梯度法不需要矩阵存储，且有较快的收敛速度和二次终止性等优点，现在共轭梯度法已经广泛地应用与实际问题中。 共轭梯度法是一个典型的共轭方向法，它的每一个搜索方向是互相共轭的，而这些搜索方向d仅仅是负梯度方向与上一次迭代的搜索方向的组合，因此，存储量少，计算方便 。 共轭梯度法的思想 Fletcher-Reeves共轭梯度法，简称FR法。 共轭梯度法的基本思想是把共轭性与最速下降方法相结合，利用已知点处的梯度构造一组共轭方向，并沿这组方向进行搜素，求出目标函数的极小点。根据共轭方向基本性质，这种方法具有二次终止性。 给定初始点，取初始搜索方向，在后面的迭代中取负梯度方向和前一搜索方向的线性组合作为搜索方向即，其中是待定参数，适当选取