無(wú)約束優(yōu)化方法

1、第四章第四章 無(wú)約束最優(yōu)化方法無(wú)約束最優(yōu)化方法第一節(jié)第一節(jié) 概述概述第二節(jié)第二節(jié) 最速下降法最速下降法第三節(jié)第三節(jié) 牛頓法牛頓法第四節(jié)第四節(jié) 共軛方向法共軛方向法第五節(jié)第五節(jié) 變尺度法變尺度法第六節(jié)第六節(jié) 坐標(biāo)輪換法坐標(biāo)輪換法第七節(jié)第七節(jié) powellpowell法法作業(yè)作業(yè)第一節(jié)第一節(jié) 概概 述述一、求解問(wèn)題一、求解問(wèn)題 () 0f X二、方法分類(lèi)二、方法分類(lèi)解析法解析法數(shù)值法數(shù)值法間接法：用導(dǎo)數(shù)信息構(gòu)造搜索方向間接法：用導(dǎo)數(shù)信息構(gòu)造搜索方向d(k)min () nf XXR(1)( )( )kkkkXXd直接法：用函數(shù)信息構(gòu)造搜索方向直接法：用函數(shù)信息構(gòu)造搜索方向d(k)三、數(shù)值法的基本問(wèn)

2、題三、數(shù)值法的基本問(wèn)題顯然，若使數(shù)值法切實(shí)可行，必需首先解決以下四個(gè)問(wèn)題：顯然，若使數(shù)值法切實(shí)可行，必需首先解決以下四個(gè)問(wèn)題：如何確定某點(diǎn)處的搜索方向如何確定某點(diǎn)處的搜索方向？如何確定步長(zhǎng)如何確定步長(zhǎng)？如何確定迭代過(guò)程的終止準(zhǔn)則如何確定迭代過(guò)程的終止準(zhǔn)則？1.1.如何衡量數(shù)值算法的好壞如何衡量數(shù)值算法的好壞？ 下降性下降性簡(jiǎn)便性簡(jiǎn)便性收斂性收斂性(1)( )()()kkf Xf X(1)( )( )kkkkXXd( )*limkkXX四、算法的收斂性四、算法的收斂性這里這里X* *是無(wú)約束問(wèn)題的局部解。是無(wú)約束問(wèn)題的局部解。所謂收斂，是指序列所謂收斂，是指序列 X(k) 或它的一個(gè)子列或它的一

3、個(gè)子列( (不妨仍記為不妨仍記為 X(k) )滿(mǎn)滿(mǎn)足足( )*limkkXX 若對(duì)于某些算法來(lái)說(shuō)若對(duì)于某些算法來(lái)說(shuō), ,只有當(dāng)初始點(diǎn)只有當(dāng)初始點(diǎn)X(0)充分靠近極小點(diǎn)充分靠近極小點(diǎn)X* *時(shí)，才能保證序列時(shí)，才能保證序列 X(k) 收斂到收斂到X* *，則稱(chēng)這類(lèi)算法為局部收斂。，則稱(chēng)這類(lèi)算法為局部收斂。 反之，若對(duì)任意的初始點(diǎn)反之，若對(duì)任意的初始點(diǎn)X(0)，產(chǎn)生的序列產(chǎn)生的序列 X(k) 收斂到收斂到X* *，則稱(chēng)這類(lèi)算法為全局收斂則稱(chēng)這類(lèi)算法為全局收斂. .如果算法產(chǎn)生的序列如果算法產(chǎn)生的序列 X(k) 雖然收斂到雖然收斂到X*，但收斂的太但收斂的太“慢慢”，以致于在計(jì)算機(jī)允許的時(shí)間內(nèi)仍得不

4、到滿(mǎn)意的結(jié)果，那么，以致于在計(jì)算機(jī)允許的時(shí)間內(nèi)仍得不到滿(mǎn)意的結(jié)果，那么，這類(lèi)算法也稱(chēng)不上好算法這類(lèi)算法也稱(chēng)不上好算法. .五、算法的收斂速率五、算法的收斂速率設(shè)序列設(shè)序列 X(k) 收斂到收斂到x x* *, ,若極限若極限存在，當(dāng)存在，當(dāng)0101p1時(shí)，時(shí)，p p階收斂必為超線性收斂，階收斂必為超線性收斂，但反之不一定成立。在最優(yōu)化算法中，通?？紤]線性收斂、但反之不一定成立。在最優(yōu)化算法中，通常考慮線性收斂、超線性收斂和二階收斂。超線性收斂和二階收斂。上面談到的收斂性和收斂速率能夠較為準(zhǔn)確地刻劃出算法的上面談到的收斂性和收斂速率能夠較為準(zhǔn)確地刻劃出算法的優(yōu)劣程度，但使用起來(lái)比較困難。特別是證

5、明一個(gè)算法是否優(yōu)劣程度，但使用起來(lái)比較困難。特別是證明一個(gè)算法是否收斂或具有什么樣的收斂速率，需要很強(qiáng)的理論知識(shí)。在這收斂或具有什么樣的收斂速率，需要很強(qiáng)的理論知識(shí)。在這里給出一較為簡(jiǎn)單地判斷算法優(yōu)劣的評(píng)價(jià)標(biāo)準(zhǔn)里給出一較為簡(jiǎn)單地判斷算法優(yōu)劣的評(píng)價(jià)標(biāo)準(zhǔn)算法的二算法的二次終止性。次終止性。定義：若某個(gè)算法對(duì)于任意的正定二次函數(shù)，從任意的初始定義：若某個(gè)算法對(duì)于任意的正定二次函數(shù)，從任意的初始點(diǎn)出發(fā)，都能經(jīng)有限步迭代達(dá)到其極小點(diǎn)，則稱(chēng)該算法具有點(diǎn)出發(fā)，都能經(jīng)有限步迭代達(dá)到其極小點(diǎn)，則稱(chēng)該算法具有二次終止性。二次終止性。六、算法的二次終止性六、算法的二次終止性從某一點(diǎn)從某一點(diǎn)X(k)出發(fā)，以該點(diǎn)的最速

