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

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

2、法的迭代格式：（4-38） 按按上式上式求得負(fù)梯度方向的一個求得負(fù)梯度方向的一個極小點(diǎn)極小點(diǎn) ，作為作為的一個近似的一個近似最優(yōu)解最優(yōu)解；若此解尚不滿足若此解尚不滿足精度要求精度要求，則再以，則再以 作為作為迭迭代起始點(diǎn)代起始點(diǎn)，以，以 處的負(fù)梯度方向處的負(fù)梯度方向 作為搜索方向，作為搜索方向，求得該方向的求得該方向的極小點(diǎn)極小點(diǎn) ，如此進(jìn)行下去，直到如此進(jìn)行下去，直到求得的解求得的解滿足收斂條件滿足收斂條件為止。為止。)1( kX(1)()kf X(2)kX)1( kX)1( kX式中式中 為為最優(yōu)步長最優(yōu)步長。( )k（1）任取）任取初始點(diǎn)初始點(diǎn) ，選定收斂精度，選定收斂精度 0，令，令

3、。（2）計(jì)算）計(jì)算 。（3）若）若 ，則迭代終止，取，則迭代終止，取 ，否則，否則進(jìn)行步驟（進(jìn)行步驟（4）。）。（4）用）用一維搜索求一維搜索求 ，得最優(yōu)步長，得最優(yōu)步長 。（5）令）令 ， ，返回步，返回步驟（驟（2）。）。 0X0k kXf kXf k*XX kkSXfmin kkkkkkXfXX11 kk( )kX112212()102()42()f Xxxxf Xxxf Xx 解：解：由由梯度的定義梯度的定義，該目標(biāo)函數(shù)該目標(biāo)函數(shù)的的梯度梯度為：為：例例2-A 已知已知一目標(biāo)函數(shù)一目標(biāo)函數(shù)為為22121212()60 104f Xxxxxx x，試求試求在點(diǎn)在點(diǎn) 的梯度。的梯度。( )

4、112( )12122()102102 1 210()42()42 2 11kkxf Xxxxf Xxxf Xx 則則該函數(shù)該函數(shù)在在點(diǎn)點(diǎn)的梯度的梯度為為( )1, 2TkX梯度法的終止條件梯度法的終止條件：( )|()| kf X ()1()()2()()()() ()kkkknfXxfXfXxfXx2()()1/ 21()|() | () knkiifXfXx梯度法的特點(diǎn)：梯度法的特點(diǎn)：算法簡單；算法簡單； (2) 前后兩次迭代方向前后兩次迭代方向正交正交，所以，所以搜索路線搜索路線是是呈直角鋸齒形呈直角鋸齒形； (3) 開始搜索時，收斂速度較快，但當(dāng)靠近開始搜索時，收斂速度較快，但當(dāng)靠近

5、極極小點(diǎn)小點(diǎn)附近，收斂速度越來越慢，這是附近，收斂速度越來越慢，這是梯度法梯度法的較的較大缺點(diǎn)。大缺點(diǎn)。4.4.4 牛頓法牛頓法 和和兩種。兩種。 也是一種也是一種解析法解析法，它是，它是梯度法梯度法的進(jìn)一步發(fā)展。的進(jìn)一步發(fā)展。該法的搜索方向的構(gòu)造該法的搜索方向的構(gòu)造：是根據(jù)是根據(jù)目標(biāo)函數(shù)目標(biāo)函數(shù)的的負(fù)梯度負(fù)梯度和和二階偏導(dǎo)數(shù)矩陣二階偏導(dǎo)數(shù)矩陣來構(gòu)造的。來構(gòu)造的。牛頓法分為牛頓法分為：其其迭代過程迭代過程是在求目標(biāo)函數(shù)是在求目標(biāo)函數(shù) 的極小值時，先的極小值時，先將它在點(diǎn)將它在點(diǎn)X附近附近作泰勒展開作泰勒展開，并取，并取二次近似函數(shù)式二次近似函數(shù)式；然后求出這個二次函數(shù)的然后求出這個二次函數(shù)的極

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

7、作泰勒展開泰勒展開，并取，并取二次近似式二次近似式：( )kX( )( )( )( )( )( )()()()() ()1 ()()()2kkTkkkkf XXf Xf XXXXXH XXX ()f X為求得為求得二次近似式二次近似式 的的極小點(diǎn)極小點(diǎn) ，對上式求梯度，并令對上式求梯度，并令)(X*X( )( )( )()()()0kkkXf XH XXX 解之可解之可求得求得：*( )( )1( )()()kkkXXH Xf X式中式中: 為為海森海森（Hessian）矩陣矩陣的逆矩陣。的逆矩陣。( )1()kH X在一般情況下，在一般情況下，不一定是不一定是二次函數(shù)二次函數(shù)，則所求得的則所

8、求得的極小點(diǎn)極小點(diǎn) 也不一定是也不一定是原目標(biāo)函數(shù)原目標(biāo)函數(shù) 的的真正極小點(diǎn)真正極小點(diǎn)。但由于在但由于在點(diǎn)點(diǎn)附近，函數(shù)附近，函數(shù) 和和 是近似的，因而是近似的，因而 可作可作為為 的的近似極小點(diǎn)近似極小點(diǎn)。為為求得求得滿足精度要求的滿足精度要求的近似極小點(diǎn)近似極小點(diǎn) ，可將，可將 作為下一次迭代的作為下一次迭代的起始點(diǎn)起始點(diǎn) ，即得，即得 (1)( )( )1( )()()kkkkXXH Xf X()f X*X*X()f X)(kX()f X)1( kX()f X*X)(X（4-39） ( )( )1( )()()kkkSH Xf X 由上由上式式( (4-39) )可知，可知，為為上式就是上

9、式就是。上式中的上式中的搜索方向搜索方向稱為稱為牛頓方向牛頓方向，可見可見原始牛頓法原始牛頓法的的步長因子步長因子恒?。汉闳。?，因此，因此，原始牛頓法原始牛頓法是一種是一種定步長定步長的迭代過程。的迭代過程。)(kS( )1k對于對于二次函數(shù)二次函數(shù)是非常有效的，迭代一步就可達(dá)到是非常有效的，迭代一步就可達(dá)到極值點(diǎn)極值點(diǎn)，而這一步根本不需要進(jìn)行一維搜索。而這一步根本不需要進(jìn)行一維搜索。對于對于高次函數(shù)高次函數(shù)，只有當(dāng)?shù)拷挥挟?dāng)?shù)拷鼧O值點(diǎn)極值點(diǎn)附近，附近，目標(biāo)函數(shù)目標(biāo)函數(shù)近似近似二次函二次函數(shù)數(shù)時，才會保證時，才會保證很快收斂很快收斂，否則也可能導(dǎo)致算法失敗。，否則也可能導(dǎo)致算法失敗

