620
優化：梯度下降法、牛頓法、共軛梯度法
1、基本概念
1.1 方向導數
1.2 梯度的概念
如果考慮z=f(x,y)描繪的是一座在點(x,y)的高度為f(x,y)的山。那麼，某一點的梯度方向是在該點坡度最陡的方向，而梯度的大小告訴我們坡度到底有多陡。
對於含有n個變量的標量函數，其梯度表示為 
1.3 梯度與方向導數
函數在某點的梯度是這樣一個向量，它的方向與取得最大方向導數的方向一致，而它的模為方向導數的最大值。
1.4 梯度與等高線
函數z=f(x)在點P(x,y)的梯度的方向與過點的等高線f(x,y)=c在這點的法線的一個方向相同，且從數值較低的等高線指向數值較高的等高線，而梯度的模等於函數在這個法線方向的方向導數。這個法線方向就是方向導數取得最大值的方向。
即負梯度方向為最速下降方向。
1.5 等高麵
對於二次函數 
其中A為n*n的對稱正定矩陣，x-為一定點，則函數f(x)的等值麵f(x,y)=c是一個以x-為中心的橢球麵。
此橢球麵的形狀受 Hesse 矩陣的條件數影響，長軸與短軸對應矩陣的最小特征值和最大特征值的方向，其大小與特征值的平方根成反比，最大特征值與最小特征值相差越大，橢球麵越扁。
矩陣的條件數：矩陣A的條件數等於A的範數與A的逆的範數的乘積，即cond(A)=‖A‖·‖A^(-1)‖，是用來判斷矩陣病態與否的一種度量，條件數越大矩陣越病態。
1.6 Hesse 矩陣
在牛頓法中應用廣泛，定義為 
1.7 Jacobi矩陣
前麵講的都是從n維空間到一維空間的映射函數，對於從n維歐式空間變換到m維歐式空間的函數f，也可以表示成由m個實函數組成y=f(x)=[y1(x1,…xn),…ym(x1,…,xn)]T。對於函數f，如果其偏導數都存在，可以組成一個m行n列的矩陣，即所謂的Jacobi矩陣： 
顯然， 當f(x) 是一個標量函數時，Jacobi矩陣是一個向量，即f(x)的梯度，此時Hesse 矩陣是一個二維矩陣；當f(x)是一個向量值函數時，Jacobi 矩陣是一個二維矩陣，Hesse 矩陣是一個三維矩陣。
1.8 共軛方向
先給出共軛方向的定義： 
當A為單位陣時，這兩個方向關於A共軛將等價於兩個方向正交，可見共軛是正交概念的推廣。
我們在來看共軛方向的幾何意義。
前麵提到過二次函數
的等值麵f(x,y)=c是一個以x-為中心的橢球麵。設x^(1)為此橢球麵邊緣的一點，則x^(1)處的法向量為 
將其中後麵一項記作 
即由x(1)指向橢圓麵中心x-的向量。
下麵，設d^(1)為此橢球麵在x(1)處的切向量，由於切向量d^(1)與法向量delta f(x(1))正交，即 
可見，等值麵上一點處的切向量與由此點指向極小點的向量是關於A共軛的。
因此，極小化上述二次函數，若依次沿著d^(1)和d^(2)進行一維搜索，則經過兩次迭代必達到極小點。
1.9 一維搜索
在許多迭代下降算法中，具有一個共同點，就是得到x(k)後，按某種規則確定一個方向d(k)，再從x(k)除法，沿方向d(k)在直線上求目標函數f(x(k)+lambda*d(k))的的極小點，從而得到x(k)的後繼點x(k+1)，這裏求目標函數在直線上的極小點，稱為一維搜索，或者線搜索，可以歸結為單變量lambda的極小化問題。確定的lambda可以成為步長。
一維搜索方法很多，大致可以分為試探法和函數逼近法（插值法）。當然，這兩種方法都是求得即小的的近似值。
試探法包括0.618法、Fibonacci法、進退法、平分法等。
函數逼近法包括牛頓法、割線法、拋物線法、三次插值法、有理插值法等。
2、梯度下降法（最速下降法）
即利用一階的梯度信息找到函數局部最優解的一種方法。核心迭代公式為 
其中，pk是第k次迭代時選取的移動方向，在梯度下降法中，移動的方向設定為梯度的負方向。
ak是第k次迭代是移動的步長，每次移動的步長可以固定也可以改變。在數學上，步長可以通過line search令導數為零找到該方向上的最小值，但是在實際編程時，這樣計算的代價太大，我們一般可以將它設定位一個常量。
因此，梯度下降法計算步驟可以概括為 
如果目標函數是一個凸優化問題，那麼梯度下降法獲得的局部最優解就是全局最優解，理想的優化效果如下圖，值得注意一點的是，每一次迭代的移動方向都與出發點的等高線垂直： 
實際上，梯度還可以提供不在最快變化方向的其他方向上坡度的變化速度，即在二維情況下，按照梯度方向傾斜的圓在平麵上投影成一個橢圓。橢球麵的形狀受 Hesse 矩陣的條件數影響，橢球麵越扁，那麼優化路徑需要走很大的彎路，計算效率很低。這就是常說的鋸齒現象（ zig-zagging），將會導致收算法斂速度變慢。
3、牛頓法
前麵提到的梯度下降法，主要利用的是目標函數的局部性質，具有一定的“盲目性”。
牛頓法則是利用局部的一階和二階偏導信息，去推測整個目標函數的形狀，進而可以求得近似函數的全局最小值，然後將當前的最小值設定為近似函數的最小值。也就是說，牛頓法在二階導數的作用下，從函數的凸性出發，直接搜索怎樣到達極值點，即在選擇方向時，不僅考慮當前坡度是否夠大，還會考慮走了一步之後，坡度是否會變得更大。
相比最速下降法，牛頓法帶有一定對全局的預測性，收斂性質也更優良。當然由於牛頓法是二階收斂的，比梯度下降法收斂的更快。
假設我們要求f(x)的最小值，首先用泰勒級數求得其二階近似 
顯然這裏x是自變量，x^(k)是常量，求解近似函數phi(x)的極值，即令其倒數為0，很容易得到 
從而得到牛頓法的迭代公式 
顯然除了f(x)二次可微外，還要求f(x)的Hesse矩陣可逆。此外，由於矩陣取逆的計算複雜為 n 的立方，當問題規模比較大時，計算量很大，解決的辦法是采用擬牛頓法，如 BFGS, L-BFGS, DFP, Broyden’s Algorithm 進行近似。
此外，如果初始值離局部極小值太遠，泰勒展開並不能對原函數進行良好的近似，導致牛頓法可能不收斂。
我們給出阻尼牛頓法的計算步驟，其實阻尼牛頓法相較原始牛頓法隻是增加了沿牛頓方向的一維搜索： 
4、共軛梯度法
共軛梯度法是介於最速下降法與牛頓法之間的一個方法，它僅需一階導數信息，但克服了最速下降法收斂慢的缺點，又避免了牛頓法需要存儲和計算Hesse矩陣並求逆的缺點。
共軛梯度法的基本思想是把共軛性與最速下降法相結合，利用已知點處的梯度構造一組共軛方向，並沿這組方向進行搜索，求出目標函數的極小點。根據共軛方向的基本性質，這種方法具有二次終止性。
共軛梯度法中的核心迭代過程可以采取不同的方案，一種是直接延續，即總是用d^(k+1)=-g(k+1)+beta_k*d^(k)構造搜索方向；一種是把n步作為一輪，每搜索一輪之後，取一次最速下降方向，開始下一輪，此種策略稱為“重置”。
下麵我們介紹一種傳統的共軛梯度法
注意，上述算法中均假設采用的精確一維搜索，但實際計算中，精確一維搜索會帶來一定困難，代價較大，通常還是采用不精確的一維搜索。但此時（4）中構造的搜索方向可能就不是下降方向了，解決這個問題有兩個方法。
其一，當d^(k+1)不是下降方向時，以最速下降方向重新開始。事實上，這也存在問題，但一維搜索比較粗糙時，這樣重新開始可能是大量的，會降低計算效率。
其二，在計算過程中增加附加的檢驗，具體細節可以參考陳寶林老師的“最優化理論與方法”的P301。
最後更新：2017-10-11 10:33:41