2023年运筹学实验报告FR共轭梯度法Wolfe简约梯度法.docx
运筹学课程实验报告dj_dj_姓名:学号:*T1T、，T、p*班级:，T、，*p，T、*T、，T、，T、，T、日期:2023/12/17for j=l: 4if ( n e w_directi o n ( j ) <0)T (j ) = n ew_di r e c t i o n (j ) el s eT ( j ) =0;e n dif (T(j)<0)TT=abs ( Tt, (x_1 (j)/T(j) endj=j+l；endn=s i z e (TT)；:0 r uk= 1 ： ni f (tmax>TT(u k)tm a x=T T (uk)n= n + 1 ；endend:=x_ 1 +t* n ew_dir e ction；x x = x (1) ,x (2)；f_s t e p = s ub s (f z findsym ( f ) , xx);F=dif f ( f _ s t e p , t);o 1 v e (F, t );t0 = tmax;x _2=x_ 1 +0.18* new_ dire ctionA= A； x_2;no r m0= n orm；sea r ch_di r ection=n e w_dire c tion x_l=x_2;xx2= x _2 (1) , x_2 (1);Y=sub s ( f , findsym ( f ) , x x2);HSZ=(HSZ； Yk =k+ 1 ； end x_2norm程序运营结果如下初始点(0, 0,2, 5 ) ear c hdire ction = 46-1 034tm a x=0. 14 7假如不交还B矩阵与A矩阵则运营结果如下x_ 1 =( 0.6 2510. 87080. 5077 0. 0246)s e arch d i r e ction =3.44. 4-82 5 . 6很显然X4已经无法再取有效值，故须交还B与Ax 1 = ( 0. 58820. 88240. 52 9 40) s earch d i re c tion = 1.8 2220 2.2578-0.4 4tm a x= 0 . 231x_2 =1.0 9 620. 8 8240. 12 3 00由以上结果显示： x* = （1.0962, 0.8824）t而理论计算值为/35 24丁,、丁X =（亓五）"（l，29,0.7742）T有一定的计算误差。五、实验体会：通过这次运筹学课内实验，我对无约束优化问题及约束优 化问题的思想和部分算法的求解过程有了进一步了解与掌握。 这次实验使我对用进退法拟定一维搜索区间，如何进行一维搜 索，对求解无约束优化问题的F R共跳梯度法和约束最优化 问题的Wolfe简约梯度法的基本思想和算法有了更深理解,对 课内的所学知识进一步消化。在本次实验过程中，发现真正用Matla b求解实际问题的能 力还很欠缺,对Matlab的纯熟限度还不够！求解过程出现了许 多错误，通过网上查找资料和运用图书馆图书资源得到解决; 但是仍有部分问题还没太明白。希望自己以后加强用M a tlab 解决实际问题的能力，合理将运筹学所学理论知识应用到实际 生活中！一、实验目的:1、掌握求解无约束最优化问题的F-R共轨梯度法，以及 约束最优化问题Wol fe简约梯度法。2、学会用MATLA B编程求解问题,并对以上方法的计算 过程和结果进行分析。二、实验原理与环节：。1、F-R共朝梯度法基本环节是在点幻处选取搜索方向使其与前一 次的搜索方向小1关于A共筑，即vd叫>=0然后从点X出发，沿方向小幻求得，(x)的极小值点X,"), 即/(Xa+,) = min f(X(k)+Ada>)A>()如此下去，得到序列X。不难求得<"叫4/'5 >=。的解为Y(a+i)_ <6->(竹注意到d“)的选取不唯一，我们可取由共辄的定义viM/i >=°可得：共规梯度法的计算过程如下:第一步:取初始向量X( 计算d<0) = r(0)= -y/(X(0) = Z?- AX(0)<-)>X= X + 4)d第欠+1步:计算r(k) =-V/1(X<k) = Z?-AX(k).心=r 3 + 01dg)<r(kAd(k>k= <dkAdk >X(k+D=x0°+4d 凶2、Wol f e简约梯度法W o If e基本计算环节：第一步：取初始可行点X。E X,给定终止误差£ >0 ，令k ：-0；第二步:设。是xk的m个最大分量的下标集，对矩阵A进行 相应分解A = (Bk , Nk)；第三步：计算 比伊)=(然，)，然后计算简约梯度喧= -困治)%代)+ “«);第四步：构造可行下降方向pk.若|pk|W£，停止迭代， 输出xk。否则进行第五步。第五步：进行有效一维搜索，求解min f(xk + tpk),得到最优解tk. 令xk+1 = xk + tkpk , k： = k +1,转入第二三、实验内容：1、(运筹学P 153页第20题)用FR法求解 min(l -xO2 + 2(x2 -xx2)2 选取初始点x。= (0,0)T, e = lot2、(运筹学P154页第25题)用Wol f e法求解以下问题:min f(xltx2) = 2x/ + 2x22 2xrx2 4x16x2s. t.选取初始可行点x° = (0,0)T,£ = IO".四、问题求解：问题1求解：(F-R法)程序代码如下：(1)主函数s yms xl x2 r;f=(l-xl)2+2*(x2 -x 1 A2)A2;X = xl, x 2 ；df = jaco b i a n (f, x);e r r o r=0. 000001；x0= 0,0，g l=sub s (df > x , x 0 )；k=0;while (norm (g 1 ) >err o r)if k=0d=-gl;elseb t a=gl* *gl/ ( g 0'*g0);d=- g 1+b t a*d0;endy = s ubs (f, x, x0+ r *d);resu 1 t=j int u if a (yz r)；result 2 =g o lden (y, r» result);st e p=result 2 ；x0=x0+step*d；g0=gl; gl=subs (df, x,xO);d 0=d;k=k+l;e nd;kxO(2)子函数进退法拟定一维搜索区间：f u n c tion r e sul t =j i n t uif a ( y , r )t 0 =0; ste p =0.0125； tl=t 0 +step; ftO=sub s (y, r , t 0);ftl = sub s (yz r, tl)；if (ftl<= f tO)s t ep=2*ste p ；t2=tl+st e p；f t2 = subs ( y , r, t2 )；while (ftl>ft 2 )tl=t 2 ； s t e p=2*s t ep;t 2 =t 1 +s t e P ；ft 1 =s u b s (y, r, tl);f t 2 =subs (y, r, t 2 );ende 1 sestep=step/ 2 ； t2=tl; tl=t2- step；f tl=s u bs(yz r,tl);while(ftl>ftO)ste p =step/2; t2=tl； t l = t 2 - s t e p； f t 1 =subs (y, r, (tl);en de ndresult= t2 ：黄金分割法进行一维搜索：fu n cti o n resu 1 t=gol d en (y, r, m)a = 0 ;b=m;e =le-5；al=a+0.382*(b-a )； f l = s u bs (y, r, al )；a 2=a+ 0 . 6 18* (b-a);f2=su b s (y, rz a 2 );whi1e abs(b-a)>=ei f f l<f2b= a 2； a2= al；f2=f 1 ： al= a + 0 , 3 82* (b-a);f l=su b s (y> r, a 1 );elsea = a 1 ；al= a 2；fl=f 2 ；a2 =a+0.618* (b-a)；f2=s u b s (y, r , a2 );enden d ；a nswer= 0 . 5*(a+ b );res ult= an s wer;运营结果如下：Name 一B epWoolM o. iix-R kdMAanrl 上 kd«u“dIcdMji.urfBjaW L KdE 医2.b3 zUb”“ 国 A »nccb«« 闺*ug8KL »n«»aXih.pm RKLI 时 cduc&c4s 8E woj gUft1.00001.0000>> FR2x0-1.00001.0000min =1.7345e-1500022Vfofkkpe一0 , x0 包。，田田田MLtjMLii一!:1:|:1匚:|一 2*2L0000.06lai n*n>1R4WSe07：14 抵.4L7MV-15 «!，乃极小值二1.7345 x极小值二1.7345 x由上图知极值点为X* = (L1)T10-15 « 0 (x*相应的理论极小值)。问题2求解：(Wo 1 f e法)程序代码如下：error=10 46;x 0=0, 0;s yms x 1 x2f = 2 * x 1A2+2* x 2A2 2 * x 1 *x 2 -4* x 1-6* x 2 ；AB=1,1,1, 0;1,5,0,1；B=l,0;0,l：N=l,l;l, 5 ;a z b =siz e ( x 0);in i ti a 1_gradi ent =gra d ient_m y ( f, x0z b)；n o rm=0;n orm0= 0 ；syms t;A=;rN= init i a 1_g r ad i e nt ( 1 ) > i n itial_gradi e nt (2)p N=rN ；pB = -pN( 1 ) +pN( 2 ) z-pN (1) -5*pN(2)；s ear c h_dire c ti o n= pN pBf or i=l： 4norm0=n o rm0+ (s e arch di r ec t ion (i) ) A2e ndtmax = 5/ 3 4;xOO= 0,0, 2,-5;x= x 00+ t *s e a r ch_d i re c t ion;xx= x (1), x ( 2 )；f_st e p = subs (f, findsym (f) , x x);F=di f f (f_ s tepz t )；solve(F, t )x _l=x0 0 +tmax* s earch_direc t i o nnorm=n o rmO；k=l；HSZ=:while ( norm>error && k< 3 )x_ll= x_l (1), x_l (2)g r ad i en t =gr a d i ent_m y (f, x_1 1 , b)r N = 1. 2 5 *g r ad i ent(l), 0 .25* g radien t ( 2 )pN=- rN(l)*x_l(3), rN(2) *x_l ( 4 )pB=- 1.2 5*pN(l) ,0.25* p N ( 2 );n e w_di r ection= pB pN;norm=0;TT=；t m a x = l；fo r i=l： 4norm=norm+ ( n e w_di r e c ti o n (i)人 2end
