-無約束優(yōu)化方法-

Chapter

5多變量無約束優(yōu)化方法直接法:1變量輪換法、2原始共軛方向法

3鮑威爾（共軛方向）法。間接法:1梯度法、2牛頓法、3變尺度法。（用

）?；仡櫍?/p>

通過前面學(xué)習可知，對多維無約束優(yōu)化問題最關(guān)鍵是選搜索方向S，然后，進行一維搜索，S的選擇與迭代速度計算速率關(guān)系很大。1

梯度法基本構(gòu)思利用“函數(shù)在其負梯度方向函數(shù)值下降最快”這一局部性質(zhì)，將n維無約束最優(yōu)化問題轉(zhuǎn)化為：一系列沿目標函數(shù)的負梯度方向一維優(yōu)化問題。迭代通式K=0,1,2,…….迭代的終止條件點距準則

:或梯度準則:迭代過程(1)給定初始點,迭代精度,維數(shù).(2)置K=0(輪數(shù))(3)計算迭代點的梯度及其模.得到搜索方向S，yes,輸出，⑷檢查no，進行下一步。⑸從

出發(fā)，沿負梯度方向進行一維搜索求最優(yōu)化步長

，使⑹計算迭代新點，⑺

量k+1

k，

返回（3）進行下一次迭代計算。

迭代框圖見p96圖5-16梯度法迭代框?三、效能特點梯度法又稱最

速下降法。因為每次迭代都是沿著迭代點函數(shù)值下降最快的方向搜索。但實際上，只有在一些特殊

情況下是“最速

下降”。如圖5-18三、效能特點梯度法迭代路線很曲折，如圖5-17，收斂速度很慢，

“最速下降”只是函數(shù)在迭代點的局部性質(zhì)，從整個迭代過程看，負梯度方向并非最速下降梯度法優(yōu)點：

迭代幾何概念直觀，方法程序簡單，只求一階偏導(dǎo)數(shù)，存儲單元較少。2

牛頓法（1）原始牛頓法（2）阻尼牛頓法（1）原始牛頓法基本原理：

原目標函數(shù)用

在迭代點

鄰域展開的泰勒二次多項式

去近似代替，再以

這個二次函數(shù)的極小點作原目標函數(shù)的下一個迭代點

，重復(fù)迭代，逼近

。與二次插值法原理類似。極小點存在的必要條件：即這樣如果赫森矩陣可逆，則：取作下即原始牛頓法迭代公式（將一個優(yōu)化迭代點

）：原始牛頓法的迭代通式：搜索方向：步長恒定：缺點：對于非二次型目標函數(shù)，不能保證函數(shù)值穩(wěn)定下降。（2）阻尼牛頓法為了消除原始牛頓法對于非二次型目標函數(shù)不能保證函數(shù)值穩(wěn)定下降的弊病，對原始牛頓法加以改進：迭代方向不變，但每次迭代需沿此方向作一維搜索，求出其最優(yōu)步長因子。即：阻尼牛頓法的迭代公式：阻尼牛頓法的迭三、效能特點牛頓法是梯度法的進一步發(fā)展，梯度法利用了目標函數(shù)的一階偏導(dǎo)數(shù)，以負梯度方向作為搜

索方向，只考慮目標函數(shù)在迭代點的局部性質(zhì)。而牛頓法還利用了二階偏導(dǎo)數(shù)，考慮了梯度化 的趨勢，因此更全面地確定了搜索方向，以加快收斂速度，但H（x）及其逆陣計算工作量大，存儲單元多。

以上兩種方法各有千秋，于是就產(chǎn)生先用梯度后用牛頓法，并避開赫森矩陣的逆矩陣的繁瑣計算。即變尺度法的基本構(gòu)思。3

變尺度法基本思想梯度法：阻尼牛頓法：變尺度法：式中—最優(yōu)步長因子，由一維搜索得到階對稱矩陣，需要認為構(gòu)造，并在迭代過程中隨迭代點的位置變化而變化。對于初始點取

取單位矩陣I

,在以后的迭代過程中，當造矩陣時，不直接計算

，而構(gòu)去逼近赫森矩陣的逆矩陣。?稱為變尺度矩陣。上機作業(yè)：從1變量輪換法、2原始共軛方向法、3梯度法和4牛頓法中任選其一，用VC或VB語言編制計算程序，并用每節(jié)后的相應(yīng)例題進行驗證。時間為一周。完成后存入個人磁盤或信箱等，待通知時間檢查！嚴禁抄洗和給他人抄襲程序，一經(jīng)發(fā)現(xiàn)，二人都不給成績，并按考試作弊論。不懂或不會編程者，可在編程前請教他人或討論，自編程序，達到能解釋清楚每一條語句。的基本二、構(gòu)造變尺度矩陣要求1、

必須為對稱正定矩陣。2、形式簡單，能利用本次迭代信息以固定的格式構(gòu)造下次迭代的變尺度矩陣3必須滿足擬牛頓條件：三、DFP法變尺度矩陣若能確定

，而校正矩陣計算時必須使?jié)M足擬牛頓條件。聯(lián)立構(gòu)成一簇算法，形式不同的變尺計算度算法。DFP法校正矩陣計算：四、效能特點①恒有確切解。②DFP法搜索方向的共軛性。（有限步收斂。）③DFP解法的穩(wěn)定性。（對稱正定矩陣）理論上保證DFP法的數(shù)值穩(wěn)定下降，但實際上由于一維最優(yōu)化搜索不可能絕對準確，計算舍入誤差，仍有可能使變尺度矩陣的正定性遭到破壞而導(dǎo)致奇異。五、DFGS變尺度法70年代初提出改進算法DFGS變尺度法。雖然計算更復(fù)雜一些，但其構(gòu)造的變尺度矩陣不易變?yōu)槠娈悾蚨?/p>

DFP法在