求解无约束最优化问题的共轭梯度法.doc

首次试做实验记录

年 月 日
实验课程名称
最优化方法
面向专业
信息与计算科学
总学时数

实验项目名称
求解无约束最优化问题的共轭梯度法
实验学时

一、实验目的、要求
目的：进一步掌握解无约束最优化问题的共轭梯度法的基本思想，熟悉关于极小化正定二次函数以及非二次函数的共轭梯度法的算法，了解它们的特点，加强编程能力和编程技巧，能够上机求解一些多变量函数最优化问题。
要求：针对给定的实验题目，根据共轭梯度法的算法，能够熟练地使用某种语言上机编程，给出实验结果，注意上机编程的正确性。
二、实验原理
共轭梯度法是介于最速下降法与牛顿法之间的一个方法，它仅需利用一阶导数信息，但克服了最速下降法收敛慢的缺点，又避免了牛顿法需要存储和计算Hesse矩阵并求逆的特点。共轭梯度法具有二次终止性，即对于正定二次函数，在精确线搜索的条件下，方法有限步终止。关于正定二次函数和非二次函数的共轭梯度法详见教材中的算法4.3.4和算法4.3.8。需要写算法
三、实验内容：
极小化函数，其中
。

四、实验过程原始记录(数据、图表、计算等)
%首先我们给出给出针对正定二次函数的共轭梯度法的程序
% 该程序具有一定的适应性，适合一般的正定二次函数
function [x,iter]=cgopt(G,b,x0,max_iter,tol)
% Conjugate gradient method for the following positive definite quadratic
% function
% x0: starting point
% max_iter: maximum number of iterations
% tol: tolerance of the gradient
x=x0;
fprintf('\n x0= ');
fprintf(' %10.6f',x0);
r=G*x-b;
d=-r;
for k=1:max_iter
if norm(r)<=tol
iter=k-1;
fprintf('\n Algorithm finds a solution!');
return
end
alpha=(r'*r)/(d'*G*d);
xx=x+alpha*d;
rr=r+alpha*G*d;
beta=(rr'*rr)/(r'*r);
d=-rr+beta*d;
x=xx;
r=rr;
fprintf('\n x%d= ',k);
fprintf(' %10.6f',x);
end
iter=max_iter;
return

%下面我们给出利用共轭梯度法法求解本实验题目的主程序
%该程序具有针对性，需针对具体的题目进行适当的修改
function CG_main()
G=[10 1 2 3 4;1 9 -1 2 -3;2 -1 7 3 -5;3 2 3 12 -1;4 -3 -5 -1 15];
b=[12 -27 14 -17 12]';
x0=[0 0 0 0 0]';
max_iter=1000;
tol=1e-6;
fprintf('\n');
fprintf('Conjugate Gradient Method: \n');
fprintf('============= \n');
[x,iter]=cgopt(G,b,x0,max_iter,tol);
fprintf('Iterative number:\n %d\n',iter);
fprintf('Solution: \n');
fprintf(' %10.6f ',x);
fprintf('\n============= \n');

五、实验结果及分析
我们在工作窗口输入命令CG_main ()，运行后得结果

Conjugate Gradient Method:
=============

x0= 0.000000 0.000000 0.000000 0.000000 0.000000
x1= 1.073560 -2.415510 1.252487 -1.520877 1.073560
x2= 1.305605 -2.627981 2.146636 -1.694270 0.442393
x3= 1.446618 -2.225384 2.448048 -1.970691 0.620722
x4= 1.086550 -2.063574 2.792911 -2.101645 0.836386
x5= 1.000000 -2.000000 3.000000 -2.000000 1.000000
Algorithm finds a solution!Iterative number:
5
Solution:
1.000000 -2.000000 3.000000 -2.000000 1.000000
=============

结果分析：我们根据解针对正定二次函数的共轭梯度法的算法编写了Matla程序。上机运行后经过5次迭代后得到了精确最优解。本题中的目标函数是正定二次函数，未知变量的维数为5，理论上共轭梯度法经过5次迭代后即可得到最优解，而上机数值实验的结果也是如此。结果说明了用共轭梯度法求解无约束最优化问题的可行性，同时也表明了我们编写的程序的正确性。