10、。為了克服這一缺點(diǎn)，便將為了克服這一缺點(diǎn)，便將迭代公式迭代公式（4-39）修改為：修改為：(1)( )( )( )1( )()()kkkkkXXH Xf X)(k（4-41）上式為上式為阻尼牛頓法的迭代公式阻尼牛頓法的迭代公式。式中，式中，步長因子步長因子 又稱阻尼因子。又稱阻尼因子。上式稱為上式稱為阻尼牛頓法的迭代公式阻尼牛頓法的迭代公式。式中，。式中，步長因步長因子子 又稱阻尼因子。又稱阻尼因子。為了克服牛頓法缺點(diǎn)，將為了克服牛頓法缺點(diǎn)，將迭代公式迭代公式（4-39）修修改為：改為：)(k（4-41）(1)( )( )( )1( )()()kkkkkXXH Xf X阻尼牛頓法阻尼牛頓法 ，

11、則迭代停止，則迭代停止 ，0，令，令 。如下：如下： 0X0k kXf kXf kX 12kXf kkkXfXfS12 kS kkkkkSXX11 kk（1）給定初始點(diǎn)）給定初始點(diǎn) ，收斂精度，收斂精度（2）計(jì)算）計(jì)算，若，若 即為所求，否則進(jìn)行（即為所求，否則進(jìn)行（3）。）。（3）計(jì)算）計(jì)算 及及 。（4）沿）沿 進(jìn)行一維搜索，確定最優(yōu)步長進(jìn)行一維搜索，確定最優(yōu)步長 。（5）令）令 ，返回（，返回（2）。）。 而且對目標(biāo)函數(shù)的要求嚴(yán)格，除了要求函數(shù)而且對目標(biāo)函數(shù)的要求嚴(yán)格，除了要求函數(shù)二階連續(xù)可微二階連續(xù)可微外，外，為了保證函數(shù)的為了保證函數(shù)的穩(wěn)定下降穩(wěn)定下降， 必須處處正定，為了能求必須處

12、處正定，為了能求逆陣又要求逆陣又要求 必須必須非奇異非奇異。 阻尼牛頓法阻尼牛頓法保持了牛頓法收斂快的優(yōu)點(diǎn)，又不要求初始點(diǎn)選保持了牛頓法收斂快的優(yōu)點(diǎn)，又不要求初始點(diǎn)選得很好，因而在實(shí)際得很好，因而在實(shí)際應(yīng)用應(yīng)用中取得了較好的效果。其中取得了較好的效果。其缺點(diǎn)缺點(diǎn)仍然是仍然是需計(jì)算需計(jì)算 及其逆陣，及其逆陣，計(jì)算相當(dāng)復(fù)雜，程序存儲量大計(jì)算相當(dāng)復(fù)雜，程序存儲量大； kXH kXH kXH4.4.5 變尺度法變尺度法 是在克服了是在克服了 和和 的的缺點(diǎn)缺點(diǎn)基礎(chǔ)上而發(fā)展起來的基礎(chǔ)上而發(fā)展起來的一種最有效的解析法一種最有效的解析法?，F(xiàn)已得到廣泛應(yīng)用。現(xiàn)已得到廣泛應(yīng)用。利用利用牛頓法的迭代形式牛頓法的迭

13、代形式，但并不直接計(jì)算但并不直接計(jì)算 ，而是用一個而是用一個對稱正定矩陣對稱正定矩陣 近似地代替近似地代替 。它在它在迭代過程中迭代過程中不斷地改進(jìn)，最后逼近不斷地改進(jìn)，最后逼近 。這種算法這種算法，省去了，省去了海森矩陣海森矩陣的計(jì)算和求逆，的計(jì)算和求逆，使之使之計(jì)算量計(jì)算量大為減少，大為減少，并且還保持了并且還保持了收斂快的優(yōu)點(diǎn)。收斂快的優(yōu)點(diǎn)。( )1()kH X( )kA(*)1()H X( )1()kH X在在變尺度法變尺度法 中，較為常用的有：中，較為常用的有：變尺度法變尺度法特點(diǎn)特點(diǎn)： DFP變尺度法變尺度法 BFGS變尺度法變尺度法。變尺度法變尺度法基本思想基本思想：1. DFP

14、變尺度法變尺度法 是最為常用的一種是最為常用的一種變尺度算法變尺度算法。 為：為：(1)( )( )( )( )( )( )( )()kkkkkkkkXXSXAf X(4-42) 式中式中: 是是變尺度矩陣變尺度矩陣，是一，是一nn階階對稱對稱正定矩陣正定矩陣，在迭代過程中，在迭代過程中, ,它是它是逐次形成逐次形成并并不不斷修正斷修正，即從一次迭代到另一次迭代是變化的，即從一次迭代到另一次迭代是變化的，故稱故稱變尺度矩陣變尺度矩陣。 ( )kA1. DFP變尺度法變尺度法 由由式式(4-42)，不難看出：不難看出：當(dāng)當(dāng) （單位矩陣）時：（單位矩陣）時：式式 (4-42)變?yōu)樽優(yōu)?；?dāng)當(dāng) 時：時

