最优化实验报告

1、数值最优化算法与理论课程实验报告姓 名：周飞飞(201210020231 )张琳靖(201210020228)班级：信息与计算科学2班 指导教师：刘陶文2014年11月27日数值最优化算法与理论课程实验报告课程名称数值最优化算法与理论班级信息与计算科学2班小组成员周飞飞（201210020231）张琳婧（201210020228）实验课题拟Newton法（BFGS算法）及FR共轭梯度法求解无约束问题实验目的通过上机实验掌握最优化的实用算法的结构及性能，并用这些 算法解决实际的最优化问题，掌握一些实用的编程技巧。实验要求选用你喜欢的无约束优化的某种梯度法（最速下降法，Newton 法，拟牛顿法，

2、共轭梯度法）通过编程，上机实验对所提供的测 试问题进行测试、运行，然后提供实验报告。在实验报告中指 出你选用的算法、参数设置、终止准则、线性搜索以及实验结 果，附加你的实验心得。实验内容使用非精确Wolf-Powell线性搜索实现拟牛顿法（BFGS算法） 及FR共轭梯度法求解无约束问题，并通过Matlab软件实现算 法，观察分析实验过程，对比实验结果来进步理解两种方法 的原理及优点与缺陷。 TOC o 1-5 h z HYPERLINK l bookmark12 o Current Document 1、实验原理1 HYPERLINK l bookmark83 o Current Docume

3、nt 2、实验内容43、实验结果与分析8 HYPERLINK l bookmark118 o Current Document 4、实验心得12附录 13一、实验原理无约束问题min f (x), x e Rn这里函数广:Rn T R是连续可微的下降算法是求解无约束优化问题的一类最基本的算法。其一般步骤为：(已知近似最优解气)首先，计算下降方向4满足：Vf (xy0满足：f闵+a )。专对称正定,使得产生的拟Newton方向为下降方向；B易于计算.k(3)拟牛顿法的BFGS算法tBa;tBFGS 修正公式：B = B - k k k k +(1.1)k+1kstB s yrs该公式由：Broy

4、den-Fletcher-Goldfarb-Shanno提出，是迄今为止最好的拟牛顿修 正公式。BFGS算法：步1给定初始点 e Rn,初始对称正定矩阵B0,精度8 0.令k = 0;步2若| Vf (气)118，则得解气,算法终止.否则转下一步； TOC o 1-5 h z 步3解线性方程组*B d + Vf (x ) = 0(4.16)得解dk；k k步4由线性搜索计算步长以k;步5令x = x +以d ,若| Vf (x )|Bk+1； HYPERLINK l bookmark45 o Current Document 步6 令k := k +1,转步3.+(二)非线性共轭梯度法(FR算

5、法)共轴梯度法的简述共轴梯度法是介于最速下降法与牛顿法之间的一个方法，它仅需利用一阶导 数信息，但克服了最速下降法收敛慢的缺点，又避免了牛顿法需要存储和计算 Hessian矩阵并求逆的缺点，共轴梯度法不仅是解决大型线性方程组最有用的方 法之一，也是解大型非线性最优化最有效的算法之一。共轴梯度法最早是由 Hestenes和Stiefle(1952)提出来的，用于解正定系数矩阵的线性方程组，在这 个基础上，Fletcher和Reeves(1964)首先提出了解非线性最优化问题的共轴梯 度法。由于共轴梯度法不需要矩阵存储，且有较快的收敛速度和二次终止性等优 点，现在共轴梯度法已经广泛地应用与实际问题

6、中。共轴梯度法是一个典型的 共轴方向法，它的每一个搜索方向是互相共轴的，而这些搜索方向d仅仅是负梯 度方向与上一次迭代的搜索方向的组合，因此，存储量少，计算方便。共轴梯度法的思想Fletcher-Reeves共轴梯度法，简称FR法。共轴梯度法的基本思想是把共轴性与最速下降方法相结合，利用已知点处的梯度 构造一组共轴方向，并沿这组方向进行搜素，求出目标函数的极小点。根据共轴 方向基本性质，这种方法具有二次终止性。给定初始点xo e Rn，取初始搜索方向do =-Vf (%)，在后面的迭代中取负梯度方向和前一搜索方向的线性组合作为搜索方向即d =-Vf （x ） + p d ,k 1，其中 kk

7、k k-1Pk是待定参数，适当选取Pk，使得d：Qdki= 0。FR共轭梯度法，搜索方向的计算公式为：只 I - Vf (x ),k = 0d = 50kI-Vf (x ) + p FRd , k 1侦k k k-1(3)FR共轭梯度法算法(2.1)c II Vf (x)I|2 .XP FR = k、 由 Fletcher-Reeves(1964)提 出。k II Vf (x )I|2k -1FR算法：步1给定初始点x0 e Rn，精度 0.令d0 = -Vf (x0),令k := 0;步2若II Vf (xk)ll8，则得解xk,算法终止.否则转步3；步3由线性搜索计算步长ak；步4 令七

