優(yōu)化設(shè)計(jì)第5次課

第三節(jié)牛頓型方法最速下降法在迭代過(guò)程中由于存在鋸齒狀搜索路徑，使得最初幾步迭代數(shù)值下降很快，但是總體下降得并不快，而且愈接近極值點(diǎn)下降得越慢，其主要原因是梯度法在確定搜索方向時(shí)只考慮目標(biāo)函數(shù)在迭代點(diǎn)的局部性質(zhì)．即利用一階偏導(dǎo)數(shù)(梯度)信息。而牛頓法進(jìn)一步利用了目標(biāo)函數(shù)的二階偏導(dǎo)數(shù)，考慮了梯度的變化趨勢(shì)，因而更為全面地確定合適的搜索方向，以便很快地搜索到極小點(diǎn)。這里所介紹的牛頓型方法主要包括牛頓法和阻尼牛頓法。一、牛頓法的基本原理牛頓法是一種收斂速度很快的方法，其基本思路是利用二次曲線來(lái)逐點(diǎn)近似原目標(biāo)函數(shù)，以二次曲線的極小點(diǎn)來(lái)近似原目標(biāo)函數(shù)的極小點(diǎn)并逐漸逼近該點(diǎn)。設(shè)已知一維目標(biāo)函數(shù)的初始點(diǎn)，過(guò)點(diǎn)作一與原目標(biāo)函數(shù)相切的二次曲線——拋物線，求拋物線的極小點(diǎn)的坐標(biāo)，將代入原目標(biāo)函數(shù)，求得得到點(diǎn)。過(guò)點(diǎn)再作一個(gè)與相切的二次函數(shù)，得到下一個(gè)最小點(diǎn),解得點(diǎn)。重復(fù)做下去直到找到原目標(biāo)函數(shù)的極小點(diǎn)的坐標(biāo)值為止，如下圖所示。在逼近的過(guò)程中所用的二次函數(shù)是以原目標(biāo)函數(shù)在迭代點(diǎn)附近的泰勒展開式的二次項(xiàng)，一維目標(biāo)函數(shù)在點(diǎn)，逼近所用二次函數(shù)為此二次函數(shù)的極小點(diǎn)，可由極值存在的必要條件求得,也即求得。

下一次逼近原目標(biāo)函數(shù)的二次曲線即用在點(diǎn)的泰勒展開式二次項(xiàng)。

把上述過(guò)程推廣到維問(wèn)題，即是當(dāng)時(shí)，可求得二次函數(shù)的極值點(diǎn)，對(duì)上式矩陣方程求導(dǎo)，可得到若為可逆矩陣，從而得到這次逼近的二次函數(shù)的最小點(diǎn)

由于是的一個(gè)近似表達(dá)式，所求得的極小點(diǎn)并不是目標(biāo)函數(shù)真正的極小點(diǎn)。只有當(dāng)目標(biāo)函數(shù)本身是二次函數(shù)時(shí)，所求的極小點(diǎn)才是目標(biāo)函數(shù)的真正極小點(diǎn),這種情況一次迭代就可求出目標(biāo)函數(shù)的最優(yōu)點(diǎn)。二、牛頓法的迭代公式或者寫成其中稱牛頓搜索方向，。在一般情況下，不一定是二次函數(shù)，則不能通過(guò)一次迭代就求出極小點(diǎn)，即極小點(diǎn)不在方向上，但由于在點(diǎn)附近，函數(shù)與是近似的，所以這個(gè)方向可以作為近似方向，為了求得極小值，可以把由上式求得的作為下一個(gè)迭代點(diǎn)，通過(guò)反復(fù)地循環(huán)迭代，不斷逼近到的極小點(diǎn)。于是得到牛頓法的迭代格式為牛頓法就是通過(guò)這種迭代，逐次向極小點(diǎn)逼近。例：函數(shù)的初始點(diǎn)取，用牛頓法求它的極值點(diǎn)。三、阻尼牛頓法從牛頓法迭代公式的推導(dǎo)過(guò)程可以看出，迭代點(diǎn)的位置是按照極值條件確定的，其中并未強(qiáng)調(diào)含有沿下降方向搜素的概念。因此對(duì)于非二次函數(shù)，如果采用上述牛頓法迭代計(jì)算，有時(shí)可能會(huì)使函數(shù)值上升，即出現(xiàn)的現(xiàn)象，這就有可能導(dǎo)致迭代結(jié)果收斂于極大點(diǎn)或者不收斂等情況。基于這種原因需對(duì)上述牛頓法進(jìn)行改進(jìn)，于是便出現(xiàn)了“阻尼牛頓法”。其具體的修正方法是，用求時(shí)不是直接利用原來(lái)的迭代公式計(jì)算，而是沿著點(diǎn)處的牛頓方向進(jìn)行一維搜索，將該方向上的最優(yōu)點(diǎn)作為，于是牛頓法迭代公式可以改寫成其中搜索方向取牛頓方向，即式中為沿牛頓方向進(jìn)行一維搜素的最優(yōu)步長(zhǎng)，可稱之為阻尼因子。可通過(guò)如下極小化過(guò)程求得這種阻尼牛頓法通常又稱為廣義牛頓方法，或稱修正牛頓法。原來(lái)的牛頓法相當(dāng)于阻尼牛頓法的搜索步長(zhǎng)恒取1的情況。雖然相對(duì)于原來(lái)的牛頓法，阻尼牛頓法的計(jì)算工作量多了一些，但是在目標(biāo)函數(shù)的誨色矩陣為正定的情況下，它能保證每次迭代都能使函數(shù)值有所下降。即使初始點(diǎn)選擇不當(dāng)，用這種搜索方法也會(huì)成功，同時(shí)，它還保留了古典牛頓法收斂快的優(yōu)點(diǎn)。四、阻尼牛頓法的計(jì)算步驟(1)給定初始點(diǎn)，給定精度，置；(2)計(jì)算點(diǎn)的梯度及其梯度模；(4)計(jì)算海色矩陣并求其逆矩陣，確定牛頓向并沿牛頓方向做一維搜索，求出在方向上的最優(yōu)步長(zhǎng)；(5)計(jì)算第個(gè)迭代點(diǎn)；(3)檢查收斂精度。若，則迭代停止，輸出最優(yōu)解，；否則，轉(zhuǎn)下一步；(6)置，返回到(2)繼續(xù)進(jìn)行搜索。