6、下降方向：即負(fù)梯度方向出發(fā)，以該點(diǎn)的最速下降方向：即負(fù)梯度方向 f( (X(k) )，進(jìn)行一維搜索，得最優(yōu)步長(zhǎng)，進(jìn)行一維搜索，得最優(yōu)步長(zhǎng) k，從而獲得新的迭，從而獲得新的迭代點(diǎn)代點(diǎn)X(k+1)，如此重復(fù)迭代，如此重復(fù)迭代，即得到無(wú)約束問(wèn)題的最優(yōu)解即得到無(wú)約束問(wèn)題的最優(yōu)解. .第二節(jié)第二節(jié) 最速下降法最速下降法一、方法說(shuō)明一、方法說(shuō)明(1)( )( )kkkkXXd( )( ) () kkdf X ( )( ) ( )()()minkkf Xf Xf X 二、幾何說(shuō)明二、幾何說(shuō)明相鄰兩次搜索方向正交，相鄰兩次搜索方向正交，(1)( )(1)( ) () 0kkkkddf Xd由由( )( ) (

7、)()0kdf Xf Xd 得得(1) (1) 取初始點(diǎn)取初始點(diǎn)X(0)，精度指標(biāo)，精度指標(biāo) ，置置k= =0. .三、算法步驟三、算法步驟(2) (2) 若若 則停止計(jì)算，將則停止計(jì)算，將X(k)作作為無(wú)約束問(wèn)題的最優(yōu)解輸出；為無(wú)約束問(wèn)題的最優(yōu)解輸出； 否則置否則置(3)(3)求解一維問(wèn)題求解一維問(wèn)題( )()kf X( )( )()kkdf X (4)(4)置置k=k+1，轉(zhuǎn)轉(zhuǎn)(2).(2).(1)( )( )kkkkXXd( )( ) ( )()minkkf Xd 得得3. 3. 若一維搜索是精確的，則最速下降法產(chǎn)生的相鄰兩次的搜若一維搜索是精確的，則最速下降法產(chǎn)生的相鄰兩次的搜索方向是

8、相互正交的。索方向是相互正交的。四、算法特點(diǎn)四、算法特點(diǎn)由此表明，最速下降法相鄰的兩次迭代的前進(jìn)方向是相互垂由此表明，最速下降法相鄰的兩次迭代的前進(jìn)方向是相互垂直的，因而整個(gè)行進(jìn)路徑呈鋸齒形，因此從全局來(lái)看直的，因而整個(gè)行進(jìn)路徑呈鋸齒形，因此從全局來(lái)看, ,收斂較收斂較慢。從前面的分析可以得到這樣一個(gè)結(jié)論：最速下降法不最慢。從前面的分析可以得到這樣一個(gè)結(jié)論：最速下降法不最速。換句話說(shuō)，最速下降方向未必是最好的搜索方向。應(yīng)該速。換句話說(shuō)，最速下降方向未必是最好的搜索方向。應(yīng)該考慮其它的下降方向作為搜索方向。考慮其它的下降方向作為搜索方向。1. 1. 要求目標(biāo)函數(shù)連續(xù)可導(dǎo)；要求目標(biāo)函數(shù)連續(xù)可導(dǎo)；2

9、. 2. 當(dāng)初始點(diǎn)遠(yuǎn)離最優(yōu)點(diǎn)時(shí)，或目標(biāo)函數(shù)形態(tài)。接近于圓（或當(dāng)初始點(diǎn)遠(yuǎn)離最優(yōu)點(diǎn)時(shí)，或目標(biāo)函數(shù)形態(tài)。接近于圓（或球）時(shí)，步長(zhǎng)較大，收斂較快；球）時(shí)，步長(zhǎng)較大，收斂較快；1 1NewtonNewton法的基本思想法的基本思想若若x x* *是無(wú)約束問(wèn)題的局部解，則是無(wú)約束問(wèn)題的局部解，則x x* *滿(mǎn)足滿(mǎn)足第三節(jié)第三節(jié) 牛頓法牛頓法因此因此, ,可以通過(guò)求解該方程組來(lái)得到無(wú)約束最優(yōu)化問(wèn)題解。注可以通過(guò)求解該方程組來(lái)得到無(wú)約束最優(yōu)化問(wèn)題解。注意到該方程組是非線性的，處理起來(lái)比較困難，因此考慮原意到該方程組是非線性的，處理起來(lái)比較困難，因此考慮原目標(biāo)函數(shù)在點(diǎn)目標(biāo)函數(shù)在點(diǎn)X(k)處處的一個(gè)二次逼近：的一

10、個(gè)二次逼近：* () 0f X( )( )( )2( )( )( )()()()() (-)1-()(-)2kkTkkTkkf XpXf Xf XXX XXH XXX 該二次函數(shù)的極小點(diǎn)可由下式求得：該二次函數(shù)的極小點(diǎn)可由下式求得：( )( )( )2()()()(-)0kkkpXf XH XXX 1*( )( )( )()()kkkpXXH Xf X 即：即：將二次函數(shù)的這個(gè)極小點(diǎn)作為原目標(biāo)函數(shù)極小點(diǎn)的近似，將二次函數(shù)的這個(gè)極小點(diǎn)作為原目標(biāo)函數(shù)極小點(diǎn)的近似，即：即：1(1)( )( )( )()()kkkkXXH Xf X 由此可見(jiàn)，牛頓法的搜索方向?yàn)椋河纱丝梢?jiàn)，牛頓法的搜索方向?yàn)椋?( )

11、( )( )()()kkkdH Xf X 步長(zhǎng)為：步長(zhǎng)為：1k (1) (1) 取初始點(diǎn)取初始點(diǎn)X(0)，精度指標(biāo)，精度指標(biāo) ，置置k= =0. .(2) (2) 若若 則停止計(jì)算，將則停止計(jì)算，將X(k)作作為無(wú)約束問(wèn)題的最優(yōu)解輸出；為無(wú)約束問(wèn)題的最優(yōu)解輸出； 否則置否則置(3)(3)求新的迭代點(diǎn)求新的迭代點(diǎn)( )()kf X1( )( )( )()()kkkdH Xf X (4)(4)置置k=k+1，轉(zhuǎn)轉(zhuǎn)(2).(2).(1)( )( )kkkXXd2 2 算法步驟：算法步驟：3 3 例題例題NewtonNewton法的優(yōu)點(diǎn)法的優(yōu)點(diǎn): :(1)Newton(1)Newton法產(chǎn)生的點(diǎn)列法產(chǎn)

