最优化课程设计

四川理工学院

《最优化方法课程设计》报告

共轭梯度算法研究

学生：张伟程进朱春林蔡国宝

专业：信息与计算科学

班级：2008级2班

指导教师：兰恒友

四川理工学院理学院

二零一一年十二月

四川理工学院理学院

课程设计任务书

专业： 信息与计算科学 班级： 信计2008X 课程名称： 最优化方法课程设计

学生姓名： 张伟 程进 朱春林 蔡国宝 发题时间： 2011 年 12 月 18 日

一、 课题名称

共轭梯度算法研究

二、 课题条件

1. 参考文献：

[1] 孙文瑜等, 最优化方法(第二版)[M]，北京:高等教育出版社,2010.

[2] 王红梅.算法设计与分析[M].北京:清华大学出版社,2006.

2. 安排10学时（18周五 8:00-11:45 13:30-17:15）上机（信计20081 N1S-229, 信计20082 N1S-231），指导老师到场指导网上和图书馆检索文献。

三、 设计任务

理解巩固课程理论教学的知识，培养学生的实践动手能力。具体任务： 掌握共轭梯度法的思路及迭代过程；用共轭梯度法求

221212min ()2f X x x x x =+-，

自定初始点，01.0=ε 四、 设计说明书（或论文）内容

摘要、问题描述、具体理论知识点、具体实例、程序清单、程序实现、参考文献、总结、小组成员分工合作清单。

五、 进度计划（列出完成项目设计内容、绘图等具体起始日期）

12月19-25日图书馆或网络查资料，12月26-29日，根据资料整理出基础理论与实例；12月30日上机10学时，编程并上机实现；12月31日完成报告并上缴电子文档。

指导教师 （签名）： 年 月 日 教研室主任 （签名）： 年 月 日

共轭梯度算法研究

摘要

共轭梯度法是介于最速下降法与牛顿法之间的一个方法，它仅需利用一阶导数信息，但客服了最速下降法收敛慢的缺点，又避免了牛顿法需要存储和计算Hesse矩阵并求逆的缺点。共轭梯度法不仅是解大型线性方程组最有用的方法之一，也是解大型非线性最优化问题最有效的算法之一。在各种优化算法中，共轭梯度法是非常重要的一种。其优点是所需存储量小，具有步收敛性，稳定性高，而且不需要任何外来参数。

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

关键词：共轭梯度法线性搜索正定二次函数最优解

目录

一、问题提出 (1)

二、设计思路和步骤 (3)

三、程序设计 (4)

3.1问题分析 (4)

3.2 算法设计 (4)

3.3 算法框图 (4)

3.4 程序编制 (4)

四、结果分析 (6)

4.1设计结果 (6)

4.2 进一步讨论和验证 (6)

五、收获和总结 (7)

六、结束语 (8)

6.1设计的优缺点 (8)

6.2设计工作展望 (8)

参考文献 (9)

附录 (10)

四川理工学院《最优化方法课程设计》论文

一、问题提出

共轭梯度法是一个典型的共轭方向法。它的每一个搜索方向是互相共轭的。而这些搜索方向k d 仅仅是负梯度方向k g -与上一次迭代的搜索方向1d -k 的组合。因此，存储量

少，计算方便。

记

,d d 11--+-=k k k k g β

左乘，得并使得0d d ,d 111=---k T

k T k G G

1

11

1G G ----=k T k k T

k k d d d g β

（Hestenes-Stiefel 公式）

利用)(11k k k k x x G g g -=-++和01=+k T k d g ，上式也可以写成

1

1k 1k 11k 1g g g )

g -(g )

g -(g ------==k T

k T

k k T

k k T

k k g d g β

前 言

另外三个常用的公式为

,g g

)g -(g 111k 1----=k T k k T k k g β ,g d g 1

1k 1---=k T

k T

k k g β ,)g -(g g 1k 1k 1---=k T

k T

k k d g β

对于正定二次函数，若采用精确线性搜索，以上几个关于几个k β的共轭梯度公式等

价。在实际计算中，FR 公式和PRP 公式最常用。

四川理工学院《最优化方法课程设计》论文

二、设计思路和步骤

2.1设计思路

注意到对于正定二次函数，

k k k r b Gx =-=g （4.3.21）

其中k r 是方程组b Gx k =的残量，以及

,r 1k k k k Gd r α=-+

,g -T k k

T k k T

k k T k k

k Gd d r r Gd d d ==α （4.3.22）

2.2设计步骤

共轭梯度法

步骤一：

初始步： 给出,x r ,0,x 000b G -=>计算ε令0:,r d 00=-=k 。

步骤二：

如果||k r ||<=ε，停止。

步骤三：

计算

,k k

T k k

T

k Gd d r r =α

,x 1k k k k d x α+=+

,r 1k k k k Gd r α+=+

,r r 1

1k T k k T

k k r r ++=β

.d 11k k k k d r β+-=++

步骤四：

令k:=k+1，转步骤二。

第2章输电阻管理

三、程序设计

3.1问题分析

3.2 算法设计

3.3 算法框图

掌握共轭梯度法的思路及迭代过程；用共轭梯度法求

22

1212

min()2

f X x x x x

=+-，自定初始点，

01

.0

=

ε

3.4 程序编制

function f=conjugate_grad_2d(x0,t)

%input this:conjugate_grad_2d([2,2],0.01) x=x0;

syms xi yi a

f=2*xi^2+yi^2-xi*yi;

fx=diff(f,xi);

fy=diff(f,yi);

fx=subs(fx,{xi,yi},x0);

fy=subs(fy,{xi,yi},x0);

fi=[fx,fy];

count=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);

f1=diff(f);

f1=solve(f1);

if f1~=0

ai=double(f1);

else

break

x,f=subs(f,{xi,yi},x),count;

end

x=subs(x,a,ai);

f=3/2*xi^2+1/2*yi^2-2*xi-xi*yi;

fxi=diff(f,xi);

fyi=diff(f,yi);

fxi=subs(fxi,{xi,yi},x);

fyi=subs(fyi,{xi,yi},x);

fii=[fxi,fyi];

d=(fxi^2+fyi^2)/(fx^2+fy^2);

s1=-fii+d*s;

count=count+1;

fx=fxi;

fy=fyi;

end

x,f=subs(f,{xi,yi},x),count

四、结果分析

四、结果分析

4.1设计结果

（可用文字描述和贴图等方式表现设计结果）

4.2 进一步讨论和验证

（比如：设计的改进、推广等）

四川理工学院《最优化方法课程设计》论文

五、收获和总结

5.1 小组总结

5.2 个人总结

六、结束语

六、结束语

6.1设计的优缺点

6.2设计工作展望

四川理工学院《最优化方法课程设计》论文

参考文献

[1] 孙文瑜等, 最优化方法(第二版)[M]，北京:高等教育出版社,2010.

[2] 王红梅.算法设计与分析[M].北京:清华大学出版社,2006.

附录

附录