(2)對(duì)目標(biāo)函數(shù)性態(tài)有較嚴(yán)格的要求。除了函數(shù)具有連續(xù)的一、二階偏導(dǎo)數(shù)以外，為了保證函數(shù)的穩(wěn)定下降，海色矩陣必須正定。同時(shí)，為了能求逆矩陣形成牛頓方向，又要求海色矩陣必須非奇異。(3)計(jì)算較為復(fù)雜。除了求梯度以外，還要計(jì)算二階偏導(dǎo)數(shù)矩陣和它的逆矩陣，占用機(jī)器的儲(chǔ)存量也很大。(1)阻尼牛頓法具有二階收斂速度，即對(duì)于正定二元二次函數(shù)，應(yīng)用阻尼牛頓法只要一次迭代就可以達(dá)到極小點(diǎn)。五、阻尼牛頓法的特點(diǎn)同最速下降法一樣，牛頓型方法也是求解無(wú)約束優(yōu)化問(wèn)題的一種古老的算法。由于阻尼牛頓法存在上述(2)、(3)所述的缺點(diǎn)，限制了其在解決實(shí)際問(wèn)題中的應(yīng)用。近年來(lái)，人們研究了很多改進(jìn)的算法，比如后面將要介紹的變尺度法就是在阻尼牛頓法的基礎(chǔ)上形成的一種新的無(wú)約束優(yōu)化方法。牛頓法和阻尼牛頓法統(tǒng)稱牛頓型方法，這類方法的主要缺點(diǎn)每次迭代過(guò)程都要計(jì)算函數(shù)二階導(dǎo)數(shù)矩陣，并要對(duì)該矩陣求逆。這樣工作量相當(dāng)大。特別是矩陣求逆計(jì)算，當(dāng)設(shè)計(jì)變量維數(shù)較高時(shí)工作量更大。因此，牛頓法很少被直接采用，但是對(duì)于那些容易計(jì)算一階導(dǎo)數(shù)和海色矩陣及其逆的二次函數(shù)采用牛頓法還是很方便的。第四節(jié)共軛方向與共軛方向法一、共軛方向的概念和性質(zhì)1.問(wèn)題的提出

二次函數(shù)是最簡(jiǎn)單的非線性函數(shù)，而二階導(dǎo)數(shù)矩陣為正定的目標(biāo)函數(shù)在極值點(diǎn)附近又都近似于二次函數(shù)。所以研究二次函數(shù)的無(wú)約束極值問(wèn)題，可以推廣到一般無(wú)約束問(wèn)題。二次函數(shù)的一般矩陣表達(dá)式如下

(4-1)

如圖所示，二元二次函數(shù)的等值線為一族橢圓，若按最速下降法搜索極小點(diǎn),從初始點(diǎn)出發(fā)，沿方向作一維搜索，得到方向的極小點(diǎn)，再?gòu)某霭l(fā)向下搜索。如繼續(xù)用最速下降法，這時(shí)應(yīng)沿負(fù)梯度方向搜索，即，顯然與正交，即。（4-2）

下面就來(lái)討論一下直接指向極小點(diǎn)的搜索方向需要滿足什么樣的條件。若直接指向極小點(diǎn)，則迭代公式可寫成式中是方向上的最佳步長(zhǎng)因子。對(duì)前面式（4-1）二次函數(shù)的一般矩陣表達(dá)式進(jìn)行求導(dǎo)，得（4-3）

當(dāng)時(shí)，，因?yàn)槭菢O小點(diǎn)，所以應(yīng)滿足極值點(diǎn)的必要條件，即將上面式（4-3）的迭代公式代入上式，得（4-4）

