強(qiáng)wolfe非線性搜索 dfp實(shí)驗(yàn)報(bào)告剖析

1、數(shù)學(xué)與計(jì)算科學(xué)學(xué)院實(shí)驗(yàn)報(bào)告實(shí)驗(yàn)項(xiàng)目名稱強(qiáng)wolfe非精確搜索+DFP所屬課程名稱最優(yōu)化實(shí)驗(yàn)類型算法編程實(shí)驗(yàn)日期2015年12月11日班級(jí)信計(jì)1302學(xué)號(hào)201353100230姓名謝劉成績(jī) 一、實(shí)驗(yàn)概述:【實(shí)驗(yàn)?zāi)康摹?:掌握無(wú)約束優(yōu)化問(wèn)DFP算法的數(shù)值求解思路;2:學(xué)習(xí)強(qiáng)wolfe非精確搜索的有關(guān)知識(shí)。3:熟悉應(yīng)用Matlab求解無(wú)約束最優(yōu)化問(wèn)題的編程方法.【實(shí)驗(yàn)原理】強(qiáng)wolfe準(zhǔn)則：由于精確線搜索往往需要計(jì)算很多的函數(shù)值和梯度值，從而耗費(fèi)很多的計(jì)算資源。特別是當(dāng)?shù)c(diǎn)原理最優(yōu)點(diǎn)時(shí)，精確搜索通常不是十分有效和合理的，對(duì)于許多優(yōu)化算法，其收斂速度并不依賴于精確搜索過(guò)程。因此，既能保證目標(biāo)函數(shù)具

2、有可接受的下降量又能使最終形成的迭代序列收斂的非精確搜索變得越來(lái)越流行，本次實(shí)驗(yàn)主要介紹里面的強(qiáng)wolfe準(zhǔn)則。wolfe準(zhǔn)則是指給定pg(0,0.5)qg(p,0.5)，求%使得下面兩個(gè)不等式同時(shí)成立：k(1.10)(1.11)(1.12)f(x+ad)agrdkkkkkk其中g(shù)=g(X)=Vf(x)，而當(dāng)(1.11)改成另一個(gè)條件時(shí)kkkIVf(x+ad)Tdl-cgTdkkkkkk這樣當(dāng)b0充分小時(shí)，可保證(1.12)變成近似精確線搜索。(1.10)和(1.12)稱強(qiáng)wolfe準(zhǔn)則。強(qiáng)wolfe準(zhǔn)則表明，由該準(zhǔn)則到新的迭代點(diǎn)x二x+d在x的某一鄰域內(nèi)且使k+1kkkk目標(biāo)函數(shù)值有一定的下

3、降量。由于gTd0，可以證明wolfe準(zhǔn)則的有限終止性，kk即步長(zhǎng)的存在性，有定理：設(shè)f(x)有下界且gTd0，令pG(0,0.5)，CG(p,0.5)，kk則存在一個(gè)區(qū)間【a,b】，0ab，使每個(gè)ga,b均滿足(1.10)和(1.12)DFP算法：變尺度法是在牛頓法的基礎(chǔ)上發(fā)展起來(lái)的，它和梯度法亦有密切關(guān)系變尺度法避免了Newton法在每次迭代都要計(jì)算目標(biāo)函數(shù)的Hesse矩陣和它的逆矩陣而導(dǎo)致隨問(wèn)題的維數(shù)增加計(jì)算量迅速增加.DFP算法是變尺度法中一個(gè)非常好的算法.DFP算法首先是1959年由Davidon提出的后經(jīng)Fletcher和Powell改進(jìn)故名之為DFP算法，它也是求解無(wú)約束優(yōu)化問(wèn)題

4、最有效的算法之一.(1)變尺度法基本原理在Newton法中，基本迭代公式X二X+1P，k+1kkk其中，t=1，P=-V2f(X)-1Vf(X)，TOC o 1-5 h zkkkk于是有X二XG-1g,k二0,1,2(1)k+1kkk其中X是初始點(diǎn)，g和G分別是目標(biāo)函數(shù)f(X)在點(diǎn)X的梯度和Hesse矩陣為0kkk了消除這個(gè)迭代公式中的Hesse逆矩陣G-1，可用某種近似矩陣H二H(X)來(lái)kkk替換它，即構(gòu)造一個(gè)矩陣序列H去逼近Hesse逆矩陣序列G-1此時(shí)式(1)變kk為X=X-Hg事實(shí)上，式中P=-Hg無(wú)非是確定了第k次迭代的搜索方k+1kkkkkk向，為了取得更大的靈活性，我們考慮更一般

