1、猶方民族丈皆礫程筱針報告系（部、中心）信息與計算科學(xué)學(xué)院專業(yè)信息與計算科學(xué)班級09信計（3）班小組成員課程名稱最優(yōu)化方法設(shè)計題目名稱 運(yùn)用DFP算法解決無約束最優(yōu)化問題提交時間2012年6月26日成 績指導(dǎo)教師摘要變尺度法是在牛頓法的基礎(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)化問題最有效的算法之一.DF

2、P變尺度法綜合了梯度法、牛頓法的優(yōu)點(diǎn)而又避棄它們各自的缺點(diǎn)，只 需計算一階偏導(dǎo)數(shù)，無需計算二階偏導(dǎo)數(shù)及其逆矩陣，對目標(biāo)函數(shù)的初始點(diǎn)選 擇均無嚴(yán)格要求，收斂速度快.本文主要分析DFP算法原理及運(yùn)用Matalb軟件編程解決實(shí)際數(shù)學(xué)問題.最 后運(yùn)算結(jié)果符合計算精度且只用了一次迭代，由此可見收斂速度快.關(guān)鍵詞：Newton法 變尺度法 Hesse矩陣 Matlab軟件一、課程設(shè)計目的1二、課程設(shè)計要求1三、課程設(shè)計原理1(1) 變尺度法基本原理1(2) DFP 算法3四、實(shí)驗內(nèi)容4五、數(shù)學(xué)建模及求解41. DFP算法迭代步驟42. DFP算法的流程圖5六、程序?qū)崿F(xiàn)5七、數(shù)值實(shí)驗的結(jié)果與分析8八、實(shí)驗總

3、結(jié)與體會91. DFP公式恒有確切解92. DFP算法的穩(wěn)定性9參考文獻(xiàn)10一、課程設(shè)計目的：1、掌握無約束優(yōu)化問題DFP算法的數(shù)值求解思路：2、訓(xùn)練分析DFP算法的運(yùn)算存儲量及收斂速度的能力，了解算法的優(yōu) 缺點(diǎn)：3、通過運(yùn)用DFP算法求解實(shí)際無約束優(yōu)化問題的意義：4、熟悉應(yīng)用Matlab求解無約束最優(yōu)化問題的編程方法.二、課程設(shè)計要求熟悉了解DFP算法原理及求解無約束優(yōu)化問題的步驟，并運(yùn)用Matlab件 編程實(shí)現(xiàn)求解問題.三、課程設(shè)計原理(I)變尺度法基本原理在Newton法中，基本迭代公式兀+1 =兀+ S人，其中，“=1,于是有蜀+嚴(yán)兀一6/ = 0,1,2(1)其中X。是初始點(diǎn)，和6分

4、別是目標(biāo)函數(shù)/(%)在點(diǎn)蜀的梯度和Hesse矩陣.為了消除這個迭代公式中的Hesse逆矩陣Gj ,可用某種近似矩陣Hk =H(Xk)來替換它，即構(gòu)造一個矩陣序列/去逼近Hesse逆矩陣序列GJ此時式(1)變?yōu)閄k=Xk-Hkgk事實(shí)上，式中P嚴(yán)-H&無非是確定了第乞次迭代的搜索方向，為了取得更大 的靈活性，我們考慮更一般的的迭代公式Xjt+i = X k gH kgk其中步長因子-通過從A；出發(fā)沿Pk=-Hkgk作直線搜索來確定.式（2）是代表 很長的一類迭代公式.例如，當(dāng)比三1 （單位矩陣）時，它變?yōu)樽钏傧陆捣ǖ牡?代公式為使確實(shí)與GJ近似并且有容易計算的特點(diǎn)，必須對附加某些條 件：第一，為

