最優(yōu)化方法-課程設計報告-運用DFP算法解決無約束最優(yōu)化問題

1、北方民族大學課程設計報告系（部、中心） 信息與計算科學學院 專 業(yè) 信息與計算科學 班 級 09信計（3）班 小組成員 課程名稱 最優(yōu)化方法 設計題目名稱 運用DFP算法解決無約束最優(yōu)化問題 提交時間2012年6月26日 成 績 指導教師 摘要變尺度法是在牛頓法的基礎上發(fā)展起來的，它和梯度法亦有密切關系.變尺度法避免了Newton法在每次迭代都要計算目標函數(shù)的Hesse矩陣和它的逆矩陣而導致隨問題的維數(shù)增加計算量迅速增加.DFP算法是變尺度法中一個非常好的算法.DFP算法首先是1959年由Davidon提出的后經Fletcher和Powell改進，故名之為DFP算法，它也是求解無約束優(yōu)化問題最

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

3、8八、實驗總結與體會91.DFP公式恒有確切解92.DFP算法的穩(wěn)定性9參考文獻10一、 課程設計目的：1、掌握無約束優(yōu)化問題DFP算法的數(shù)值求解思路；2、訓練分析DFP算法的運算存儲量及收斂速度的能力，了解算法的優(yōu)缺點；3、通過運用DFP算法求解實際無約束優(yōu)化問題的意義；4、熟悉應用Matlab求解無約束最優(yōu)化問題的編程方法.二、 課程設計要求熟悉了解DFP算法原理及求解無約束優(yōu)化問題的步驟，并運用Matlab件編程實現(xiàn)求解問題.三、 課程設計原理 （1）變尺度法基本原理 在Newton法中，基本迭代公式，其中，于是有（1）其中是初始點，和分別是目標函數(shù)在點的梯度和Hesse矩陣.為了消除這

4、個迭代公式中的Hesse逆矩陣，可用某種近似矩陣來替換它，即構造一個矩陣序列去逼近Hesse逆矩陣序列此時式（1）變?yōu)槭聦嵣?，式中無非是確定了第次迭代的搜索方向，為了取得更大的靈活性，我們考慮更一般的的迭代公式 (2)其中步長因子通過從出發(fā)沿作直線搜索來確定.式（2）是代表很長的一類迭代公式.例如，當（單位矩陣）時，它變?yōu)樽钏傧陆捣ǖ牡?為使確實與近似并且有容易計算的特點，必須對附加某些條件：第一， 為保證迭代公式具有下降性質，要求中的每一個矩陣都是對稱正定的.理由是，為使搜索方向是下降方向，只要成立即可，即成立.當對稱正定時，此公式必然成立，從而保證式（2）具有下降性質.第二， 要求之

5、間的迭代具有簡單形式.顯然， (3)是最簡單的形式了.其中稱為校正矩陣，式（3）稱為校正公式.第三， 必須滿足擬Newton條件.即： (4)為了書寫方便也記于是擬Newton條件可寫為 (5)有式（3）和（5）知，必須滿足或 (6)（2）DFP算法DFP校正是第一個擬牛頓校正是1959年由Davidon提出的后經Fletcher和Powell改進故名之為DFP算法它也是求解無約束優(yōu)化問題最有效的算法之一.DFP算法基本原理考慮如下形式的校正公式 (7)其中是特定維向量，是待定常數(shù).這時，校正矩陣是.現(xiàn)在來確定.根據(jù)擬Newton條件，必須滿足（6），于是有或.滿足這個方程的待定向量和有無窮多

6、種取法，下面是其中的一種：，注意到和都是數(shù)量，不妨取，同時定出，.將這兩式代回（5.32）得. （8）這就是DFP校正公式.四、 實驗內容采用課本P102頁例5.3和P107頁例5.4進行數(shù)值計算；1，求，取初始點.2，求，取初始點.五、 數(shù)學建模及求解1.DFP算法迭代步驟在擬Newton算法中，只要把第五步改為計算式（8）而其他不變，該算法就是DFP算法了.但是由于計算中舍去誤差的影響，特別是直線搜索不精確的影響，可能要破壞迭代矩陣的正定性，從而導致算法失效.為保證的正定性，采取以下重置措施：迭代次后，重置初始點和迭代矩陣，即以后重新迭代.已知目標函數(shù)及其梯度，問題的維數(shù)，終止限.（1）

7、選定初始點.計算，.（2） 置，.（3） 作直線搜索；計算，.（4） 判別終止準則是否滿足：若滿足，則打印，結束；否轉（5）.（5） 若，則置，轉（2）；否則轉（6）.（6） 計算， 置，轉（3）.2.DFP算法的流程圖開始選定，終止準則滿足？Y結束N？YN六、 程序實現(xiàn)七、 數(shù)值實驗的結果與分析由上述運行結果可得出：第一題迭代一次就解得：與精確解誤差遠小于，符合要求.第二題同樣迭代一次就解得：與精確解誤差遠小于，符合要求.且所計算的矩陣和梯度與精確計算所得一樣，這也表明DFP算法的matalb程序完全符合要求.八、 實驗總結與體會DFP變尺度法綜合了梯度法、牛頓法的優(yōu)點而又避棄它們各自的缺點

8、，只需計算一階偏導數(shù)，無需計算二階偏導數(shù)及其逆矩陣，對目標函數(shù)的初始點選擇均無嚴格要求，收斂速度快，這些良好的性能已作闡述。.對于高維（維數(shù)大于50）問題被認為是無約束極值問題最好的優(yōu)化方法之一。下面對其效能特點再作一些補充說明.1.DFP公式恒有確切解分析DFP公式為使變尺度矩陣恒有確定的解，必須保證該式右端第二項和第三項的分母為異于零的數(shù)，南京大學編的最優(yōu)化方法已證明了這兩項的分母均為正數(shù).2.DFP算法的穩(wěn)定性優(yōu)化算法的穩(wěn)定性是指每次迭代都能使目標函數(shù)值逐次下降。在闡述構造變尺度矩陣的基本要求中。已經證明為保證擬牛頓方向目標函數(shù)值下降，必須是對稱正定矩陣。南京大學編的最優(yōu)化方法證明了對于f(X)的一切非極小點處，只要矩陣對稱正定，則按DFP公式產生的矩陣亦為對稱正定。通常我們取初始變尺度矩陣為對稱正定的單位矩陣，因此隨后構造的變尺度矩陣序列 (k=1,2, )必為對稱正定矩陣序列，這就從理論上保證DFP法使目標函數(shù)值穩(wěn)定地下降。但實際上由于一維最優(yōu)搜索不可能絕對準確，而且計算機也不可避免地有舍入誤差，仍有可能使變尺度矩陣的正定性遭到破壞或導致奇異。為提高實際計算的穩(wěn)定性，除提高一維搜索的精度外，通常還將進行n次(n為目標函數(shù)的維數(shù))迭代作為一個循環(huán)，將變尺度矩陣重置為單位矩陣I,并以上一循環(huán)的