手機用戶95992772337
最優化算法屬於數學方法，其目的就是為了得到針對某些問題的最優解，比如在一定成本下，如何得到最大的利潤。最常用的最優化算法就有梯度下降法和牛頓法。
梯度下降法（Gradient Descent）
梯度下降法在最優化算法中是最簡單的也是用的最多的。對於最小優化問題，即希望找到能使得目標函數值最小的解，梯度下降法實際上就是將最優化問題轉換成了搜索的問題。
將當前位置處梯度的反方向作為尋優的方向，也就是能使得結果下降最快的方向，同時設定一定的步長（在機器學習中，就是學習率），就能對問題的參數進行更新，使得目標函數值變小。然後反覆進行上述過程，最終目標函數值將會收斂，而梯度則下降為0，也就到了最優點。
對於簡單的凸函數優化問題，梯度下降法能有找到全局最優解；但是對於更為複雜的函數，梯度下降往往僅能找到局部的最優解，同時梯度下降的優化過程也可能會是波動的（比如隨機梯度下降），參數的變化呈現之字形，收斂比較慢。因為梯度下降法僅僅用到了一階梯度信息，只能知道往哪裡走會變小，而不知道梯度的變化信息，即二階梯度。
牛頓法（Newton Method）
牛頓法同樣需要用到目標函數的梯度信息，但是牛頓法不僅利用到了當前點的一階導數（梯度），還結合了二階導數（海塞矩陣）來對目標函數進行優化。
首先對函數f(x)進行二階的泰勒展開，得到
然後對函數求導，並令其為0
整理之後就可以得到牛頓法參數的更新方式
牛頓法中利用到了二階的變化信息，因此相比於梯度下降法收斂速度更快。此外，還有另一種解釋就是，牛頓法是用二次曲面來擬合當前位置的曲面，而梯度下降則是用平面，所以牛頓法的方向選擇會更加優。但是在多元參數時，需要計算二階海賽矩陣的逆，計算量十分大。
下圖為牛頓法和梯度下降法的收斂性能比較，綠色的為梯度下降；紅色的為牛頓法。
北航秦曾昌
GD 和Newton法其實都屬於導數下降方法。區別是GD以一階導數方向作為下降方向，牛頓法作優化問題時可以看做二階方法，牛頓法比GD有更快的下降速度，證明可以參考斯坦福大學Boyd大神的凸優化。導數方法最大優點是簡潔高效，缺點是遇到鞍點就玩完了。這就是為什麼目前訓練深度學習網絡結構需要drop out避免過擬合。非凸問題比較難，目前可以參考進化算法比如GA PSO DE。或者利用Wotao Yin大神的Nonconvex ADMM，原理是針對不同的變量構造不同導數方向根據Augment Lagrange 函數實現。
最後說點理論，因為根據範數等價原理，GD在其二階導數有界條件下，調節步長可以等效為Banach空間的壓縮算子，又因為有限範數線性組合是凸問題，所以利用壓縮映像原理，一定收斂於全局最優即不動點。當然，牛頓法有類似結論。對於深度學習中的drop out，是為了防止其梯度陷入局部最優值，如果在有限維的Banach空間討論，可以看做有界連續算子，利用閉圖像原理證明。其他情形，可以經過簡化抽象為緊算子，利用列緊的ε網證明即可。還有，GD 和Newton在有限迭代情況下，其收斂點集合可以看做Fσ型集合，一定條件下也可以看做σ代數。順便說下，GD 和Newton方法都可以看做一類算子的強收斂，弱於算子的一致收斂。
最後補充一點，最近剛剛實現了並行的Nonconvex ADMM用的 Proximal Proximal GD求稀疏解，CUDA 8.0實現的並行化，nvcc compiler 和 CMake file頭都大了…
