《最优化方法》
课程设计
题目：共轭梯度法算法分析与实现
院系：数学与计算科学学院
专业：数学与应用数学
*名：***
学号：**********
指导教师：***
日期：2015 年12 月30 日
在各种优化算法中，共轭梯度法是非常重要的一种。本文主要介绍的共轭梯度法是介于最速下降法与牛顿法之间的一种无约束优化算法，它具有超线性收敛速度, 而且算法结构简单, 容易编程实现。
在本次实验中,我们首先分析共轭方向法、对该算法进行分析，运用基于共轭方向的一种算法—共轭梯度法进行无约束优化问题的求解。无约束最优化方法的核心问题是选择搜索方向。共轭梯度法的基本思想是把共轭性与最速下降方法相结合，利用已知点处的梯度构造一组共轭方向，并沿这组方向进行搜索，求出目标函数的极小点。根据共轭方向的基本性质，这种方法具有二次终止性。再结合该算法编写matlab程序，求解无约束优化问题，再结合牛顿算法的理论知识，编写matlab程序，求解相同的无约束优化问题，进行比较分析，得出共轭梯度法和牛顿法的不同之处以及共轭梯度法的优缺点。
共轭梯度法仅需利用一阶导数信息，避免了牛顿法需要存储和计算Hesse矩阵并求逆的缺点，共轭梯度法不仅是解决大型线性方程组最有用的方法之一，也是解大型非线性最优化最有效的算法之一。共轭梯度法是一个典型的共轭方向法，它的每一个搜索方向是互相共轭的，而这些搜索方向仅仅是负梯度方向与上一次迭代的搜索方向的组合，因此，存储量少，计算方便。
关键词：共轭梯度法；超线性收敛；牛顿法；无约束优化
In 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 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 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 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 unconstrained optimization problems, combined with Newton’s 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 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 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 direction of the portfolio, therefore, storage less computational complexity.
Key words: Conjugate gradient method; Superlinear convergence; Newton method Unconstrained optimization
