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

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

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

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

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

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

(4-1)

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

下面就來討論一下直接指向極小點(diǎn)的搜索方向需要滿足什么樣的條件。若直接指向極小點(diǎn)，則迭代公式可寫成式中是方向上的最佳步長因子。對前面式（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）可以簡化為（4-5）

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

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

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

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

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

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

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

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

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

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

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

根據(jù)極小點(diǎn)的迭代方程，可以將上面式（4-9）簡化為為使次的搜索方向與共軛，應(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)的梯度來求得共軛方向，所以這種方法稱為共軛梯度法。綜上所述得到一組共軛梯度法的計(jì)算公式為（4-14）

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

(2)用一維搜索方法求