1. 最優(yōu)化方法的迭代思想： 最優(yōu)化方法采用的都是迭代的方法，基本思想是給定一個初始的點(diǎn)x_0，按照某一個迭代的規(guī)則產(chǎn)生一個點(diǎn)列{x_k}，在點(diǎn)列有限的情況下最后一個x_k就為最優(yōu)解，當(dāng)點(diǎn)列無窮的時候，則極限點(diǎn)為最優(yōu)解?；镜牡匠绦问饺缦拢?/span>

其中x_k就是迭代點(diǎn)列中的點(diǎn)，d_k為第k次搜索的方向，a_k為步長。

在所有的優(yōu)化方法中三個關(guān)鍵的因素是：初始值x_0,方向d_k以及步長a_k，因此在一般的對于優(yōu)化算法的學(xué)習(xí)，只需要搞懂這三個東西是怎么生成的，也就可以了。進(jìn)一步理解則需要對于其理論進(jìn)行深入的分析了。

2.  最速下降法（Gradient descent）：GD算法是無約束最優(yōu)化算法中最簡單的一種算法，它的各種變種也被應(yīng)用到大規(guī)模的機(jī)器學(xué)習(xí)任務(wù)中來，比如SGD，batch GD，mini-batch等。

GD算法的一個基本假設(shè)就是函數(shù)f(x)在x_k處是連續(xù)可謂的，并且其導(dǎo)數(shù)g_k在x_k處不為0.將一個函數(shù)在x_k這一點(diǎn)做一階的泰勒展開，得到：

優(yōu)化的目的是讓函數(shù)值隨著點(diǎn)列{x_k}的漸進(jìn)，逐漸下降，在上式中就是讓f(x)小于f(x_k)，如何達(dá)到這一個目的呢。

由于泰勒展開余項的值相對很小，因此我們可以忽略它?？吹诙?/span> ，如果它為負(fù)值，就可以達(dá)到我們的目的。記，那么的方向d_k就是下降的方向，這個方向有無窮多個，那那個最大呢，由Cauchy-Schwartz不等式，有

這樣我么可以很容易的推導(dǎo)出當(dāng)且僅當(dāng)時候，第二項最小，由此得到最速下降法的迭代公式

這里需要注意的是，最速下降方向僅僅是算法的局部性質(zhì)，也就是說在局部它是一個下降最快的方向，并不是在全局上。在極值點(diǎn)附近，步長越小，前進(jìn)越慢。

3. 牛頓法（Newton method）

最速下降法采用的泰勒的一階展開，而牛頓法采用的是泰勒二階展開。

對于正定的二次函數(shù)，牛頓法一步就可以達(dá)到最優(yōu)解，也就是不用迭代，就是解析解。而對于非二次函數(shù)，牛頓法并不能保證經(jīng)過有限次迭代就可以求得最優(yōu)解。有一點(diǎn)是在極小點(diǎn)附近目標(biāo)函數(shù)接近于二次函數(shù)，因此其收斂速度一般是快的（2階收斂速度）。另外需要注意的是牛頓法需要計算二階導(dǎo)也就是hesse矩陣，因此需要較大的存儲空間和計算量，在大規(guī)模的數(shù)值計算中直接使用牛頓法是不合適的。

4. 共軛梯度法(Conjugate Gradient)：共軛梯度法是介于GD和Newton法之間的一個方法，它僅僅需要利用一階導(dǎo)數(shù)的信息，克服了GD方法收斂慢的特點(diǎn)，由避免了計算和存儲Hesse矩陣信息。其基本思想是把共軛性與最速下降方法相結(jié)合，利用已知點(diǎn)處的梯度構(gòu)造一組共軛方向，并沿這組方向進(jìn)行搜素，求出目標(biāo)函數(shù)的極小點(diǎn)。

 共軛：對于任意兩個n維向量d1，d2來說，如果對于對于一個n*n對稱正定矩陣，滿足則稱d1，d2是G共軛的，同時它們也就是線性無關(guān)的。假設(shè)我們所要求的函數(shù)具有以下形式（這個形式和牛頓法的那個二階展開是否很像，G是二階導(dǎo)數(shù)矩陣，G正定？，這一點(diǎn)是BFGS算法的核心點(diǎn)，下面會提到）。

導(dǎo)數(shù)矩陣為

共軛梯度法關(guān)鍵點(diǎn)是如何找共軛的方向，同時保證函數(shù)下降。一般說來，基本的假設(shè)是當(dāng)前的搜索方向是當(dāng)前梯度和前面所有梯度的一個線性組合，這個假設(shè)在一定程度上是合理的：每一個下降方向都是和前面的相關(guān)的，并不是完全無關(guān)的。初始化一個d_0方向，根據(jù)這個假設(shè)可以得到:

其中beta就是關(guān)于上一方向的系數(shù)，而beta如何計算？我們?nèi)绻辛艘粋€對稱的正定矩陣G，beta可以由下面的公式來計算（由上式子，和共軛條件推導(dǎo)得來）

這樣最后可以得到最終的共軛梯度法的計算公式：

總結(jié)以下4個屬性

a. 同一點(diǎn)處的搜索方向與梯度的點(diǎn)積等于該點(diǎn)處的負(fù)梯度與梯度的點(diǎn)積，

b. 某一點(diǎn)處的梯度與前面所有搜索方向的點(diǎn)積為0，

c. 某一點(diǎn)處的梯度與前面所有梯度的點(diǎn)積為0，

d . 某一點(diǎn)處的搜索方向與前面所有搜索方向共軛。

