AAA最優(yōu)化理論與方法課件(第5章-馬昌鳳版)

最優(yōu)化理論與方法Chapter5擬牛頓法

牛頓太偉大了，我們只能模擬他5.1擬牛頓法及其性質(zhì)5.2BFGS算法及其Matlab實現(xiàn)5.3DFP算法及其Matlab實現(xiàn)5.4Broyden族算法及其Matlab實現(xiàn)5.5擬牛頓法的收斂性模擬模擬了哪部分？模擬的就是牛頓法中的搜索方向（可以叫作“牛頓方向”）的生成方式。在著名數(shù)學家斯米爾給出的本世紀18個數(shù)學難題中，其中以下4個就與運籌學相關(guān)：（1）“P是否等于NP”，也被列為本世紀的7個數(shù)學難題之一；（2）單變量多項式整解的個數(shù)；（3）可描述價格調(diào)整的一般均衡理論的數(shù)學模型；（4）實系數(shù)線性規(guī)劃是否多項式時間可解。以下12個問題是運籌學相關(guān)方向具有一定代表性的未解難題：（1）凸多面體的d-步猜想；（2）有限多個二次函數(shù)最大值的極小化問題；（3）推廣的Lax猜想；（4）DFP擬牛頓法的收斂性；(OpenProblem)（5）最小阻力凸體問題；（6）是否存在求解性線性規(guī)劃的強多項式時間算法？（7）組合優(yōu)化反問題的計算復雜性；（8）求解旅行商問題的更好的近似算法；（9）k-服務器猜想；（10）裝箱問題是否存在絕對近似算法；（11）隨機排隊網(wǎng)絡的遍歷性；（12）PH-分布的最小表示。其中凸多面體的d-步猜想--Hirschconjecture已經(jīng)被解決了。該數(shù)學家找到了一個反例并證否了該猜想，發(fā)在了當年的AnnalsofMathematics上，并且被邀請到了ICM做了報告。機器學習算法中經(jīng)常碰到非線性優(yōu)化問題，如SparseFiltering算法，其主要工作在于求解一個非線性極小化問題。在具體實現(xiàn)中，大多調(diào)用的是成熟的軟件包做支撐，其中最常用的一個算法是L-BFGS。擬牛頓法(Quasi-NewtonMethods)是求解非線性優(yōu)化問題最有效的方法之一，于20世紀50年代由美國Argonne國家實驗室的物理學家W.C.Davidon所提出來。Davidon設計的這種算法在當時看來是非線性優(yōu)化領(lǐng)域最具創(chuàng)造性的發(fā)明之一。不久R.Fletcher和M.J.D.Powell證實了這種新的算法遠比其他方法快速和可靠，使得非線性優(yōu)化這門學科在一夜之間突飛猛進。在之后的20年里，擬牛頓方法得到了蓬勃發(fā)展，出現(xiàn)了大量的變形公式以及數(shù)以百計的相關(guān)論文。中國也有一些學者在這方面做出很好的結(jié)果。方法總結(jié):基本思想:牛頓法收斂很快，但需要計算Hesse矩陣，而此矩陣可能非正定，可能導致搜索方向不是下降方向。

擬牛頓法就是利用目標函數(shù)值f和一階導數(shù)g的信息,構(gòu)造出目標函數(shù)的曲率近似，而不需要明顯形成Hesse矩陣，同時具有收斂速度快的優(yōu)點。擬牛頓法具有超線性收斂速度。

用不包含二階導數(shù)的矩陣近似Hesse矩陣的逆。同共軛梯度法相比，擬牛頓法不需要重新開始策略。保優(yōu)去劣5.1擬牛頓法及其性質(zhì)

Quasi-NewtonMethodandItsProperties牛頓法的迭代公式為5.1擬牛頓法及其性質(zhì)5.1擬牛頓法及其性質(zhì)記則5.1擬牛頓法及其性質(zhì)(A1)稱為擬牛頓條件(方程)，也稱為割線方程。怎樣確定滿足這個條件的H

k+1?校正矩陣欠定方程自由度？5.1擬牛頓法及其性質(zhì)如何逼近Hesse矩陣或其逆矩陣？？？對稱秩1校正5.1擬牛頓法及其性質(zhì)

Hk稱為校正矩陣.

確定

