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

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

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

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

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

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

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

Hk稱為校正矩陣.

確定

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

Bk稱為校正矩陣。確定

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

對稱秩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ì)點(diǎn)評在一定條件下，對稱秩1校正算法收斂且具有二次終止性。無法保證Hk和Bk的正定性。具體而言，有以下三種情況：5.1擬牛頓法及其性質(zhì)5.1擬牛頓法及其性質(zhì)5.1擬牛頓法及其性質(zhì)5.2BFGS算法及其Matlab實(shí)現(xiàn)

BFHSMethodandItsMatlabCode

BFGS校正是目前最流行也是最有效的擬牛頓校正,它是由Broyden,Fletcher,Goldfarb和Shanno在1970年各自獨(dú)立提出的擬牛頓法,故稱為BFGS算法。5.2BFGS算法及其Matlab實(shí)現(xiàn)考慮擬牛頓條件對稱形式其對稱形式其中Bk+1為Hesse矩陣的近似。下面用迭代法求Bk+1使其滿足(A2)。記取△Bk為秩2校正矩陣，即5.2BFGS算法及其Matlab實(shí)現(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實(shí)現(xiàn)將uk和vk代入(A4)得整理得令上式顯然成立。從而得到BFGS秩2校正公式如下5.2BFGS算法及其Matlab實(shí)現(xiàn)顯然，若Bk對稱，則校正后的Bk+1也對稱。同時(shí)可以證明BFGS校正公式有如下性質(zhì)。曲率條件5.2BFGS算法及其Matlab實(shí)現(xiàn)5.2BFGS算法及其Matlab實(shí)現(xiàn)容易實(shí)現(xiàn)嗎？？？容易，比如嚴(yán)格凸5.2BFGS算法及其Matlab實(shí)現(xiàn)5.2BFGS算法及其Matlab實(shí)現(xiàn)5.2BFGS算法及其Matlab實(shí)現(xiàn)要求線性方程組5.2BFGS算法及其Matlab實(shí)現(xiàn)基于Armijo搜索的BFGS算法的Matlab程序。5.2BFGS算法及其Matlab實(shí)現(xiàn)5.2BFGS算法及其Matlab實(shí)現(xiàn)對利用一次該定理，得5.2BFGS算法及其Matlab實(shí)現(xiàn)記則那么5.2BFGS算法及其Matlab實(shí)現(xiàn)于是對于線性方程組我們沒有必要解它，而只需要根據(jù)H0,x0,x1,g0,g1,求出s0,y0,進(jìn)而根據(jù)上面的迭代公式求出H1,進(jìn)而的求出d1,然后一步一步的進(jìn)行即可。5.3DFP算法及其Matlab實(shí)現(xiàn)

DPFMethodandItsMatlabCode

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

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

BroydenMethodandItsMatlabCode

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