第八章無約束優(yōu)化方法

1、第八章第八章 無約束優(yōu)化方法無約束優(yōu)化方法8-1 8-1 最速下降法（梯度法）最速下降法（梯度法）8-2 8-2 牛頓類方法牛頓類方法8-3 8-3 變尺度法變尺度法8-4 8-4 共軛方向法共軛方向法 8-5 8-5 鮑威爾方法鮑威爾方法8-6 8-6 其它方法（如坐標輪換法、單純形法）其它方法（如坐標輪換法、單純形法）第八章第八章 無約束優(yōu)化方法無約束優(yōu)化方法 第第1章所列舉的機械優(yōu)化設計問題，都是在一定的限章所列舉的機械優(yōu)化設計問題，都是在一定的限制條件下追求某一指標為最小，它們都屬于約束優(yōu)化問制條件下追求某一指標為最小，它們都屬于約束優(yōu)化問題。工程問題大都如此。題。工程問題大都如此。

2、為什么要研究無約束優(yōu)化問題為什么要研究無約束優(yōu)化問題? （1）有些實際問題，其數(shù)學模型本身就是一個無約束）有些實際問題，其數(shù)學模型本身就是一個無約束優(yōu)化問題。優(yōu)化問題。 （2）通過熟悉它的解法可以為研究約束優(yōu)化問題打下良）通過熟悉它的解法可以為研究約束優(yōu)化問題打下良好的基礎。好的基礎。 （3）約束優(yōu)化問題的求解可以通過一系列無約束優(yōu)化方）約束優(yōu)化問題的求解可以通過一系列無約束優(yōu)化方法來達到。所以無約束優(yōu)化問題的解法是優(yōu)化設計方法法來達到。所以無約束優(yōu)化問題的解法是優(yōu)化設計方法的基本組成部分，也是優(yōu)化方法的基礎。的基本組成部分，也是優(yōu)化方法的基礎。第八章第八章 無約束優(yōu)化方法無約束優(yōu)化方法 （4

3、）對于多維無約束問題來說，古典極值理論中令）對于多維無約束問題來說，古典極值理論中令一階導數(shù)為零，但要求二階可微，且要判斷海賽矩一階導數(shù)為零，但要求二階可微，且要判斷海賽矩陣為正定才能求得極小點，這種方法有理論意義，陣為正定才能求得極小點，這種方法有理論意義，但無實用價值。和一維問題一樣，若多元函數(shù)但無實用價值。和一維問題一樣，若多元函數(shù)F(X)不可微，亦無法求解。但古典極值理論是無約束優(yōu)不可微，亦無法求解。但古典極值理論是無約束優(yōu)化方法發(fā)展的基礎?；椒òl(fā)展的基礎。 第八章第八章 無約束優(yōu)化方法無約束優(yōu)化方法 目前已研究出很多種無約束優(yōu)化方法，它們的目前已研究出很多種無約束優(yōu)化方法，它們的主

4、要不同點在于主要不同點在于構造搜索方向構造搜索方向上的差別。上的差別。 min( )nfRxx（1）間接法）間接法要使用導數(shù)，如梯度法、（阻尼）要使用導數(shù)，如梯度法、（阻尼）牛頓法、變尺度法、共軛梯度法等。牛頓法、變尺度法、共軛梯度法等。（2）直接法）直接法不使用導數(shù)信息，如坐標輪換法、不使用導數(shù)信息，如坐標輪換法、鮑威爾法單純形法等。鮑威爾法單純形法等。無約束優(yōu)化問題是：無約束優(yōu)化問題是：12Tnx xxx求求n維設計變量維設計變量( )minfx使目標函數(shù)使目標函數(shù) 第八章第八章 無約束優(yōu)化方法無約束優(yōu)化方法1(0,1,2,)kkkkskxx搜索方向的構成問題乃是無約束優(yōu)化方法的關鍵。搜索

5、方向的構成問題乃是無約束優(yōu)化方法的關鍵。 用直接法尋找極小點時，不必求函數(shù)的導數(shù)，只要計用直接法尋找極小點時，不必求函數(shù)的導數(shù)，只要計算目標函數(shù)值。這類方法較適用于解決變量個數(shù)較少的算目標函數(shù)值。這類方法較適用于解決變量個數(shù)較少的（n 20）問題，一般情況下比間接法效率低。間接法除）問題，一般情況下比間接法效率低。間接法除要計算目標函數(shù)值外，還要計算目標函數(shù)的梯度，有的要計算目標函數(shù)值外，還要計算目標函數(shù)的梯度，有的還要計算其海賽矩陣。還要計算其海賽矩陣。 第八章第八章 無約束優(yōu)化方法無約束優(yōu)化方法8-1 8-1 梯度法梯度法1(0,1,2,)kkkkskxx1() (0,1,2,)kkkka

6、fkxxx 基本思想基本思想：函數(shù)的負梯度方向是函數(shù)值在該點：函數(shù)的負梯度方向是函數(shù)值在該點下降最快的方向。將下降最快的方向。將n n維問題轉化為一系列沿負梯度維問題轉化為一系列沿負梯度方向用一維搜索方法尋優(yōu)的問題，利用負梯度作為方向用一維搜索方法尋優(yōu)的問題，利用負梯度作為搜索方向，故稱最速下降法或梯度法。搜索方向，故稱最速下降法或梯度法。 ( )fx 搜索方向搜索方向s取該點的負梯度方向取該點的負梯度方向 (最速下降方最速下降方向向) ，使函數(shù)值在該點附近的范圍內(nèi)下降最快，使函數(shù)值在該點附近的范圍內(nèi)下降最快 。第八章第八章 無約束優(yōu)化方法無約束優(yōu)化方法 為了使目標函數(shù)值沿搜索方向為了使目標函

7、數(shù)值沿搜索方向 能夠獲能夠獲得最大的下降值，其步長因子得最大的下降值，其步長因子 應取一維搜索的最應取一維搜索的最佳步長。即有佳步長。即有()kf xk1()()min ()min ( )kkkkkkaaffaffa f xxxxx 根據(jù)一元函數(shù)極值的必要條件和多元復合根據(jù)一元函數(shù)極值的必要條件和多元復合函數(shù)求導公式，得函數(shù)求導公式，得 ( )()()0Tkkkkfff xxx1()()0kTkffxx1()0kTkss第八章第八章 無約束優(yōu)化方法無約束優(yōu)化方法 在最速下降法中，相在最速下降法中，相鄰兩個迭代點上的函數(shù)梯鄰兩個迭代點上的函數(shù)梯度相互垂直。而搜索方向度相互垂直。而搜索方向就是負梯

