目录
运筹学实验报告 (2)
1.实验背景 (2)
2.方法简介 (2)
3.问题分析 (2)
4.算法步骤 (2)
5.程序代码以及部分注释 (2)
6.实验结果及截屏 (3)
7.心得体会 (5)
运筹学实验报告
——最速下降法的matlab实现
1.实验背景
梯度下降法是一个最优化算法，通常也称为最速下降法。最速下降法是求解无约束优化问题最简单和最古老的方法之一，虽然现在已经不具有实用性，但是许多有效算法都是以它为基础进行改进和修正而得到的。最速下降法是用负梯度方向为搜索方向的，最速下降法越接近目标值，步长越小，前进越慢。
2.方法简介
顾名思义，梯度下降法的计算过程就是沿梯度下降的方向求解极小值（也可以沿梯度上升方向求解极大值）。其迭代公式为,其中代
表梯度负方向，表示梯度方向上的搜索步长。梯度方向我们可以通过对函数求导得到，步长的确定比较麻烦，太大了的话可能会发散，太小收敛速度又太慢。一般确定步长的方法是由线性搜索算法来确定，即把下一个点的坐标ak+1看做是的函数，然后求满足f(ak+1)的最小值的即可。
因为一般情况下，梯度向量为0的话说明是到了一个极值点，此时梯度的幅值也为0.而采用梯度下降算法进行最优化求解时，算法迭代的终止条件是梯度向量的幅值接近0即可，可以设置个非常小的常数阈值。
3.问题分析
本实验分析的问题对象是无约束的非线性规划问题，最速下降法是以负梯度方向最为下降方向的极小化算法，相邻两次的搜索方向是互相直交的。若要求解此问题，则需要对目标函数的极小点进行求解，通过matlab软件对目标函数的极小点进行求解，则首先需要确定迭代的初始点，再确定迭代方向和步长。前曾已经指出，负梯度方向是函数值下降最快的方向，沿这个方向搜寻可以更快的找到极小点。步长可以通过黄金分割法在负梯度方向进行一维搜索，来确定最佳步长。
4.算法步骤
（1）假定初始点x0=[1,1,1,1,1]与误差输入矩阵Q，矩阵Q是一个5阶半正定矩阵，以及5维常数列向量C，即可确定初始方程。
（2）a.输出结果若在误差允许范围之内，则直接输出。
b.输出结果若不符合误差允许，则求逆梯度方向，确定迭代方向。
（3）通过黄金分割法来在负梯度方向做一维搜索确定步长，确定下一个迭代点继续返回。
5.程序代码以及部分注释
function w= hump(T,A)%T为5阶半定矩阵，A为5维常数列向量
tic;
syms x1x2x3x4x5c
c=[x1,x2,x3,x4,x5];
w=c*T*c.'+c*A;%要求的目标函数
h=10^-5;b=0.5;s=0.5;t=0.5;
x=[1,1,1,1,1];%x0的初始值
gradient=jacobian(w,[x1,x2,x3,x4,x5]);%梯度函数
x1=x(:,1);x2=x(:,2);x3=x(:,3);x4=x(:,4);x5=x(:,5);
d1=eval(gradient);%梯度
while(sqrt(sum(d1.^2))>h)%梯度二范数大于h=10^-5
d=-d1;%搜索方向
n=0;a=s*b^n;
s1=eval(w);%在xk点的值
y=x+a*d; x1=y(:,1);x2=y(:,2);x3=y(:,3);x4=y(:,4);x5=y(:,5);
s2=eval(w);%在x+a*d的值
s3=-t*a*dot(d1,-d1);%第一步迭代前的值
while(s1-s2n=n+1;
a=s*b^n;
y=x+a*d; x1=y(:,1);x2=y(:,2);x3=y(:,3);x4=y(:,4);x5=y(:,5); s2=eval(w);
s3=-t*a*dot(d1,-d1);
end
x=y;
x1=x(:,1);x2=x(:,2);x3=x(:,3);x4=x(:,4);x5=x(:,5);
d1=eval(gradient);
end
x
z=eval(w)%全局最优值
toc;
6.实验结果及截屏
在matlab命令窗口内输入：
T=[1,1,0,0,0;0,1,1,0,0;0,0,1,0,0;0,0,0,1,0;0,0,0,0,1];
>> A=[1;0;0;0;0];
>> w=hump(T,A)
得到结果如下截屏图1
matlab命令窗口内输入：
T=[1,1,0,0,0;0,1,1,0,0;0,0,1,0,0;0,0,0,1,0;0,0,0,0,1];
A=[0;1;1;0;0];
>> w=hump(T,A)
得到结果如下截屏图2
图1
图2
7.心得体会
在开始动手操作这个实验之前，我首先把书上这一节的内容仔细看了一遍，再研究透彻之后，又上网找寻了一些已有的资料，其中有不少是用黄金分割法来搜寻步长的最速下降法，我认真思考了一番，决定参考已有的代码，进行自己修改，最终得出了一个可行的程序代码，。又分别代入了两组数据进行实验，发现结果比较理想。通过这个实验，我发现matlab对学习数学有很大的帮助，运筹学本来就是一门讲究建模基础的课程，建立模型之后总是需要得到合适的数值解，这就需要利用已有的数学软件来帮助求解了，所以显而易见，建模和计算其实是同等重要的。计算往往是最后也是最关键的一步，这就需要我们对计算中的优化和误差分析更精确，将误差降低到最小限度。运筹学其实是一门非常有趣味的学科，只要用心去学习揣摩，会渐渐喜欢上这门学科。在经过一个学期的学习之后，我感觉我学会了很多全新的知识，对运筹学有了一个从认识到熟悉的过程，对问题的分析能力也得到了稳步提高，也掌握了一些初步的建模基础。