在一個需要特別指出的一點(diǎn)：共軛梯度法只使用到了函數(shù)的一階導(dǎo)數(shù)的，而沒有涉及到二階導(dǎo)數(shù)，在beta的計算中給消掉了，所以不用計算和存儲Hesse矩陣了。但是共軛方法經(jīng)過n步迭代之后，產(chǎn)生的新方向可能不再有共軛性，需要進(jìn)一步的修正，比如從新取負(fù)梯度方向為下降方向等。

5.擬牛頓法（Quasi-Newton）

在牛頓法中，函數(shù)的Hesse矩陣實(shí)際上提供的是函數(shù)的曲率，但是計算Hesse矩陣在很多情況下并不是很方便的事情，在高緯的情況下，存在計算量大，需要較大的存儲空間的問題，人們想到能不能不顯示的計算Hesse矩陣，而是利用一個和Hesse矩陣的近似來替代它呢，這就是擬牛頓法的初衷也是它名字的由來。

擬牛頓法的核心思想是：構(gòu)造與Hesse矩陣相似的正定矩陣，而這個構(gòu)造方法計算量比牛頓法小。其實(shí)可以發(fā)現(xiàn)上面講的共軛梯度法也避免了Hesse矩陣的直接計算，一定程度上可以認(rèn)為擬牛頓法是共軛梯度法的兄弟。

首先將目標(biāo)函數(shù)展成二階的泰勒級數(shù)，（和3中的牛頓法的表示略有不同，只是為了后邊書寫的方便，其實(shí)是一樣的）

目標(biāo)是推導(dǎo)一個G的近似，因此上面兩邊對x求導(dǎo)，可以得到

令  可以得到 

再變化一下，得到

此處的H表示的是G的逆的近似，這個公式就是逆牛頓條件或者逆牛頓方程。同時我們也可以這樣來寫這個方程

此處的B表示的就是G的近似，也是BFGS公式推導(dǎo)的一個基礎(chǔ)。以上兩個公式互為對偶。

總結(jié)一下，如果我們使用H來替代原來牛頓方法中的G的逆，就變成了擬牛頓法。如何擬合H變成了重點(diǎn)。

在擬牛頓法中有兩個重要的方法，一個是DFP（Davidon、Fletcher、Powell三人的首字母）方法，由Davidon（1959）提出，Felether和Powell（1963）發(fā)展，一個就是BFGS方法。下面分別來討論一下。

6. 擬牛頓法 - DFP

DFP算法的矯正公式為

這個公式是由對于矩陣的秩二矯正（rank two update）推導(dǎo)而來的，設(shè)u，v為任意的n維向量，構(gòu)造：

帶入擬牛頓條件可以得到：

 為了使得上述公式成立，做如下的構(gòu)造：

這樣公式就成立了，由此導(dǎo)出了DFP算法的矯正公式。

7. 擬牛頓法 - BFGS

到這里我們終于距離L-BFGS算法越來越接近了。關(guān)于B的BFGS矯正公式如下

利用兩次Sharman-Morrison的逆的rank one update就可以得到關(guān)于H的BFGS矯正公式

Sharman-Morrison 定理(如下式)是描述的如何求秩一校正后的矩陣的逆矩陣：

其實(shí)B_k就是H_k的逆矩陣，利用這個定理可以對于B的BFGS矯正公式的右端求逆矩陣，從而可以得到關(guān)于H的BFGS矯正。

8. L-BFGS算法

在上述的BFGS算法的計算過程中，H_k逐漸的變得稠密，因此計算量逐漸正大。為了避免這個問題，LBFGS算法做了以下的改進(jìn)：

a) 在每一步估算hesse矩陣的近似的時候，給出一個當(dāng)前的初始估計H0

b) 利用過去的m-1次的曲率信息修正H0直到得到最終的Hesse矩陣。

在關(guān)于H的BFGS矯正中，令

得到

 然后給定m，則迭代m+1次后得到此時的H

寫出H的最終表達(dá)式為

初始值由以下公式給出。

L-BFGS算法的優(yōu)點(diǎn)是，它不需要記憶H或者B這兩個近似矩陣，而只需要存儲{si，yi}的一個序列，這樣就大大節(jié)省了存儲空間。

9. 在@夏粉_百度 的幾次講座中都提到了LBFGS算法，并提到百度首創(chuàng)的Shooting算法，既然是和LBFGS算法比較的，相必也應(yīng)該是從這個算法出發(fā)的，提出的一些改進(jìn)。可以看到Shooting算法在初始的時候下降的非?？?，收斂速度比LBFGS要快一些，具體怎么做的就不知道了。

順便提一下，LBFGS構(gòu)造的H并不一定是最優(yōu)的下降方向，但保證正定，也就是函數(shù)一定會下降，估計Shooting算法會在這個最優(yōu)方向上做文章。

10. 總結(jié)：

從LBFGS算法的流程來看，其整個的核心的就是如何快速計算一個Hesse的近似：重點(diǎn)一是近似，所以有了LBFGS算法中使用前m個近似下降方向進(jìn)行迭代的計算過程；重點(diǎn)二是快速，這個體現(xiàn)在不用保存Hesse矩陣上，只需要使用一個保存后的一階導(dǎo)數(shù)序列就可以完成，因此不需要大量的存儲，從而節(jié)省了計算資源；重點(diǎn)三，是在推導(dǎo)中使用秩二校正構(gòu)造了一個正定矩陣，即便這個矩陣不是最優(yōu)的下降方向，但至少可以保證函數(shù)下降。

參考文獻(xiàn)：

1. 《最優(yōu)化理論與方法》 袁亞湘 孫文瑜

2.   http://blog.csdn.net/nocml/article/details/8287466

3.  Updating Quasi-Newton Matrices with Limited Storage , Jorge Nocedal

4.  Nonlinear Programming, second edition, Dimitri P. Bertsekas

5. 《廣告數(shù)據(jù)上的大規(guī)模機(jī)器學(xué)習(xí)》  夏粉