8、度方向，因此相就是負梯度方向，因此相鄰兩個搜索方向互相垂直。鄰兩個搜索方向互相垂直。這就是說在迭代點向函數(shù)這就是說在迭代點向函數(shù)極小點靠近的過程，走的極小點靠近的過程，走的是曲折的路線。形成是曲折的路線。形成“之之”字形的鋸齒現(xiàn)象，而且越字形的鋸齒現(xiàn)象，而且越接近極小點鋸齒越細。接近極小點鋸齒越細。 圖圖4-2 最速下降法的搜索路徑最速下降法的搜索路徑第八章第八章 無約束優(yōu)化方法無約束優(yōu)化方法第八章第八章 無約束優(yōu)化方法無約束優(yōu)化方法方法特點方法特點（1 1）初始點可任選，每次迭代計算量小，存儲）初始點可任選，每次迭代計算量小，存儲量少，程序簡短。即使從一個不好的初始點出量少，程序簡短。即使從

9、一個不好的初始點出發(fā)，開始的幾步迭代，目標函數(shù)值下降很快，發(fā)，開始的幾步迭代，目標函數(shù)值下降很快，然后慢慢逼近局部極小點。然后慢慢逼近局部極小點。 （2 2）任意相鄰兩點的搜索方向是正交的，它的）任意相鄰兩點的搜索方向是正交的，它的迭代路徑為繞道逼近極小點。當?shù)c接近極迭代路徑為繞道逼近極小點。當?shù)c接近極小點時，步長變得很小，越走越慢。小點時，步長變得很小，越走越慢。 第八章第八章 無約束優(yōu)化方法無約束優(yōu)化方法開始給定結束0,x()kkf dx1:min()kkkkkkkfxxdxd1kkxx*1kxx否是1kk0k s sk k第八章第八章 無約束優(yōu)化方法無約束優(yōu)化方法00102()1

10、0424()50100 xfxfxxx沿負梯度方向進行一維搜索，有沿負梯度方向進行一維搜索，有01000024()2 100fxxx0為一維搜索最佳步長，應滿足極值必要條件為一維搜索最佳步長，應滿足極值必要條件 122()min (24 )25(2100 )min ( )f x例例8 81 1 求目標函數(shù)求目標函數(shù) 的極小點。的極小點。解解 取初始點取初始點則初始點處函數(shù)值及梯度分別為則初始點處函數(shù)值及梯度分別為02,2Tx2212( )25fxxx第八章第八章 無約束優(yōu)化方法無約束優(yōu)化方法00( )8(24)5 000(2 100)0 算出一維搜索最佳步長算出一維搜索最佳步長 06260.0

11、20 030 7231 252第一次迭代設計點位置和函數(shù)值第一次迭代設計點位置和函數(shù)值 0120241.919 8772 1000.307178 5 10 x1()3.686164fx繼續(xù)作下去，經(jīng)繼續(xù)作下去，經(jīng)1010次迭代后，得到最優(yōu)解次迭代后，得到最優(yōu)解 00Tx()0fx第八章第八章 無約束優(yōu)化方法無約束優(yōu)化方法 這個問題的目標函數(shù)的等值線為一簇橢圓這個問題的目標函數(shù)的等值線為一簇橢圓, ,迭代點從迭代點從 走的是一段鋸齒形路線，見圖走的是一段鋸齒形路線，見圖4-3。0 x1 1圖圖8-3第八章第八章 無約束優(yōu)化方法無約束優(yōu)化方法將上例中目標函數(shù)將上例中目標函數(shù) 引入變換引入變換221

12、2( )25fxxx221212(,)y yyy其等值線由橢圓變成一簇同心圓。其等值線由橢圓變成一簇同心圓。 仍從仍從 即即 出發(fā)進行最速下降法出發(fā)進行最速下降法尋優(yōu)。此時：尋優(yōu)。此時：02,2Tx02,10Ty00102()10424()220yyyyy沿負梯度方向進行一維搜索：沿負梯度方向進行一維搜索：則函數(shù)則函數(shù)f(f(X X) )變?yōu)椋鹤優(yōu)椋簓1=x1, y2=5x2第八章第八章 無約束優(yōu)化方法無約束優(yōu)化方法1000000()242410201020yyy為一維搜索最佳步長，可由極值條件：為一維搜索最佳步長，可由極值條件：10022()min ()min( )( )(24 )(1020

13、 ) yyy0()0由由0260.552從而算得一步計算后設計點的位置及其目標函數(shù)：從而算得一步計算后設計點的位置及其目標函數(shù)：第八章第八章 無約束優(yōu)化方法無約束優(yōu)化方法010124010200()0 yy經(jīng)變換后，只需一次迭代，就可找到最優(yōu)解。經(jīng)變換后，只需一次迭代，就可找到最優(yōu)解。這是因為經(jīng)過尺度變換：這是因為經(jīng)過尺度變換：11225yxyx等值線由橢圓變成圓。等值線由橢圓變成圓。第八章第八章 無約束優(yōu)化方法無約束優(yōu)化方法梯度法的特點梯度法的特點 （1）理論明確，程序簡單，對初始點要求不嚴格。）理論明確，程序簡單，對初始點要求不嚴格。 （2）對一般函數(shù)而言，梯度法的收斂速度并不快，因）對一

14、般函數(shù)而言，梯度法的收斂速度并不快，因為最速下降方向僅僅是指某點的一個局部性質(zhì)。為最速下降方向僅僅是指某點的一個局部性質(zhì)。 （3）梯度法相鄰兩次搜索方向的正交性，決定了迭代）梯度法相鄰兩次搜索方向的正交性，決定了迭代全過程的搜索路線呈全過程的搜索路線呈鋸齒鋸齒狀，在遠離極小點時逼近速度狀，在遠離極小點時逼近速度較快，而在接近極小點時逼近速度較慢。較快，而在接近極小點時逼近速度較慢。 （4）梯度法的收斂速度與目標函數(shù)的性質(zhì)密切相關。）梯度法的收斂速度與目標函數(shù)的性質(zhì)密切相關。對于等值線對于等值線(面面)為同心圓（球）的目標函數(shù)，一次搜索為同心圓（球）的目標函數(shù)，一次搜索即可達到極小點。即可達到極

