最優(yōu)化方法-課程設(shè)計(jì)報(bào)告-運(yùn)用DFP算法解決無約束最優(yōu)化問題

PAGE北方民族大學(xué)課程設(shè)計(jì)報(bào)告系（部、中心）信息與計(jì)算科學(xué)學(xué)院專業(yè)信息與計(jì)算科學(xué)班級(jí)09信計(jì)（3）班小組成員課程名稱最優(yōu)化方法設(shè)計(jì)題目名稱運(yùn)用DFP算法解決無約束最優(yōu)化問題提交時(shí)間2012年6月26日成績(jī)指導(dǎo)教師 摘要變尺度法是在牛頓法的基礎(chǔ)上發(fā)展起來的，它和梯度法亦有密切關(guān)系.變尺度法避免了Newton法在每次迭代都要計(jì)算目標(biāo)函數(shù)的Hesse矩陣和它的逆矩陣而導(dǎo)致隨問題的維數(shù)增加計(jì)算量迅速增加.DFP算法是變尺度法中一個(gè)非常好的算法.DFP算法首先是1959年由Davidon提出的后經(jīng)Fletcher和Powell改進(jìn)，故名之為DFP算法，它也是求解無約束優(yōu)化問題最有效的算法之一.DFP變尺度法綜合了梯度法、牛頓法的優(yōu)點(diǎn)而又避棄它們各自的缺點(diǎn)，只需計(jì)算一階偏導(dǎo)數(shù)，無需計(jì)算二階偏導(dǎo)數(shù)及其逆矩陣，對(duì)目標(biāo)函數(shù)的初始點(diǎn)選擇均無嚴(yán)格要求，收斂速度快.本文主要分析DFP算法原理及運(yùn)用Matalb軟件編程解決實(shí)際數(shù)學(xué)問題.最后運(yùn)算結(jié)果符合計(jì)算精度且只用了一次迭代，由此可見收斂速度快.關(guān)鍵詞：Newton法變尺度法Hesse矩陣Matlab軟件目錄一、課程設(shè)計(jì)目的 1二、課程設(shè)計(jì)要求 1三、課程設(shè)計(jì)原理 1（1）變尺度法基本原理 1（2）DFP算法 3四、實(shí)驗(yàn)內(nèi)容 4五、數(shù)學(xué)建模及求解 41.DFP算法迭代步驟 42.DFP算法的流程圖 5六、程序?qū)崿F(xiàn) 5七、數(shù)值實(shí)驗(yàn)的結(jié)果與分析 8八、實(shí)驗(yàn)總結(jié)與體會(huì) 91.DFP公式恒有確切解 92.DFP算法的穩(wěn)定性 9參考文獻(xiàn) 10WORD格式--可編輯--專業(yè)資料完整版學(xué)習(xí)資料分享課程設(shè)計(jì)目的：1、掌握無約束優(yōu)化問題DFP算法的數(shù)值求解思路；2、訓(xùn)練分析DFP算法的運(yùn)算存儲(chǔ)量及收斂速度的能力，了解算法的優(yōu)缺點(diǎn)；3、通過運(yùn)用DFP算法求解實(shí)際無約束優(yōu)化問題的意義；4、熟悉應(yīng)用Matlab求解無約束最優(yōu)化問題的編程方法.課程設(shè)計(jì)要求熟悉了解DFP算法原理及求解無約束優(yōu)化問題的步驟，并運(yùn)用Matlab件編程實(shí)現(xiàn)求解問題.課程設(shè)計(jì)原理（1）變尺度法基本原理在Newton法中，基本迭代公式，其中，，，于是有···（1）其中是初始點(diǎn)，和分別是目標(biāo)函數(shù)在點(diǎn)的梯度和Hesse矩陣.為了消除這個(gè)迭代公式中的Hesse逆矩陣，可用某種近似矩陣來替換它，即構(gòu)造一個(gè)矩陣序列去逼近Hesse逆矩陣序列此時(shí)式（1）變?yōu)槭聦?shí)上，式中無非是確定了第次迭代的搜索方向，為了取得更大的靈活性，我們考慮更一般的的迭代公式(2)其中步長(zhǎng)因子通過從出發(fā)沿作直線搜索來確定.式（2）是代表很長(zhǎng)的一類迭代公式.例如，當(dāng)（單位矩陣）時(shí)，它變?yōu)樽钏傧陆捣ǖ牡?為使確實(shí)與近似并且有容易計(jì)算的特點(diǎn)，必須對(duì)附加某些條件：為保證迭代公式具有下降性質(zhì)，要求中的每一個(gè)矩陣都是對(duì)稱正定的.理由是，為使搜索方向是下降方向，只要成立即可，即成立.當(dāng)對(duì)稱正定時(shí)，此公式必然成立，從而保證式（2）具有下降性質(zhì).要求之間的迭代具有簡(jiǎn)單形式.顯然，(3)是最簡(jiǎn)單的形式了.其中稱為校正矩陣，式（3）稱為校正公式.必須滿足擬Newton條件.即：(4)為了書寫方便也記于是擬Newton條件可寫為(5)有式（3）和（5）知，必須滿足或(6)（2）DFP算法DFP校正是第一個(gè)擬牛頓校正是1959年由Davidon提出的后經(jīng)Fletcher和Powell改進(jìn)故名之為DFP算法它也是求解無約束優(yōu)化問題最有效的算法之一.DFP算法基本原理考慮如下形式的校正公式(7)其中是特定維向量，是待定常數(shù).這時(shí)，校正矩陣是.現(xiàn)在來確定.根據(jù)擬Newton條件，必須滿足（6），于是有或.滿足這個(gè)方程的待定向量和有無窮多種取法，下面是其中的一種：，注意到和都是數(shù)量，不妨取，，同時(shí)定出，.將這兩式代回（5.32）得.（8）這就是DFP校正公式.實(shí)驗(yàn)內(nèi)容采用課本P102頁例5.3和P107頁例5.4進(jìn)行數(shù)值計(jì)算；1，求，取初始點(diǎn).2，求，取初始點(diǎn).數(shù)學(xué)建模及求解1.DFP算法迭代步驟在擬Newton算法中，只要把第五步改為計(jì)算式（8）而其他不變，該算法就是DFP算法了.但是由于計(jì)算中舍去誤差的影響，特別是直線搜索不精確的影響，可能要破壞迭代矩陣的正定性，從而導(dǎo)致算法失效.為保證的正定性，采取以下重置措施：迭代次后，重置初始點(diǎn)和迭代矩陣，即以后重新迭代.已知目標(biāo)函數(shù)及其梯度，問題的維數(shù)，終止限.選定初始點(diǎn).計(jì)算，.置，，.作直線搜索；計(jì)算，.判別終止準(zhǔn)則是否滿足：若滿足，則打印，結(jié)束；否轉(zhuǎn)（5）.若，則置，，，轉(zhuǎn)（2）；否則轉(zhuǎn)（6）.計(jì)算，，，，置，轉(zhuǎn)（3）.2.DFP算法的流程圖開始開始選定，，，，終止準(zhǔn)則滿足？Y結(jié)束N？YN程序?qū)崿F(xiàn)數(shù)值實(shí)驗(yàn)的結(jié)果與分析由上述運(yùn)行結(jié)果可得出：第一題迭代一次就解得：與精確解誤差遠(yuǎn)小于，符合要求.第二題同樣迭代一次就解得：與精確解誤差遠(yuǎn)小于，符合要求.且所計(jì)算的矩陣和梯度與精確計(jì)算所得一樣，這也表明DFP算法的matalb程序完全符合要求.實(shí)驗(yàn)總結(jié)與體會(huì)DFP變尺度法綜合了梯度法、牛頓法的優(yōu)點(diǎn)而又避棄它們各自的缺點(diǎn)，只需計(jì)算一階偏導(dǎo)數(shù)，無需計(jì)算二階偏導(dǎo)數(shù)及其逆矩陣，對(duì)目標(biāo)函數(shù)的初始點(diǎn)選擇均無嚴(yán)格要求，收斂速度快，這些良好的性能已作闡述。.對(duì)于高維（維數(shù)大于50）問題被認(rèn)為是無約束極值問題最好的優(yōu)化方法之一。下面對(duì)其效能特點(diǎn)再作一些補(bǔ)充說明.1.DFP公式恒有確切解