15、：式式 (4-42)就變?yōu)榫妥優(yōu)椤? )kAI( )( )1()kkAH X由此可見，由此可見，和和可以看作可以看作變尺度法變尺度法的一種的一種特例特例。變尺度矩陣變尺度矩陣可用下式迭代下式迭代：(1)( )( )kkkAAA式中，式中， 稱作稱作校正矩陣校正矩陣，在在DFP變尺度法變尺度法中中它它可用可用下式下式來計(jì)算：來計(jì)算：( )kA( )( )( )( )( )( )( )( )( )( )( )( )kkTkkkTkkkTkkTkkXXAggAAXggAg式中式中:第第 k 次迭代中前后迭代點(diǎn)的次迭代中前后迭代點(diǎn)的向量差向量差 ；前后迭代點(diǎn)的前后迭代點(diǎn)的梯度向量差梯度向量差 。( )

16、(1)( )( )(1)( )()()kkkkkkXXXgf Xf X迭代開始迭代開始（k0）規(guī)定）規(guī)定： 。(0)HI 上式上式稱為稱為，由該式可以看出，由該式可以看出，變尺度矩陣變尺度矩陣 的確定的確定取決于取決于在第在第 k 次迭代中的次迭代中的下列信息下列信息：不僅不需求不僅不需求海森矩陣海森矩陣 及其及其求逆矩陣求逆矩陣的計(jì)的計(jì)算，而且保持了算，而且保持了牛頓法收斂速度快牛頓法收斂速度快和和梯度法計(jì)算簡梯度法計(jì)算簡單單的優(yōu)點(diǎn)。的優(yōu)點(diǎn)。(1)kA 上次的變尺度矩陣上次的變尺度矩陣 ， 迭代點(diǎn)的向量差迭代點(diǎn)的向量差 迭代點(diǎn)的梯度向量差迭代點(diǎn)的梯度向量差 。)(kA)(kX)( kg)()

