第4章 優(yōu)化設(shè)計(無約束優(yōu)化-間接法)

4.4.3梯度法梯度法是求解多維無約束優(yōu)化問題的解析法之一?；谔荻仁呛瘮?shù)增大最快的方向，而負(fù)梯度則是函數(shù)下降最快的方向。沿該方向搜索，使函數(shù)值在該點附近下降最快。則梯度法就是取迭代點處的函數(shù)負(fù)梯度方向作為搜索方向，該法又稱最速下降法。梯度法的基本思想:梯度法的迭代格式：（4-38）

按上式求得負(fù)梯度方向的一個極小點，作為原問題的一個近似最優(yōu)解；若此解尚不滿足精度要求，則再以作為迭代起始點，以處的負(fù)梯度方向作為搜索方向，求得該方向的極小點，如此進(jìn)行下去，直到求得的解滿足收斂條件為止。式中為最優(yōu)步長。（1）任取初始點，選定收斂精度＞0，令。（2）計算。（3）若≤，則迭代終止，取，否則進(jìn)行步驟（4）。（4）用一維搜索求，得最優(yōu)步長。（5）令，，返回步驟（2）。梯度法的迭代步驟

解：由梯度的定義，該目標(biāo)函數(shù)的梯度為：例2-A

已知一目標(biāo)函數(shù)為，試求在點的梯度。則該函數(shù)在點

的梯度為梯度法的終止條件：

梯度法的特點：

(1)算法簡單；

(2)前后兩次迭代方向正交，所以搜索路線是呈直角鋸齒形；

(3)開始搜索時，收斂速度較快，但當(dāng)靠近極小點附近，收斂速度越來越慢，這是梯度法的較大缺點。4.4.4牛頓法

原始牛頓法和阻尼牛頓法兩種。

牛頓法也是一種解析法，它是梯度法的進(jìn)一步發(fā)展。該法的搜索方向的構(gòu)造：是根據(jù)目標(biāo)函數(shù)的負(fù)梯度和二階偏導(dǎo)數(shù)矩陣來構(gòu)造的。牛頓法分為：其迭代過程是在求目標(biāo)函數(shù)

的極小值時，先將它在點X附近作泰勒展開，并取二次近似函數(shù)式；然后求出這個二次函數(shù)的極小點，并以該極小點作為原目標(biāo)函數(shù)的極小點X*的一次近似解；

它是以二次函數(shù)來逼近原目標(biāo)函數(shù)。若此解不滿足精度要求，則可以此近似解作為下一次迭代的初始點，仿照上面的做法，求出二次近似解；照此迭代下去，直至所求出的近似極小點滿足精度要求。該算法的基本思路：現(xiàn)用二維問題來加以說明，將目標(biāo)函數(shù)

在給定點作泰勒展開，并取二次近似式：為求得二次近似式的極小點

，對上式求梯度，并令解之可求得：式中:為海森（Hessian）矩陣的逆矩陣。

在一般情況下，

不一定是二次函數(shù)，則所求得的極小點也不一定是原目標(biāo)函數(shù)的真正極小點。

但由于在點附近，函數(shù)和是近似的，因而可作為的近似極小點。

為求得滿足精度要求的近似極小點

，可將作為下一次迭代的起始點，即得（4-39）

由上式(4-39)可知，牛頓法的搜索方向為上式就是原始牛頓法的迭代公式。上式中的搜索方向稱為牛頓方向，可見原始牛頓法的步長因子恒取：，因此，原始牛頓法是一種定步長的迭代過程。

牛頓算法對于二次函數(shù)是非常有效的，迭代一步就可達(dá)到極值點，而這一步根本不需要進(jìn)行一維搜索。對于高次函數(shù)，只有當(dāng)?shù)拷鼧O值點附近，目標(biāo)函數(shù)近似二次函數(shù)時，才會保證很快收斂，否則也可能導(dǎo)致算法失敗。為了克服這一缺點，便將迭代公式（4-39）修改為：

（4-41）上式為阻尼牛頓法的迭代公式。式中，步長因子又稱阻尼因子。上式稱為阻尼牛頓法的迭代公式。式中，步長因子又稱阻尼因子。為了克服牛頓法缺點，將迭代公式（4-39）修改為：

（4-41）阻尼牛頓法

，則迭代停止，＞0，令。修正牛頓法的迭代步驟如下：（1）給定初始點，收斂精度（2）計算，若

＜

即為所求，否則進(jìn)行（3）。（3）計算

及。（4）沿

進(jìn)行一維搜索，確定最優(yōu)步長。（5）令，，返回（2）。

