第四章 無約束最優(yōu)化方法-大學(xué)課件-閱讀-

第四章無約束最優(yōu)化方法§

4.1

最速下降法問題提出下降最快?時，

取極小值．問題：在點

處，沿什么方向分析：考查：顯然當(dāng)因此：下降最快，亦即最速結(jié)論：負(fù)梯度方向使下降方向．最速下降法算法Step1:給出停．Step2:

計算

如果Step3:

計算下降方向Step4:

計算步長因子Step5:

令轉(zhuǎn)步２.是正定二次函數(shù),分析：設(shè)由精確的線搜索確定的特別當(dāng)：例1：用最速下降法求解：解：分析：(1)因此：最速下降法是整體收斂的，且是線性收斂的．(2)兩個相鄰的搜索方向是正交的．收斂性分析定理1:設(shè)在上存在且一致連續(xù)，則最速下降法產(chǎn)生的序列滿足或者對某個

有

或者證明：對于最速下降法，由以上定理立得．收斂性分析定理2:

設(shè)

二次連續(xù)可微，且其中

是個正常數(shù)，對任何給定的初始點最速下降算法或有限終止，或者或者證明：用以上的結(jié)論：最速下降法優(yōu)點程序設(shè)計簡單，計算量小，存儲量小，對初始點沒有特別要求．有著很好的整體收斂性，即使對一般的目標(biāo)函數(shù)，它也整體收斂．最速下降法缺點(1)最速下降法是線性收斂的，并且有時是很慢的線性收斂．原因：①僅反映

在

處的局部性質(zhì)．②相繼兩次迭代中搜索方向是正交的．小結(jié)(1)最速下降法是基本算法之一，而非有效的實用算法．最速下降法的本質(zhì)是用線性函數(shù)來近似目標(biāo)函數(shù)，要想得到快速算法，需要考慮對目標(biāo)函數(shù)的高階逼近．§

4.2

牛頓法基本思想利用目標(biāo)函數(shù)

在點

處的二階Taylor展開式去近似目標(biāo)函數(shù)，用二次函數(shù)的極小點去逼近目標(biāo)函數(shù)的極小點．算法構(gòu)造設(shè)海色陣二階連續(xù)可微，正定．問題：如何從有唯一極小點，用這個因為

正定，則極小點作為所以要求：即：因此：這就是牛頓法迭代公式．注：這里牛頓法算法停．Step1:給出

Step2:計算Step3:否則計算Step4:令如果并且求解方程得出轉(zhuǎn)步２.例1：用牛頓法求解：解：牛頓法收斂定理定理1:設(shè)部極小點，二次連續(xù)可微，

是正定．假定的局的海色陣滿足Lipschitz條件，即存在使得對于所有

有：元素．則當(dāng)

牛頓迭代有意義，其中

是海色陣

的充分靠近

時，對于一切迭代序列收斂到

并且具有二階收斂速度．牛頓法優(yōu)點(1)如果正定且初始點選取合適，算法二階收斂．(2)對正定二次函數(shù)，迭代一次就可以得到極小點．牛頓法缺點對多數(shù)問題算法不是整體收斂的．每次都需要計算

計算量大．每次都需要解方程組有時奇異或病態(tài)的，無法確定或

不是下降方向．收斂到鞍點或極大點的可能性并不?。枘崤ｎD法算法Step1:給出停．Step2:計算

Step3:否則計算如果并且求解方程得出Step4:沿

Step5:令進行線搜索，得出轉(zhuǎn)Step2.阻尼牛頓法收斂定理二階連續(xù)可微，又設(shè)對任意的使得

在定理2:設(shè)存在常數(shù)上滿足：則在精確線搜索條件下，阻尼牛頓法產(chǎn)生的點列滿足：當(dāng)

是有限點列時，其最后一個點為的唯一極小點．當(dāng)

是無限點列時，收斂到

的唯一極小點阻尼牛頓法收斂定理二階連續(xù)可微，又設(shè)對任意的使得

在定理3:設(shè)存在常數(shù)上滿足：則在Wolfe不精確線搜索條件下，阻尼牛頓法產(chǎn)生的點列

滿足：且收斂到的唯一極小點．例2：用阻尼牛頓法求解：解：顯然

不是正定的，但：于是，沿方向

進行線搜索，得其極小點

從而迭代不能繼續(xù)下去．帶保護的牛頓法算法為奇異的，轉(zhuǎn)Step8，否則，給出

Step1:若Step2:令

Step3:若Step4:若則轉(zhuǎn)Step8，否則，則轉(zhuǎn)Step9，否則，進行線搜索，求出Step5:沿方向并令Step6:若

Step7:令

Step8:令

Step9:令停；轉(zhuǎn)Step1；轉(zhuǎn)Step5；轉(zhuǎn)Step5.例3：用帶保護的牛頓法求解：解：顯然

不是正定的，但：于是，因為，

故令，沿

進行線搜索得：第二次迭代：而：使

故令沿

進行線搜索，得出于是:此時:Gill-Murray穩(wěn)定牛頓法當(dāng)

正定時，總有Cholesky分解：當(dāng)

不是正定時，Gill-Murray(1974)提出了強迫正定的修改Cholesky分解，使得：其中

是對角陣．然后解：問題1:如何建立有效的算法？從二次模型到一般模型問題2:什么樣的算法有效呢？二次終止性§

4.3

共軛方向法與共軛梯度法算法特點（１）建立在二次模型上，具有二次終止性．（２）有效的算法，克服了最速下降法的慢