分析DFP公式

為使變尺度矩陣恒有確定的解，必須保證該式右端第二項(xiàng)和第三項(xiàng)的分母為異于零的數(shù)，南京大學(xué)編的《最優(yōu)化方法》已證明了這兩項(xiàng)的分母均為正數(shù).

2.DFP算法的穩(wěn)定性

優(yōu)化算法的穩(wěn)定性是指每次迭代都能使目標(biāo)函數(shù)值逐次下降。在闡述構(gòu)造變尺度矩陣的基本要求中。已經(jīng)證明為保證擬牛頓方向目標(biāo)函數(shù)值下降，必須是對(duì)稱正定矩陣。南京大學(xué)編的《最優(yōu)化方法》證明了對(duì)于f(X)的一切非極小點(diǎn)處，只要矩陣對(duì)稱正定，則按DFP公式產(chǎn)生的矩陣亦為對(duì)稱正定。通常我們?nèi)〕跏甲兂叨染仃嚍閷?duì)稱正定的單位矩陣，因此隨后構(gòu)造的變尺度矩陣序列{(k=1,2,…)}必為對(duì)稱正定矩陣序列，這就從理論上保證DFP法使目標(biāo)函數(shù)值穩(wěn)定地下降。但實(shí)際上由于一維最優(yōu)搜索不可能絕對(duì)準(zhǔn)確，而且計(jì)算機(jī)也不可避免地有舍入誤差，仍有可能使變尺度矩陣的正定性遭到破壞或?qū)е缕娈悺樘岣邔?shí)際計(jì)算的穩(wěn)定性，除提高一維搜索的精度外，通常還將進(jìn)行n次(n為目標(biāo)函數(shù)