|
轉載須注明出處：http://www./
在最優(yōu)化領域，有幾個你絕對不能忽略的關鍵詞：擬牛頓、DFP、BFGS。名字很怪，但是非常著名。下面會依次地說明它們分別“是什么”，“有什么用” 以及 “怎么來的”。
但是在進入正文之前，還是要先提到一個概念上的區(qū)別，否則將影響大家的理解：其實DFP算法、BFGS算法都屬于擬牛頓法，即，DFP、BFGS都分別是一種擬牛頓法。
先從擬牛頓法（Quasi-Newton）說起。這個怪怪的名詞其實很形象：這是一種”模擬“的牛頓法。那么，它模擬了牛頓法的哪一部分呢？答：模擬的就是牛頓法中的搜索方向（可以叫作“牛頓方向”）的生成方式。 牛頓法是什么？本文是基于你已經(jīng)知道牛頓法的原理的假設，如果你不清楚，那么可以看我這篇文章，里面非常簡單而又清晰地描述了牛頓法的原理。 了解了牛頓法的原理，我們就知道了：在每一次要得到新的搜索方向的時候，都需要計算Hesse矩陣（二階導數(shù)矩陣）。在自變量維數(shù)非常大的時候，這個計算工作是非常耗時的，因此，擬牛頓法的誕生就有意義了：它采用了一定的方法來構造與Hesse矩陣相似的正定矩陣，而這個構造方法計算量比牛頓法小。這就是對它“有什么用”的回答了。 （1）DFP算法 下面，就從DFP算法來看看“擬牛頓”是如何實現(xiàn)的（DFP算法是以Davidon、Fletcher、Powell三位牛人的名字的首字母命名的）。 前面說了，Hesse矩陣在擬牛頓法中是不計算的，擬牛頓法是構造與Hesse矩陣相似的正定矩陣，這個構造方法，使用了目標函數(shù)的梯度（一階導數(shù)）信息和兩個點的“位移”（Xk-Xk-1）來實現(xiàn)。有人會說，是不是用Hesse矩陣的近似矩陣來代替Hesse矩陣，會導致求解效果變差呢？事實上，效果反而通常會變好。有人又會問為什么？那么就簡要地說一下—— 由牛頓法的原理可知如下幾個等式：
若最后一個等式子的最左邊 < 0，即 文章來源：http://www./ 由于涉及到Hesse矩陣（二階導數(shù)矩陣），我們當然要從目標函數(shù) f(X) 的泰勒展開式說開去。與最優(yōu)化理論中的很多問題一樣，在這里，我們依然要假設目標函數(shù)可以用二次函數(shù)進行近似（實際上很多函數(shù)都可以用二次函數(shù)很好地近似）：
忽略高階無窮小部分，只看前面的3項，其中A為目標函數(shù)的Hesse矩陣（二階導數(shù)矩陣）。此式兩邊對X求導得：
于是，當 X=Xi 時，將[2]式兩邊均左乘(Ai+1)-1，有：
上式左右兩邊近似相等，但如果我們把它換成等號，并且用另一個矩陣H來代替上式中的A-1，則得到：
文章來源：http://www./ 這個方程，就是擬牛頓方程，其中的矩陣H，就是Hesse矩陣的逆矩陣的一個近似矩陣。但是，從初始的H0開始，如何得到每一步迭代過程中需要的H1，H2，……呢？在迭代過程中生成的矩陣序列H0，H1，H2，……中，每一個矩陣Hi+1，都是由前一個矩陣Hi修正得到的，這個修正方法有很多種，這里只說DFP算法的修正方法。設：
然后又有問題：矩陣E怎么求？再設：
其中，m和n均為實數(shù)，v和w均為N維向量。將[6]代入[5]式，再將[5]式代入[4]式，可得：
文章來源：http://www./ [8]式與[7]式完全相同，只不過用簡化的記號重寫了一下。如果求出了m，n，v，w，就可以知道[6]式怎么求，從而進一步知道[5]式怎么求，從而我們的問題就徹底解決了。符合[7]這個方程的v，w可能有很多，但是我們有沒有可能找到v，w的一個“特例”，使之符合這個等式呢？仔細觀察一下，是可以找到的：[7]式的右邊兩個向量相減的結果，是一個n×1的向量，因此，等式左邊的計算結果當然也是一個n×1的向量（每一項都是一個n×1的向量），所以我們把[7]式寫成了[8]式的樣子，可以看到，其中的第二、第三項中的括號里的向量的點積均為實數(shù)，這里，可以使第一個括號中的mvTqi值為1，使第二個括號中的nwTqi值為-1，這樣的話，v只要取si，w只要取Hiqi，就可以使[8]式成立了。的確，這種帶有一點猜測性質的做法，確實可以讓我們找到一組適合的m，n，v，w值。 所以，我們得到的m，n，v，w值如下：
現(xiàn)在我們幾乎大功告成了：將[8]~[11]代入[6]式，然后再將[6]代入[5]式，就得到了Hesse矩陣的逆矩陣的近似陣H的計算方法：
在上面的推導過程中，有人可能覺得有點無厘頭：為什么[6]式要那樣假設，是怎么想到的？我能給出的答案是：這一點我也沒想明白。如果你知道，請告訴我，非常感謝。某些書上經(jīng)常寫類似于“很顯然，XXX”之類的話，從一個定理直接得出了一個讓人摸不著頭腦的結論，而作為我這樣比較笨的人來說，我覺得寫書的很多專家們認為“很顯然”的東西一點也不“顯然”，甚至于有時候，我覺得那就像鳳姐突然變成了范冰冰一樣——一下子變出來了一個漂亮的結論，難以相信。所以這也是為什么我花費了很多時間，來把一些“很顯然”的東西記下來，寫明白的原因了。對于大多數(shù)牛人，他們需要的當然不是這種思維跨度這么小的文章，而是那種從地球可以一下子飛到火星的文章。所以，我寫的東西不適合于水平高的人看，我只期望能幫助一小部分人就知足了。 文章來源：http://www./ 說到這里，那么到底什么是DFP算法呢？上面的矩陣H的計算方法就是其核心，下面再用簡單的幾句話描述一下DFP算法的流程：
已知初始正定矩陣H0，從一個初始點開始（迭代），用式子 有人會說，上面那些亂七八糟的都是搞什么啊，猜來猜去的就折騰出了一個公式，然后就確定這公式能用了？就不怕它在迭代的時候根本無法尋找到目標函數(shù)的極小值？正因為有這些疑問，所以在這里，還要提及一個非常重要的問題：我們通過帶有猜測性質的做法，得到了矩陣H的計算公式，但是，這個修正過的矩陣，能否保持正定呢？前面已經(jīng)說了，矩陣H正定是使目標函數(shù)值下降的條件，所以，它保持正定性很重要。可以證明，矩陣H保持正定的充分必要條件是：
并且，在迭代過程中，這個條件也是容易滿足的。此結論的證明并不復雜，但是為了不影響本文的主旨，這里就沒有必要寫出來了?？傊?，我覺得作為一個最優(yōu)化的學習者來說，首先要關注的是不是這些細節(jié)問題，而是先假設這些算法都適用，然后等積累到一定程度了，再去想“為什么能適用”的問題。
（2）BFGS算法 在上面的DFP算法的推導中，我們得到了矩陣H的計算公式，而BFGS算法和它有點像，但是比它形式上復雜一點。盡管它更復雜，但是在BFGS算法被Broyden，F(xiàn)letcher，Goldfarb，Shanno四位牛人發(fā)明出來到現(xiàn)在的40多年時間里，它仍然被認為是最好的擬牛頓算法。歷史總是這樣，越往后推移，人們要超越某種技術所需的時間通常就越長。但是我們很幸運地可以站在巨人的肩膀上，從而可以在使用前人已經(jīng)發(fā)明的東西的基礎上感嘆一聲：這玩意太牛了。 好吧，又扯遠了…… 回到中心主題，看看在BFGS算法中，與上面的[13]式一樣的矩陣H是如何計算的：
在[14]式中，最后一項（深藍色的部分）就是BFGS比DFP多出來的東西。其中，w為一個n×1的向量。我們看到，由于向量w的表達式太長，所以沒有把它直接寫在[14]式中，而是單獨列在了[15]式里。 可能[14]式一看就讓人頭暈，所以先來弱弱地解釋一下這個式子的計算結果（如果你覺得好雷人，那么請直接無視）：wwT是一個n×1的向量與一個1×n的向量相乘，結果為一個n×n的矩陣，而[14]式中最后一項里，除了wwT之外的那一部分是（1×n）向量、n×n矩陣、n×1向量相乘，結果為一實數(shù)，因此[14]式最后一項結果為一個n×n矩陣，這與[14]式等號左邊的矩陣H為n×n矩陣一致。這一點沒有問題了。 在目標函數(shù)為二次型（“在數(shù)學中，二次型是一些變量上的二次齊次多項式”）時，無論是DFP還是BFGS——也就是說，無論[14]式中有沒有最后一項——它們均可以使矩陣H在n步之內收斂于A-1。 文章來源：http://www./ 延伸閱讀：BFGS有一個變種（我不知道這樣稱呼是否正確），叫作“Limited-memory BFGS”，簡稱“L-BFGS”或“LM-BFGS”（這里的“LM”與Levenberg-Marquard算法沒有關系），從它的名字上看，你肯定能猜到，使用L-BFGS算法來編寫程序時，它會比BFGS算法占用的內存小。從前面的文章中，我們知道，BFGS在計算過程中要存儲一個n×n的矩陣，當維數(shù)n很大的時候，這個內存占用量會很大——例如，在10萬維的情況下，假設矩陣H中的元素以double來存儲，那么，內存占用即為100000×100000×8÷1024÷1024÷1024≈74.5（GB），這太驚人了，一般的服務器幾乎無法承受。所以，使用L-BFGS來降低內存使用量在某些情況下是非常有意義的。 關于L-BFGS的英文解釋，請點擊這個Wiki鏈接。由于我還沒有深入學習L-BFGS，所以沒辦法在這里詳細敘述了。 （全文完） |
|
|
，就是直觀概念上的“沿方向d上，目標函數(shù)值下降”的表達。而在逐步尋找最優(yōu)解的過程中，我們是要求目標函數(shù)值下降的，因此，應該有-(X-Xi)A(X-Xi) < 0，也即 (X-Xi)A(X-Xi) > 0。這表明矩陣A是