收斂性，又避免了牛頓法的計算量大和局部收性的缺點．（３）算法簡單，易于編程，需存儲空間小等優(yōu)點，是求解大規(guī)模問題的主要方法．共軛方向及其性質(zhì)定義1:設(shè)非零向量，如果：則稱是

中任一組是關(guān)于

共軛的．注：若

則是正交的，因此共軛是正交的推廣．定理1:設(shè)為

階正定陣，非零向量組關(guān)于

共軛，則必線性無關(guān)．推論1:

設(shè)

為

階正定陣，非零向量組關(guān)于

共軛，則向量構(gòu)成的一組基．推論2:設(shè)為

階正定陣，非零向量組關(guān)于

共軛，若向量

與關(guān)于

共軛，則共軛方向法算法Step1:給出計算

Step2:如果Step3:計算和初始下降方向停止迭代．使得Step4:

采用某種共軛方向法計算

使得：Step5:

令

轉(zhuǎn)Step2.共軛方向法基本定理定義2:

設(shè)

維向量組

線性無關(guān)，向量集合為

與

生成的維超平面．引理1:設(shè)維向量組則：是連續(xù)可微的嚴(yán)格凸函數(shù)，線性無關(guān)，是

在

上唯一極小點的充要條件是：證：構(gòu)造：分析：(1)是

維嚴(yán)格凸函數(shù)．充要條件是(2)

是

在

上的極小點的是在

上的極小點．定理2:

設(shè)

為

階正定陣，向量組關(guān)于

共軛，對正定二次函數(shù)由任意

開始，依次進行次精確線搜索：則：（１）（２）是在

上的極小點．時，

為正定二次函數(shù)在推論:當(dāng)上的極小點．共軛梯度法記：左乘并使得：（Hestenes-Stiefel公式）?。汗曹椞荻确ɑ拘再|(zhì)定理3:對于正定二次函數(shù)，采用精確線搜索的共軛梯度法在

步后終止，且對成立下列關(guān)系式：（共軛性）（正交性）（下降條件）系數(shù)的其他形式（１）FR公式（1964）（2）PRP公式（1969）FR共軛梯度法算法停．Step1:給出Step2:

計算

如果Step3:Step4:由精確線搜索求

Step5:轉(zhuǎn)Step2.例4：用FR共軛梯度法求解：解：化成形式(1)(2)例5：用FR共軛梯度法求解：解：化成形式(1)(2)FR共軛梯度法收斂定理定理4:

假定

在有界水平集上連續(xù)可微，且有下界，那么采用精確線搜索下的FR共軛梯度法產(chǎn)生的點列 至少有一個聚點是駐點，即：(1)當(dāng)(2)當(dāng)是有窮點列時，其最后一個點是的駐點．是無窮點列時，它必有聚點，且任一聚點都是

的駐點．再開始FR共軛梯度法算法Step1:給出Step2:計算如果停，否則Step3:由精確線搜索求并令：若Step4:計算令如果轉(zhuǎn)Step2;停.令轉(zhuǎn)step2.Step5:若

Step6:計算令轉(zhuǎn)step2,Step7:如果否則轉(zhuǎn)step3.作業(yè)：FR共軛梯度法（上機）上機實現(xiàn)FR共軛梯度法．并求解Rosenbrock函數(shù)，初始點選線搜索分別采用黃金分割法與強Wolfe線搜索，并對比．§

4.4

擬牛頓法基本思想本質(zhì)上是基于逼近牛頓法的方法．牛頓法每次都計算

1959年,Davidon提出設(shè)想僅用每次迭代中得到的梯度信息來近似海色陣，基于此導(dǎo)致了一類非常成功的擬牛頓法．本節(jié)介紹Broyden族擬牛頓法：

DFP算法和BFGS算法．算法原理最速下降法和阻尼牛頓法的迭代公式可統(tǒng)一為：思考：要使上面的算法比最速下降法快，比牛頓法計算簡單，且整體收斂性好，關(guān)鍵在于構(gòu)造矩陣列要求：

的選取既能逐步逼近

又無需計算二階導(dǎo)數(shù)，且具備以下條件：C1：

是對稱正定陣．C2：

由

經(jīng)簡單修正而得：C3：

滿足下面的擬牛頓方程．（推導(dǎo)如下）設(shè)

是二次連續(xù)可微的，則：令：令：

因此：（對二次函數(shù)為等式）若

非奇異：設(shè)想：這樣（擬牛頓方程）就可很好的近似擬牛頓算法Step1:給出

Step2:計算

Step3:Step4:精確線搜索求

Step5:若停；否則轉(zhuǎn)Step7.使擬牛頓方程成立．Step6:計算

Step7:校正

Step8:轉(zhuǎn)Step3.DFP校正公式是

維待定向量．要求：所以：令：得：因此：所以：（DFP校正公式）例6：用DFP算法求解：取解：

(1)(2)注:（１）DFP算法具有二次終止性．（２）搜索方向是共軛方向：DFP校正公式的正定繼承性引理2:設(shè)為正定陣，且則：為正定陣的充要條件是定理5:

在DFP算法中，

如果

正定，則整個矩陣列

都正定．DFP算法的二次終止性推論:

在上面定理條件下：DFP算法至多經(jīng)過

次迭代就可得到極小點，即存在

有：若

則BFGS校正公式(稱為關(guān)于

的BFGS校正公式或互補DFP公式)由上式可得：對稱秩一校正公式要求：因此：即：要求Hesse逆近似也是對稱的，?。鹤?通常不能保證

的正定性．分母可能取零,修正公