15、小點。第八章第八章 無約束優(yōu)化方法無約束優(yōu)化方法2、牛頓法及其改進牛頓法及其改進2( )( )()() ()1()()()2kkTkkTkkffff xxxxxxxxxxx設設 為為 的極小點的極小點 1kx( )x1()0kx( )x( )x( )f x1kx( )f x21()()()0kkkkffxxxx第八章第八章 無約束優(yōu)化方法無約束優(yōu)化方法121()()(0,1,2,)kkkkffk xxxx這就是多元函數(shù)求極值的牛頓法迭代公式。這就是多元函數(shù)求極值的牛頓法迭代公式。 對于二次函數(shù)對于二次函數(shù) ，海賽矩陣海賽矩陣H H是一個常矩陣，其中是一個常矩陣，其中各元素均為常數(shù)。因此，無論從

16、任何點出發(fā)，只各元素均為常數(shù)。因此，無論從任何點出發(fā)，只需一步就可找到極小點。需一步就可找到極小點。 例例8 82 2 求目標函數(shù)求目標函數(shù) 的極小點。的極小點。解解 取初始點取初始點2212( )25fxxx02,2Tx102010102402()()121000050ff xxxx第八章第八章 無約束優(yōu)化方法無約束優(yōu)化方法00 x()0fx 從牛頓法迭代公式的推演中可以看到，迭代點從牛頓法迭代公式的推演中可以看到，迭代點的位置是按照極值條件確定的，其中并未含有沿下的位置是按照極值條件確定的，其中并未含有沿下降方向搜尋的概念。因此對于非二次函數(shù)，如果采降方向搜尋的概念。因此對于非二次函數(shù)，如

17、果采用上述牛頓迭代公式，有時會使函數(shù)值上升用上述牛頓迭代公式，有時會使函數(shù)值上升 。阻尼牛頓法阻尼牛頓法 121()()(0,1,2,)kkkkkkkksffkxxxxxk阻尼因子阻尼因子 ，沿牛頓方向進行一維搜索的最佳沿牛頓方向進行一維搜索的最佳步長，由下式求得：步長，由下式求得： 1()()min()kkkkkkkffsfsxxx經(jīng)過一次迭代即求得極小點經(jīng)過一次迭代即求得極小點函數(shù)極小值函數(shù)極小值第八章第八章 無約束優(yōu)化方法無約束優(yōu)化方法開始給定結束0,x21()()kkkff dxx1:min()kkkkkkkfxxdxd1kkxx*1kxx否是1kk0k 阻尼牛頓法程序框圖阻尼牛頓法程

18、序框圖第八章第八章 無約束優(yōu)化方法無約束優(yōu)化方法方法特點方法特點 （1） 初始點應選在初始點應選在X*附近，有一定難度；附近，有一定難度； （2） 盡管每次迭代都不會是函數(shù)值上升，但不能保證每次下降盡管每次迭代都不會是函數(shù)值上升，但不能保證每次下降 ； （3） 若迭代點的海賽矩陣為奇異，則無法求逆矩陣，不能構造若迭代點的海賽矩陣為奇異，則無法求逆矩陣，不能構造牛頓法方向；牛頓法方向； （4） 不僅要計算梯度，還要求海賽矩陣及其逆矩陣，計算量和不僅要計算梯度，還要求海賽矩陣及其逆矩陣，計算量和存儲量大。此外，對于二階不可微的存儲量大。此外，對于二階不可微的F(X)也不適用。也不適用。 雖然阻尼牛

19、頓法有上述缺點，但在特定條件下它具有收斂雖然阻尼牛頓法有上述缺點，但在特定條件下它具有收斂最快的優(yōu)點，并為其他的算法提供了思路和理論依據(jù)。最快的優(yōu)點，并為其他的算法提供了思路和理論依據(jù)。第八章第八章 無約束優(yōu)化方法無約束優(yōu)化方法1(0,1,2,)kkkkskxx1() (0,1,2,)kkkkafkxxx121()()(0,1,2,)kkkkffk xxxx121()()(0,1,2,)kkkkkffkxxxx一般迭代式：一般迭代式：梯度法：梯度法：牛頓法：牛頓法：阻尼牛頓法：阻尼牛頓法：梯度法與牛頓法：梯度法與牛頓法：1()kkkkkfxxAx第八章第八章 無約束優(yōu)化方法無約束優(yōu)化方法8-3

20、 變尺度法變尺度法 DFP變尺度法首先有戴維頓（變尺度法首先有戴維頓（Davidon）與）與1959年提出，又于年提出，又于1963年由弗萊徹（年由弗萊徹（Fletcher）和鮑維爾加）和鮑維爾加以發(fā)展和完善，成為現(xiàn)代公認的較好的算法之一。以發(fā)展和完善，成為現(xiàn)代公認的較好的算法之一。 DFP法法（Davidon-Fletcher-Powell)是基于牛頓是基于牛頓法的思想又作了重要改進。這種算法僅用到梯度，不法的思想又作了重要改進。這種算法僅用到梯度，不必計算海賽陣及其逆矩陣，但又能使搜索方向逐漸逼必計算海賽陣及其逆矩陣，但又能使搜索方向逐漸逼近牛頓方向，具有較快的收斂速度。近牛頓方向，具有較

21、快的收斂速度。 第八章第八章 無約束優(yōu)化方法無約束優(yōu)化方法基本思想基本思想 變量的尺度變換是放大或縮小各個坐標。通過變量的尺度變換是放大或縮小各個坐標。通過尺尺度變換可以把函數(shù)的偏心程度降到最低限度。度變換可以把函數(shù)的偏心程度降到最低限度。 值時值時 ,需要進行需要進行10次迭代才能達到極小點次迭代才能達到極小點0,0Tx 如作變換如作變換 y1=x1, y2=5x2把把 的尺度放大的尺度放大5倍，則目標函數(shù)等值線由一簇倍，則目標函數(shù)等值線由一簇橢圓變成一簇同心圓。橢圓變成一簇同心圓。x2例如在用最速下降法求例如在用最速下降法求 極小極小221212(,)25f第八章第八章 無約束優(yōu)化方法無約