Hk的一個方法是令秩為1r(AB)≤min{r(A),r(B)}從而(A2)利用上面的式子，得---秩1校正公式5.1擬牛頓法及其性質(zhì)得新信息的嵌入原先信息的繼承可直接驗證擬牛頓條件

Bk稱為校正矩陣。確定

Bk的一個方法是令5.1擬牛頓法及其性質(zhì)5.1擬牛頓法及其性質(zhì)利用秩1校正極小化函數(shù)f(x),在第k次迭代中,令搜索方向5.1擬牛頓法及其性質(zhì)確定后繼點算法

對稱秩1算法5.1擬牛頓法及其性質(zhì)其它更好的近似5.1擬牛頓法及其性質(zhì)5.1擬牛頓法及其性質(zhì)5.1擬牛頓法及其性質(zhì)5.1擬牛頓法及其性質(zhì)5.1擬牛頓法及其性質(zhì)5.1擬牛頓法及其性質(zhì)5.1擬牛頓法及其性質(zhì)5.1擬牛頓法及其性質(zhì)點評在一定條件下，對稱秩1校正算法收斂且具有二次終止性。無法保證Hk和Bk的正定性。具體而言，有以下三種情況：5.1擬牛頓法及其性質(zhì)5.1擬牛頓法及其性質(zhì)5.1擬牛頓法及其性質(zhì)5.2BFGS算法及其Matlab實現(xiàn)

BFHSMethodandItsMatlabCode

BFGS校正是目前最流行也是最有效的擬牛頓校正,它是由Broyden,Fletcher,Goldfarb和Shanno在1970年各自獨立提出的擬牛頓法,故稱為BFGS算法。5.2BFGS算法及其Matlab實現(xiàn)考慮擬牛頓條件對稱形式其對稱形式其中Bk+1為Hesse矩陣的近似。下面用迭代法求Bk+1使其滿足(A2)。記取△Bk為秩2校正矩陣，即5.2BFGS算法及其Matlab實現(xiàn)于是由擬牛頓方程(A2)得即滿足上式的uk和vk不唯一。下面令uk和vk分別平行于Bksk和yk,

即令uk=γBksk,vk=θyk,其中γ和θ為待定參數(shù)。r(A+B)≤r(A)+r(B)秩為2于是有5.2BFGS算法及其Matlab實現(xiàn)將uk和vk代入(A4)得整理得令上式顯然成立。從而得到BFGS秩2校正公式如下5.2BFGS算法及其Matlab實現(xiàn)顯然，若Bk對稱，則校正后的Bk+1也對稱。同時可以證明BFGS校正公式有如下性質(zhì)。曲率條件5.2BFGS算法及其Matlab實現(xiàn)5.2BFGS算法及其Matlab實現(xiàn)容易實現(xiàn)嗎？？？容易，比如嚴格凸5.2BFGS算法及其Matlab實現(xiàn)5.2BFGS算法及其Matlab實現(xiàn)5.2BFGS算法及其Matlab實現(xiàn)要求線性方程組5.2BFGS算法及其Matlab實現(xiàn)基于Armijo搜索的BFGS算法的Matlab程序。5.2BFGS算法及其Matlab實現(xiàn)5.2BFGS算法及其Matlab實現(xiàn)對利用一次該定理，得5.2BFGS算法及其Matlab實現(xiàn)記則那么5.2BFGS算法及其Matlab實現(xiàn)于是對于線性方程組我們沒有必要解它，而只需要根據(jù)H0,x0,x1,g0,g1,求出s0,y0,進而根據(jù)上面的迭代公式求出H1,進而的求出d1,然后一步一步的進行即可。5.3DFP算法及其Matlab實現(xiàn)

DPFMethodandItsMatlabCode

DFP校正是第一個擬牛頓校正,是1959年由Davidon提出的,后經(jīng)Fletcher和Powell解釋和改進,故名之為DFP算法,它也是求解無約束優(yōu)化問題最有效的算法之一。5.3DFP算法及其Matlab實現(xiàn)考慮擬牛頓條件對稱形式類似于BFGS校正公式的推導,可得DFP校正公式。定義校正矩陣秩為25.3DFP算法及其Matlab實現(xiàn)DFP(Davidon-Fletcher-Power)公式則BFGS公式DFP公式BFGS修正公式5.3DFP算法及其Matlab實現(xiàn)上一節(jié)，我們推導的BFGS校正公式的逆矩陣的迭代公式經(jīng)驗表明BFGS公式比DFP公式好。5.3DFP算法及其Matlab實現(xiàn)5.3DFP算法及其Matlab實現(xiàn)5.3DFP算法及其Matlab實現(xiàn)5.3DFP算法及其Matlab實現(xiàn)5.3DFP算法及其Matlab實現(xiàn)例5.1

