运筹学实验报告(F-R共轭梯度法、Wolfe简约梯度法).doc

运筹学课程实验报告姓名：*学号：*班级：*日期：2012/12/17一、实验目的:1、掌握求解无约束最优化问题的 F-R共轭梯度法，以及约束最优化问题 Wolfe简约梯度法。2、学会用MATLAB编程求解问题，并对以上方法的计算过程和结果进行分析。二、实验原理与步骤: 1、F-R共轭梯度法基本步骤是在点 处选取搜索方向, 使其与前一次的搜索方向 关于共轭，即然后从点 出发，沿方向求得的极小值点 , 即如此下去, 得到序列。不难求得的解为注意到的选取不唯一，我们可取由共轭的定义可得：共轭梯度法的计算过程如下：第一步：取初始向量, 计算第步：计算2、Wolfe简约梯度法Wolfe基本计算步骤：第一步：取初始可行点 x0Xl ,给定终止误差0 ，令k:=0；第二步：设 IBk是xk的 m 个最大分量的下标集，对矩阵A进行相应分解 A=(Bk , Nk)；第三步：计算 fxk=BfxkNfxk ,然后计算简约梯度rNk=-(Bk-1Nk)TBfxk+Nfxk；第四步：构造可行下降方向 pk. 若|pk| ，停止迭代，输出xk。否则进行第五步。第五步：进行有效一维搜索，求解minfxk+tpk,得到最优解tk. 令xk+1=xk+ tkpk , k:=k+1, 转入第二步。三、实验内容：1、（运筹学P153页第20题）用F-R法求解min(1-x1)2+2(x2-x12)2选取初始点x0=(0,0)T, =10-6.2、（运筹学P154页第25题）用Wolfe法求解以下问题：minfx1,x2=2x12+2x22-2x1x2-4x1-6x2s.t. x1+x22 x1+5x25 x10, x20选取初始可行点 x0=(0,0)T, =10-6.四、问题求解：问题1求解：（F-R法）程序代码如下：（1）主函数syms x1 x2 r;f=(1-x1)2+2*(x2-x12)2;x=x1,x2;df=jacobian(f,x);df=df.;error=0.000001;x0=0,0;g1=subs(df,x,x0);k=0;while(norm(g1)error) if k=0 d=-g1; else bta=g1*g1/(g0*g0); d=-g1+bta*d0; end y=subs(f,x,x0+r*d); result=jintuifa(y,r); result2=golden(y,r,result); step=result2; x0=x0+step*d; g0=g1;g1=subs(df,x,x0); d0=d;k=k+1;end;kx0（2）子函数进退法确定一维搜索区间：function result=jintuifa(y,r)t0=0; step=0.0125;t1=t0+step;ft0=subs(y,r,t0);ft1=subs(y,r,t1);if(ft1ft2) t1=t2;step=2*step;t2=t1+step;ft1=subs(y,r,t1);ft2=subs(y,r,t2); endelse step=step/2;t2=t1;t1=t2-step;ft1=subs(y,r,t1); while(ft1ft0) step=step/2;t2=t1;t1=t2-step;ft1=subs(y,r,t1); endendresult=t2;黄金分割法进行一维搜索：function result=golden(y,r,m)a=0;b=m;e=1e-5;a1=a+0.382*(b-a);f1=subs(y,r,a1);a2=a+0.618*(b-a);f2=subs(y,r,a2);while abs(b-a)=e if f1error & k3) x_11=x_1(1),x_1(2) gradient=gradient_my(f,x_11,b) rN=-1.25*gradient(1),0.25*gradient(2) pN=-rN(1)*x_1(3),rN(2)*x_1(4) pB=-1.25*pN(1),0.25*pN(2); new_direction=pB pN; norm=0; TT=; tmax=1; for i=1:4 norm=norm+(new_direction(i)2 end for j=1:4 if (new_direction(j)0) T(j)= new_direction(j) else T(j)=0; end if (T(j)TT(uk) tmax=TT(uk) n=n+1; end end x=x_1+t*new_direction; xx=x(1),x(2); f_step=subs(f,findsym(f),xx); F=diff(f_step,t); solve(F,t); t0=tmax; x_2=x_1+0.18*new_direction A=A;x_2; norm0=norm; search_direction=new_direction x_1=x_2; xx2=x_2(1),x_2(1); Y=subs(f,findsym(f),xx2); HSZ=HSZ;Y k=k+1; endkx_2norm程序运行结果如下初始点(0,0,2,5) earch_direction = 4 6 -10 34 tmax=0.147如果不交还B矩阵与A矩阵则运行结果如下x_1 =(0.6251 0.8708 0.5077 0.0246) search_direction =3.4 4.4 -8 -25.6很显然X4已经无法再取有效值，故须交还B与Ax_1 =(0.5882 0.8824 0.5294 0) search_direction =1.8222 0 - 2.2578 -0.44tmax=0.231 x_2 =1.0962 0.8824 0.1230 0由以上结果显示： x*=1.0962, 0.8824T 而理论计算值为x*=3531,2431T1.129, 0.7742T有一定的计算误差。 五、实验体会：通过这次运筹学课内实验，我对无约束优化问题及约束优化问题的思想和部分算法的求解过程有了进一步了解与掌握。这次实验使我对用进退法确定一维搜索区间，如何进行一维搜索，对求解无约束优化问题的F-R共轭梯度法和约束最优化问题 的Wolfe简约梯度法的基本思想和算法有了更深理解，对课内的所学知识进一步消化。在本次实