22、束優(yōu)化方法221212(,)y yyy 消除了函數(shù)的偏心，用最速下降法只需一次迭消除了函數(shù)的偏心，用最速下降法只需一次迭代即可求得極小點。代即可求得極小點。 梯度法構造簡單，只用到一階偏導數(shù)，計算量小，梯度法構造簡單，只用到一階偏導數(shù)，計算量小，初始點可任選，且開始幾次迭代，目標函數(shù)值下降很初始點可任選，且開始幾次迭代，目標函數(shù)值下降很快；其主要缺點是迭代點接近快；其主要缺點是迭代點接近X*時，即使對二次正時，即使對二次正定函數(shù)收斂也非常慢。定函數(shù)收斂也非常慢。 牛頓法收斂很快，對于二次函數(shù)只需迭代一次便牛頓法收斂很快，對于二次函數(shù)只需迭代一次便達到最優(yōu)點，對非二次函數(shù)也能較快迭代到最優(yōu)點，達

23、到最優(yōu)點，對非二次函數(shù)也能較快迭代到最優(yōu)點，但要計算二階偏導數(shù)矩陣及其逆陣，對維數(shù)較高的優(yōu)但要計算二階偏導數(shù)矩陣及其逆陣，對維數(shù)較高的優(yōu)化問題，其計算工作和存儲量都太大?；瘑栴}，其計算工作和存儲量都太大。能不能將兩種算法的優(yōu)點綜合起來，揚長避短？能不能將兩種算法的優(yōu)點綜合起來，揚長避短？第八章第八章 無約束優(yōu)化方法無約束優(yōu)化方法1()kkkkkfxxAxAk 是需要構造是需要構造nn的一個對稱方陣的一個對稱方陣 ，如如Ak=I, 則得到梯度法則得到梯度法 ；21()kkf Ax 則得到阻尼牛頓法則得到阻尼牛頓法 ；如如當矩陣當矩陣Ak 不斷地迭代而能很好地逼近不斷地迭代而能很好地逼近 21()

24、kfx時，就可以不再需要計算二階導數(shù)。時，就可以不再需要計算二階導數(shù)。 變尺度法的關鍵在于尺度矩陣變尺度法的關鍵在于尺度矩陣Ak的產(chǎn)生的產(chǎn)生 。對于二次函數(shù)對于二次函數(shù):1( )2TTfxx Gxb xc第八章第八章 無約束優(yōu)化方法無約束優(yōu)化方法xQx進行尺度變換進行尺度變換在新的坐標系中，函數(shù)在新的坐標系中，函數(shù)f(x)的二次項變?yōu)椋旱亩雾椬優(yōu)椋?122TTTx Gxx Q GQx目的：減少二次項的偏心目的：減少二次項的偏心如如G是正定，則總存在矩陣是正定，則總存在矩陣Q，使得：，使得：TQ GQI 用矩陣用矩陣Q-1右乘等式兩邊，得：右乘等式兩邊，得：用矩陣用矩陣Q左乘等式兩邊，得：左乘

25、等式兩邊，得：1TQ GQTQQ GI所以所以1TQQG上式說明：二次函數(shù)矩陣上式說明：二次函數(shù)矩陣G的逆陣，可以通過尺度變換的逆陣，可以通過尺度變換矩陣矩陣Q來求得。來求得。第八章第八章 無約束優(yōu)化方法無約束優(yōu)化方法121()()(0,1,2,)kkkkkffkxxxx牛頓迭代公式：牛頓迭代公式：1()(0,1,2,)kkTkkQQfkxxx記：記：TAQQ搜索方向：搜索方向：1()(0,1,2,)kkksfk Ax迭代公式：迭代公式：1()(0,1,2,)kkkkkfkxxAxA A 稱為變尺度矩陣稱為變尺度矩陣第八章第八章 無約束優(yōu)化方法無約束優(yōu)化方法2212( )25fxxx在例在例8

26、2中中122121222011( )2505022Txfxxx xxxx Gx20050G如取如取102105 2Q11002010221050101005 25 2TQ GQI第八章第八章 無約束優(yōu)化方法無約束優(yōu)化方法求得：求得：1111000222111000505 25 2TGQQ第八章第八章 無約束優(yōu)化方法無約束優(yōu)化方法構造尺度矩陣構造尺度矩陣Ak從初始矩陣從初始矩陣A0=I(單位矩陣單位矩陣)開始，通過對公式開始，通過對公式 1kkkAAA因此，一旦達到最優(yōu)點附近，就可望達到牛頓法因此，一旦達到最優(yōu)點附近，就可望達到牛頓法的收斂速度的收斂速度。1）DFP法（法（Davidon-Fle