由于在點(diǎn)的梯度可以表示為于是式（4-4）可以簡(jiǎn)化為（4-5）

將式（4-5）左乘，并考慮式（4-2）和，則有式（4-6）即為從點(diǎn)出發(fā)直接指向目標(biāo)函數(shù)的極小點(diǎn)的搜索方向所需滿足的條件。（4-6）

從上述推導(dǎo)可知，在滿足(4-6)的條件下，對(duì)正定的二元函數(shù)，可從任意初始點(diǎn)出發(fā)，沿和方向，經(jīng)二次搜索即可達(dá)到極小點(diǎn)。把滿足式(4-6)的向量和稱為對(duì)的共軛向量，或者稱與為的共軛方向。

2.共軛方向的概念由前面分析可知，設(shè)為階實(shí)對(duì)稱正定矩陣，如果在維歐氏空間中有兩個(gè)維非零向量與滿足（4-7）

則稱向量與關(guān)于實(shí)對(duì)稱正定矩陣是共軛的?；蚝?jiǎn)稱與關(guān)于共軛，或與為的共軛方向。（4-8）

如果非零向量組，且這個(gè)向量組中的任意兩個(gè)向量關(guān)于階實(shí)對(duì)稱正定矩陣是共軛的，即滿足式則稱向量組關(guān)于矩陣是共扼的，或簡(jiǎn)稱該向量組為的共軛方向。當(dāng)(單位矩陣)時(shí)，式(4-8)變成另外，對(duì)于某一固定的矩陣來(lái)說(shuō)，和也不是唯一的，即存在多于一對(duì)向量與滿足式(4-7)。例如：若，，，則若，，同樣可得3.共軛方向的性質(zhì)性質(zhì)1

設(shè)為階對(duì)稱正定矩陣，若非零向量組是對(duì)共軛的，則這n個(gè)向量是線性無(wú)關(guān)的。性質(zhì)2

從任意初始點(diǎn)出發(fā)，順次沿n個(gè)的共軛方向進(jìn)行一維搜索．最多經(jīng)過(guò)n次迭代就可以找到由式(4-1)所表示的二次函數(shù)的極小點(diǎn)。性質(zhì)3

在n維空間中互相共軛的非零向量的個(gè)數(shù)不超過(guò)n。二、共軛梯度法采用共軛方向進(jìn)行搜索的方法統(tǒng)稱為共軛方向法。實(shí)際上，提供共軛向量組的方法有許多種，從而可以形成各種具體的共軛方向法。共軛梯度法就是共軛方向法的一種，它與其他共軛方向算法的區(qū)別，就在于在該方法中每一個(gè)共軛向量都是依賴于迭代點(diǎn)處的負(fù)梯度而構(gòu)造出來(lái)的。1.共軛方向的構(gòu)成

對(duì)于正定二次函數(shù)從任意沿

給定的初始點(diǎn)出發(fā)，先沿著負(fù)梯度方向進(jìn)行一維搜索，求得極小點(diǎn)。然后每迭代一步就構(gòu)成一個(gè)共軛方向，經(jīng)過(guò)次迭代，產(chǎn)生個(gè)互相共軛方向，第個(gè)迭代點(diǎn)，就是極小點(diǎn)。如下圖所示?？紤]第步迭代，從迭代點(diǎn)出發(fā)，作一維搜索，求極小點(diǎn)，即式中最優(yōu)步長(zhǎng)因子，可由下式求得在和兩點(diǎn)函數(shù)的梯度分別為由式上面兩式相減得（4-9）

為了簡(jiǎn)便起見，令將上式左乘，得到（4-10）

根據(jù)極小點(diǎn)的迭代方程，可以將上面式（4-9）簡(jiǎn)化為為使次的搜索方向與共軛，應(yīng)使將上式代入（4-10）中，得（4-11）上式表明了共軛方向與梯度之間的關(guān)系，同時(shí)也表明了沿著方向進(jìn)行一維搜索，所得到的終點(diǎn)和起點(diǎn)的梯度之差與共軛方向正交。式中要使得求出的與共軛，故稱為共軛系數(shù)，它可以根據(jù)共軛方向與梯度的關(guān)系求得。將上式代入式（4-11），得共軛梯度法在點(diǎn)構(gòu)成一個(gè)新的共軛方向，是利用迭代點(diǎn)的負(fù)梯度與前一步迭代的搜索方向兩者的線性組合而成的，即（4-12）（4-13）由于與正交，故有將以上兩個(gè)關(guān)系代入，并展開式（4-13）得即

式中，分別為點(diǎn)，的梯度的模。

把上式代入式（4-12），就可利用相鄰兩個(gè)迭代點(diǎn)的梯度來(lái)求得共軛方向，所以這種方法稱為共軛梯度法。綜上所述得到一組共軛梯度法的計(jì)算公式為（4-14）

2.共軛梯度法的計(jì)算步驟(1)給定初始點(diǎn)，允許誤差，輸入維數(shù)n，計(jì)算函數(shù)在初始點(diǎn)處的梯度，即

(2)用一維搜索方法求