5、保證迭代公式具有下降性質(zhì)，要求中的每一個矩陣都是對稱 正定的.理由是，為使搜索方向Pk=-HkSk是下降方向，只要g；A =-gk，HkSk 0成立.當(dāng)對稱正宦時，此公式必然成立，從而保證式（2）具有下降性質(zhì).第二，要求之間的迭代具有簡單形式顯然，乞+產(chǎn)+瓦（3）是最簡單的形式了.其中瓦稱為校正矩陣，式（3）稱為校正公式.第三，必須滿足擬Newton條件.即：弘+心知一航）=（兀+廣乙）（4）為了書寫方便也記yk=g-gkSk=x-xt于是擬Newton條件可寫為H3嚴(yán)Se有式（3）和（5）知，乞必須滿足（Ht +E）兒=sk2或 Ekyk = = Hkyk (6)(2) DFP算法DFP校正

6、是第一個擬牛頓校正是1959年由Davidon提出的后經(jīng)Fletcher和 Powell改進(jìn)故名之為DFP算法它也是求解無約束優(yōu)化問題最有效的算法之一. DFP算法慕本原理考慮如下形式的校正公式弘+產(chǎn)以+/0；+幾號(7)其中Uk,Vk是特定“維向量，如，僅是待定常數(shù).這時，校正矩陣是E嚴(yán)匕UWOWM.現(xiàn)在來確左乞.根據(jù)擬Newton條件，乞必須滿足(6),于是有(akUkUl+/3kVkV：)yt=Sk-Hkyk或+ 0必匕S = S弘兒滿足這個方程的待定向量t/衣和匕有無窮多種取法，下面是其中的一種：幾=Sk，時嚴(yán)-Hy注意到兒和X兒都是數(shù)量，不妨取57, Vk=Hkyk,同時泄出s Pk

7、 ynkyk *將這兩式代回(5.32)得skyk ykHkyk(8)這就是DFP校正公式.四、實(shí)驗內(nèi)容采用課本P102頁例5.3和P107頁例5.4進(jìn)行數(shù)值計算；1, 求m町(石宀)=彳+25遲,取初始點(diǎn)Xo =2,2r.2, 求min/(“,)=時+4遲，取初始點(diǎn)%0=l,lr.五、數(shù)學(xué)建模及求解1.DFP算法迭代步驟在擬Newton算法中，只要把第五步改為計算式(8)而其他不變，該算法 就是DFP算法了.但是由于計算中舍去誤差的影響，特別是直線搜索不精確的影 響，可能要破壞迭代矩陣7/雞的正定性，從而導(dǎo)致算法失效.為保證的正左性, 采取以下重置措施：迭代” + 1次后，重置初始點(diǎn)和迭代矩

8、陣，即XQ=XnHQ = I以后重新迭代已知目標(biāo)函數(shù)/(X)及其梯度g(X),問題的維數(shù)，終止限.(1) 選定初始點(diǎn)計算f0=f(X0), g0=g(X0).(2) 置H0=Itk=0.(3) 作直線搜索俎+嚴(yán)ls(Xt,/)；計算A+1= /(G)，躺=g(G)(4) 判別終止準(zhǔn)則是否滿足：若滿足，則打印結(jié)束；否轉(zhuǎn)(5) .若k = n,則置=/o=A+1 go=g“，轉(zhuǎn)(2)：否則轉(zhuǎn)(6) .(6)計算Sk=Xg-Xk，4置k = E + l,轉(zhuǎn).2. DFP算法的流程圖六、程序?qū)崿F(xiàn)垃塔李-C: 1Dori impnt e QX：DH篇國處已|ia檔超1咱:駕cl-l.o | + | -