8、1 = x +akd；步5由(2.1)确定d ,其中。=Pfr.令k:= k +1,转步2k+1k+1k +1（三）Wolfe-Powell线搜索Wolfe-Powell线性搜索：给定常数0b 1/2,b c 取气0使得11f （x +以 d ） f （x ）+b 以 Vf （x）Td b Vf（x）Td 、k k k k 2 k k(3.1)Armijo型线性搜索的条件是 Wolfe-Powell型线性搜索中的第一个条件。Wolfe-Powell型线性搜索中的第二个条件的作用在于限制过小的步长，减少了求 解时的计算量。同时运用非精确Wolfe-Powell线性搜索保证了拟牛顿法（BFDS算法

9、）中的气矩阵对称正定。Wolfe-Powell线搜索算法：步0:若气=1满足（3.1），则取气=1;否则转下一 步1:给定常数。 0, p, P e （0,1）.令ako）是集合 1PP 的第一个不等式成立的最大值.令i ：= 0.步2:若以（）满足（3.1）中的第二个不等式 k令 P（/） = p-1a （/）.转步长3.步3:令以（i+1）是集合a （/） + 的最大值.令i := i +1.转步2.一止步.I i = 0,1,2,.中使得(3.1)中i则终止计算，并得步长以k=a，以否则，P1；（叩）-以；，）,j = 0,1,.中使得（3.1）中第一个不等式成立二、实验内容拟牛顿法程序

10、：for i=1:nn %1-nn函数依次进入运算初值准备nprob=numer(i);n,m,xk,filename=initf(nprob) ;%读初始数据 xk=factor*xk;bk=eye(n);k=0;tic; %计时开始fk=objfcn(n,m,xk,nprob);fnum=1;gk=grdfcn(n,m,xk,nprob);gnum=1;delta=norm(gk,2);迭代开始while k1000%迭代上限 1000if delta=-1.0e-14%当 dk不是充分下降时采用负梯度为搜索方向 dk=-gk;end确定步长ak%利用 Wolfe-Powell 搜索计算步

11、长alphak,fk,gk,wfnum,wgnum=wolfe2(n,m,xk,dk,fk1,gk1,nprob);%利用 Wolfe-Powell 搜索计算步长计算xk+ifnum=fnum+wfnum;gnum=gnum+wgnum;xk1=xk;xk=xk1+alphak*dk;fk=objfcn(n,m,xk,nprob);gk=grdfcn(n,m,xk,nprob);if norm(gk,2)0bks1=bk*sk*sk*bk;yks=yk*yk/yksk;bk1=bk;bk=bk1-bk1*sk*sk*bk1/(sk*bk1*sk)+yk*yk/(yk*sk);endendk=k

12、+1;End无约束问题运算结束后记录所花费时间time=toc;%终止计时if time=0.000001t(i,s)=0.0001;elset(i,s)=time;%将每个无约束问题求解时间记录End输出无约束问题的运行结果fprintf(nt%sttt%2dttt%5dtttt%5dttt%5dttt%4fn,filename,n,k,fnum,gnum,time);% 结果输出EndFR共轭梯度法for i=1:nn(1)初值准备nprob=numer(i);n,m,xk,filename=initf(nprob) ;%读初始数据xk=factor*xk;bk=eye(n);k=0;ti

13、c; %计时开始fk=objfcn(n,m,xk,nprob);fnum=1;gk=grdfcn(n,m,xk,nprob);gnum=1;delta=norm(gk,2);dk=-gk;迭代开始while k1000%迭代上限 1000if delta=teminatebreak;elsegk1=gk;fk1=fk;确定步长ak%利用 Wolfe-Powell 搜索计算步长alphak,fk,gk,wfnum,wgnum=wolfe2(n,m,xk,dk,fk1,gk1,nprob);%利用 Wolfe-Powell 搜索计算步长计算 Xk+1fnum=fnum+wfnum;gnum=gnu

14、m+wgnum;xk1=xk;xk=xk1+alphak*dk;确定下降方向d(k)fk=objfcn(n,m,xk,nprob);gk=grdfcn(n,m,xk,nprob);temk1=norm(gk1,2);temk=norm(gk,2);dk1=dk;bk=temk八2/temk1八2;dk=-gk+bk*dk1;endk=k+1;delta=norm(gk,2);End无约束问题运算结束后记录所花费时间time=toc;%终止计时if time=0.000001t(i,s)=0.0001;elset(i,s)=time;End(8)输出无约束问题的运行结果fprintf(nt%st

15、tt%2dttt%5dtttt%5dttt%5dttt%4fn,fil ename,n,k,fnum,gnum,time);End非精确Wolf-powell线性搜索function alphak1,fk2,gk2,wfnum,wgnum=wolfe2(n,m,xk,dk,fk,gk,nprob)rho1=0.8;rho2 = 0.6;sigma1=0.01;sigma2 = 0.6;% P = 0.8, P = 0.6q = 0.01,2 = 0.6fk1=fk;gk1=gk;wfnum=0;wgnum=0;%step 0alphak1=1;fk2=objfcn(n,m,xk+alphak1

16、*dk,nprob);wfnum=wfnum+1;gk2=grdfcn(n,m,xk+alphak1*dk,nprob);wgnum=wgnum+1;if fk2-fk1=sigma2*gk1*dk return;end%step 0else%step 1%i=-8;while 1if i=0alphak1=rho1八i;fk2=objfcn(n,m,xk+alphak1*dk,nprob);wfnum=wfnum+1;endif fk2-fk1sigma1*rho1八i*gk1*dk %alphak=alphak1 break;endelsei=i+1;endend%alphak1=rho1