而且對目標(biāo)函數(shù)的要求嚴(yán)格，除了要求函數(shù)二階連續(xù)可微外，為了保證函數(shù)的穩(wěn)定下降，必須處處正定，為了能求逆陣又要求必須非奇異。

阻尼牛頓法保持了牛頓法收斂快的優(yōu)點，又不要求初始點選得很好，因而在實際應(yīng)用中取得了較好的效果。其缺點仍然是需計算及其逆陣，計算相當(dāng)復(fù)雜，程序存儲量大；4.4.5變尺度法

是在克服了梯度法收斂慢

和牛頓法計算量大

的缺點基礎(chǔ)上而發(fā)展起來的一種最有效的解析法?，F(xiàn)已得到廣泛應(yīng)用。利用牛頓法的迭代形式，但并不直接計算，而是用一個對稱正定矩陣近似地代替。它在迭代過程中不斷地改進(jìn)，最后逼近。這種算法，省去了海森矩陣的計算和求逆，使之計算量大為減少，并且還保持了牛頓法收斂快的優(yōu)點。變尺度法：在變尺度法

中，較為常用的有：變尺度法特點：●

DFP變尺度法●

BFGS變尺度法。變尺度法基本思想：1.DFP變尺度法

DFP變尺度法是最為常用的一種變尺度算法。

該算法的迭代公式為：(4-42)

式中:是變尺度矩陣，是一n×n階對稱正定矩陣，在迭代過程中,它是逐次形成并不斷修正，即從一次迭代到另一次迭代是變化的，故稱變尺度矩陣。

1.DFP變尺度法

由式(4-42)，不難看出：當(dāng)（單位矩陣）時：式(4-42)變?yōu)樘荻确ǖ牡剑划?dāng)時：式(4-42)就變?yōu)榕ｎD法的迭代公式。

由此可見，梯度法和牛頓法可以看作變尺度法的一種特例。變尺度矩陣可用下式迭代：式中，稱作校正矩陣，在DFP變尺度法中它可用下式來計算：式中:第k次迭代中前后迭代點的向量差；前后迭代點的梯度向量差。迭代開始（k＝0）規(guī)定：。

上式稱為DFP公式，由該式可以看出，變尺度矩陣的確定取決于在第k次迭代中的下列信息：不僅不需求海森矩陣及其求逆矩陣的計算，而且保持了牛頓法收斂速度快和梯度法計算簡單的優(yōu)點。●

上次的變尺度矩陣

，●

迭代點的向量差●迭代點的梯度向量差。因此，DFP變尺度法：

利用上式求得的校正矩陣代入變尺度矩陣計算公式，可得到變尺度矩陣的DFP遞推公式：上式常稱DFP公式。通過式(4-42)可確定新的搜索方向，進(jìn)行第k+1次迭代的一維搜索。

DFP變尺度法的迭代步驟為：(1)給定初始點和收斂精度ε，維數(shù)n；(2)計算梯度，取A(0)=I(單位矩陣)，置k=0，(3)構(gòu)造搜索方向(4)沿方向進(jìn)行一維搜索，求最優(yōu)步長，使得到新迭代點(5)計算，進(jìn)行收斂判斷：

若，則令，停止迭代，輸出最優(yōu)解；否則，轉(zhuǎn)下一步(6)；DFP變尺度法的計算框圖，見圖4-22。并令，轉(zhuǎn)步驟(3)。(7)計算：構(gòu)造新的變尺度矩陣和搜索方向：

(6)檢查迭代次數(shù)，若k=n，則令

，并轉(zhuǎn)入步驟(2)；若k<n，則轉(zhuǎn)下步(7)；

圖4-22DFP變尺度法的計算框圖DFP變尺度法的優(yōu)點變尺度矩陣A(K)，在開始的幾步接近于I，因而類似于梯度法，具有計算量小，函數(shù)值下降快的優(yōu)點；在最后的幾步A(K)接近于[H（X(K)）]-1,因而類似于牛頓法收斂速度快的優(yōu)點，但克服了其計算量大的缺點。2.BFGS變尺度法

計算實踐表明：由于DFP變尺度法在計算變尺度矩陣的公式中，

其分母含有近似矩陣A(k)，使之計算中容易引起數(shù)值不穩(wěn)定，甚至有可能得到奇異矩陣A(k)。

BFGS變尺度法與DFP變尺度法的迭代步驟相同，不同之點，只是校正矩陣的計算公式不一樣。

BFGS變尺度法的變尺度矩陣迭代公式仍為

為了克服DFP變尺度法計算穩(wěn)定性不夠理想的缺點，Broydon

等人在DFP法的基礎(chǔ)上提出了另一種變尺度法稱為BFGS變尺度法。但其中的校正矩陣的計算公式為

上式中，所使用的基本