9、1.1 | X 癖疾 | Qfunct ion x, f, t de =dfp (xO, A, fun, gfun)LJ2E丨功能:用DFP算法求解無約束問題:min f (x)，x0是初始點(diǎn).3%輸出:x, f分別是近似最優(yōu)點(diǎn)和最優(yōu)值，計算運(yùn)行循壞次數(shù).4%A為所求問題Hess矩陣,fun為問題函數(shù)，gfun為梯度函數(shù).5 -ep=le-6;%ep為終止限精度6 -k=l ;n=length(xO);7 Hk=eye(n) ;X(:, l)=x0;8 -G(:, l)=gfun(X(:, D);9 -X(:,k+l)=X(:,k)-G(:,l)* *G(：,1)/(G(:,1)* *A*G(

10、:, 1)*G(:, 1);%卜步最速下降10 -G(:,k+l)=gfun(X(:,k+l);11 -tdc=O;%計算迭代次繳12 -while(norm(G(:, k+1)ep)13 -if k=n+l14 -xO=X(:,k+l);15 -gO=gfun(xO);16 -Hk=eye(n);k=l;17 -pk=-gO;18 -X(:,k)=xO;19 -G(:,k)=gO;20 -else21 -sk=X(:,k+l)-X(:,k);22 -yk=G(:,k+l)-G(:,k);23 -Hk=Hk+sk*sk, /(sk *yk)-Hk*yk*yk, *Hk/(yk *Hk*yk)2

11、4 -pk=-Hk*G (:, k+1);25 -k=k+l;26 一end27 -X (:, k+l)=X (:, k) + (pk, *pk/ (pk *A*pk) *pk28 -G (:, k+1) =gfun (X(:,k+1)一29 -tdc=t dc+1;30 -end31 -x=X(:,k+l) ;f=fun(x);dfp行9 列59蘆七、數(shù)值實(shí)驗的結(jié)果與分析由上述運(yùn)行結(jié)果可得出：第一題迭代一次就解得：% = 1 .Oe -015 -0.2220,-0.0664與精確解% = 0,0誤差遠(yuǎn)小于 = 10“，符合要求.第二題同樣迭代一次就解得：% = 1.0e-015*0.1110

12、,-0.0555與精確解% = 0,0誤差遠(yuǎn)小于 = 10“，符合要求.且所計算的Hk矩陣和梯度與精確計算 所得一樣，這也表明DFP算法的matalb程序完全符合要求.八、實(shí)驗總結(jié)與體會DFP變尺度法綜合了梯度法、牛頓法的優(yōu)點(diǎn)而又避棄它們各自的缺點(diǎn)，只 需計算一階偏導(dǎo)數(shù)，無需計算二階偏導(dǎo)數(shù)及其逆矩陣，對目標(biāo)函數(shù)的初始點(diǎn)選 擇均無嚴(yán)格要求，收斂速度快，這些良好的性能已作闡述。.對于高維(維數(shù)大 于50)問題被認(rèn)為是無約束極值問題最好的優(yōu)化方法之一。下面對其效能特點(diǎn) 再作一些補(bǔ)充說明.1. DFP公式恒有確切解分析DFP公式SkS HkykyHk sb y：Hy為使變尺度矩陣h*恒有確定的解，必須

13、保證該式右端第二項和第三項的分母 為異于零的數(shù)，南京大學(xué)編的最優(yōu)化方法已證明了這兩項的分母均為正數(shù).2. DFP算法的穩(wěn)定性優(yōu)化算法的穩(wěn)定性是指每次迭代都能使目標(biāo)函數(shù)值逐次下降。在闡述構(gòu)造變 尺度矩陣的基本要求中。已經(jīng)證明為保證擬牛頓方向目標(biāo)函數(shù)值下降，必須是對稱正定矩陣。南京大學(xué)編的最優(yōu)化方法證明了對于f(X)的一 切非極小點(diǎn)X*處，只要矩陣丹對稱正左，則按DFP公式產(chǎn)生的矩陣亦為 對稱正定。通常我們?nèi)〕跏甲兂叨染仃嚍閷ΨQ正左的單位矩陣/,因此隨后 10構(gòu)造的變尺度矩陣序列H& （k=l,2,”必為對稱正宦矩陣序列，這就從理論 上保證DFP法使目標(biāo)函數(shù)值穩(wěn)怎地下降。但實(shí)際上由于一維最優(yōu)搜索不可能絕 對準(zhǔn)確，而且計算機(jī)也不可避免地有舍入誤差，仍有可能使變尺度矩陣的正立 性遭到破壞或?qū)е缕娈?。為提高?shí)際計算的