第四章 第四節(jié)

§2.4無約束優(yōu)化法

梯度法牛頓法

共軛方向法變尺度法

共軛梯度法一、梯度法

1.基本思想梯度方向是函數(shù)增加最快的方向，而負(fù)梯度方向是函數(shù)下降最快的方向；梯度法以負(fù)梯度方向?yàn)樗阉鞣较?，每次迭代都沿著?fù)梯度方向一維搜索，直到滿足精度要求為止；因此，梯度法又稱為最速下降法。

設(shè)在某次迭代中已取得迭代點(diǎn)，從該點(diǎn)出發(fā)，取負(fù)梯度方向：式中，這樣，第k+1次迭代計(jì)算所得的新點(diǎn)為：梯度法迭代公式

因?yàn)闉橐阎?，故和易求出，只要知道步長后，就可以得到新點(diǎn)，且能保證如此反復(fù)計(jì)算，直到達(dá)到最優(yōu)點(diǎn)。為了使目標(biāo)函數(shù)值在搜索方向上獲得最多的下降，沿負(fù)梯度方向一維搜索，從而求得最優(yōu)步長。2.迭代步驟步驟一

任選初始點(diǎn)，計(jì)算精度ε，令k=0；步驟二計(jì)算點(diǎn)的梯度及梯度的模，并令步驟三判斷是否滿足精度指標(biāo)若，則為近似最優(yōu)點(diǎn)，迭代停止，輸出最優(yōu)解和若不滿足，轉(zhuǎn)下一步步驟四以為出發(fā)點(diǎn)，沿負(fù)梯度方向求最優(yōu)步長，即沿進(jìn)行一維搜索，求能使函數(shù)值下降最多的步長因子；步驟五確定新的近似點(diǎn)，此點(diǎn)就是下次迭代的出發(fā)點(diǎn)，即步驟六令k=k+1轉(zhuǎn)步驟二，直到滿足精度要求為止。給定、k=0

？轉(zhuǎn)出k=k+1梯度法的程序框圖3.舉例用梯度法求函數(shù)的極小值，初始點(diǎn)，計(jì)算精度。解(1)計(jì)算梯度：(2)計(jì)算函數(shù)在點(diǎn)的梯度及梯度的模：(3)因?yàn)椋粷M足精度指標(biāo)，轉(zhuǎn)入第(4）步；(4)從出發(fā)，沿著方向一維搜索，將代入目標(biāo)函數(shù)并求其極小值式中為單變量α的一維函數(shù)，令

所以求得一維優(yōu)化的最優(yōu)步長(5)新點(diǎn)(6)計(jì)算目標(biāo)函數(shù)在點(diǎn)的梯度及梯度的模

由于已滿足精度要求，故停止迭代下去，得到最優(yōu)解為：二、牛頓法

1.基本思想設(shè)目標(biāo)函數(shù)是連續(xù)二階可微的，將函數(shù)在點(diǎn)按泰勒級數(shù)展開，并取到二次項(xiàng)：將其展開為：對x求導(dǎo)，其極值點(diǎn)必滿足一階導(dǎo)數(shù)為零，所以，得到上式與一維搜索公式比較，則有搜索方向，步長因子牛頓法的迭代算式其中稱為牛頓方向。2.迭代步驟步驟一給定初始點(diǎn)，計(jì)算精度ε，令k=0；步驟二計(jì)算點(diǎn)的梯度、二階導(dǎo)數(shù)矩陣及其逆矩陣。步驟三構(gòu)造搜索方向步驟四沿方向進(jìn)行一維搜索，得迭代點(diǎn)步驟五收斂判斷：若，則為近似最優(yōu)點(diǎn)，迭代停止，輸出最優(yōu)解和終止計(jì)算。若不滿足，令k=k+1，轉(zhuǎn)第二步繼續(xù)迭代。3.舉例用牛頓法求函數(shù)的極小值。解：(1)取初始點(diǎn)(2)計(jì)算牛頓方向故(3)極小值

數(shù)學(xué)分析表明，牛頓法具有很好的局部收斂性質(zhì)，對二次函數(shù)來說，僅一步就達(dá)到優(yōu)化點(diǎn)，但對一般函數(shù)來說，在一定條件下，當(dāng)初始點(diǎn)的選取充分接近目標(biāo)函數(shù)的極小點(diǎn)時(shí)，有很快的收斂速度，但若初始點(diǎn)選取離最小點(diǎn)比較遠(yuǎn)，就難保證收斂；牛頓法必須求一階、二階導(dǎo)數(shù)及求逆陣，這對較復(fù)雜的目標(biāo)函數(shù)來說，是較困難的。三、共軛方向法橢圓的共軛方向共軛方向的基本思想1.橢圓的共軛方向如圖所示的橢圓中，任意一組平行弦的中點(diǎn)的連線必位于過橢圓中心O的直線S上，這些平行弦所組成的直線族的方向S1與中點(diǎn)連線方向S互稱為共軛方向，即S1與S互為共軛方向。

橢圓中的平行弦的極限情況是與橢圓相切的弦S0，根據(jù)一維搜索觀點(diǎn)，該弦S0與橢圓的切點(diǎn)就是沿S0方向的一維搜索的優(yōu)化點(diǎn)。共軛方向的代數(shù)含義是：設(shè)有兩個(gè)向量Si與Sj及n×n階對稱正定矩陣A，若滿足則稱兩向量Si與Sj對于矩陣A共軛。2.共軛方向的基本思想設(shè)二元函數(shù)的極值點(diǎn)為，將函數(shù)在展開成泰勒級數(shù)，并取其二次項(xiàng)，若其海色矩陣為正定矩陣，則其目標(biāo)函數(shù)的等值線的極值點(diǎn)附近是近似的同心橢圓族，根據(jù)橢圓的共軛方向，只要沿兩個(gè)相互平行的方向S1進(jìn)行一維搜索，找出目標(biāo)函數(shù)沿該兩個(gè)方向的極小點(diǎn)，然后沿與S共軛的方向進(jìn)行一維搜索，就可以求得目標(biāo)函數(shù)的優(yōu)化點(diǎn)，也就是說共軛方向法是以橢圓的共軛方向作為搜索方向的。

在n維空間中，用數(shù)學(xué)歸納法可以證明，對n維二次目標(biāo)函數(shù)，從任意點(diǎn)出發(fā)，可以找到n個(gè)共軛的向量。依次對這些向量分別進(jìn)行一維搜索，就可以找到n維二次目標(biāo)函數(shù)f(X)的極小點(diǎn)，即應(yīng)用這種算法通過有限次（即n步），可以得到目標(biāo)函數(shù)的極小點(diǎn)。

如果一種算法，從理論上講經(jīng)過有限步的搜索可以求出二次目標(biāo)函數(shù)的極小點(diǎn)，則稱這種算法具有二次收斂性，因此，共軛方向法具有二次收斂性。基于共軛方向的思想，發(fā)展起來了多種共軛方向法，在此介紹比較成熟的三種方法：變尺度法、共軛梯度法和Powell法。四、變尺度法

變尺度法是優(yōu)化方法在最近二十幾年來發(fā)展起來的最有影響的研究成果之一，它被公認(rèn)為是求解無約束極值問題的最有效的算法之一，這種方法是在牛頓法基礎(chǔ)上發(fā)展起來的一種共軛方向法，用得較多的是DFP變尺度法。1.DFP(Davidon-Fletcher-Powell)

牛頓法雖比梯度法收斂的快，但必須求目標(biāo)函數(shù)的二階導(dǎo)數(shù)及逆陣，不僅困難且工作量大，因此在牛頓法基礎(chǔ)上Davidon-Fletcher-Powell提出了用一個(gè)近似矩陣代替求二階導(dǎo)數(shù)及逆陣，而且該矩陣在每一次迭代中都不同，所以稱為變尺度矩陣。一維搜索中最優(yōu)步長因子:變尺度法的搜索方向?yàn)?迭代公式為:2.迭代步驟步驟一

