最優(yōu)化方法第四次

最優(yōu)化方法第四次第1頁(yè)，共21頁(yè)，2023年，2月20日，星期六

6.牛頓法的缺陷。7.編寫最速下降法程序。(建議用數(shù)學(xué)軟件)第2頁(yè)，共21頁(yè)，2023年，2月20日，星期六二、共軛梯度法1.共軛方向從前面已經(jīng)看出，負(fù)梯度方向并不是理想的搜索方向，要提高算法的收斂速度，需要尋找其它搜索方向。為了給尋找搜索方向提供依據(jù)，我們先來(lái)考慮判斷算法優(yōu)劣的方法。二次函數(shù)是一種比較簡(jiǎn)單的函數(shù)，而一般的目標(biāo)函數(shù)在極小點(diǎn)附近的性態(tài)又近似于二次函數(shù)，所以可以設(shè)想，一個(gè)算法如果對(duì)第3頁(yè)，共21頁(yè)，2023年，2月20日，星期六于二次函數(shù)比較有效，就可望對(duì)于一般函數(shù)（至少在極小點(diǎn)附近）也有較好的效果。下面我們就從二次函數(shù)出發(fā)，尋找比較有效的搜索方向。

第4頁(yè)，共21頁(yè)，2023年，2月20日，星期六考慮正定二次函數(shù)

由于A為正定矩陣，從而函數(shù)的等值線為平面上的一簇橢圓。第5頁(yè)，共21頁(yè)，2023年，2月20日，星期六顯然，如果橢圓非常狹長(zhǎng)，則最速下降法鋸齒形迭代的步長(zhǎng)越來(lái)越小。能否找到理想的搜索方向，使算法用最短的迭代找到極小點(diǎn)呢？下面的分析告訴我們，對(duì)于只包含兩個(gè)變量的正定二次函數(shù)，最多只要兩次迭代即可找到極小點(diǎn)。在初始點(diǎn)處，取負(fù)梯度方向?yàn)樗阉鞣较?，即，沿下降至處。假設(shè)在處，選擇適當(dāng)?shù)乃阉鞣较?沿即第6頁(yè)，共21頁(yè)，2023年，2月20日，星期六可直接找到極小點(diǎn)，即有,使。由最優(yōu)性條件，即，代入得，，亦即。用乘上式后得到。由最速下降法知，，從而。第7頁(yè)，共21頁(yè)，2023年，2月20日，星期六因?yàn)榕c正交，當(dāng)然線性無(wú)關(guān)，從而它們構(gòu)成二維平面的基底，故可表示為它們的線性組合，用左乘上式得，考慮到，得

從而第8頁(yè)，共21頁(yè)，2023年，2月20日，星期六定義2.1設(shè)為中的k個(gè)非零向量，A為n階正定矩陣。若對(duì)任意均有，則稱關(guān)于A兩兩共軛。當(dāng)A為單位矩陣時(shí)，意味著兩兩正交，所以共軛是正交的推廣。第9頁(yè)，共21頁(yè)，2023年，2月20日，星期六定理2.2設(shè)A為n階正定矩陣，若關(guān)于A兩兩共軛，則是線性無(wú)關(guān)的。證設(shè)有，使得用左乘上式，得因?yàn)锳正定，，得，即線性無(wú)關(guān)。第10頁(yè)，共21頁(yè)，2023年，2月20日，星期六2.n元正定二次函數(shù)的共軛梯度法對(duì)n元正定二次函數(shù)有下面兩個(gè)重要定理。定理2.3對(duì)n元正定二次函數(shù)設(shè)關(guān)于A兩兩共軛。從任意初始點(diǎn)出發(fā)，依次沿方向執(zhí)行一維搜索到，第11頁(yè)，共21頁(yè)，2023年，2月20日，星期六則垂直于前面所有的搜索方向，即

定理2.4：對(duì)n元正定二次函數(shù)

設(shè)關(guān)于A兩兩共軛。從任意初始點(diǎn)出發(fā)，依次沿執(zhí)行一維搜索到，則即為極小點(diǎn)。第12頁(yè)，共21頁(yè)，2023年，2月20日，星期六2.正定二次函數(shù)的共軛梯度法仿照與的關(guān)系，我們構(gòu)造下列搜索方向，據(jù)此可證明定理2.5。第13頁(yè)，共21頁(yè)，2023年，2月20日，星期六定理2.5：對(duì)n元正定二次函數(shù)從任意初始點(diǎn)出發(fā)，依次按上述搜索方向經(jīng)次迭代下降至，即則即為極小點(diǎn)。如果一個(gè)算法能用有限步求出二次函數(shù)的極小點(diǎn)（從理論上說(shuō)），則稱這個(gè)算法具有二階收斂性或有限步收斂性。第14頁(yè)，共21頁(yè)，2023年，2月20日，星期六3.一般函數(shù)的共軛梯度法對(duì)于一般函數(shù)，已無(wú)正定矩陣A和共軛的概念，因此必須尋求一種與共軛方向表達(dá)式等價(jià)的形式，其中不含有矩陣A。由，得從而第15頁(yè)，共21頁(yè)，2023年，2月20日，星期六又故最終第16頁(yè)，共21頁(yè)，2023年，2月20日，星期六綜上所述，對(duì)于一般目標(biāo)函數(shù)，可按下述規(guī)則確定搜索方向：此方法稱為F-R(Fletcher-Reeves)共軛梯度法。第17頁(yè)，共21頁(yè)，2023年，2月20日，星期六§3.擬牛頓法一、牛頓法最速下降法的本質(zhì)是用線性函數(shù)逼近目標(biāo)函數(shù)。因此，要想得到快速算法，需要考慮用高次函數(shù)逼近。如果采用二次多項(xiàng)式逼近，則稱為牛頓法。在給定點(diǎn)附近將展為二階Taylor展式，即第18頁(yè)，共21頁(yè)，2023年，2月20日，星期六記，則。若正定，則為凸函數(shù),有惟一極小點(diǎn),滿足，即，。記，則,稱之為牛頓迭代，稱為牛頓方向。牛頓迭代可以理解為從出發(fā)，沿牛頓方向取步長(zhǎng)。顯然，對(duì)正定二次函數(shù),從任意初始點(diǎn)出發(fā)，牛頓迭代一步即可達(dá)到第19頁(yè)，共21頁(yè)，2023年，2月20日，星期六最小點(diǎn)。理論分析表明，當(dāng)初始點(diǎn)離較近時(shí)，牛頓迭代法能以二階速度收斂到。但當(dāng)離較遠(yuǎn)時(shí)，牛頓迭代可能不收斂，甚至迭代過(guò)程無(wú)法進(jìn)行，原因如下：①若為奇異陣，無(wú)意義，迭代無(wú)法進(jìn)行；②即使非奇異，但不一定正定，從而不能保證，即牛頓方向第20頁(yè)，共21頁(yè)，2023年，2月20日，星期六不一定是下降方向；③即使