強(qiáng)wolfe非線性搜索 dfp實驗報告剖析

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

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

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

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是初始點，g和G分別是目標(biāo)函數(shù)f(X)在點X的梯度和Hesse矩陣為0kkk了消除這個迭代公式中的Hesse逆矩陣G-1，可用某種近似矩陣H二H(X)來kkk替換它，即構(gòu)造一個矩陣序列H去逼近Hesse逆矩陣序列G-1此時式(1)變kk為X=X-Hg事實上，式中P=-Hg無非是確定了第k次迭代的搜索方k+1kkkkkk向，為了取得更大的靈活性，我們考慮更一般

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

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

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

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

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

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

11、用太繁瑣。解決高維函數(shù)也是不錯的選擇。三、指導(dǎo)教師評語及成績：評語評語等級優(yōu)良中及格不及格1.實驗報吿按時完成，字跡清楚,文字?jǐn)⑹隽鲿?，邏輯性?qiáng)2.實驗方案設(shè)計合理3.實驗過程（實驗步驟詳細(xì)，記錄完整，數(shù)據(jù)合理，分析透徹）4實驗結(jié)論正確.附錄1：源程序functionx,val,k=dfp(fun,gfun,xO)%功能：用DFP算法求解無約束問題：minf(x)%輸入：x0是初始點,fun,gfun分別是目標(biāo)函數(shù)及其梯度%輸出：x,val分別是近似最優(yōu)點和最優(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);%計算梯度if(norm(gk)epsilon),break;end%檢驗終止準(zhǔn)貝Udk=-Hk*gk;%解方程組，計算搜索方向m=0;mk=0;while(m20)%用Armijo搜索求步長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：實驗報告填寫說明1實驗項目名稱：要求與實驗教學(xué)大綱一致。2實驗?zāi)康模耗康囊鞔_，要抓住重點，符合實驗教學(xué)大綱要求。3實驗原理：簡要說明本實驗項目所涉及的理論知識。4實驗環(huán)境：實驗用的軟、硬件環(huán)境。5實驗方案（思路、步驟和方法等）：這是實驗報告極其重要的內(nèi)容。概括整個實驗過程對于驗證性實驗，要寫明依據(jù)何種原理、操作方法進(jìn)行實驗，要寫明需要經(jīng)過哪幾個步驟來實現(xiàn)其操作。對于設(shè)計性和綜合性實驗，在