Chapter

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

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

）。回顧：

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

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

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

出發，沿負梯度方向進行一維搜索求最優化步長

，使⑹計算迭代新點，⑺

量k+1

k，

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

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

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

情況下是“最速

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

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

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

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

原目標函數用

在迭代點

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

去近似代替，再以

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

，重復迭代，逼近

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

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

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

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

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

取單位矩陣I

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

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

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

，而校正矩陣計算時必須使滿足擬牛頓條件。聯立構成一簇算法，形式不同的變尺計算度算法。DFP法校正矩陣計算：四、效能特點①恒有確切解。②DFP法搜索方向的共軛性。（有限步收斂。）③DFP解法的穩定性。（對稱正定矩陣）理論上保證DFP法的數值穩定下降，但實際上由于一維最優化搜索不可能絕對準確，計算舍入誤差，仍有可能使變尺度矩陣的正定性遭到破壞而導致奇異。五、DFGS變尺度法70年代初提出改進算法DFGS變尺度法。雖然計算更復雜一些，但其構造的變尺度矩陣不易變為奇異，因而比

DFP法在