最最佳化演算法屬於數學方法，其目的就是為了得到針對某些問題的最優解，比如在一定成本下，如何得到最大的利潤。最常用的最最佳化演算法就有梯度下降法和牛頓法。

梯度下降法（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頭都大了…