5、的的迭代公式X二X-tHgk+1kkkk其中步長(zhǎng)因子kt通過(guò)從X出發(fā)沿P=-Hg.式（2）kkkk是代表很長(zhǎng)的一類迭代公式例如，當(dāng)H=I（單位矩陣）時(shí)：它變?yōu)樽钏傧陆祂法的迭代公式為使H確實(shí)與G-1近似并且有容易計(jì)算的特點(diǎn)，必須對(duì)H附加某些kkk條件：第一，為保證迭代公式具有下降性質(zhì)，要求H中的每一個(gè)矩陣都是對(duì)稱k正定的.理由是，為使搜索方向P=-Hg總下降方向.只要kkkgTP二g-THg0成立當(dāng)H對(duì)稱正定時(shí)，此公式必然成立，從而保證式（2）具有下kkkk降性質(zhì).第二，要求H之間的迭代具有簡(jiǎn)單形式顯然，kH二H+Ek+1kk是最簡(jiǎn)單的形式了其中E稱為校正矩陣，式（3）稱為校正公式.k第三，必

6、須滿足擬Newton條件即：H（g-g）=（X-X）TOC o 1-5 h zk+1k+1kk+1k為了書(shū)寫(xiě)方便也記y二g-gkk+1kS二X-Xkk+1k于是擬Newton條件可寫(xiě)為Hy二S（5）k+1kk由式（3）和（5）知，E必須滿足k(6)(H+E)y=S或Ey=S=HykkkkkkkkkDFP算法DFP校正是第一個(gè)擬牛頓校正是1959年由Davidon提出的后經(jīng)Fletcher和Powell改進(jìn)故名之為DFP算法它也是求解無(wú)約束優(yōu)化問(wèn)題最有效的算法之一.DFP算法基本原理考慮如下形式的校正公式H=H+aUUt+卩VVt(7)k+1kkkkkkk其中U,V是特定n維向量，a,kkkP,

7、是待定常數(shù).這時(shí)，校正矩陣是kE=aUUt+pVVt.現(xiàn)在來(lái)確定E.kkkkkkkk根據(jù)擬Newton條件，E必須滿足（6），k于是有(aUUt+卩VVt)y=S-Hykkkkkkkkkk或aUUT+BVVTy=S-Hykkkkkkkkkk.滿足這個(gè)方程的待定向量U和Vkk有無(wú)窮多種取法，下面是其中的一種：UUTy=SkkkkkBVVTy=_Hykkkkkk注意到UTy和VTy都是數(shù)量，不妨取U=S,V=Hykkkkk同時(shí)定出11a=，B=kSTykyTHykkkkk.將這兩式代回（5.32）得SStHyyTHH=H+kkkkkk+1kSTyyTHykkkkk（8）這就是DFP校正公式.1.D

8、FP算法迭代步驟在擬Newton算法中，只要把第五步改為計(jì)算式（8）而其他不變，該算法就是DFP算法了但是由于計(jì)算中舍去誤差的影響，特別是直線搜索不精確的影響，可能要破壞迭代矩陣H的正定性，從而導(dǎo)致算法失效為保證的H正定性，采取kk以下重置措施：迭代n+1次后，重置初始點(diǎn)和迭代矩陣，即X二X,H二I，以后0n+10重新迭代.已知目標(biāo)函數(shù)f(X)及其梯度g(X)，問(wèn)題的維數(shù)n，終止限(1)選定初始點(diǎn)計(jì)算fo=f(X0),g廠g(X0).（2）置H=I,P=_g,k=0.000（3）作直線搜索X=ls（X,P）；計(jì)算f=f（X）,g=g（X）.k+1kkk+1k+1k+1k+1（4）判別終止準(zhǔn)則是

9、否滿足：若滿足，則打印（X，/），結(jié)束；否轉(zhuǎn)（5）.k+1k+1（5）若k=n：貝I.罔X=X,f=f,g=g，轉(zhuǎn)（2）；否則轉(zhuǎn)（6）.0k+10k+10k+1（6）計(jì)算S=X-X,kk+1ky=g-g,kk+1kHH,SSTHyyTH，k+1kSTyyTHykkkkkP=Hg,k+1k+1k+1置k=k+1，轉(zhuǎn)(3).【實(shí)驗(yàn)環(huán)境】Windowsxp,matlab2007二、實(shí)驗(yàn)內(nèi)容：【實(shí)驗(yàn)方案】1:根據(jù)強(qiáng)wolfe準(zhǔn)則和dfp算法建立wolfe.m文件編寫(xiě)matlab程序代碼。2:調(diào)用函數(shù)，帶入不同的初始點(diǎn)，規(guī)定精確度，計(jì)算結(jié)果?！緦?shí)驗(yàn)過(guò)程】(實(shí)驗(yàn)步驟、記錄、數(shù)據(jù)、分析)1:代入目標(biāo)函數(shù)為f