取初始點(diǎn)，計(jì)算精度ε；步驟二令k=0,,I為單位陣，搜索方向；步驟三一維搜索(梯度法）；步驟四計(jì)算(k+1)步梯度，步驟五判別精度指標(biāo)：如果，則為極小點(diǎn)；否則轉(zhuǎn)下一步。步驟六計(jì)算近似矩陣，構(gòu)造新的搜索方向；所以令k=k+1，轉(zhuǎn)步驟三，直到滿足精度要求為止。3.舉例用變尺度法求函數(shù)的極小值。解：(1)取初始點(diǎn)：(2)一維搜索(3)如何求？(4)搜索方向

與牛頓法比較其結(jié)果非常接近，從本例中可以看出用近似矩陣代替二階導(dǎo)數(shù)及逆陣是可行的。如何判斷搜索結(jié)束？五.共軛梯度法

1.基本思想從初始點(diǎn)出發(fā)，沿著該點(diǎn)負(fù)梯度方向一維搜索到，如圖所示。然后從出發(fā)，按照與上一次搜索方向相共軛的方向進(jìn)行搜索，也就是，A為對稱正定矩陣。根據(jù)共軛方向原理，沿著方向一維搜索，就可以直接達(dá)到優(yōu)化點(diǎn)。2.共軛梯度的遞推公式設(shè)梯度用g表示，k+1點(diǎn)的梯度可以由k點(diǎn)的梯度推算出來；設(shè)目標(biāo)函數(shù)是n維二次函數(shù)：式中A——n×n對稱正定矩陣；梯度為：現(xiàn)從出發(fā)，沿方向一維搜索得：由一維搜索的幾何描述可知，搜索方向是處等值線的切線，而點(diǎn)的梯度與該切點(diǎn)切線方向垂直，所以：

和的梯度由式可得以上兩式相減得遞推公式為：當(dāng)已知時(shí)，可計(jì)算。若目標(biāo)函數(shù)是非二次函數(shù)，則可將函數(shù)按泰勒級數(shù)展開，忽略三次方以上的項(xiàng)，然后用二次函數(shù)來逼近3.共軛梯度方向共軛梯度法的關(guān)鍵是如何構(gòu)造梯度的共軛方向。由圖可以看出，的方向可以看成是和的線性組合，即式中只要求出，則可求出：由梯度遞推公式兩邊乘以得：因?yàn)楦鶕?jù)共軛方向的含義：所以把代入得：

展開該式得：因?yàn)?，代入：可得：則有：4.迭代步驟(以二維為例)步驟一取初始點(diǎn)，計(jì)算精度ε；步驟二計(jì)算梯度，從出發(fā)，沿方向一維搜索到；步驟三由式計(jì)算；

由式計(jì)算；則步驟四從出發(fā)，沿方向一維搜索，就可以達(dá)到優(yōu)化點(diǎn)。5.舉例用共軛梯度法求函數(shù)的極小值。解：(1)第一步是梯度法，取初始點(diǎn)沿方向一維搜索得：(2)計(jì)算點(diǎn)的梯度：

由計(jì)算(3)計(jì)算搜索方向(4)從出發(fā)，沿著的方向一維搜索，其最優(yōu)步長由此可得：(5)判斷是否達(dá)到精度ε=0.01要求：則為極小點(diǎn)。

從以上可以看出，對同一個(gè)