12、生的點(diǎn)列 X(k)若收斂，則收斂速度快，具有若收斂，則收斂速度快，具有二階收斂速率二階收斂速率( (證明略證明略) )。(2)Newton(2)Newton法具有二次終止性。法具有二次終止性。4 4 算法特點(diǎn)：算法特點(diǎn)：NewtonNewton法的缺點(diǎn)法的缺點(diǎn): :(1)(1)可能會(huì)出現(xiàn)在某步迭代時(shí)目標(biāo)函數(shù)值上升，即存在可能會(huì)出現(xiàn)在某步迭代時(shí)目標(biāo)函數(shù)值上升，即存在k，使得，使得f(X(k+1)f(X(k)。如在上例中。如在上例中, ,取取x x(1)(1)=(1=(1，1)1)T T，f(x(x(1)(1)=4)=4，由，由NewtonNewton法得到的法得到的x x(2)(2)=(-0.7

13、5,-1.25)=(-0.75,-1.25)T T，此時(shí)，此時(shí)，f(x(x(2)(2)=4.5156)=4.5156函數(shù)值上升。函數(shù)值上升。(2)(2)當(dāng)初始點(diǎn)當(dāng)初始點(diǎn)x x(1)(1)距距x x* *較遠(yuǎn)時(shí)，產(chǎn)生的點(diǎn)列較遠(yuǎn)時(shí)，產(chǎn)生的點(diǎn)列 X(k)可能不收斂；或可能不收斂；或者收斂到鞍點(diǎn)；或者者收斂到鞍點(diǎn)；或者H(xH(x(k)(k) )奇異無(wú)法計(jì)算。奇異無(wú)法計(jì)算。 (3)(3)需要計(jì)算需要計(jì)算HesseHesse矩陣矩陣, ,計(jì)算量大。計(jì)算量大。修正修正NewtonNewton法是針對(duì)缺點(diǎn)法是針對(duì)缺點(diǎn)(1)(1)提出改進(jìn)方案的。為了避免函提出改進(jìn)方案的。為了避免函數(shù)值上升，在算法中增加一維搜

14、索策略，即將數(shù)值上升，在算法中增加一維搜索策略，即將d d(k)(k)作為搜索方作為搜索方向向( (此時(shí)稱(chēng)此時(shí)稱(chēng)d d(k)(k)為為NewtonNewton方向方向) )，而不是作為增量，由此得到如，而不是作為增量，由此得到如下算法下算法. .5.5.修正修正NewtonNewton法法1(1)( )( )( )()()kkkkkXXH Xf X( )( )( )()min kkf Xd 1( )( )( )()()kkkdH Xf X 修正修正NewtonNewton法保持了法保持了NewtonNewton法的優(yōu)點(diǎn)法的優(yōu)點(diǎn), ,，如算法的二次，如算法的二次終止性等，克服了目標(biāo)函數(shù)值上升的缺

15、點(diǎn)，由于增加了一終止性等，克服了目標(biāo)函數(shù)值上升的缺點(diǎn)，由于增加了一維搜索，對(duì)缺點(diǎn)維搜索，對(duì)缺點(diǎn)(2)(2)有所改善，但不能完全克服。有所改善，但不能完全克服。對(duì)于缺點(diǎn)對(duì)于缺點(diǎn)(3)(3)沒(méi)有任何改進(jìn)，因?yàn)樾拚龥](méi)有任何改進(jìn)，因?yàn)樾拚齆ewtonNewton法仍需要計(jì)法仍需要計(jì)算算HesseHesse矩陣。矩陣。 另一種修正方案是將另一種修正方案是將NewtonNewton方向與最速下降方向相結(jié)合。方向與最速下降方向相結(jié)合。設(shè)設(shè)d(k)N是是NewtonNewton方向，即方向，即d(k)N滿(mǎn)足滿(mǎn)足這里假設(shè)這里假設(shè)H H(X(k)非奇異。設(shè)非奇異。設(shè) k是是dN(k)與與- - f(X(k)之間的

16、夾角。之間的夾角。當(dāng)然希望當(dāng)然希望 k不要大于不要大于/2,/2,即存在正數(shù)即存在正數(shù)01,01,使得使得coscosk . .( )1( )( )()()kkkNdH Xf X GoldsteinGoldstein和和PricePrice在在19671967年提出的修正方案是令年提出的修正方案是令這樣得到的這樣得到的d(k)d(k)總是下降方向，并滿(mǎn)足總是下降方向，并滿(mǎn)足coscosk( )1( )( )( )()()()kkkkH Xf Xdf Xcoscosk其他其他第四節(jié)第四節(jié) 共軛方向法共軛方向法一、共軛方向的概念一、共軛方向的概念對(duì)于一個(gè)二維二次函數(shù)對(duì)于一個(gè)二維二次函數(shù)1()2TT

17、f XX AXB XC其等值線為同心橢圓族其等值線為同心橢圓族(0)X(0)d(1)X(1)()f X(1)d(0)0d(2)*XX(1)(0)(0)0XXd(2)(1)(1)1XXd(2)*XX兩次一維搜索即可達(dá)到最優(yōu)點(diǎn)，兩次一維搜索即可達(dá)到最優(yōu)點(diǎn)，兩次搜索方向滿(mǎn)足什么條件？?jī)纱嗡阉鞣较驖M(mǎn)足什么條件？由無(wú)約束最優(yōu)點(diǎn)的必要條件得：由無(wú)約束最優(yōu)點(diǎn)的必要條件得：*()0f XAXB即即(2)(1)(1)1()0AXBA XdB(1)(1)1()0f XAd(0)(1)()()0Tdf X上式兩邊同左乘以上式兩邊同左乘以d(0)，得：，得：(0)(1)(0)(1)1()()()0TTdf XdAd又

18、由于又由于故得故得(0)(1)()0TdAd稱(chēng)方向稱(chēng)方向d(0)與方向與方向d(1)關(guān)于矩陣關(guān)于矩陣A共軛共軛二、共軛方向的定義二、共軛方向的定義設(shè)矩陣設(shè)矩陣A為為n n的的對(duì)稱(chēng)正定矩陣，對(duì)稱(chēng)正定矩陣， 若若n維空間中有維空間中有m個(gè)非零向個(gè)非零向量量d(0)， d(1)， d(m-1)，滿(mǎn)足，滿(mǎn)足( )( )()0 ( ,0,1,.,1)()iTjdAdi jmij則稱(chēng)則稱(chēng)向量向量d(0)， d(1)， d(m-1)關(guān)于關(guān)于矩陣矩陣A相互共軛；當(dāng)相互共軛；當(dāng)矩陣矩陣A為單位矩陣時(shí)，為單位矩陣時(shí)，則稱(chēng)則稱(chēng)向量向量d(0)， d(1)， d(m-1)相互正交。相互正交。三、共軛方向的性質(zhì)三、共軛

19、方向的性質(zhì)1. 1. 若若m個(gè)非零向量個(gè)非零向量d(0)， d(1)， d(m-1)關(guān)于關(guān)于矩陣矩陣A相互共軛，相互共軛，則這則這m個(gè)非零向量線性無(wú)關(guān)。個(gè)非零向量線性無(wú)關(guān)。( )(0)(1)(1)011()(.)0 0 0,1,.,1iTmmidAdddim2. 2. 從任意初始點(diǎn)出發(fā)從任意初始點(diǎn)出發(fā)X(0) ，順次沿，順次沿n個(gè)個(gè)關(guān)于關(guān)于矩陣矩陣A共軛共軛方向方向d(0)， d(1)， d(n-1)進(jìn)行一維搜索進(jìn)行一維搜索，最多經(jīng)過(guò)，最多經(jīng)過(guò)n次迭代，就次迭代，就可求得可求得n維二次函數(shù)的理論極小點(diǎn)維二次函數(shù)的理論極小點(diǎn)X*，即以，即以共軛共軛方向方向d(0)， d(1)， d(n-1)作為

20、搜索方向的方法具有二次收斂性。作為搜索方向的方法具有二次收斂性。即即證明：證明：X(0)為任意初始點(diǎn)。為任意初始點(diǎn)。 若若d(0)， d(1)， d(n-1)為為n個(gè)個(gè)關(guān)于關(guān)于矩陣矩陣A的共軛的共軛方向，方向，則它們可作為則它們可作為n維空間的一組基向量，則有維空間的一組基向量，則有1()2TTf XX AXB XC設(shè)設(shè)n維二次函數(shù)維二次函數(shù)的理論極小點(diǎn)為的理論極小點(diǎn)為X*(0)(0)(1)(1)011.nnXXddd兩邊左乘兩邊左乘d(0)TA，得：，得：(0)*(0)(0)(0)(0)0()()()TTTdAXdAXdAd又由于：又由于：*() ()0f XAXBf XAXB和(0)*(0

21、)(0)(0)(0)0() () ()TTTdAXBdAXBdAd(0)(0)0(0)(0)()()()TTdf XdAd故得：故得：( )( )( )( )()()()kTkkkTkdf XdAd記：記：*( )( )(1)1.kknknXXdd則同理可得則同理可得下面證明，由下面證明，由X(k)出發(fā)，沿出發(fā)，沿共軛共軛方向方向d(k)進(jìn)行一維搜索，得點(diǎn)進(jìn)行一維搜索，得點(diǎn)X(k1)，即，即(1)( )( )kkkkXXd其步長(zhǎng)如下確定：其步長(zhǎng)如下確定：(1)( )()0kTkf Xd( )(1)()0k TkdAXB( )( )( )()0k TkkkdAXAdB( )( )( )( )()

22、k Tkkk Tkdf XdAd 由此可見(jiàn)：由此可見(jiàn)：kk故證故證其步長(zhǎng)為：其步長(zhǎng)為：四、共軛方向的構(gòu)造四、共軛方向的構(gòu)造對(duì)于對(duì)于n個(gè)線性無(wú)關(guān)向量個(gè)線性無(wú)關(guān)向量e(0)， e(1)， e(n-1)，對(duì)其進(jìn)行關(guān)于，對(duì)其進(jìn)行關(guān)于矩矩陣陣A的共軛的共軛化處理，得化處理，得n個(gè)個(gè)共軛共軛方向方向d(0)， d(1)， d(n-1)。然。然后順次沿這后順次沿這n個(gè)個(gè)共軛共軛方向方向進(jìn)行一維搜索，這就是進(jìn)行一維搜索，這就是共軛共軛方向法方向法的基本思想。的基本思想。1()2TTf XX AXB XC由由初始點(diǎn)初始點(diǎn)X(0)出發(fā)，出發(fā)，對(duì)于對(duì)于n維二次函數(shù)維二次函數(shù)首先取首先取(0)(0)de令令(1)(1

23、)(0)10dee由由d(0)， d(1)關(guān)于關(guān)于矩陣矩陣A的共軛，得：的共軛，得：(0)(1)10(0)(0)TTdAedAe 令令(1)( )( )1,0kkkjkjjdee由由d(k+1) 與與d(0)， d(1)， d(k)關(guān)于關(guān)于矩陣矩陣A的共軛，得：的共軛，得：( )(1)1,( )( )j Tkkjj TjdAedAe 開(kāi)始開(kāi)始置置e(j)=0,0,.,1,0.,0，j=0,1,n-1Min Min ( ( )=f()=f(X(k),l+ d(k) X(k+1),l = X(k),l+ k k d(k) kn?置置X(l +1) =X(n) l, l=l+1結(jié)束結(jié)束yesyesn

24、onoyesyesnono五、共軛方向五、共軛方向法算法框圖法算法框圖置置X(0),l= X(l),A=H( X(l)置置d(0)=e(0) , k=0k= k +1(1)( )( )1,0kkkjkjjdee( )(1)1,( )( )j Tkkjj TjdAedAe 輸出輸出: : X*=X(n),l和和f *= f (X(n),l)輸入輸入: : n, , X(0)( ),(0),n llXX?六、共軛梯度法六、共軛梯度法共軛梯度法共軛梯度法( (Conjugate Graient Method) )是最著名的共軛方向方是最著名的共軛方向方法，它首先由法，它首先由HestenesHest

25、enes和和StiefelStiefel在在19521952年提出來(lái)作為解線年提出來(lái)作為解線性方程組的方法。性方程組的方法。19641964年年FletcherFletcher和和ReevesReeves應(yīng)用于求解無(wú)約應(yīng)用于求解無(wú)約束問(wèn)題。在該方法中每個(gè)共軛方向的構(gòu)造都依賴(lài)于迭代點(diǎn)處束問(wèn)題。在該方法中每個(gè)共軛方向的構(gòu)造都依賴(lài)于迭代點(diǎn)處的負(fù)梯度，而不必確定矩陣的負(fù)梯度，而不必確定矩陣A A。對(duì)于一個(gè)二維二次函數(shù)對(duì)于一個(gè)二維二次函數(shù)1()2TTf XX AXB XC( +1)( )( )kkkkXXd(1)(1)1()kkkgf XAXB由由初始點(diǎn)初始點(diǎn)X(k)出發(fā)，沿出發(fā)，沿共軛共軛方向方向d(

26、k)，進(jìn)行一維搜索，得點(diǎn)進(jìn)行一維搜索，得點(diǎn) X(k1)，即，即( +1)( )( )kkkkXXd或或在在點(diǎn)點(diǎn)X(k)、點(diǎn)、點(diǎn)X(k1)處的梯度記為：處的梯度記為：( )( )()kkkgf XAXB(1)( )( )1()kkkkkkggA XXAd( )kX(1)kX( )kd( ) jd( )()kkgf X (1)1()kkgf X 1kkkggg設(shè)設(shè)方向方向d(j)與與方向方向d(k)關(guān)于矩陣關(guān)于矩陣A共軛，共軛，則有則有( )( )( )1()0j Tj TkkkkdggdAd此式表明，沿此式表明，沿方方向向d(k)進(jìn)行一維搜進(jìn)行一維搜索索, ,其終點(diǎn)其終點(diǎn)X(k1)和始點(diǎn)和始點(diǎn)X

27、(k)的梯的梯度之差，與度之差，與d(k)的的共軛方向正交。共軛方向正交。共軛梯度法就是共軛梯度法就是利用這個(gè)性質(zhì)做利用這個(gè)性質(zhì)做到不必計(jì)算矩陣到不必計(jì)算矩陣A就能求得共軛就能求得共軛方向的。方向的。共軛梯度法的計(jì)算過(guò)程共軛梯度法的計(jì)算過(guò)程1. 由由X(0)出發(fā)，沿出發(fā)，沿方向方向d(0)g0 f(X(0)進(jìn)行一維搜索，進(jìn)行一維搜索，得點(diǎn)得點(diǎn)X(1)，即，即(1)(0)(0)0XXd2. 令令g1 f(X(1)，則，則g1與與d(0)( g0)正交，在該正交系中求與正交，在該正交系中求與方向方向d(0)共軛的方向共軛的方向d(1)，令，令(1)(0)10dgd 由共軛方向由共軛方向d(1)與梯

28、度關(guān)系：與梯度關(guān)系：(1)10()0Tdgg(0)1010() ()0Tgdgg(0)(0)110110000TTTTg gdgg gdg21(0)1110102(0)000,0,TTTTgg gg gdgdgg得：得：即：即：由由X(1)出發(fā)，沿出發(fā)，沿方向方向d(1) 進(jìn)行一維搜索，得點(diǎn)進(jìn)行一維搜索，得點(diǎn)X(2)，即，即(2)(1)(1)1XXd令令g2 f(X(2)，則，則g2與與d(1)正交，即正交，即(0)(0)1021202()0TTTgdgg gdg 由共軛方向由共軛方向d(0)與梯度關(guān)系：與梯度關(guān)系：(0)21()0Tdgg(0)(0)1012020()0TTdgggdggg1

29、2120Tg ggg3. 在在g0、g1 、 g2所構(gòu)成的正交系中，求與方向所構(gòu)成的正交系中，求與方向d(0)及及d(1)均共軛均共軛的方向的方向d(2)，設(shè)，設(shè)(2)21100dggg 因?yàn)橐笠驗(yàn)橐骴(2) 與與d(0) 和和d(1)均共軛，由共軛方向與梯度關(guān)系得：均共軛，由共軛方向與梯度關(guān)系得：2110010() ()0Tggggg2110021() ()0Tggggg考慮到考慮到g0、g1 、 g2相互正交，故有相互正交，故有11121001201100000TTTTTTgggggggggggg11222111002210010TTTTTTg ggggggggggg1110000TT

30、g ggg221110TTggg g故得故得22111TTggg g 22000TTgggg (2)2110022222102210 dgggggggggg 2221(0)212210 ()ggggdgg 22(1)(1)22121 ggdgdg 共軛梯度法共軛方向生成通式共軛梯度法共軛方向生成通式21(1)( )12(0,1,1)kkkkkgdgdkng 共軛梯度法的特點(diǎn)：共軛梯度法的特點(diǎn)：1. 共軛梯度法可看作是對(duì)最速下降法的修正，故收斂速度較最共軛梯度法可看作是對(duì)最速下降法的修正，故收斂速度較最速下降法快；速下降法快；2. 共軛梯度法具有二次收斂性；共軛梯度法具有二次收斂性；3. 共軛梯

31、度法程序簡(jiǎn)單，存儲(chǔ)量小，對(duì)初始點(diǎn)要求不嚴(yán)。共軛梯度法程序簡(jiǎn)單，存儲(chǔ)量小，對(duì)初始點(diǎn)要求不嚴(yán)。4. 共軛梯度法梯度模較小時(shí)容易上溢出。共軛梯度法梯度模較小時(shí)容易上溢出。第五節(jié)第五節(jié) 變尺度法變尺度法變尺度法變尺度法( (Variable Metric Method) )也稱(chēng)為擬也稱(chēng)為擬NewtonNewton法法( (Quasi-Newton Method) )，是求解無(wú)約束最優(yōu)化問(wèn)題最有效的算法之，是求解無(wú)約束最優(yōu)化問(wèn)題最有效的算法之一，它不需要求二階一，它不需要求二階Hesse矩陣，而只利用一階導(dǎo)數(shù)來(lái)構(gòu)造二矩陣，而只利用一階導(dǎo)數(shù)來(lái)構(gòu)造二階信息的近似矩陣，從而該算法有較好的收斂性質(zhì)。階信息的近似

32、矩陣，從而該算法有較好的收斂性質(zhì)。一、尺度矩陣的概念一、尺度矩陣的概念變量的尺度變換就是對(duì)其坐標(biāo)進(jìn)行放大或縮小處理，達(dá)到降低變量的尺度變換就是對(duì)其坐標(biāo)進(jìn)行放大或縮小處理，達(dá)到降低函數(shù)偏心率的目的。函數(shù)偏心率的目的。對(duì)于二次函數(shù)對(duì)于二次函數(shù)1()2TTf XX HXB XC進(jìn)行尺度變換進(jìn)行尺度變換XQX則函數(shù)的二次項(xiàng)變?yōu)閯t函數(shù)的二次項(xiàng)變?yōu)?122TTTX HXX Q HQX若矩陣若矩陣H H是正定的，則一定存在是正定的，則一定存在尺度矩陣尺度矩陣Q Q，使，使TQ HQI由此可見(jiàn)，二次函數(shù)的由此可見(jiàn)，二次函數(shù)的Hesse矩陣矩陣HH的逆陣的逆陣HH-1-1 ，可以通過(guò)尺，可以通過(guò)尺度矩陣度矩陣Q

33、Q求得。求得。11TTTTQ HQIQ HQQQ HIHQQNewtonNewton法迭代公式因此而變?yōu)椋悍ǖ揭虼硕優(yōu)椋?(1)( )( )( )()()kkkkkXXH Xf X梯度法迭代公式為：梯度法迭代公式為：(1)( )( )()kkkkXXIf X記記TAQQ稱(chēng)為尺度矩陣稱(chēng)為尺度矩陣則則NewtonNewton法和梯度法的迭代公式可統(tǒng)一寫(xiě)為：法和梯度法的迭代公式可統(tǒng)一寫(xiě)為：(1)( )( )()kkkkXXA f X為了避免在牛頓法中直接計(jì)算目標(biāo)函數(shù)為了避免在牛頓法中直接計(jì)算目標(biāo)函數(shù)f(X)的的Hesse矩陣的逆陣矩陣的逆陣 H(X(k) -1-1 ，故構(gòu)造一個(gè)尺度矩陣序列，

34、故構(gòu)造一個(gè)尺度矩陣序列 Ak 來(lái)逼近來(lái)逼近 H(X(k) -1-1 , ,則則稱(chēng)稱(chēng)Ak為變?yōu)樽兂叨染仃?。從而可得尺度矩陣。從而可得變變尺度法的迭代公式為：尺度法的迭代公式為：二、變尺度矩陣的?gòu)造原則：二、變尺度矩陣的構(gòu)造原則：1. 1. 為了保證迭代公式具有下降性質(zhì)，要求為了保證迭代公式具有下降性質(zhì)，要求 Ak 中的每個(gè)矩陣中的每個(gè)矩陣都是對(duì)稱(chēng)正定的。都是對(duì)稱(chēng)正定的。(1)( )( )()kkkkkXXAf X( )( )()()0kTkkf XAf X2. 2. 為了計(jì)算簡(jiǎn)便，要求為了計(jì)算簡(jiǎn)便，要求Ak具有如下的遞推關(guān)系：具有如下的遞推關(guān)系：1kkkAAA3. 3. 為了獲得牛頓法的收斂速度

35、，要求為了獲得牛頓法的收斂速度，要求Ak H(X(k) -1-1 。 Ak不可能在數(shù)值上近似不可能在數(shù)值上近似于于 H(X(k) 11，因?yàn)槲覀兊哪繕?biāo)是不，因?yàn)槲覀兊哪繕?biāo)是不計(jì)算計(jì)算HesseHesse矩陣矩陣 H(X(k) 11。那么，。那么， Ak只能在性質(zhì)上近似只能在性質(zhì)上近似 H(X(k) 11。因此，先研究一下。因此，先研究一下HesseHesse矩陣的逆陣矩陣的逆陣 H(X(k) 11的性質(zhì)。的性質(zhì)。考慮考慮 f(X)在在X(k)處的處的TaylorTaylor展開(kāi)式展開(kāi)式( )( )( )( )( )( )()()() ()1 () ()() 2kkTkkTkkf Xf Xf X

36、XXXXH XXX 令令X=X(k+1)，得，得求梯度求梯度得得( )( )( )()()()() kkkf Xf XH XXX (1)( )( )(1)( )()()()() kkkkkf Xf XH XXX記記(1)( )1(1)( )()() kkkkkkkkgggf Xf XXXX 則得擬牛頓條件：則得擬牛頓條件：( )1()g kkkXH X令令A(yù)k+1滿(mǎn)足擬牛頓條件，得：滿(mǎn)足擬牛頓條件，得：(A ) g kkkkXA即即AggkkkkkXA 滿(mǎn)足上述擬牛頓條件的滿(mǎn)足上述擬牛頓條件的 Ak 有無(wú)窮多個(gè)，因此變尺度法是一有無(wú)窮多個(gè)，因此變尺度法是一族方法。族方法。三、三、DFPDFP變

37、尺度矩陣變尺度矩陣DFPDFP公式是由公式是由DavidenDaviden在在19591959年提出來(lái)的，后由年提出來(lái)的，后由FletcherFletcher和和PowellPowell在在19631963年于以簡(jiǎn)化，故此而得名的。年于以簡(jiǎn)化，故此而得名的。Ag (g )TTkkkkkkkkkXXAA設(shè)設(shè)代入擬牛頓條件代入擬牛頓條件得：得：AggkkkkkXA Aggg (g )g gTTkkkkkkkkkkkkkkkXXAAXA 11 gggkkTTkkkkkXA比較系數(shù)得：比較系數(shù)得：DFP變尺度矩陣迭代變尺度矩陣迭代公式為：公式為：1gg ggg (0,1,2,) TTkkkkkkkkT

38、TkkkkkXXAAAAXAk四、四、BFGSBFGS變尺度矩陣變尺度矩陣由于由于DFPDFP變尺度法的數(shù)值穩(wěn)定性差，變尺度法的數(shù)值穩(wěn)定性差，19701970年由年由BrogdenBrogden、FletcherFletcher、GoldfarbGoldfarb、ShannoShanno提出數(shù)值穩(wěn)定性好的提出數(shù)值穩(wěn)定性好的BFGSBFGS變變尺度法，其尺度矩陣迭代公式如下：尺度法，其尺度矩陣迭代公式如下：1gg1gggg gg (0,1,2,) kTTkkkkkkkTTkkkkTTkkkkkTTkkkkAXXAAXXAXX AXXk五、變尺度矩陣的統(tǒng)一表達(dá)式五、變尺度矩陣的統(tǒng)一表達(dá)式19701

39、970年年HuangHuang對(duì)變尺度矩陣迭代公式進(jìn)行了統(tǒng)一處理，得出對(duì)變尺度矩陣迭代公式進(jìn)行了統(tǒng)一處理，得出如下公式：如下公式：Ag ()TTkkkkkkkX uAv 其中其中1112gkkkkkkuXA2122gkkkkkkvXA當(dāng)取當(dāng)取112211 gggkkTTkkkkkXA 12210kk為為DFPDFP公公式式當(dāng)取當(dāng)取1221kk220k為為BFGSBFGS公式公式當(dāng)取當(dāng)取當(dāng)取當(dāng)取12220kk1121111 gkkkTkkX 為為McCormickMcCormick公式公式11210kk1222121 gkkkTkkkg A 為為PearsonPearson公式公式(1)(1)取

40、初始點(diǎn)取初始點(diǎn)X(0)，置初始矩陣，置初始矩陣A A0 0=I=I，置精度要求，置精度要求, ,置置k=0.=0.六、變尺度法的算法步驟六、變尺度法的算法步驟(2)(2)計(jì)算計(jì)算gk= f(X(k)，如果如果 f(X(k)，則停止計(jì)算，將，則停止計(jì)算，將X(k)作為無(wú)約束問(wèn)題的解輸出；否則計(jì)算搜索方向作為無(wú)約束問(wèn)題的解輸出；否則計(jì)算搜索方向(3)(3)沿沿d(k)方向進(jìn)行一維搜索方向進(jìn)行一維搜索, ,即求解一維問(wèn)題即求解一維問(wèn)題( )( )()kkkdAf X (4)(4)計(jì)算計(jì)算 gk+1= f(X(k+1), gk= gk+1- gk， Xk= X(k+1)- X(k) 修正矩陣修正矩陣

41、Ak和尺度矩陣和尺度矩陣 Ak+1 =Ak + Ak( )( )min ( )()kkkf XAf X 得：得：(1)( )( )()kkkkkXXAf X(5)(5)置置k=k+1，若，若k0 0，則由，則由DFPDFP公式公式( (或或 BFGSBFGS公式公式) )構(gòu)造的構(gòu)造的A Ak+1是正定對(duì)稱(chēng)的。是正定對(duì)稱(chēng)的。若一維搜索是精確的，假設(shè)已進(jìn)行了若一維搜索是精確的，假設(shè)已進(jìn)行了m次迭代，則次迭代，則: :定理：若用定理：若用DFPDFP算法算法( (或或BFGSBFGS算法算法) )求解正定二次函數(shù)求解正定二次函數(shù)1()2TTf XX HXB XC(1)(1)搜索方向搜索方向d(0),

42、d(1),d(m-1)是是m個(gè)非零的個(gè)非零的HH共軛方向共軛方向; ;(2)(2)對(duì)于對(duì)于j=0，2，m-1，有有 A Am Xj= = gj 且當(dāng)且當(dāng)m=n-1-1時(shí)，有時(shí)，有A An=H=H-1-1證明：證明：僅對(duì)僅對(duì)DFPDFP公式進(jìn)行證明即可公式進(jìn)行證明即可. .由于由于 XkT gk 0 0，蘊(yùn)含著，蘊(yùn)含著 gk 0 0，再由，再由A Ak的正定性，得到的正定性，得到 gkT A Ak gk 0 0 ，因此，因此DFPDFP公式有意義。公式有意義。對(duì)任意的對(duì)任意的xRxRn n，考察，考察122ggggg()( gg )(g )() gggTTTTTTkkkkkkkkTTkkkkkT

43、TTTkkkkkkkTTkkkkkXXX XX AA XX AXX A XXAX A XAX AXXAX由廣義由廣義Cauchy-SchwarzCauchy-Schwarz不等式不等式證得證得A Ak1是正定的，其是正定的，其對(duì)稱(chēng)性是顯然的對(duì)稱(chēng)性是顯然的. .2()( gg )(g )TTTkkkkkkX A XAX A證明：證明：由算法知，搜索方向由算法知，搜索方向d(0),d(1),d(m-1)是零的?，F(xiàn)證明其共是零的?，F(xiàn)證明其共軛性。用數(shù)學(xué)歸納法證明：軛性。用數(shù)學(xué)歸納法證明： 01 01iTjmjjX H XjimAXgjm 八、變尺度法的算例八、變尺度法的算例用用DFPDFP變尺度法求

44、解下述無(wú)約束優(yōu)化問(wèn)題變尺度法求解下述無(wú)約束優(yōu)化問(wèn)題第六節(jié)第六節(jié) 坐標(biāo)輪換法坐標(biāo)輪換法 (CyclicCoordinateMethod) 一、方法簡(jiǎn)介一、方法簡(jiǎn)介 ( )( )min ()kkf Xd( )0,.,0,1,0,.,0kTkde取搜索方向?yàn)樽鴺?biāo)軸方向，即取搜索方向?yàn)樽鴺?biāo)軸方向，即 沿該方向求最優(yōu)點(diǎn)，即沿該方向求最優(yōu)點(diǎn)，即(1)( )( )=kkkXXd每次迭代只改變?cè)O(shè)計(jì)變量每次迭代只改變?cè)O(shè)計(jì)變量X的一個(gè)分量的值，而其他分的一個(gè)分量的值，而其他分量的值保持不變，故該方法又稱(chēng)為降維法。量的值保持不變，故該方法又稱(chēng)為降維法。二、幾何說(shuō)明二、幾何說(shuō)明 現(xiàn)以二維函數(shù)極小化問(wèn)題為例，說(shuō)明坐標(biāo)輪

45、換法的尋優(yōu)過(guò)程?，F(xiàn)以二維函數(shù)極小化問(wèn)題為例，說(shuō)明坐標(biāo)輪換法的尋優(yōu)過(guò)程。 1x2x(0)1X1e1e2e2e(1)1X(2)1X由由 (0)1X沿沿 1e求求 (1)1X即即 (1)(0)1111 1XXe(2)(0)11XX即即 (2)(1)1112 2XXe由由 沿沿 求求 (1)1X2e(2)1X完成第一輪搜索完成第一輪搜索 ，若，若 則停止搜索；負(fù)責(zé)進(jìn)行則停止搜索；負(fù)責(zé)進(jìn)行下一輪搜索。下一輪搜索。 三、算法框圖三、算法框圖 開(kāi)始開(kāi)始X1(0)= X(0),l=1輸入輸入X(0), ,n k=1 min ( ) =f(Xl(k-1)+ ek) Xl(k)= Xl(k-1)+ kl ek k

46、=n ? no k= k+1 yes ?( )(0)nllXX yes開(kāi)始開(kāi)始 Xl+1(0)= Xl(n) l=l+1 no輸出輸出X(*)= Xl(n)四、方法特點(diǎn)四、方法特點(diǎn) 1 1、簡(jiǎn)單、方便；、簡(jiǎn)單、方便； 2 2、對(duì)函數(shù)無(wú)連續(xù)性要求；、對(duì)函數(shù)無(wú)連續(xù)性要求； 3 3、收斂速度慢；、收斂速度慢； 4 4、可能產(chǎn)生偽最優(yōu)。、可能產(chǎn)生偽最優(yōu)。 第七節(jié)第七節(jié) powellpowell法法一、共軛方向的直接生成一、共軛方向的直接生成 對(duì)于一個(gè)二次函數(shù)對(duì)于一個(gè)二次函數(shù)1()2TTf XX AXB XC( )kX(1)kd( ,0)kX( )kd(1)kX( +1,0)kX( )kd( )()kf

47、 X(1)()kf X設(shè)點(diǎn)設(shè)點(diǎn)X(k)和和點(diǎn)點(diǎn)X(k1)是從不同出發(fā)點(diǎn)，沿同一方向是從不同出發(fā)點(diǎn)，沿同一方向d (k)進(jìn)行一維搜索而得的兩個(gè)極小點(diǎn)，進(jìn)行一維搜索而得的兩個(gè)極小點(diǎn)，則方向則方向d(k)與與點(diǎn)點(diǎn)X(k)和和點(diǎn)點(diǎn)X(k1)處的梯度處的梯度有如下關(guān)系：有如下關(guān)系：( )( )()0k Tkdf X( )(1)()0k Tkdf X上面兩式相減得：上面兩式相減得：( )(1)( )()0k TkkdA XX記記(1)(1)( )kkkdXX則則( )(1)0k TkdAd即即d(k)與與d(k1)關(guān)于矩陣關(guān)于矩陣A共軛共軛二、基本算法二、基本算法 以二維問(wèn)題為例，介紹以二維問(wèn)題為例，介紹

48、Powell基本算法基本算法1 1）任取初始點(diǎn)）任取初始點(diǎn)X1(0)(0)，沿各個(gè)坐標(biāo)軸方向，沿各個(gè)坐標(biāo)軸方向( (基本方向基本方向) )進(jìn)行一維搜索，進(jìn)行一維搜索，即即 (1)(0)1111 1XXe(2)(1)1112 2XXe2 2）產(chǎn)生新生方向，并由）產(chǎn)生新生方向，并由X1(2)(2)出發(fā)，出發(fā)，沿新生方向進(jìn)行一維搜索，沿新生方向進(jìn)行一維搜索，即即 (3)(2)1111XXd(2)(0)111dXX3 3）用新生方向）用新生方向d1擠掉原擠掉原基本方向基本方向組中的第一個(gè)方向組中的第一個(gè)方向e1,形成新的形成新的基本基本方向組方向組e2, d1。1x2x(0)1X1e2e(1)1X(2

49、)1X1d(2)1X2e1d2d*X4 4）令）令(0)(3)21XX進(jìn)行下一輪搜索。進(jìn)行下一輪搜索。對(duì)于二元二次目標(biāo)函數(shù)則可得其理論最優(yōu)解。對(duì)于二元二次目標(biāo)函數(shù)則可得其理論最優(yōu)解。三、基本算法框圖三、基本算法框圖開(kāi)始開(kāi)始X1(0)= X(0),l=1輸入輸入X(0), ,n i=1 min ( ) =f(Xl(i-1)+ di) Xl(i)= Xl(i-1)+ il di i=n ? no i= i+1 yes ?( )(0)nllXX yes輸出輸出X(*)= Xl(n)開(kāi)始開(kāi)始基本方向取為基本方向取為di, i=2,n1 Xl+1(0)= Xl(n1) ,l=l+1 no將將n個(gè)坐標(biāo)方向

50、作為初始基本方向個(gè)坐標(biāo)方向作為初始基本方向di, i=1,n dn+1= Xl(n)- Xl(0) min ( ) =f(Xl(i-1)+ dn+1) Xl(n+1)= Xl(n)+ ln+1 dn+1 l=n ? yes noX1(0)= Xl(n+1), l=1四、基本算法的缺陷四、基本算法的缺陷 POWELL基本算法在迭代中逐次生成共軛方向，而共軛方向是較好基本算法在迭代中逐次生成共軛方向，而共軛方向是較好的搜索方向，所以鮑威爾法又稱(chēng)作方向加速法。的搜索方向，所以鮑威爾法又稱(chēng)作方向加速法。 上述基本算法僅具有理論意義，不要說(shuō)對(duì)于一般函數(shù)，就是對(duì)于二次上述基本算法僅具有理論意義，不要說(shuō)對(duì)于一般函數(shù)，就是對(duì)于二次函數(shù)，這個(gè)算法也可能失效，因?yàn)樵诘械暮瘮?shù)，這個(gè)算法也可能失效，因?yàn)樵诘械膎個(gè)搜索方向有時(shí)會(huì)變成線個(gè)搜索方向有時(shí)會(huì)變成線性相關(guān)而不能形成共軛方向。這時(shí)張不成性相關(guān)而不能形成共軛方向。這時(shí)張不成n維空間，可能求不到極小點(diǎn)，維空間，可能求不到極小點(diǎn)，所以上述基本算法有待改進(jìn)。所以上述基本算法有待改進(jìn)。 在鮑威爾基本算法中，每一輪迭代都用連結(jié)始點(diǎn)和終點(diǎn)在鮑威爾基本算法中，每一輪迭代都用連結(jié)始點(diǎn)和終點(diǎn)所產(chǎn)生出的搜索方向去替換原向量組中的第一個(gè)向量，而不所產(chǎn)生出的搜索方向去替換原向量組中的第一個(gè)向量，而不管它的管它的“好壞好壞”，這是產(chǎn)生向量組線性相關(guān)的原因所在。因，