共轭梯度法
最速下降法
1.最速下降方向
函数f(x)在点x处沿方向d的变化率可用方向导数来表示。对于可微函数，方向导数等于梯度与方向的内积，即：
Df(x;d) = ▽f(x)T d,
因此，求函数f(x)在点x处的下降最快的方向，可归结为求解下列非线性规划：
min ▽f(x)T d
s.t. ||d|| ≤ 1
当 d = -▽f(x) / ||▽f(x)||
时等号成立。因此，在点x处沿上式所定义的方向变化率最小，即负梯度方向为最速下降方向。
2.最速下降算法
最速下降法的迭代公式是
x(k+1) = x(k) + λk d(k) ,
其中d(k)是从x(k)出发的搜索方向，这里取在x(k)处的最速下降方向，即
d = -▽f(x(k)).
λk是从x(k)出发沿方向d(k)进行一维搜索的步长，即λk满足
f(x(k) + λk d(k)) = min f(x(k)+λd(k)) (λ≥0).
计算步骤如下：
(1)给定初点x(1) ∈ R n，允许误差ε> 0，置k = 1。
(2)计算搜索方向d = -▽f(x(k))。
(3)若||d(k)|| ≤ε，则停止计算；否则，从x(k)出发，沿d(k)进行一维搜索，求λk，使
f(x(k) + λk d(k)) = min f(x(k)+λd(k)) (λ≥0).
(4)令x(k+1) = x(k) + λk d(k)，置k = k + 1，转步骤(2)。
共轭梯度法
1.共轭方向
无约束问题最优化方法的核心问题是选择搜索方向。
以正定二次函数为例，来观察两个方向关于矩阵Ａ共轭的几何意义。
设有二次函数：
f(x) = 1/2 (x - x*)T A(x - x*) ,
其中A是n×n对称正定矩阵，x*是一个定点，函数f(x)的等值面
1/2 (x - x*)T A(x - x*) = c
是以x*为中心的椭球面，由于
▽f(x*) = A(x - x*) = 0，
A正定，因此x*是f(x)的极小点。
设x(1)是在某个等值面上的一点，该等值面在点x(1)处的法向量
▽f(x(1)) = A(x(1) - x*)。
又设d(1)是这个等值面在d(1)处的一个切向量。记作
d(2) = x* - x(1)。
自然，d(1)与▽f(x(1))正交，即d(1)T▽f(x(1)) = 0，因此有
d(1)T Ad(2) = 0，
即等值面上一点处的切向量与由这一点指向极小点的向量关于A共轭。
由此可知，极小化式所定义的二次函数，若依次沿着d(1)和d(2)进行一维搜索，则经两次迭代必达到极小点。
1.共轭梯度法
共轭梯度法最初由Hesteness和Stiefel于1952年为求解线性方程组而提出的。后来，人们把这种方法用于求解无约束最优化问题，使之成为一种重要的最优化方法。
Fletcher-Reeves共轭梯度法，简称FR法。
共轭梯度法的基本思想是把共轭性与最速下降方法相结合，利用已知点处的梯度构造一组共轭方向，并沿这组方向进行搜素，求出目标函数的极小点。根据共轭方向基本性质，这种方法具有二次终止性。
对于二次凸函数的共轭梯度法：
min f(x) = 1/2 x T Ax + b T x + c,
其中x∈ R n，A是对称正定矩阵，c是常数。
具体求解方法如下：
首先，任意给定一个初始点x(1)，计算出目标函数f(x)在这点的梯度，若||g1|| = 0，则停止计算；否则，令
d(1) = -▽f(x(1)) = -g1。
沿方向d(1)搜索，得到点x(2)。计算在x(2)处的梯度，若||g2|| ≠ 0，则利用-g2和d(1)构造第2个搜索方向d(2)，在沿d(2)搜索。
一般地，若已知点x(k)和搜索方向d(k)，则从x(k)出发，沿d(k)进行搜索，得到
x(k+1) = x(k) + λk d(k) ,
其中步长λk满足
f(x(k) + λk d(k)) = min f(x(k)+λd(k))。
此时可求出λk的显示表达
计算f(x)在x(k+1)处的梯度。若||g k+1|| = 0，则停止计算；否则，用-g k+1和d(k)构造下一个搜索方向d(k+1)，并使d(k+1)和d(k)关于A共轭。按此设想，令
d(k+1) = -g k+1 + βk d(k)，
上式两端左乘d(k)T A，并令
d(k)T Ad(k+1) = -d(k)T Ag k+1 + βk d(k)T Ad(k) = 0，
由此得到
βk = d(k)T Ag k+1 / d(k)T Ad(k)。
再从x(k+1)出发，沿方向d(k+1)搜索。
在FR法中，初始搜索方向必须取最速下降方向，这一点决不可忽视。因子βk可以简化为：βk = ||g k+1||2 / ||g k||2。
3.非线性共轭梯度
当目标函数是高于二次的连续函数(即目标函数的梯度存在)时，其对应的解方程是非线性方程，非线性问题的目标函数可能存在局部极值，并且破坏了二次截止性，共轭梯度法需要在两个方面加以改进后，仍然可以用于实际的反演计算，但共轭梯度法不能确保收敛到全局极值。
(1)首先是共轭梯度法不能在n维空间内依靠n步搜索到达极值点，需要重启共轭梯度法，继续迭代，以完成搜索极值点的工作。
(2)在目标函数复杂，在计算时，由于需要局部线性化，需计算Hessian矩阵A，且计算工作量比较大，矩阵A也有可能是病态的。Fletcher和Reeves的方案最为常用，抛弃了矩阵A的计算，具体形式如下：
式中g k-1和g k分别为第k-1和第k次搜索是计算出来的目标函数的梯度。
第五章共轭梯度法
大家已经看到，在使用SOR方法求解线性方程组时，需要确定松驰因子，只有系数矩阵具有较好的性质时，才有可能找到最佳松驰因子，而且计算时还需要求得对应的Jacobi矩阵B的谱半径，这常常是非常困难的。
这一章，我们介绍一种不需要确定任何参数的求解对称正定线性方程组的方法——共轭梯度法（或简称CG法）。它是50年代初期由Hestenes和Stiefel 首先提出的，近20年来有关的研究得到了前所未有的发展，目前有关的方法和
理论已经相当成熟，并且已经成为求解大型稀疏线性方程组最受欢迎的一类方法。
共轭梯度法可由多种途径引入，这里我们将采用较为直观的最优化问题来引入。为此，我们先来介绍最速下降法。
5.1 最速下降法
考虑线性方程组
(5.1.
1)
的求解问题。其中是给定的阶对称正定矩阵，是给定的维向量，是待求的维向量。为此，我们定义二次泛函
(5.1.2)
定理5.1.1设对称正定，求解方程组等价于求二次泛函的极小点。
证明直接计算可得
令，则有
若在某点处达到极小，则必有，从而有，即是方程组的解。
反之，若是方程组的解，即于是对任一向量有
注意到A的正定性，则，因此，即是泛函的极小点。
定理证毕
这样，求解线性方程组的问题就转化为求二次泛函的极小点的问题。求二次函数的极小值问题，通常的做法就好象盲人下山那样，先任意给定一个初始向量，确定一个下山的方向，沿着经过点而方向为的直线
找一个点
使得对所有实数有
也就是说，在这条直线上，使达到极小。然后从出发，再确定一个
下山的方向，沿直线再找一个使得在点达到极小，即
如此等等。于是得到一串
和，
我们称为搜索方向，为步长。一般情况下是，先在点找下山方向，再在直线上确定步长使
，
最后求出. 对不同的确定搜索方向和步长的方法，就给出各种不同的算法。
我们先考虑如何确定步长。设从出发，已经选定了下山方向为。我
们现在的任务是，在直线上确定使得在上达到极小。为此，令
其中由初等微分学的理论知，由方程
所确定的即为所求的步长，即
. (
5.1.3)
步长确定以后，即可算法
.
那么是否小于呢？因为
因此，只要，就有
再考虑如何确定下山方向，我们知道增加最快的方向是梯度方向，因此，负梯度方向应该是减小最快的方向，于是最简单而直观的做法是选取
为负梯度方向，即这样便得到了如下算法：
算法5.1.1 （解对称正定方程组：最速下降法）
对于最速下降法有如下的收敛性定理。
定理5.1.2设的特征值为，则由上述算产生的序列
满足
，
其中
为了证明这一定理，我们先证一个引理。
引理5.1.1设的特征值为，是的一个实系数多项式，则
证明设是的对应于的特征向量所构成的的一组标准正交基，则对应任意的的有，从而有
于是
引理证毕定理5.1.2的证明由满足
，
并注意到
（5.1.4）由(5.1.4)得
于是有
（5.1.5）对任意的成立。记，应用引理5.1.1，从(5.1.5)可得
(5.1.6)
对一切成立，再利用Chebyshev极小极大特征定理知，使取极小的充分必要条件是在区间上至少含有2个轮流为正负的偏差点。由于的线性性知，的交错点组恰好含有两个点，而且为和. 即
，于是得到，从而
. (5.1
.7) 将(5.1.7)代入（5.1.6）即得
.
定理证明定理5.1.2表明，从任一初始向量出发，由最速下降法产生的点列总是收敛到方程组(5.1.1)的解，其收敛的快慢由的大小来决定。
虽然最速下降法简单易用，又可以充分利用的稀疏性，但由于当时收敛速度变得非常之慢，因此很少用于实际计算。然而它提示了一种重要的思想，
开辟了一条全新的求解线性方程组的途径。例如把上述方法稍加改进，就可得到著名的共轭梯度法。
5.2 共轭梯度法及其基本性质
5.2.1 预备知识
定义1 设是对称正定矩阵。称是A-共轭的，是指
性质1 设有是彼此共轭的维向量，即
则一定是线性无关的。
［证明］若有一组数满足
则对一切一定有
注意到，由此得出：即所有的＝０．因此，
是线性无关的．
性质２设向量是线性无关的向量组，则可通过它们的线性组合得出一组向量，而是两两共轭的．
［证明］我们用构造法来证实上面的结论．
Ｓ０：取；
Ｓ１：令，取．
……
Ｓm：令
取
容易验证：符合性质２的要求．
性质３设是两两Ａ－共轭的，是任意指定的向量，那么从出发，逐次沿方向搜索求的极小值，所得序列，满足：
．
［证明］由下山算法可知，从出发，沿方向搜索，获得
从而
性质４设是两两Ａ共轭的，则从任意指定的出发，依次沿搜索，所得序列满足：
（１）
（２），其中是方程组(5.1.1)的解．
［证明］（１）是性质３的直接推论，显然成立．
（２）由于是两两Ａ共轭的，故是线性无关的．所以对于向量可用线性表出，即存在一组数使
由于及，得出
，
于是，再由得出
于是，与得出一样地，我们可以陆续得出：
对比和的表达式可知，
证明完毕
性质４是性质３的直接推论．但它给出了一种求（５.１.１）的算法，这种算法称之为共轭方向法．结合性质２，我们可以得到如下的性质５．
性质５设是上的一组线性无关的向量，则从任意指定的出发，按以下迭代产生的序列：
Ｓ１：取，，；
Ｓ２：计算，取；
计算，得出；
如此进行下去，直到第n步：
Ｓn：计算取
计算，得出．
显然：
根据性质４可知，不论采用什么方法，只要能够构造个两两Ａ共轭的向量作为搜索方向，从任一初始向量出发，依次沿两两Ａ共轭的方向进行搜索，经
步迭代后，便可得到正定方程组的解．
5.2.2 共轭梯度法
算法步骤如下：
［预置步］任意，计算，并令取：指定算法终止常数，置，进入主步；
［主步］（１）如果，终止算法，输出；否则下行；
（２）计算：
（３）计算：
（４）置，转入（１）．
定理５.2.1 由共轭梯度法得到的向量组和具有如下性质：
（１）
（２）
（３）
（４），其中
（5.2.1）通常称之为Krylov子空间．
［证明］用归纳法．当时，因为
，
因此定理的结论成立．现在假设定理的结论对成立，我们来证明其对也成立．
利用等式及归纳假设，有
又由于
，
故定理的结论（１）对成立．
利用归纳假定有
而由（１）所证知，与上述子空间正交，从而有定理的结论（２）对
也成立．
利用等式
和，
并利用归纳法假定和（２）所证之结论，就有
．成立；而由的定义得
这样，定理的结论（３）对也成立．
由归纳法假定知
进而
于是
再注意到（２）和（３）所证的结论表明，向量组和
都是线性无关的，因此定理的结论（４）对同样成立．
定理证毕定理5.2.1表明，向量和分别是Krylov子空间的正交基和共轭正交基．由此可见，共轭梯度法最多步便可得到方程组的解．因此，理论上来讲，共轭梯度法是直接法．
定理5.2.2 用共轭梯度法计算得到的近似解满足
（5.2.２）或
（5.2.３）
其中，是方程组的解，是由（5.2.1）所定义的Krylov子空间．
证明注意到：，则（5.2.2）和(5.2.3)是等价的，因此我们下面只证明(5.2.3)成立．
假定共轭梯度法计算到步出现，那么有
此外，对计算过程中的任一步，有
设是属于的任一向量，则由定理5.2.1的（４）知，可以表示为
，
于是
而
，
再利用定理5.2.1的（３）就可以推出
于是定理得证．
定理证毕由定理5.2.1，我们容易得出
由此可得
(5.2.4)
另外，从理论上讲，该迭代法经次迭代，便能得到精确解．但考虑到计算误差，可以作为无限迭代算法进行计算，直到为止．
从而，我们得到如下实用的共轭梯度算法：
［预置步］任意，计算，并令取：指定算法终止常数，置，进入主步；
［主步］（１）计算：，
（２）如果，转入（3）．否则，终止算法，输出计算结果
（３）计算：
（４）置，转入（1）
注：在算法［主步］中，引入变量，及，可以简化计算。
结合程序设计的特点，共轭梯度法可改为如下实用形式：
算法５·３·１（解对称正定方程组：实用共轭梯度法）
；
while and
if
else
end
end
共轭梯度法作为一种实用的迭代法，它主要有下面的优点：
算法中，系数矩阵Ａ的作用仅仅是用来由已知向量产生向量
，这不仅可充分利用Ａ的稀疏性，而且对某些提供矩阵Ａ较为困难而由已知向量产生向量又十分方便的应用问题
是很有益的；
不需要预先估计任何参数就可以计算，这一点不像ＳＯＲ等；
每次迭代所需的计算，主要是向量之间的运算，便于并行化。
5.2.3 收敛性分析
将共轭梯度法作为一种迭代法，它的收敛性怎样呢？这是本节下面主要讨论的问题：
定理５.2.3 如果而且，则共轭梯度法至多迭代步即可得到方程组的精确解。
证明注意到蕴含着子空间
的维数不会超过，由定理５.2.1即知定理的结论成立。
定理证毕
定理5·2·3表明，若线性方程组（5·1·1）的系数矩阵与单位相关一个秩的矩阵，而且很小时，则共轭梯度法将会收敛得很快。
定理5·2·4 用共轭梯度法求得的有如下的误差估计
（5·2·5）
最优化课程设计--共轭梯度法算法分析与实现
最优化课程设计--共轭梯度法算法分析与实现(设计程序) 题目共轭梯度法算法分析与实现 班级 / 学号 14140101/2011041401011 学生姓名黄中武指导教师王吉波王微微 课程设计任务书 课程名称最优化方法课程设计院(系) 理学院专业信息与计算科学 课程设计题目共轭梯度法算法分析与实现课程设计时间: 2014 年 6月 16日至 2014 年 6月 27日 课程设计的要求及内容: [要求] 1. 学习态度要认真，要积极参与课程设计，锻炼独立思考能力; 2. 严格遵守上机时间安排; 3. 按照MATLAB编程训练的任务要求来编写程序; 4. 根据任务书来完成课程设计论文; 5. 报告书写格式要求按照沈阳航空航天大学“课程设计报告撰写规范”; 6. 报告上交时间:课程设计结束时上交报告; 7. 严禁抄袭行为，一旦发现，课程设计成绩为不及格。 一、运用共轭梯度法求解无约束最优化问题 要求:1)了解求解无约束最优化问题的共轭梯度法; 2)绘出程序流程图; 3)编写求解无约束最优化问题的共轭梯度法MATLAB程序; 4)利用编写文件求解某无约束最优化问题;
5)给出程序注释。 指导教师年月日 负责教师年月日 学生签字年月日 沈阳航空航天大学 课程设计成绩评定单 课程名称最优化理论与算法课程设计院(系) 理学院专业信息与计算科学课程设计题目共轭梯度法算法分析与实现学号 2011041401011 姓名黄中武指导教师评语: 课程设计成绩 指导教师签字 年月日 最优化方法课程设计沈阳航空航天大学课程设计用纸目录 目录 一、正 文 (1) 二、总结 ............................................................... 8 参考文 献 ............................................................... 9 附录 .. (10) 第 I 页 最优化方法课程设计沈阳航空航天大学课程设计用纸正文 一、正文 一无约束最优化问题的共轭梯度法
16梯度法和共轭梯度法基本原理和特点
16梯度法和共轭梯度法基本原理和特点？ 梯度法又称最速下降法，基本原理是在迭代点附近采用使目标函数值下降最快的负梯度方向作为搜索方向， 求目标函数的极小值，特 点；迭代计算简单，只需求一阶偏导数，所占的存储单 元少，对初始点的要求不 高，在接近极小点位置时收敛速度很慢，共轭的特点为 在梯度法靠近极值点收敛速度放慢时，它可以构造共轭方向使其收敛速度加快， 迭代计算比较简单，效果 好，在每一步迭代过程中都要构造共轭的、方向，比较繁琐。 17迭代终止准则有哪三种？ 1）当设计变量在相邻两点之间的移动距离充分小时，可用相邻两点的矢量差的模作为终止的判据， 2）当相邻两点目标函数值之差达到充分小时，可 用两次迭代的目标函数之 差作为终止判据。 3）当迭代点逼近极值点时，目标函数在该点的梯度已达到充分小时，可用梯度的模作为
终止判据。 18 .无约束设计法，1）powell法，它是在下降迭代过运算中只需计算和比较目标函数值的大小，不需计算偏导数的方法，是较好的一种直接搜索 算法。 2）梯度法，又称最速下降法，它是采用使目标 函数值下降最快的负梯度方向作为搜索方向来求目标函数的极小值。 3）共轭梯度法，又称FR法，是利用目标函数的梯度确定共轭方向，使得计算简便而效 果好，只需利用相邻两点的梯度就可以构造一个共轭方向，这种方式产生共轭方 向并进行迭代的算法称为 共轭梯度法。 4）变尺度法，又称DFP法，为了得到既有快速收敛的性质，又能避免计算二阶导数矩阵及逆矩阵，减少计算工作量。迭代公式X=X+aS, 19有约束设计法？ 1）复合形法，在可行域中选取k个设计点作为
初始复合形的顶点，然后比较复合形个各项 目标函数值的大小，其中目标函数值最大的点为坏点，以坏点之外其余各点的中心为映 射中心，寻坏点的映射点，以映射点替换坏点，并与原复合 型除坏点之外其余各点构成就k 顶点的新的复合型，这样反复迭代直到达到精度找到最优点， 2）简约梯度法，用来解决线性约束非线性规划问题。3）罚函数法，是把一个有约束的问 题转化为一系列无约束的问 题求解，逐渐逼近最优值。 . 可靠性工程包括的三个方面？ 1可靠性设计，包括设计方面的分析，对比评价，必要时也包 括可靠性实验，生产制造中的质量控制设计 及使用维修规程的设计。 2可靠性分析，主要是失效分析，也包括故障分析 3可靠性数学， 这是数理统计方法在开展 可靠性工作中发展起来的 数学分支。 常用的可靠
共轭梯度法
共轭梯度法 1.算法思想： 共轭梯度法是利用目标函数梯度逐步产生共轭方向作为线搜索方向的方法，每次搜索方向都是在目标函数梯度的共轭方向，搜索步长通过一维极值算法确定。 2.算法步骤： 用共轭梯度法求无约束多维极值问题min (),n f x x R ∈的算法步骤如下： （1） 给定初始点(0)x ，及精度0ε>； （2） 若 (0)()f x ε ?≤，停止，极小值点为(0)x ，否则转步骤（3）； （3） 取(0)(0)()p f x =-?，且置0k =； （4） 用一维搜索法求k t ，使得()()()()()0 ()min k k k k k t f x t p f x tp ≥+=+，令，(1)()()k k k k x x t p +=+，转步骤5； （5） 若 (1)()k f x ε +?≤，停止，极小值点为(1)k x +，否则转步骤（6）； （6） 若1k n +=，令(0)()n x x =，转步骤（3），否则转步骤（7）； （7） 令(1)(1)()()k k k k p f x p λ++=-?+，2(1)2 () () () k k k f x f x λ+?=?，置1k k =+，转 步骤（4）。 3.算法源程序： #include
#define N 10 #define eps pow(10,-6) double f(double x[],double p[],double t) { double s; s=pow(x[0]+t*p[0],2)+25*pow(x[1]+t*p[1],2); return s; } /*以下是进退法搜索区间源程序*/ void sb(double *a,double *b,double x[],double p[]) { double t0,t1,t,h,alpha,f0,f1; int k=0; t0=2.5; /*初始值*/ h=1; /*初始步长*/ alpha=2; /*加步系数*/ f0=f(x,p,t0); t1=t0+h; f1=f(x,p,t1); while(1) {
共轭梯度法C语言(西安交大)
#include printf("\n"); printf("input the Maxtr X\n"); /*给X0输入一个初始向量*/ for(i=0;i 高等数值计算实践题目一 1. 实践目的 本次计算实践主要是在掌握共轭梯度法，Lanczos 算法与MINRES 算法的基础上，进一步探讨这3种算法的数值性质，主要研究特征值特征向量对算法收敛性的影响。 2. 实践过程 （一）生成矩阵 （1）作5个100阶对角阵i D 如下： 1D 对角元：1,1,...,20,1+0.1(-20),21,...,100j j d j d j j ==== 2D 对角元：1,1,...,20,1+(-20),21,...,100j j d j d j j ==== 3D 对角元：,1,...,80,81,81,...,100j j d j j d j ==== 4D 对角元：,1,...,40,41,41,...,60,41+(60),61,...,100j j j d j j d j d j j =====-= 5D 对角元：,1,...,100j d j j == 记i D 的最大模特征值和最小模特征值分别为1i λ和i n λ，则i D 特征值分布有如下特点： 1D 的特征值有较多接近于i n λ，并且1/i i n λλ较小， 2D 的特征值有较多接近于i n λ，并且1/i i n λλ较大， 3D 的特征值有较多接近于1i λ，并且1/i i n λλ较大， 4D 的特征值有较多接近于中间模特征值，并且1/i i n λλ较大， 5D 的特征值均匀分布，并且1/i i n λλ较大 （2）随机生成10个100阶矩阵j M ： (100(100))j M fix rand = 并作它们的QR 分解，得j Q 和j R ，这样可得50个对称的矩阵T ij j i j A Q DQ =，其中i D 的对角元就是ij A 的特征值，若它们都大于0，则ij A 正定，j Q 的列就是相应的特征向量。结合（1）可知，ij A 都是对称正定阵。 最优化方法第四次作业 题目：利用FR-共轭梯度法求解无约束优化问题222 12122min ()44412x R f x x x x x x ∈=+--。初始点(0)(0.5,1).T x =- () ()T k k T k k k k k k k g g g g k d g k g d 111110.0,;0,-----=???≥+-=-=ββ 一、程序 function [x,val,k]=frcg(fun,gfun,x0) %功能：用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 while (m<20) %用Armijo 搜索求步长 if (feval(fun,x0+rho^m*d) 编号:_ 09 《最优化方法》 课程设计 题目：共轭梯度算法分析与实现 院系：数学与计算科学学院 专业：数学与应用数学 姓名学号： 指导教师： 日期：2013 年12 月23 日 摘要 在最优化计算中，共轭梯度法是非常重要的一种方法。共轭梯度法是一种改进的最速下降法，介于最速下降法与牛顿法之间的一种无约束优化算法,是为求解目标函数为二次函数的问题而设计的一类算法。它利用目标函数的梯度逐步产生共轭方向并将其作为搜索方向的方法，收敛速度快。共轭梯度法仅需利用一阶导数信息，避免了牛顿法需要存储和计算Hesse矩阵并求逆的缺点，具有二次终止性。 关键词：共轭梯度法；牛顿法；二次函数；无约束优化 Abstract In the calculation of optimization method, conjugate gradient method is a very important one. The conjugate gradient method is a unconstrained optimization method between the steepest descent method and Newton method, and sove the objective function for the original quadratic function problems and design for a class of algorithm. Conjugate gradient method using only first derivative information, to avoid the Newton method requires storage and computing the inverse Hesse matrix and shortcomings, this method has the quadratic termination. Keywords: Conjugate gradient method; Newton method;Unconstrained optimization 最优化课程设计--共轭梯度法算法分析与实现 (设计程序) 题目共轭梯度法算法分析与实现 班级 / 学号 14140101/11 学生姓名黄中武指导教师王吉波王微微 课程设计任务书 课程名称最优化方法课程设计院(系) 理学院专业信息与计算科学 课程设计题目共轭梯度法算法分析与实现课程设计时间: 2014 年 6月 16日至2014 年 6月 27日 课程设计的要求及容: [要求] 1. 学习态度要认真，要积极参与课程设计，锻炼独立思考能力; 2. 严格遵守上机时间安排; 3. 按照MATLAB编程训练的任务要求来编写程序; 4. 根据任务书来完成课程设计论文; 5. 报告书写格式要求按照航空航天大学“课程设计报告撰写规”; 6. 报告上交时间:课程设计结束时上交报告; 7. 严禁抄袭行为，一旦发现，课程设计成绩为不及格。 一、运用共轭梯度法求解无约束最优化问题 要求:1)了解求解无约束最优化问题的共轭梯度法; 2)绘出程序流程图; 3)编写求解无约束最优化问题的共轭梯度法MATLAB程序; 4)利用编写文件求解某无约束最优化问题; 5)给出程序注释。 指导教师年月日 负责教师年月日 学生签字年月日 航空航天大学 课程设计成绩评定单 课程名称最优化理论与算法课程设计院(系) 理学院专业信息与计算科学课程设计题目共轭梯度法算法分析与实现学号 11 黄中武指导教师评语: 课程设计成绩 指导教师签字 年月日 最优化方法课程设计航空航天大学课程设计用纸目录 目录 一、正文 ............................................................... 1 二、总 结 ............................................................... 8 参考文 献 ............................................................... 9 附 录 (10) 第 I 页 最优化方法课程设计航空航天大学课程设计用纸正文 一、正文 一无约束最优化问题的共轭梯度法 共轭梯度法最初是由Hesteness和Stiefel于1952年为求解线形方程组而提出的。后来，人们把这种方法用于求解无约束最优化问题，使之成为一种重要的最优化方法。 下面，重点介绍Fletcher-Reeves共轭梯度法，简称FR法。 一、共轭梯度法 共轭梯度法（Conjugate Gradient）是共轭方向法的一种，因为在该方向法中每一个共轭向量都是依靠赖于迭代点处的负梯度而构造出来的，所以称为共轭梯度法。由于此法最先由Fletcher和Reeves （1964）提出了解非线性最优化问题的，因而又称为FR 共轭梯度法。由于共轭梯度法不需要矩阵存储，且有较快的收敛速度和二次终止性等优点，现在共轭梯度法已经广泛地应用于实际问题中。共轭梯度法是一个典型的共轭方向法，它的每一个搜索方向是互相共轭的，而这些搜索方向d仅仅是负梯度方向与上一次迭代的搜索方向的组合，因此，存储量少，计算方便，效果好。 二、共轭梯度法的原理 设有目标函数 f（X）=1/2X T HX+b T X+c 式1 式中，H作为f（X）的二阶导数矩阵，b为常数矢量，b=[b1,b2,b3,...b n]T 在第k次迭代计算中，从点X（k）出发，沿负梯度方向作一维搜索，得 S(K)=-?f（X（k））式2 X(k+1)=X(k)+ɑ(k)S(k) 式3 在式中，ɑ（k）为最优步长。 设与S(k）共轭的下一个方向S(k+1)由点S(k）和点X(k+1)负梯度的线性组 合构，即 S (k+1)=-?f （X （k+1））+β(k)S (k) 式4 根据共轭的条件有 [S (k)]T ?2f （X (k)）S (k+1)=0 式5 把式2和式4带入式5，得 -[?f(X (k))]T ?2f （X (k)）[-?f （X （k+1））+β(k)S (k) ]=0 式6 对于式1，则在点X (k)和点X (k+1)的梯度可写为 ?f(X (k))=HX (k)+b 式7 ?f （X （k+1）)=HX (k+1)+b 式8 把上面两式相减并将式3代入得 ɑ(k)H S (k)=?f （X （k+1）)-?f(X (k)) 式9 将式4和式9两边分别相乘，并代入式5得 -[?f （X （k+1）)+β(k)?f(X (k))]T [?f （X （k+1）)-?f(X (k)]=0 式10 将式10展开，并注意到相邻两点梯度间的正交关系，整理后得 β （k ） =2 2 ||))((||||))1((||k X f k X f ?+? 式11 把式11代入式4和式3，得 S （k+1）=-?f （X (k)）+β （k ） S （k ） X (k+1)=X （k ）+ɑ（k ）S （k ） 由上可见，只要利用相邻两点的梯度就可以构造一个共轭方向。以这种方式产生共轭方向并进行迭代运算的方法，即共轭梯度法。 /*min f(x)=x1^2-2*x1*x2+4*x2^2+x1-3*x2 初值,x=(1,1)*/ //FR共轭梯度法 #include 竭诚为您提供优质文档/双击可除 共轭梯度实验报告 篇一：共轭梯度法实验报告 数值代数实验报告 一、实验名称：用共轭梯度法解线性方程组。 二、实验目的：进一步熟悉理解掌握共轭梯度法解法思路，提高matlab编程能力。三、实验要求：已知线性方程 矩阵，应用共轭梯度法在相关软件编程求解线性方程组的解。 四、实验原理： 1．共轭梯度法： 考虑线性方程组 Ax?b 的求解问题，其中A是给定的n阶对称正定矩阵，b是 给定的n维向量，x是待求解的n维向量.为此,定义二次泛 函 ?(x)?xTAx?2bTx. 定理1设A对称正定,求方程组Ax?b的解，等价于求二次泛函?(x)的极小值点.定理1表明，求解线性方程组问题 就转化为求二次泛函?(x)的极小值点问题.求解二次函数极 小值问题，通常好像盲人下山那样，先给定一个初始向量x0，确定一个下山方向p0，沿着经过点x0而方向为p0的直线 x?x0??p0找一个点 x1?x0??0p0， 使得对所有实数?有 ??x0??0p0????x0??p0?， 即在这条直线上x1使?(x)达到极小.然后从x1出发， 再确定一个下山的方向p1，沿着直 线x?x1??p1再跨出一步，即找到?1使得??x?在 x2?x1??1p1达到极小： ??x1??1p1????x1??p1?. 重复此步骤，得到一串 ?0,?1,?2, x?xk??pk上确定步长?k使 和p0,p1,p2, ， 称pk为搜索方向，?k为步长.一般情况下，先在xk点 找下山方向pk，再在直线 ??xk??kpk????xk??pk?, 最后求出xk?1?xk??kpk.然而对不同的搜索方向和步长，得到各种不同的算法. 最速下降法and 共轭梯度法 分类：matlab 2011-04-17 17:02 961人阅读评论(2) 收藏举报算法出版优化 注明：程序中调用的函数jintuifa.m golddiv.m我在之前的笔记中已贴出 最速下降法 %最速下降法求解f = 1/2*x1*x1+9/2*x2*x2的最小值，起始点为x0=[9 1] %算法根据最优化方法（天津大学出版社）97页算法3.2.1编写 %v1.0 author: liuxi BIT %format long syms x1 x2 alpha; f = 1/2*x1*x1+9/2*x2*x2;%要最小化的函数 df=jacobian(f,[x1 x2]);%函数f的偏导 epsilon=1e-6;%0.000001k=0; x0=[9 1];%起始点 xk=x0; gk=subs(df,[x1 x2],xk);%起始点的梯度 gk=double(gk); while(norm(gk)>epsilon)%迭代终止条件||gk||<=epsilon pk=-gk;%负梯度方向 f_alpha=subs(f,[x1 x2],xk+alpha*pk);%关于alpha的函数 [left right] = jintuifa(f_alpha,alpha);%进退法求下单峰区间 [best_alpha best_f_alpha]=golddiv(f_alpha,alpha,left,right);%黄金分割法求最优步长xk=xk+best_alpha*pk; k=k+1; gk=subs(df,[x1 x2],xk); gk=double(gk); end best_x=xk;%最优点 best_fx=subs(f,[x1 x2],best_x);%最优值 共轭梯度法 牛顿法 迭代公式：(1)2()1()[()]()k k k k x x f x f x +-=-?? Matlab 代码： function [x1,k] =newton(x1,eps) hs=inline('(x-1)^4+y^2'); 写入函数 ezcontour(hs,[-10 10 -10 10]); 建立坐标系 hold on; 显示图像 syms x y 定义变量 f=(x-1)^4+y^2; 定义函数 grad1=jacobian(f,[x,y]); 求f 的一阶梯度 grad2=jacobian(grad1,[x,y]); 求f 的二阶梯度 k=0; 迭代初始值 while 1 循环 grad1z=subs(subs(grad1,x,x1(1)),y,x1(2)); 给f 一阶梯度赋初值 grad2z=subs(subs(grad2,x,x1(1)),y,x1(2)); 给f 二阶梯度赋初值 x2=x1-inv(grad2z)*(grad1z)'; 核心迭代公式 if norm(x1-x2) end end end 优点：在极小点附近收敛快 缺点：但是要计算目标函数的hesse 矩阵 最速下降法 1. ：选取初始点xo ，给定误差 2. 计算一阶梯度。若一阶梯度小于误差，停止迭代，输出 3. 取()()()k k p f x =? 4. 10 t ()(), 1.min k k k k k k k k k k t f x t p f x tp x x t p k k +≥+=+=+=+进行一维搜索，求，使得令转第二步 例题： 求min (x-2)^4+(x-2*y)^2.初始值（0,3）误差为0.1 (1)编写一个目标函数，存为f.m function z = f( x,y ) z=(x-2.0)^4+(x-2.0*y)^2; end (2)分别关于x 和y 求出一阶梯度，分别存为fx.m 和fy.m function z = fx( x,y ) z=2.0*x-4.0*y+4.0*(x-2.0)^3; end 和 function z = fy( x,y ) 共轭梯度法及其基本性质 预备知识 定义1 设是对称正定矩阵。称是A-共轭的，是指 性质1 设有是彼此共轭的维向量，即 则一定是线性无关的。 ［证明］若有一组数满足 则对一切一定有 注意到，由此得出：即所有的＝０．因此， 是线性无关的． 性质２设向量是线性无关的向量组，则可通过它们的线性组合得出一组向量，而是两两共轭的． ［证明］我们用构造法来证实上面的结论． Ｓ０：取； Ｓ１：令，取． …… Ｓm：令 取 容易验证：符合性质２的要求． 性质３设是两两Ａ－共轭的，是任意指定的向量，那么从出发，逐次沿方向搜索求的极小值，所得序列，满足： ． ［证明］由下山算法可知，从出发，沿方向搜索，获得 从而 性质４设是两两Ａ共轭的，则从任意指定的出发，依次沿搜索，所得序列满足： （１） （２），其中是方程组(5.1.1)的解． ［证明］（１）是性质３的直接推论，显然成立． （２）由于是两两Ａ共轭的，故是线性无关的．所以对于向量可用线性表出，即存在一组数使 由于及，得出 ， 于是，再由得出 于是，与得出一样地，我们可以陆续得出： 对比和的表达式可知， 证明完毕 性质４是性质３的直接推论．但它给出了一种求（５.１.１）的算法，这种算法称之为共轭方向法．结合性质２，我们可以得到如下的性质５． 性质５设是上的一组线性无关的向量，则从任意指定的出发，按以下迭代产生的序列： Ｓ１：取，，； Ｓ２：计算，取； 计算，得出； 如此进行下去，直到第n步： Ｓn：计算取 计算，得出． 显然： 根据性质４可知，不论采用什么方法，只要能够构造个两两Ａ共轭的向量作为搜索方向，从任一初始向量出发，依次沿两两Ａ共轭的方向进行搜索，经 步迭代后，便可得到正定方程组的解． 1、设计题目 用共轭梯度法求二次函数的极小点及极小值。 2、运行与程序 （1）运行：打开matlab,确定conjugate_grad_2d.m文件夹为当前目录。 在命令窗中输入：f=conjugate_grad_2d([1,1],0.001) 选择不同的初始点坐标[0,0],[0,1],[1,0],和迭代精度0.01，0.0001, 进行运行时，需要多次调用conjugate_grad_2d函数。 （2）程序及说明： function f=conjugate_grad_2d(x0,t) %用共轭梯度法求已知函数f(x1,x2)=x1^2+2*x2^2-4*x1-2*x1*x2的极值点 %已知初始点坐标：x0 %已知收敛精度：t %求得已知函数的极值：f x=x0; syms xi yi a; %定义自变量，步长为符号变量 f=xi^2+2*yi^2-4*xi-2*xi*yi; %创建符号表达式f fx=diff(f,xi); %求表达式f对xi的一阶求导 fy=diff(f,yi); %求表达式f对yi的一阶求导 fx=subs(fx,{xi,yi},x0); %代入初始点坐标计算对xi的一阶求导实值 fy=subs(fy,{xi,yi},x0); %代入初始点坐标计算对yi的一阶求导实值 fi=[fx,fy]; %初始点梯度向量 count=0; %搜索次数初始为0 while double(sqrt(fx^2+fy^2))>t %搜索精度不满足已知条件 s=-fi; %第一次搜索的方向为负梯度方向 if count<=0 s=-fi; else s=s1; end x=x+a*s; %进行一次搜索后的点坐标 f=subs(f,{xi,yi},x); %构造一元搜索的一元函数φ(a) f1=diff(f); %对函数φ(a)进行求导 f1=solve(f1); %得到最佳步长a if f1~=0 ai=double(f1); %强制转换数据类型为双精度数值 else break %若a=0，则直接跳出循环，此点即为极值点 end x=subs(x,a,ai); %得到一次搜索后的点坐标值 f=xi^2+2*yi^2-4*xi-2*xi*yi; fxi=diff(f,xi); 最优化课程设计 题目：共轭梯度法 姓名：田鑫 指导老师：智红英 学号： 201118030216 班级：信息与计算科学111802班 共轭梯度法（Conjugate Gradient） 是介于最速下降法与牛顿法之间的一个方法，它仅需利用一阶导数信息，但克服了最速下降法收敛慢的缺点，又避免了牛顿法需要存储和计算Hesse矩阵并求逆的缺点，共轭梯度法不仅是解决大型线性方程组最有用的方法之一，也是解大型非线性最优化最有效的算法之一。在各种优化算法中，共轭梯度法是非常重要的一种。其优点是所需存储量小，具有步收敛性，稳定性高，而且不需要任何外来参数。 设我们要求解下列线性系统 其中n-×-n矩阵A是对称的（也即，A T = A），正定的（也即，x T Ax > 0对于所有非0向量x属于R n），并且是实系数的。 将系统的唯一解记作x*。 最后算法 经过一些简化，可以得到下列求解Ax = b的算法，其中A是实对称正定矩阵。x := 0 k := 0 r := b repeat until r k is "sufficiently small": k := k + 1 if k = 1 p := r0 1 else end if x := x k-1 + αk p k k r := r k-1 - αk A p k k end repeat 结果为x k 共轭梯度法程序源代码 #include 共轭梯度法程序源代码 #include } /*以下是黄金分割法程序源代码*/ double hjfg(double x[],double p[]) { double beta,t1,t2,t; double f1,f2; double a=0,b=0; double *c,*d; c=&a,d=&b; sb(c,d,x,p);/*调用进退法搜索区间*/ printf("\nx1=%lf,x2=%lf,p1=%lf,p2=%lf",x[0],x[1],p[0],p[1]); printf("\n[a,b]=[%lf,%lf]",a,b); beta=(sqrt(5)-1.0)/2; t2=a+beta*(b-a); f2=f(x,p,t2); t1=a+b-t2; f1=f(x,p,t1); while(1) { if(fabs(t1-t2) 康福 0031 一．无约束优化方法 无约束优化方法的必要性 一般机械优化设计问题，都是在一定的限制条件下追求某一指标为最小，它们都属于约束优化问题。但是为什么要研究无约束优化问题? （1）有些实际问题，其数学模型本身就是一个无约束优化问题。 （2）通过熟悉它的解法可以为研究约束优化问题打下良好的基础。 （3）约束优化问题的求解可以通过一系列无约束优化方法来达到。所以无约束优 化问题的解法是优化设计方法的基本组成部分，也是优化方法的基础。 （4）对于多维无约束问题来说，古典极值理论中令一阶导数为零，但要求二阶可 微，且要判断海赛矩阵为正定才能求得极小点，这种方法有理论意义，但无实用价值。和一维问题一样，若多元函数F(X)不可微，亦无法求解。但古典极值理论是无约束优化方法发展的基础。 共轭梯度法 目前已研究出很多种无约束优化方法，它们的主要不同点在于构造搜索方向上的差别。 （1）间接法——要使用导数，如梯度法、（阻尼）牛顿法、变尺度法、共轭梯度 法等。 （2）直接法——不使用导数信息，如坐标轮换法、鲍威尔法单纯形法等。 用直接法寻找极小点时，不必求函数的导数，只要计算目标函数值。这类方法较适用于解决变量个数较少的（n ≤20）问题，一般情况下比间接法效率低。 间接法除要计算目标函数值外，还要计算目标函数的梯度，有的还要计算其海赛 矩阵。 搜索方向的构成问题乃是无约束优化方法的关键。 1(0,1,2,) k k k k s k α+=+=L x x 共轭梯度法是沿着共轭方向进行搜索，属于共轭方向法中的一种，该方法中每一个共轭向量都是依赖于迭代点处的负梯度而构造出来。共轭梯度法作为一种实用的迭代法，它主要有下面的优点： （1）算法中，系数矩阵Ａ的作用仅仅是用来由已知向量P 产生向量W=AP ，这不仅 可充分利用Ａ的稀疏性，而且对某些提供矩阵Ａ较为困难而由已知向量P 产生向量W=AP 又十分方便的应用问题是很有益的。 （2）不需要预先估计任何参数就可以计算，这一点不像SOR 等； （3）每次迭代所需的计算，主要是向量之间的运算，便于并行化。 共轭梯度法原理的知识较多，请详见《机械优化设计》第四章的第四、五节。 图1为共轭梯度法的程度框图 图1为共轭梯度法的程度框图 二．设计题目及要求 设计题目 用共轭梯度法求二次函数 2 21212 112(,)242f x x x x x x x =+-- 的极小点及极小值。 设计要求 （1）使用matlab 编写程序，熟练撑握matlab 编程方法。 （2）学习并撑握共轭梯度法的原理、方法及应用，并了解不同无约束优化方法的 区别、优缺点及特殊要求。 （3）编写程序，计算出二次函数的极小点及极小值，并适当选取不同的初始点及 迭代精度精度，分析比较结果。 用MATLAB 实现共轭梯度法求解实例 康福 201103710031 一．无约束优化方法 1.1 无约束优化方法的必要性 一般机械优化设计问题，都是在一定的限制条件下追求某一指标为最小，它们都属于约束优化问题。但是为什么要研究无约束优化问题? （1）有些实际问题，其数学模型本身就是一个无约束优化问题。 （2）通过熟悉它的解法可以为研究约束优化问题打下良好的基础。 （3）约束优化问题的求解可以通过一系列无约束优化方法来达到。所以无约束优 化问题的解法是优化设计方法的基本组成部分，也是优化方法的基础。 （4）对于多维无约束问题来说，古典极值理论中令一阶导数为零，但要求二阶可微，且要判断海赛矩阵为正定才能求得极小点，这种方法有理论意义，但无实用价值。和一维问题一样，若多元函数F(X)不可微，亦无法求解。但古典极值理论是无约束优化方法发展的基础。 1.2共轭梯度法 目前已研究出很多种无约束优化方法，它们的主要不同点在于构造搜索方向上的差别。 （1）间接法——要使用导数，如梯度法、（阻尼）牛顿法、变尺度法、共轭梯度法等。 （2）直接法——不使用导数信息，如坐标轮换法、鲍威尔法单纯形法等。 用直接法寻找极小点时，不必求函数的导数，只要计算目标函数值。这类方法较适用于解决变量个数较少的（n ≤20）问题，一般情况下比间接法效率低。间接法除要计算目标函数值外，还要计算目标函数的梯度，有的还要计算其海赛矩阵。 搜索方向的构成问题乃是无约束优化方法的关键。 共轭梯度法是沿着共轭方向进行搜索，属于共轭方向法中的一种，该方法中每一个共轭向量都是依赖于迭代点处的负梯度而构造出来。共轭梯度法作为一种实用的迭代法，它主要有下面的优点： （1）算法中，系数矩阵Ａ的作用仅仅是用来由已知向量P 产生向量W=AP ，这不仅可充分利用Ａ的稀疏性，而且对某些提供矩阵Ａ较为困难而由已知向量P 产生向量W=AP 又十分方便的应用问题是很有益的。 （2）不需要预先估计任何参数就可以计算，这一点不像SOR 等； （3）每次迭代所需的计算，主要是向量之间的运算，便于并行化。 共轭梯度法原理的知识较多，请详见《机械优化设计》第四章的第四、五节。 图1为共轭梯度法的程度框图 1(0,1,2,) k k k k s k α+=+=x x清华大学高等数值计算(李津)实践题目一(共轭梯度CG法,Lanczos算法与MINRES算法)
作业4-FR共轭梯度法
共轭梯度算法分析与实现
最优化课程设计--共轭梯度法算法分析与实现
共轭梯度法程序
FR共轭梯度法
共轭梯度实验报告
共轭梯度法
最优化牛顿法最速下降法共轭梯度法matlab代码
共轭梯度法及其基本性质
共轭梯度法程序及调试结果分析
共轭梯度法c++程序
共轭梯度法程序源代码
用MATLAB实现共轭梯度法求解实例
用MATLAB实现共轭梯度法求解实例
- 作业4-FR共轭梯度法
- 共轭梯度法和基本性质
- 最优化牛顿法最速下降法共轭梯度法matlab代码
- 共轭梯度法程序源代码
- 共轭梯度法的C++实现
- 共轭梯度法求解线性方程组-matlab通用程序
- 共轭梯度法求解函数最优值程序说明
- 最优化共轭梯度法
- 用MATLAB实现共轭梯度法求解实例
- 共轭梯度法的matlab代码
- 共轭梯度法,黄金分割,外推法C语言代码
- 最优化课程设计--共轭梯度法算法分析与实现
- 共轭梯度法的matlab源程序
- 计算方法——共轭梯度法求解线性方程组
- 用MATLAB实现共轭梯度法求解实例
- 共轭梯度法--MATLAB程序
- 共轭梯度法求线性方程组的解matlab程序
- 数值分析11(共轭梯度法)
- 共轭梯度法程序及调试结果分析
- 共轭梯度法 MATLAB程序