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

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

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

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

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

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

梯度法的特點(diǎn)：

(1)算法簡(jiǎn)單；

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

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

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

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

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

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

在給定點(diǎn)作泰勒展開(kāi)，并取二次近似式：為求得二次近似式的極小點(diǎn)

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

在一般情況下，

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

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

為求得滿足精度要求的近似極小點(diǎn)

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

由上式(4-39)可知，牛頓法的搜索方向?yàn)樯鲜骄褪窃寂ｎD法的迭代公式。上式中的搜索方向稱為牛頓方向，可見(jiàn)原始牛頓法的步長(zhǎng)因子恒?。?，因此，原始牛頓法是一種定步長(zhǎng)的迭代過(guò)程。

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

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

（4-41）阻尼牛頓法

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

＜

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

及。（4）沿

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

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

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

是在克服了梯度法收斂慢

和牛頓法計(jì)算量大

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

中，較為常用的有：變尺度法特點(diǎn)：●

DFP變尺度法●

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

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

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

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

1.DFP變尺度法

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

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

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

上次的變尺度矩陣

，●

迭代點(diǎn)的向量差●迭代點(diǎn)的梯度向量差。因此，DFP變尺度法：

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

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

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

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

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

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

計(jì)算實(shí)踐表明：由于DFP變尺度法在計(jì)算變尺度矩陣的公式中，

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

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

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

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

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

上式中，所使用的基本