17、八i%step 1%j=0;while 1alphak1=rho2八j*alphak1;if alphak1=0break;endgk2=grdfcn（n,m,xk+alphak1*dk,nprob）;wgnum=wgnum+1;if gk2*dk=sigma2火gk1*dk%alphak=alphak1;break;endj=j+1;endEnd（1）参数设置：Wolf-powell 搜索中的 p= 0.8,p = 0.6,b = 0.01,b = 0.6 ；拟牛顿法及共轭梯度法中相关参数：teminate=1.0e-6;factor=0.1numer=1,2,3,4,5,6,7,8,9,1

18、1,12,13,14,15,16,18,19,20,21, 22,23,24,25,26,28,29,30,31,32,33,34;（2）终止准则：Wolf-powell算法终止：当搜索到步长a满足（3.1）的第二个不等式时终k止程序；拟牛顿法及共轭梯度法算法终止：当|w3（k）|京 时，此处 = temin ate = 1.0e - 6，迭代次数k P丑冒esrq 94utui94=4T9P JToootooot eumi (乙 /淮)UIHOU=8MP i l=umub i (qojdu y(x yuiyu) uojpj=( i l=umug i (qojdu y(x yuiyu) uoj

19、 Cqo=(j-T4 ?0=N I (u) eAe=q / (x jo4Oj=(x 野凝脚段单 % (qOjdu) J4TUT=9UIU9ITJ 牛 Wu/ ( t ) jeuinu=qojdu uu:=T JOJ (iU、 , ) J Q-U T CI d J i ( j U9UIT4 44uinub44uinuj444yg9uigOHg * )(aU$耳TnS工 圣讪士湃 U 1)J Q-UT jdj T=s i (3 y:)ou=uu i (jeuinu) szts=ou 在乙*06乙8乙9乙9乙勺乙乙 SSyTSy0Sy6Ty8Ty9Ty9TyTyTySTyTTy6y8yAy9q火乙口

20、 =二 umu i 1 0=工。383 i 9 90 I=94utui94 i oi=Nnui /OT % % % qojesIISMoa-ejTOM Sutsr辛闱辩跄许桓也辛洒士湃% %if gk*dk=-1.0e-14当dk不是充分下降时采用负梯度为搜索方向dk=-gk;end%利用 Wolfe-Powell 搜索计算步长alphak,fk,gk,wfnum,wgnum=wolfe2(n,m,xk,dk,fk1,gk1,nprob )；%利用 Wolfe-Powell 搜索计算步长fnum=fnum+wfnum;gnum=gnum+wgnum;xk1=xk;xk=xk1+alphak*d

21、k;fk=objfcn(n,m,xk,nprob);gk=grdfcn(n,m,xk,nprob);if norm(gk,2)0bks1=bk*sk*sk*bk;yks=yk*yk/yksk;bk1=bk;bk=bk1-bk1*sk*sk*bk1/(sk*bk1*sk)+yk*yk/(yk*sk);endendk=k+1;endtime=toc;%终止计时if time=0.000001t(i,s)=0.0001;elset(i,s)=time;endfprintf(nt%stt%2dtt%5dttt%5dtt%5dtt%4fn,f ilename,n,k,fnum,gnum,time);en

22、ds=2;fprintf(nt*FR 共轭梯度法resultskkkkkkkkkkkkkkkkkkkkkkkkkfprintf(t*n)fprintf(tProblemttDim.ttIter.tttfnumttgnumtt timen);*for i=1:nn nprob=numer(i);n,m,xk,filename=initf(nprob) ;%读初始数据 xk=factor*xk;bk=eye(n);k=0;tic; %计时开始fk=objfcn(n,m,xk,nprob);fnum=1;gk=grdfcn(n,m,xk,nprob);gnum=1;delta=norm(gk,2);

23、dk=-gk;while k1000% 迭代上限 1000if delta=teminatebreak;elsegk1=gk;fk1=fk;%利用 Wolfe-Powell 搜索计算步长alphak,fk,gk,wfnum,wgnum=wolfe2(n,m,xk,dk,fk1,gk1,nprob );%利用 Wolfe-Powell 搜索计算步长fnum=fnum+wfnum;gnum=gnum+wgnum;xk1=xk;xk=xk1+alphak*dk;fk=objfcn(n,m,xk,nprob);gk=grdfcn(n,m,xk,nprob);temk1=norm(gk1,2);temk=norm(gk,2);dk1=dk;bk=temkA2/temk1A2;dk=-gk+bk*dk1;endk=k+1;delta=norm(gk,2);endtime=toc;%终止计时if time=0.000001t(i,s)=0.0001;elset(i,s)=time;endfprintf(nt%stt%2dtt%5dttt%5dtt%5dtt%4fn,f ilename,n,k,fnum,gnum,time