17、(kXH因此，因此，利用利用上式上式求得的求得的校正矩陣校正矩陣 代入代入變尺度矩陣計(jì)變尺度矩陣計(jì)算公式算公式，可得到，可得到 ：( )( )(k)( )( )(k)(1)( )( )( )( )(k)( )AAATTkkkkkkTTkkkkXXggAAXggg( )kA上式上式常稱常稱DFP公式公式。通過通過式式(4-42)可可確定確定新的搜索方向新的搜索方向 ，進(jìn)行，進(jìn)行第第k+1次迭代次迭代的一維搜索。的一維搜索。 )(kS)0(X(0)()f X為：為：(1)給定給定初始點(diǎn)和收斂精度初始點(diǎn)和收斂精度，維數(shù)，維數(shù)n；(2)計(jì)算計(jì)算梯度，取梯度，取A(0) = I (單位矩陣單位矩陣)，置

18、置k =0=0，(3)構(gòu)造構(gòu)造搜索方向搜索方向( )( )( )()kkkSAf X )(kS)(k (k)( )( ) ( )( )(X)min(X)kkkkfSfS(1)()kf X(1)()kf X*(1)*(1), ()()kkXXf Xf X(4)沿沿 方向進(jìn)行方向進(jìn)行一維搜索一維搜索，求，求最優(yōu)步長最優(yōu)步長 ，使，使得到得到新迭代點(diǎn)新迭代點(diǎn)(5)計(jì)算計(jì)算 ，進(jìn)行進(jìn)行收斂判斷收斂判斷：若若 ，則令，則令 ，停止迭代，停止迭代，輸出輸出最優(yōu)解；最優(yōu)解； 否則，轉(zhuǎn)下一步否則，轉(zhuǎn)下一步(6)；(1)( )( )( )kkkkXXS( )( )( )(1), , ;kkkkXgAA(1)(

19、)(1)(1)(1)(1)()kkkkkkAAASAf X 1kk，見見圖圖4-22。并令并令 ，轉(zhuǎn)，轉(zhuǎn)步驟步驟(3)。(7)計(jì)算計(jì)算：構(gòu)造構(gòu)造新的新的變尺度矩陣變尺度矩陣和和搜索方向搜索方向：(6)檢查檢查迭代次數(shù)，若迭代次數(shù)，若k = n，則令，則令 ，并轉(zhuǎn)入，并轉(zhuǎn)入步驟步驟(2)；若若k n，則轉(zhuǎn)，則轉(zhuǎn)下步下步(7)； (0)(1)kXX圖圖4-22 DFP變尺度法變尺度法 的計(jì)算框圖的計(jì)算框圖DFP變尺度法的優(yōu)點(diǎn) 變尺度矩陣A(K) ，在開始的幾步接近于I，因而類似于梯度法，具有計(jì)算量小，函數(shù)值下降快的優(yōu)點(diǎn)； 在最后的幾步A(K) 接近于H（ X(K) ）-1,因而類似于牛頓法收斂速度快的優(yōu)點(diǎn)，但克服了其計(jì)算量大的缺點(diǎn)。2. BFGS 變尺度法變尺度法計(jì)算實(shí)踐計(jì)算實(shí)踐表明：表明：由于由于DFP變尺度法變尺度法在計(jì)算在計(jì)算變尺度矩陣變尺度矩陣的公式中，的公式中，其分母其分母含有近似矩陣含有近似矩陣 A(k)，使之計(jì)算中容易引起，使之計(jì)算中容易引起數(shù)值不穩(wěn)定數(shù)值不穩(wěn)定，甚