27、tcher-Powell)TkkkkkTkkkTkkTkkxxAggAAxggAg111()()kkkkkkkkffgggxxxxx式中式中中修正矩陣中修正矩陣 的不斷修正，在迭代中逐步逼近于的不斷修正，在迭代中逐步逼近于 kA1()kGx。第八章第八章 無約束優(yōu)化方法無約束優(yōu)化方法2）BFGS算法算法(Broyden-Fletcher-Gold frob-(Broyden-Fletcher-Gold frob-ShannoShanno ) DFP算法由于舍入誤差和一維搜索不精確，有算法由于舍入誤差和一維搜索不精確，有可能導致構造矩陣的正定性遭到破壞，以至算法可能導致構造矩陣的正定性遭到破壞，

28、以至算法不穩(wěn)定。不穩(wěn)定。BFGS算法對于維數(shù)較高問題具有更好的算法對于維數(shù)較高問題具有更好的穩(wěn)定性。穩(wěn)定性。 1 kkTkTkkkkkTkTkkTkkkkTkkTxxgAgAxxxgxgAgxxgA第八章第八章 無約束優(yōu)化方法無約束優(yōu)化方法開始給定結束0,x000()f gxAI1:min()kkkkkkkfxxdxd1kkxx*1kxx否是1kkkn11111()kkkkkkkkf gxgggxxx11kkk AAA01kxx0k kkk dA g是否第八章第八章 無約束優(yōu)化方法無約束優(yōu)化方法例例8-3： 用用DFP算法求下列問題的極值：算法求下列問題的極值：221212112( ,)242

29、f x xxxxx xl解：解： 1）取初始點）取初始點 ，為了按，為了按DFP法構造第法構造第一次搜尋方向一次搜尋方向d0，需計算初始點處的梯度，需計算初始點處的梯度01 1Tx01200212244()422xxfxxxgx取初始變尺度矩陣為單位矩陣取初始變尺度矩陣為單位矩陣A0=I，則第一次，則第一次搜尋方向為搜尋方向為 00010440122 dA g第八章第八章 無約束優(yōu)化方法無約束優(yōu)化方法 沿沿d0方向進行一維搜索，得方向進行一維搜索，得010000014141212 xxd為一維搜索最佳步長，應滿足為一維搜索最佳步長，應滿足01002()min()min(40203)ffxxd得

30、得:00.25120.5x,2）再按）再按DFP法構造點法構造點x1處的搜尋方向處的搜尋方向d1，需計算，需計算1121212241422xxxxxg第八章第八章 無約束優(yōu)化方法無約束優(yōu)化方法010143224ggg0102110.510.5 xxx代入校正公式代入校正公式000000000000TTTTxxAggAAxggAg1310.5340.543310.53444=第八章第八章 無約束優(yōu)化方法無約束優(yōu)化方法100AAA21191010.5912112550010.50.251216194152550100=第二次搜尋方向為第二次搜尋方向為1118665 dA g再沿再沿d1進行一維搜索

31、，得進行一維搜索，得12111182560.55xxd第八章第八章 無約束優(yōu)化方法無約束優(yōu)化方法為一維搜索最佳步長，應滿足為一維搜索最佳步長，應滿足12112811()min()min(4)52ffxxd154242 x,得得3）判斷判斷x2是否為極值點是否為極值點 梯度梯度: : 2122212240()420 xxfxx xx海賽矩陣海賽矩陣 :2222()24fx第八章第八章 無約束優(yōu)化方法無約束優(yōu)化方法梯度為零向量梯度為零向量, ,海賽矩陣正定?？梢婞c滿足極值海賽矩陣正定。可見點滿足極值充要條件，因此為極小點。充要條件，因此為極小點。 *242Txx*()8f x第八章第八章 無約束優(yōu)

32、化方法無約束優(yōu)化方法8-4 共軛方向法共軛方向法 l1.共共軛方向：軛方向：l 設設G為為nn階實對稱正定矩陣，如果有兩個階實對稱正定矩陣，如果有兩個n維向量維向量d0和和d1滿足滿足 ，則稱向量，則稱向量d0與與d1 關于矩陣關于矩陣G共共軛。軛。01()0TdGd當當G為單位矩陣時為單位矩陣時，01()0Tdd假設目標函數(shù)假設目標函數(shù)f(x) 在極值點附近的二次近似函數(shù)為在極值點附近的二次近似函數(shù)為1( )2TfTxx Gxb xc對二維情況對二維情況任選取初始點任選取初始點x0沿某個下降方向沿某個下降方向d d0 0作一維搜索，得作一維搜索，得x11000 xxd第八章第八章 無約束優(yōu)化

33、方法無約束優(yōu)化方法 因為因為 是沿是沿d0方向搜索的最佳步長，即在點方向搜索的最佳步長，即在點x1處函數(shù)處函數(shù)f（x）沿方向）沿方向d0的方向導數(shù)為零?？紤]到點的方向導數(shù)為零。考慮到點x1處方向導數(shù)與梯度之間的關系，故有處方向導數(shù)與梯度之間的關系，故有01100()0Tff xxdd如果按最速下降法，選擇負梯度方向如果按最速下降法，選擇負梯度方向 為搜為搜索方向，則將發(fā)生鋸齒現(xiàn)象索方向，則將發(fā)生鋸齒現(xiàn)象 。1()fx 取下一次的迭代搜索方向取下一次的迭代搜索方向d1直指極小點直指極小點x* *。第八章第八章 無約束優(yōu)化方法無約束優(yōu)化方法0d0 x0 x1x*1 11d11()fxd1第八章第八

34、章 無約束優(yōu)化方法無約束優(yōu)化方法 如果能夠選定這樣的搜索方向，那么對于二元二次如果能夠選定這樣的搜索方向，那么對于二元二次函數(shù)只需順次進行函數(shù)只需順次進行d0、d1兩次直線搜索就可以求到兩次直線搜索就可以求到極小點極小點x* * ，即有，即有111xxd那么這樣的那么這樣的d1方向應該滿足什么條件呢方向應該滿足什么條件呢 ? ?對于前述的二次函數(shù)對于前述的二次函數(shù): :1( )2TfTxx Gxb xc當當 時，時，1xx10 x* *是是f( (x) )極小點，應滿足極值必要條件，故有極小點，應滿足極值必要條件，故有()0fxGxb111111()()()ff xG xdbxGd0將等式兩邊

35、同時左乘將等式兩邊同時左乘 得得：0()Td01()0TdGd11()fxGxb有有第八章第八章 無約束優(yōu)化方法無約束優(yōu)化方法01()0TdGd 就是使就是使d1直指極小點直指極小點x* * ， d1所必須滿足的條件所必須滿足的條件 。兩個向量兩個向量d0和和d1稱為稱為G的共軛向量，或稱的共軛向量，或稱d0和和d1對對G是共軛方向。是共軛方向。 2.2.共軛方向的性質(zhì)共軛方向的性質(zhì)性質(zhì)性質(zhì)1 1 若非零向量系若非零向量系d0, ,d1, ,d2,dm-1是對是對G共軛，共軛，則這則這m個向量是線性無關的。個向量是線性無關的。性質(zhì)性質(zhì)2 2 在在n維空間中互相共軛的非零向量的個數(shù)維空間中互相共