10、=(x(1)A2-x(2)A2+(x(1)-1)A2；選取初始點(diǎn)0,0，2,2,2,0.精確度分別為1e4,1e5.【實(shí)驗(yàn)結(jié)論】(結(jié)果)得到最優(yōu)點(diǎn)是1.0000,1.0000最優(yōu)值和迭代次數(shù)：精確度1初始點(diǎn)0,02,22,01e48.3532e-013|72.9957e-014|132.8877e-013|151e58.3532e-013|72.9957e-014|132.8877e-013|15分析：DFP算法只需計(jì)算一階偏導(dǎo)數(shù)，無(wú)需計(jì)算二階偏導(dǎo)數(shù)及其逆矩陣，對(duì)目標(biāo)函數(shù)的初始點(diǎn)選擇均無(wú)嚴(yán)格要求，收斂速度快?！緦?shí)驗(yàn)小結(jié)】（收獲體會(huì)）運(yùn)用強(qiáng)wolfe準(zhǔn)則和dfp算法解決無(wú)約束問(wèn)題方便快捷，步驟不

11、用太繁瑣。解決高維函數(shù)也是不錯(cuò)的選擇。三、指導(dǎo)教師評(píng)語(yǔ)及成績(jī)：評(píng)語(yǔ)評(píng)語(yǔ)等級(jí)優(yōu)良中及格不及格1.實(shí)驗(yàn)報(bào)吿按時(shí)完成，字跡清楚,文字?jǐn)⑹隽鲿?，邏輯性?qiáng)2.實(shí)驗(yàn)方案設(shè)計(jì)合理3.實(shí)驗(yàn)過(guò)程（實(shí)驗(yàn)步驟詳細(xì)，記錄完整，數(shù)據(jù)合理，分析透徹）4實(shí)驗(yàn)結(jié)論正確.附錄1：源程序functionx,val,k=dfp(fun,gfun,xO)%功能：用DFP算法求解無(wú)約束問(wèn)題：minf(x)%輸入：x0是初始點(diǎn),fun,gfun分別是目標(biāo)函數(shù)及其梯度%輸出：x,val分別是近似最優(yōu)點(diǎn)和最優(yōu)值，k是迭代次數(shù)maxk=1e8;%給出最大迭代次數(shù)rho=0.55;sigma=0.4;epsilon=1e-5;k=0;n=len

12、gth(xO);Hk=eye(n);while(kmaxk)gk=feval(gfun,xO);%計(jì)算梯度if(norm(gk)epsilon),break;end%檢驗(yàn)終止準(zhǔn)貝Udk=-Hk*gk;%解方程組，計(jì)算搜索方向m=0;mk=0;while(m20)%用Armijo搜索求步長(zhǎng)if(feval(fun,x0+rhoAm*dk)0)Hk=Hk_(Hk*yk*yk*Hk)/(yk*Hk*yk)+(sk*sk)/(sk*yk);endk=k+1;x0=x;endval=feval(fun,x0);functionf=fun(x)f=(x(1)入2_x(2)入2+(x(1)_1)入2;fun

13、ctiongf=gfun(x)gf=4*x(1)*(x(1)入2_x(2)+2*(x(1)_1),_2*(x(1)A2_x(2);clearx0=0,0;x,val,k=dfp(fun,gfun,x0)附錄2：實(shí)驗(yàn)報(bào)告填寫(xiě)說(shuō)明1實(shí)驗(yàn)項(xiàng)目名稱：要求與實(shí)驗(yàn)教學(xué)大綱一致。2實(shí)驗(yàn)?zāi)康模耗康囊鞔_，要抓住重點(diǎn)，符合實(shí)驗(yàn)教學(xué)大綱要求。3實(shí)驗(yàn)原理：簡(jiǎn)要說(shuō)明本實(shí)驗(yàn)項(xiàng)目所涉及的理論知識(shí)。4實(shí)驗(yàn)環(huán)境：實(shí)驗(yàn)用的軟、硬件環(huán)境。5實(shí)驗(yàn)方案（思路、步驟和方法等）：這是實(shí)驗(yàn)報(bào)告極其重要的內(nèi)容。概括整個(gè)實(shí)驗(yàn)過(guò)程對(duì)于驗(yàn)證性實(shí)驗(yàn)，要寫(xiě)明依據(jù)何種原理、操作方法進(jìn)行實(shí)驗(yàn)，要寫(xiě)明需要經(jīng)過(guò)哪幾個(gè)步驟來(lái)實(shí)現(xiàn)其操作。對(duì)于設(shè)計(jì)性和綜合性實(shí)驗(yàn)，在