用DFP方法求解下列問題初始點及初始矩陣分別取為5.3DFP算法及其Matlab實現(xiàn)第1次迭代令搜索方向得到5.3DFP算法及其Matlab實現(xiàn)令5.3DFP算法及其Matlab實現(xiàn)第2次迭代5.3DFP算法及其Matlab實現(xiàn)5.3DFP算法及其Matlab實現(xiàn)令5.3DFP算法及其Matlab實現(xiàn)得到于是5.3DFP算法及其Matlab實現(xiàn)得最優(yōu)解DFP法具有二次終止性！5.3DFP算法及其Matlab實現(xiàn)5.3DFP算法及其Matlab實現(xiàn)5.3DFP算法及其Matlab實現(xiàn)擬牛頓法有關(guān)說明擬牛頓法中的兩個重要算法DFP算法和BFGS算法，它們的迭代過程相同，區(qū)別僅在于校正矩陣選取不同。對于DFP法，由于一維搜索的不精確和計算誤差的積累可能導致某一輪的奇異，而BFGS法對一維搜索的精度要求不高，并且由它產(chǎn)生的不易變?yōu)槠娈惥仃?。BFGS法比DFP法更具有好的數(shù)值穩(wěn)定性，它比DFP法更具有實用性。5.3DFP算法及其Matlab實現(xiàn)5.4Broyden族算法及其Matlab實現(xiàn)

BroydenMethodandItsMatlabCode

前面討論了兩種秩2校正公式：BFGS校正與DFP校正，總結(jié)如下。5.4Broyden族算法及其Matlab實現(xiàn)定義------Broyden族5.4Broyden族算法及其Matlab實現(xiàn)Broyden族的所有成員均滿足擬牛頓條件。5.4Broyden族算法及其Matlab實現(xiàn)顯然成立證明：對k歸納。當k=1時有5.4Broyden族算法及其Matlab實現(xiàn)并且有于是當k=1時結(jié)論成立。5.4Broyden族算法及其Matlab實現(xiàn)下設k=l時命題成立,下證當k=l+1時結(jié)論也成立。由歸納假設有5.4Broyden族算法及其Matlab實現(xiàn)5.4Broyden族算法及其Matlab實現(xiàn)特點：不必計算Hesse矩陣；存儲量較大；當Hk正定時，算法產(chǎn)生的方向均為下降方向，具有二次終止性；擬牛頓法是無約束最優(yōu)化方法中最有效的一類算法。5.4Broyden族算法及其Matlab實現(xiàn)5.5擬牛頓法的收斂性

ConvergenceofQuasi-NewtonMethod

本節(jié)討論擬牛頓法的收斂性,主要給出基于非精確線搜索的BFGS算法的全局收斂性和局部超線性收斂性定理。5.5擬牛頓法的收斂性5.5擬牛頓法的收斂性5.5擬牛頓法的收斂性5.5擬牛頓法的收斂性5.5擬牛頓法的收斂性5.5擬牛頓法的收斂性5.5擬牛頓法的收斂性5.5擬牛頓法的收斂性5.5擬牛頓法的收斂性5.5擬牛頓法的收斂性5.5擬牛頓法的收斂性5.5擬牛頓法的收斂性5.5擬牛頓法的收斂性5.5擬牛頓法的收斂性總結(jié)對稱秩1校正(兩項)總結(jié)對稱秩2校正(三項)x(k+1)=x(k)+αkd(k)多變量最優(yōu)化迭代解法的一般迭代公式最優(yōu)(非精確)步長可用一維搜索技術(shù)解決不同的搜索方向d(k)構(gòu)成不同的算法算法名稱搜索方向p(k)Powell共軛方向法共軛方向最速下降法d(k)=－f(x(k)

)Newton法d(k)=

－

2f(x(k))－1

f(x(k))Marquart法d(k)

＝－[2f(x(k))

+

kI]－1

f(x(k))F-R法(共軛梯度法)d(0)=－

f(x(0)