36、軛的非零向量的個數(shù)不超過不超過n。 性質(zhì)性質(zhì)3 3 從任意初始點出發(fā)，順次沿從任意初始點出發(fā)，順次沿n個個G的共軛方的共軛方向向d0, ,d1, , d2,進行一維搜索，最多經(jīng)過進行一維搜索，最多經(jīng)過n次迭代就次迭代就可以找到的二次函數(shù)可以找到的二次函數(shù)f( (x) )極小點。極小點。 021()( )0Tfdx d第八章第八章 無約束優(yōu)化方法無約束優(yōu)化方法開始給定結束00,x d1:min()kkkkkkkfxxdxd1kkxx*1kxx否是1kk0k 提供新的共軛方向關鍵：新的共關鍵：新的共軛方向軛方向確定確定第八章第八章 無約束優(yōu)化方法無約束優(yōu)化方法 在無約束方法中許多算法都是以共軛方向

37、在無約束方法中許多算法都是以共軛方向作為搜索方向，它們具有許多特點。根據(jù)構造作為搜索方向，它們具有許多特點。根據(jù)構造共軛方向的原理不同，可以形成不同的共軛方共軛方向的原理不同，可以形成不同的共軛方向法。向法。 第八章第八章 無約束優(yōu)化方法無約束優(yōu)化方法3.3.共軛梯度法共軛梯度法 共軛梯度法是共軛方向法中的一種，該方法中共軛梯度法是共軛方向法中的一種，該方法中每一個共軛向量都是依賴于迭代點處的負梯度每一個共軛向量都是依賴于迭代點處的負梯度而構造出來。而構造出來。 從從xk出發(fā)，沿負梯度方向作一維搜索出發(fā)，沿負梯度方向作一維搜索:1(0,1,2,)kkkkkxxd()kkf dx設與設與dk共共

38、軛的下一個方向軛的下一個方向dk+1由由dk和點和點xk+1的負梯的負梯度的線形組合構成，即：度的線形組合構成，即：11()kkkkf dxd21()( )0kTkfdx d共軛條件：共軛條件：第八章第八章 無約束優(yōu)化方法無約束優(yōu)化方法 則：則：21()( )()0kTkkkfff xxxd解得：解得：212()()()()()()kTkkkkTkkffffffxxxxxx令令1( )2TfTxx Gxb xc為函數(shù)的泰勒二次展開式為函數(shù)的泰勒二次展開式()kkfxGxb則則11()kkfxGxb上兩式相減，并代入上兩式相減，并代入1kkkkxxd1()()kkkkff Gdxx第八章第八章

39、無約束優(yōu)化方法無約束優(yōu)化方法1()()kkkkff Gdxx將式將式11()kkkkf dxd與式與式轉置兩邊相乘，應用轉置兩邊相乘，應用共軛條件共軛條件得：得：11()() ()()0kkTkkkffff xxxx21112()()()()()()kkTkkkTkkffffffxxxxxx因此因此11()kkkkf dxd212()()kkkffxx1(0,1,2,)kkkkkxxd第八章第八章 無約束優(yōu)化方法無約束優(yōu)化方法第八章第八章 無約束優(yōu)化方法無約束優(yōu)化方法2212112( )242fxxxx xx，已知初始點，已知初始點1,11,1T Tl解：解： 1）第一次沿負梯度方向搜尋）第一

40、次沿負梯度方向搜尋l計算初始點處的梯度計算初始點處的梯度0120212244()422xxfxxxx010000014141212 xxd為一維搜索最佳步長，應滿足為一維搜索最佳步長，應滿足1002()min()min(40203)ffxxdl迭代精度迭代精度 。 0.001第八章第八章 無約束優(yōu)化方法無約束優(yōu)化方法得得:00.25120.5x2）第二次迭代：）第二次迭代：21200()50.2520()ffxx11()2fx11002()1.5f dxd21122220.51.50.5 1.5xxd代入目標函數(shù)代入目標函數(shù)22( )(22 )2(0.5 1.5 )2(22 )(0.5 1.5

41、 )4(22 )( )f x 第八章第八章 無約束優(yōu)化方法無約束優(yōu)化方法得得1因因2()0fx收斂。收斂。( )0 由由22240,()8,()20ff xxx從而有：從而有：第八章第八章 無約束優(yōu)化方法無約束優(yōu)化方法8-5 鮑威爾方法鮑威爾方法 鮑威爾法是以共軛方向為基礎的收斂鮑威爾法是以共軛方向為基礎的收斂較快的直接法之一，是一種十分有效的算較快的直接法之一，是一種十分有效的算法。法。1964年，鮑維爾提出這種算法，其基年，鮑維爾提出這種算法，其基本思想是直接利用迭代點的目標函數(shù)值來本思想是直接利用迭代點的目標函數(shù)值來構造共軛方向，然后從任一初始點開始，構造共軛方向，然后從任一初始點開始，

42、逐次沿共軛方向作一維搜索求極小點。并逐次沿共軛方向作一維搜索求極小點。并在以后的實踐中進行了改進。在以后的實踐中進行了改進。 第八章第八章 無約束優(yōu)化方法無約束優(yōu)化方法1()2TfTxx G xbxc對函數(shù)：對函數(shù)：基本思想基本思想：在不用導數(shù)的前提下，在迭代中逐次構造：在不用導數(shù)的前提下，在迭代中逐次構造G的共軛方向。的共軛方向。 1.1.共軛方向的生成共軛方向的生成jjkkkdd ddjgg gk+1xxk+1設設xk, , xk+1為從不同為從不同點出發(fā)，沿同一方向點出發(fā)，沿同一方向dj j進行一維搜索而到進行一維搜索而到的兩個極小點。的兩個極小點。 第八章第八章 無約束優(yōu)化方法無約束優(yōu)

43、化方法 梯度和等值面相垂直的性質(zhì)梯度和等值面相垂直的性質(zhì), , dj j和和 xk, , xk+1兩點兩點處的梯度處的梯度gk, ,gk+1之間存在關系之間存在關系: :1()0,()0jTkjTkdgdg另一方面，對于上述二次函數(shù)，其另一方面，對于上述二次函數(shù)，其xk, , xk+1兩點處的兩點處的梯度可表示為梯度可表示為: :11,kkkkgGxbgGxb因而有因而有11() ()()()0jTkkjTkkdggdG xx1kkkdxx取取這說明只要沿這說明只要沿dj j方向分別對函數(shù)作兩次一維搜索，方向分別對函數(shù)作兩次一維搜索，得到兩個極小點得到兩個極小點xk和和xk+1 ，那么這兩點的

44、連線所給，那么這兩點的連線所給出的方向出的方向dk k就是與就是與dj j一起對一起對G共軛的方向。共軛的方向。第八章第八章 無約束優(yōu)化方法無約束優(yōu)化方法2.2.基本算法基本算法 二維情況描述鮑威爾的基本算法二維情況描述鮑威爾的基本算法: : 1 1）任選一初始點）任選一初始點x0，再選兩個線性無關的再選兩個線性無關的向量，如坐標軸單位向量，如坐標軸單位向量向量e1 1=1,0=1,0T T和和e e2 2=0,1=0,1T T作為初始作為初始搜索方向。搜索方向。2 2）從）從x0出發(fā)，順次沿出發(fā)，順次沿e1 1， e1 1作一維搜索，得作一維搜索，得 點，兩點連線點，兩點連線得一新方向得一新

45、方向d1 10012,x x1002dxxx1x2x0oe1e2d1d2x*102x10 x11x12x01x第八章第八章 無約束優(yōu)化方法無約束優(yōu)化方法21120dxx沿沿d2作一維搜索得點作一維搜索得點x2 。 即是二維問題的極即是二維問題的極小點小點x* 。方法的基本迭代格式包括共方法的基本迭代格式包括共軛方向產(chǎn)生和方向替換兩軛方向產(chǎn)生和方向替換兩主要步驟。主要步驟。用用 d1代替代替e1 1形成兩個線性無關向量形成兩個線性無關向量d1 , ,e2 2 ，作為，作為下一輪迭代的搜索方向。再下一輪迭代的搜索方向。再 從出發(fā)，沿從出發(fā)，沿d1作一作一維搜索得點維搜索得點 ，作為下一輪迭代的初始

46、點。，作為下一輪迭代的初始點。 02x10 x3 3）從）從 出發(fā)，順次出發(fā)，順次沿沿e2 2, ,d1 作一維搜索，作一維搜索，得到點得到點 ，兩點連，兩點連線得一新方向線得一新方向: :x1x2x0o oe1e2d1d2x*102x10 x11x12x01x1112,xx10 x第八章第八章 無約束優(yōu)化方法無約束優(yōu)化方法 把二維情況的基本算法擴展到把二維情況的基本算法擴展到n維，則鮑威爾維，則鮑威爾基本算法的要點是：基本算法的要點是： 在每一輪迭代中總有一個始點（第一輪的始點在每一輪迭代中總有一個始點（第一輪的始點是任選的初始點）和是任選的初始點）和n個線性獨立的搜索方向。個線性獨立的搜索

47、方向。從始點出發(fā)順次沿從始點出發(fā)順次沿n個方向作一維搜索得一終點，個方向作一維搜索得一終點，由始點和終點決定了一個新的搜索方向。由始點和終點決定了一個新的搜索方向。 用這個方向替換原來用這個方向替換原來n個方向中的一個，于是個方向中的一個，于是形成新的搜索方向組。替換的原則是去掉原方向形成新的搜索方向組。替換的原則是去掉原方向組的第一個方向而將新方向排在原方向的最后。組的第一個方向而將新方向排在原方向的最后。此外規(guī)定，從這一輪的搜索終點出發(fā)沿新的搜索此外規(guī)定，從這一輪的搜索終點出發(fā)沿新的搜索方向作一維搜索而得到的極小點，作為下一輪迭方向作一維搜索而得到的極小點，作為下一輪迭代的始點。這樣就形成

48、算法的循環(huán)。代的始點。這樣就形成算法的循環(huán)。 第八章第八章 無約束優(yōu)化方法無約束優(yōu)化方法 因為在迭代中的因為在迭代中的n個搜索方向有時會變成線性個搜索方向有時會變成線性相關而不能形成共軛方向。這時組不成相關而不能形成共軛方向。這時組不成n維空間，維空間，可能求不到極小點，所以上述基本算法有待改進?？赡芮蟛坏綐O小點，所以上述基本算法有待改進。 3.3.改進的算法改進的算法 在鮑威爾基本算法中，每一輪迭代都用連結在鮑威爾基本算法中，每一輪迭代都用連結始點和終點所產(chǎn)生出的搜索方向去替換原向量組中始點和終點所產(chǎn)生出的搜索方向去替換原向量組中的第一個向量，而不管它的的第一個向量，而不管它的“好壞好壞”，

49、這是產(chǎn)生向，這是產(chǎn)生向量組線性相關的原因所在。量組線性相關的原因所在。 在改進的算法中首先判斷原向量組是否需要在改進的算法中首先判斷原向量組是否需要替換。如果需要替換，還要進一步判斷原向量組替換。如果需要替換，還要進一步判斷原向量組中哪個向量最壞，然后再用新產(chǎn)生的向量替換這中哪個向量最壞，然后再用新產(chǎn)生的向量替換這個最壞的向量，以保證逐次生成共軛方向。個最壞的向量，以保證逐次生成共軛方向。第八章第八章 無約束優(yōu)化方法無約束優(yōu)化方法 為此，要解決兩個關鍵問題為此，要解決兩個關鍵問題： （1）dk1是否較好？是否應該進入新的方向是否較好？是否應該進入新的方向組？即方向組是否進行更新？組？即方向組是

50、否進行更新？l（2）如果應該更新方向組，）如果應該更新方向組， dk1不一定替換方不一定替換方向向 ，而是有選擇地替換某一方向，而是有選擇地替換某一方向 。1kdkmd令在令在k次循環(huán)中次循環(huán)中00231()()()kknknFfFfFfxxx01,kkknnx x x100()2kkkkkknnnnxxxxxx（）分別稱為一輪迭代的始點、終點和反射點分別稱為一輪迭代的始點、終點和反射點 。第八章第八章 無約束優(yōu)化方法無約束優(yōu)化方法 則在循環(huán)中函數(shù)下降最多的第則在循環(huán)中函數(shù)下降最多的第m次迭代是次迭代是1(1,2, )iiiffin ()(0,1,2, )kiiffinx記記：11maxmim

51、mi nff 相應的方向為相應的方向為 。kmd為了構成共為了構成共軛性好的方向組，須遵循下列準軛性好的方向組，須遵循下列準則：則：在在k次循環(huán)中，若滿足條件：次循環(huán)中，若滿足條件：30FF和和202302(2)()mFFFFF2030.5()mFF則選用新方向則選用新方向dk，并在第并在第k+1迭代中用迭代中用dk替換對應于替換對應于 的方向的方向 。否則，仍然用原方向組進行第。否則，仍然用原方向組進行第k+1迭代。迭代。kmdm002,nFfFf因此因此第八章第八章 無約束優(yōu)化方法無約束優(yōu)化方法 這樣重復迭代的結果，后面加進去的向量都這樣重復迭代的結果，后面加進去的向量都彼此對彼此對G共軛

52、，經(jīng)共軛，經(jīng)n輪迭代即可得到一個由輪迭代即可得到一個由n個共個共軛方向所組成的方向組。對于二次函次，最多軛方向所組成的方向組。對于二次函次，最多n次次就可找到極小點，而對一般函數(shù)，往往要超過就可找到極小點，而對一般函數(shù)，往往要超過n次次才能找到極小點（這里才能找到極小點（這里“n”表示設計空間的維表示設計空間的維數(shù)）。數(shù)）。 第八章第八章 無約束優(yōu)化方法無約束優(yōu)化方法第八章第八章 無約束優(yōu)化方法無約束優(yōu)化方法 例例4-5 4-5 用改進的鮑威爾法求目標函數(shù)用改進的鮑威爾法求目標函數(shù)2212112( )242fxxxx xx解：（解：（1 1）第）第1 1輪迭代計算輪迭代計算， 0011 x00

53、00()3Fff x沿沿e1方向進行一維搜索方向進行一維搜索0201min()43fxe12得得00101 11132101 xxe011()7ff x0.001。l的最優(yōu)解。已知初始點的最優(yōu)解。已知初始點1,11,1T T，迭代精度，迭代精度第八章第八章 無約束優(yōu)化方法無約束優(yōu)化方法以以 為起點，沿第二坐標軸方向為起點，沿第二坐標軸方向 e2 進行一維進行一維搜索搜索01x0212min()227fxe20.5得得0021213030.5111.5 xxe022()7.5ff x第八章第八章 無約束優(yōu)化方法無約束優(yōu)化方法確定此輪中的最大下降量及其相應方向確定此輪中的最大下降量及其相應方向 0

54、010101()()4ffff xx0021212()()0.5ffff xx12max,4m 反射點及其函數(shù)值反射點及其函數(shù)值， 000320315221.512 xxx033()7Ff x檢驗檢驗PowellPowell條件條件202302(2)()1.25mFFFFF2030.5()32mFF3073FF 第八章第八章 無約束優(yōu)化方法無約束優(yōu)化方法由于滿足由于滿足PowellPowell條件，則淘汰函數(shù)值下降量最條件，則淘汰函數(shù)值下降量最大的方向大的方向e1，下一輪的基本方向組為，下一輪的基本方向組為e2， 。03d構成新的方向構成新的方向 0003203121.510.5 dxx沿沿

55、方向一維搜索得極小點和極小值方向一維搜索得極小點和極小值03d13.81.7x1()7.9f x，此點為下輪迭代初始點。此點為下輪迭代初始點。 按點距準則檢驗終止條件按點距準則檢驗終止條件 11220(3.8 1)(1.71)2.886xx需進行第二輪迭代機算。需進行第二輪迭代機算。第八章第八章 無約束優(yōu)化方法無約束優(yōu)化方法 （2 2）第）第2 2輪迭代計算輪迭代計算此輪基本方向組為此輪基本方向組為e2， ，分別相當于，分別相當于 ， ，起始點為起始點為 。03d11d12d10 x1x沿沿e2方向進行一維搜索得方向進行一維搜索得 113.81.9x111()7.98ff x以以 為起點沿為起

56、點沿 方向一維搜索得方向一維搜索得11x03d123.961.9x122()7.996ff x確定此輪中函數(shù)值最大下降量及其相應方向確定此輪中函數(shù)值最大下降量及其相應方向10.08 20.016 12max,0.08m 第八章第八章 無約束優(yōu)化方法無約束優(yōu)化方法 反射點及其函數(shù)值反射點及其函數(shù)值1113203.963.84.12221.941.72.18xxx133()7.964Ff x檢驗檢驗Powell條件，淘汰函數(shù)值下降量最大的方條件，淘汰函數(shù)值下降量最大的方向向e2，下一輪的基本方向組應為，下一輪的基本方向組應為 ， 。 03d13d構成新的方向構成新的方向1113203.963.80

57、.161.941.70.24dxx沿沿 方向進行一維搜索得方向進行一維搜索得13d242 x2()8f x第八章第八章 無約束優(yōu)化方法無約束優(yōu)化方法 檢驗終止條件檢驗終止條件 22220(43.8)(2 1.7)0.36xx（3 3）第）第3 3輪迭代計算輪迭代計算此輪基本方向組為此輪基本方向組為 ， ，起始點為，起始點為 ，先，先后沿后沿 ， 方向，進行一維搜索，得方向，進行一維搜索，得03d13d20 x2x03d13d2242 x2142 x，22200 xx*42 x*()8f x故最優(yōu)解故最優(yōu)解檢驗終止條件檢驗終止條件第八章第八章 無約束優(yōu)化方法無約束優(yōu)化方法 實際上，前兩輪迭代的實際上，前兩輪迭代的 ， 為共軛方向，由為共軛方向，由于本例目標函數(shù)是二次函數(shù)，按共軛方向的二次收斂性，于本例目標函數(shù)是二次函數(shù)，按共軛方向的二次收斂性，故前兩輪的結果就是問題的最優(yōu)解，但每一輪迭代都需故前兩輪的結果就是問題的最優(yōu)解，但每一輪迭代都需要進行要進行n+1次迭代。次迭代。 13d23d第八章第八章 無約束優(yōu)化方法無約束優(yōu)化方法 前