1. 什麼是最優化
最優化是應用數學的一個分支，主要指在一定條件限制下，選取某種研究方案使目標達到最優的一種方法。最優化問題在當今的軍事、工程、管理等領域有著極其廣泛的應用。
梯度下降法是最早最簡單，也是最為常用的最優化方法。
梯度下降法實現簡單，當目標函數是凸函數時，梯度下降法的解是全局解。一般情況下，其解不保證是全局最優解，梯度下降法的速度也未必是最快的。
梯度下降法的優化思想是用當前位置負梯度方向作為搜索方向，因為該方向為當前位置的最快下降方向，所以也被稱為是」最速下降法「。最速下降法越接近目標值，步長越小，前進越慢。
牛頓法是一種在實數域和復數域上近似求解方程的方法。方法使用函數f(x)的泰勒級數的前面幾項來尋找方程f(x) = 0的根。牛頓法最大的特點就在於它的收斂速度很快。
擬牛頓法是求解非線性優化問題最有效的方法之一，其本質思想是改善牛頓法每次需要求解復雜的Hessian矩陣的逆矩陣的缺陷，它使用正定矩陣來近似Hessian矩陣的逆，從而簡化了運算的復雜度。擬牛頓法和最速下降法一樣只要求每一步迭代時知道目標函數的梯度。
通過測量梯度的變化，構造一個目標函數的模型使之足以產生超線性收斂性。這類方法大大優於最速下降法，尤其對於困難的問題。另外，因為擬牛頓法不需要二階導數的信息，所以有時比牛頓法更為有效。如今，優化軟體中包含了大量的擬牛頓演算法用來解決無約束，約束，和大規模的優化問題。
共軛梯度法是介於最速下降法與牛頓法之間的一個方法，它僅需利用一階導數信息，但克服了最速下降法收斂慢的缺點，又避免了牛頓法需要存儲和計算Hesse矩陣並求逆的缺點，共軛梯度法不僅是解決大型線性方程組最有用的方法之一，也是解大型非線性最優化最有效的演算法之一。
在各種優化演算法中，共軛梯度法是非常重要的一種。其優點是所需存儲量小，具有步收斂性，穩定性高，而且不需要任何外來參數。
啟發式方法指人在解決問題時所採取的一種根據經驗規則進行發現的方法。其特點是在解決問題時,利用過去的經驗，選擇已經行之有效的方法，而不是系統地、以確定的步驟去尋求答案。
啟發式優化方法種類繁多，包括經典的模擬退火方法、遺傳演算法、蟻群演算法以及粒子群演算法等等。
作為一種優化演算法，拉格朗日乘子法主要用於解決約束優化問題，它的基本思想就是通過引入拉格朗日乘子來將含有n個變數和k個約束條件的約束優化問題轉化為含有（n+k）個變數的無約束優化問題。拉格朗日乘子背後的數學意義是其為約束方程梯度線性組合中每個向量的系數。
將一個含有n個變數和k個約束條件的約束優化問題轉化為含有（n+k）個變數的無約束優化問題，拉格朗日乘數法從數學意義入手，通過引入拉格朗日乘子建立極值條件，對n個變數分別求偏導對應了n個方程，然後加上k個約束條件（對應k個拉格朗日乘子）一起構成包含了（n+k）變數的（n+k）個方程的方程組問題，這樣就能根據求方程組的方法對其進行求解。
2. 幾種常用最優化方法
學習和工作中遇到的大多問題都可以建模成一種最優化模型進行求解，比如我們現在學習的機器學習演算法，大部分的機器學習演算法的本質都是建立優化模型，通過最優化方法對目標函數（或損失函數）進行優化，從而訓練出最好的模型。常見的優化方法(optimization)有梯度下降法、牛頓法和擬牛頓法、共軛梯度法等等。
1. 梯度下降法（Gradient Descent）
梯度下降法是最早最簡單，也是最為常用的最優化方法。梯度下降法實現簡單，當目標函數是凸函數時，梯度下降法的解是全局解。一般情況下，其解不保證是全局最優解，梯度下降法的速度也未必是最快的。 梯度下降法的優化思想是用當前位置負梯度方向作為搜索方向，因為該方向為當前位置的最快下降方向，所以也被稱為是」最速下降法「。最速下降法越接近目標值，步長越小，前進越慢。
梯度下降 法的缺點：
（1）靠近極小值時收斂速度減慢;
（2）直線搜索時可能會產生一些問題；
（3）可能會「之字形」地下降。
在機器學習中，基於基本的梯度下降法發展了兩種梯度下降方法，分別為隨機梯度下降法和批量梯度下降法。
比如對一個線性回歸（Linear Logistics）模型，假設下面的h(x)是要擬合的函數，J( )為損失函數， 是參數，要迭代求解的值，求解出來了那最終要擬合的函數h( )就出來了。其中m是訓練集的樣本個數，n是特徵的個數。
1）批量梯度下降法（Batch Gradient Descent，BGD）
（1）將J( )對 求偏導，得到每個theta對應的的梯度：
(2）由於是要最小化風險函數，所以按每個參數 的梯度負方向，來更新每個 ：
（3）從上面公式可以注意到，它得到的是一個全局最優解，但是每迭代一步，都要用到訓練集所有的數據，如果m很大，那麼可想而知這種方法的迭代速度會相當的慢。所以，這就引入了另外一種方法——隨機梯度下降。
對於批量梯度下降法，樣本個數m，x為n維向量，一次迭代需要把m個樣本全部帶入計算，迭代一次計算量為m*n2。
2）隨機梯度下降（Stochastic Gradient Descent，SGD）
（1）上面的風險函數可以寫成如下這種形式，損失函數對應的是訓練集中每個樣本的粒度，而上面批量梯度下降對應的是所有的訓練樣本：
（2）每個樣本的損失函數，對 求偏導得到對應梯度，來更新 ：
（3）隨機梯度下降是通過每個樣本來迭代更新一次，如果樣本量很大的情況（例如幾十萬），那麼可能只用其中幾萬條或者幾千條的樣本，就已經將
迭代到最優解了，對比上面的批量梯度下降，迭代一次需要用到十幾萬訓練樣本，一次迭代不可能最優，如果迭代10次的話就需要遍歷訓練樣本10次。但是，SGD伴隨的一個問題是噪音較BGD要多，使得SGD並不是每次迭代都向著整體最優化方向。
隨機梯度下降每次迭代只使用一個樣本，迭代一次計算量為n2，當樣本個數m很大的時候，隨機梯度下降迭代一次的速度要遠高於批量梯度下降方法。 兩者的關系可以這樣理解：隨機梯度下降方法以損失很小的一部分精確度和增加一定數量的迭代次數為代價，換取了總體的優化效率的提升。增加的迭代次數遠遠小於樣本的數量。
對批量梯度下降法和隨機梯度下降法的總結：
批量梯度下降---最小化所有訓練樣本的損失函數，使得最終求解的是全局的最優解，即求解的參數是使得風險函數最小，但是對於大規模樣本問題效率低下。
隨機梯度下降---最小化每條樣本的損失函數，雖然不是每次迭代得到的損失函數都向著全局最優方向， 但是大的整體的方向是向全局最優解的，最終的結果往往是在全局最優解附近，適用於大規模訓練樣本情況。
2. 牛頓法和擬牛頓法（Newton's method & Quasi-Newton Methods）
1）牛頓法（Newton's method）
牛頓法是一種在實數域和復數域上近似求解方程的方法。方法使用函數 f ( x )的泰勒級數的前面幾項來尋找方程 f ( x ) = 0的根。牛頓法最大的特點就在於它的收斂速度很快。
具體步驟：
首先，選擇一個接近函數 f ( x )零點的x0，計算相應的 f ( x 0)和切線斜率 f ' ( x 0)（這里 f ' 表示函數 f 的導數）。然後我們計算穿過點( x 0, f ( x 0))並且斜率為 f '( x 0)的直線和 x 軸的交點的 x 坐標，也就是求如下方程的解：
我們將新求得的點的 x 坐標命名為 x 1，通常 x 1會比 x 0更接近方程 f ( x ) = 0的解。因此我們現在可以利用 x 1開始下一輪迭代。迭代公式可化簡為如下所示：
已經證明，如果 f '是連續的，並且待求的零點 x 是孤立的，那麼在零點 x 周圍存在一個區域，只要初始值 x 0位於這個鄰近區域內，那麼牛頓法必定收斂。 並且，如果 f ' ( x )不為0, 那麼牛頓法將具有平方收斂的性能. 粗略的說，這意味著每迭代一次，牛頓法結果的有效數字將增加一倍。下圖為一個牛頓法執行過程的例子。
由於牛頓法是基於當前位置的切線來確定下一次的位置，所以牛頓法又被很形象地稱為是"切線法"。
關於牛頓法和梯度下降法的效率對比：
從本質上去看，牛頓法是二階收斂，梯度下降是一階收斂，所以牛頓法就更快。如果更通俗地說的話，比如你想找一條最短的路徑走到一個盆地的最底部，梯度下降法每次只從你當前所處位置選一個坡度最大的方向走一步，牛頓法在選擇方向時，不僅會考慮坡度是否夠大，還會考慮你走了一步之後，坡度是否會變得更大。所以，可以說牛頓法比梯度下降法看得更遠一點，能更快地走到最底部。（牛頓法目光更加長遠，所以少走彎路；相對而言，梯度下降法只考慮了局部的最優，沒有全局思想。）
根據wiki上的解釋，從幾何上說，牛頓法就是用一個二次曲面去擬合你當前所處位置的局部曲面，而梯度下降法是用一個平面去擬合當前的局部曲面，通常情況下，二次曲面的擬合會比平面更好，所以牛頓法選擇的下降路徑會更符合真實的最優下降路徑。
註：紅色的牛頓法的迭代路徑，綠色的是梯度下降法的迭代路徑。
牛頓法的優缺點總結：
優點：二階收斂，收斂速度快；
缺點：牛頓法是一種迭代演算法，每一步都需要求解目標函數的Hessian矩陣的逆矩陣，計算比較復雜。
2）擬牛頓法（Quasi-Newton Methods）
擬牛頓法是求解非線性優化問題最有效的方法之一，於20世紀50年代由美國Argonne國家實驗室的物理學家W.C.Davidon所提出來。Davidon設計的這種演算法在當時看來是非線性優化領域最具創造性的發明之一。不久R. Fletcher和M. J. D. Powell證實了這種新的演算法遠比其他方法快速和可靠，使得非線性優化這門學科在一夜之間突飛猛進。
擬牛頓法的本質思想是改善牛頓法每次需要求解復雜的Hessian矩陣的逆矩陣的缺陷，它使用正定矩陣來近似Hessian矩陣的逆，從而簡化了運算的復雜度。 擬牛頓法和最速下降法一樣只要求每一步迭代時知道目標函數的梯度。通過測量梯度的變化，構造一個目標函數的模型使之足以產生超線性收斂性。這類方法大大優於最速下降法，尤其對於困難的問題。另外，因為擬牛頓法不需要二階導數的信息，所以有時比牛頓法更為有效。如今，優化軟體中包含了大量的擬牛頓演算法用來解決無約束，約束，和大規模的優化問題。
具體步驟：
擬牛頓法的基本思想如下。首先構造目標函數在當前迭代xk的二次模型：
這里Bk是一個對稱正定矩陣，於是我們取這個二次模型的最優解作為搜索方向，並且得到新的迭代點：
其中我們要求步長ak 滿足Wolfe條件。這樣的迭代與牛頓法類似，區別就在於用近似的Hesse矩陣Bk 代替真實的Hesse矩陣。所以擬牛頓法最關鍵的地方就是每一步迭代中矩陣Bk的更新。現在假設得到一個新的迭代xk+1，並得到一個新的二次模型：
我們盡可能地利用上一步的信息來選取Bk。具體地，我們要求
從而得到
這個公式被稱為割線方程。常用的擬牛頓法有DFP演算法和BFGS演算法。
原文鏈接： [Math] 常見的幾種最優化方法 - Poll的筆記 - 博客園
3. 優化演算法總結
本文介紹一下機器學習和深度學習中常用的優化演算法和優化器以及一些其他我知道的優化演算法,部分演算法我也沒有搞懂,就先記錄下來以後慢慢研究吧.*_*.
1.梯度下降演算法(Gradient Descent)
梯度下降法可以參考我另一篇文章 機器學習-線性回歸 里的講解,這里就不在重復敘述.這里需要強調一下,深度學習里常用的SGD,翻譯過來是隨機梯度下降,但是實質是mini-batch梯度下降(mini-batch-gd),或者說是兩者的結合更准確一些.
SGD的優點是,演算法簡單,計算量小,在函數為凸函數時可以找到全局最優解.所以是最常用的優化演算法.缺點是如果函數不是凸函數的話,很容易進入到局部最優解而無法跳出來.同時SGD在選擇學習率上也是比較困難的.
2.牛頓法
牛頓法和擬牛頓法都是求解無約束最優化問題的常用方法,其中牛頓法是迭代演算法,每一步需要求解目標函數的海森矩陣的逆矩陣,計算比較復雜.
牛頓法在求解方程根的思想:在二維情況下,迭代的尋找某一點x,尋找方法是隨機一個初始點x_0,目標函數在該點x_0的切線與x坐標軸的交點就是下一個x點,也就是x_1.不斷迭代尋找x.其中切線的斜率為目標函數在點x_0的導數(梯度),切必過點(x_0,f(x_0)).所以迭代的方程式如圖1,為了求該方程的極值點,還需要令其導數等於0,也就是又求了一次導數,所以需要用到f(x)的二階導數.
在最優化的問題中,牛頓法提供了一種求解的辦法. 假設任務是優化一個目標函數f, 求函數ff的極大極小問題, 可以轉化為求解函數f導數等於0的問題, 這樣求可以把優化問題看成方程求解問題(f的導數等於0). 剩下的問題就和牛頓法求解方程根的思想很相似了.
目標函數的泰勒展開式:
化簡後:
這樣就得到了與圖1相似的公式,這里是二維的,在多維空間上,求二階導數就是求海森矩陣,因為是分母,所以還需要求海森矩陣的逆矩陣.
牛頓法和SGD的區別:
牛頓法是二階求導,SGD是一階求導,所以牛頓法要收斂的更快一些.SGD只考慮當前情況下梯度下降最快的方向,而牛頓法不僅考慮當前梯度下降最快,還有考慮下一步下降最快的方向.
牛頓法的優點是二階求導下降速度快,但是因為是迭代演算法,每一步都需要求解海森矩陣的逆矩陣,所以計算復雜.
3.擬牛頓法(沒搞懂,待定)
考慮到牛頓法計算海森矩陣比較麻煩,所以它使用正定矩陣來代替海森矩陣的逆矩陣,從而簡化了計算過程.
常用的擬牛頓法有DFP演算法和BFGS演算法.
4.共軛梯度法(Conjugate Gradient)
共軛梯度法是介於最速下降法與牛頓法之間的一個方法,它僅需利用一階導數信息,但克服了最速下降法收斂慢的缺點,又避免了牛頓法計算海森矩陣並求逆的缺點.共軛梯度法不僅是解決大型線性方程組最有用的方法之一,也是解大型非線性最優化最有效的演算法之一.
5.拉格朗日法
參考SVM里的講解 機器學習-SVM
6.動量優化法(Momentum)
動量優化法主要是在SGD的基礎上,加入了歷史的梯度更新信息或者說是加入了速度更新.SGD雖然是很流行的優化演算法,但是其學習過程很慢,因為總是以同樣的步長沿著梯度下降的方向.所以動量是為了加速學習的方法.
其中第一行的減號部分是計算當前的梯度,第一行是根據梯度更新速度v,而α是新引進的參數,在實踐中,α的一般取值為 0.5,0.9 和 0.99.和學習率 一樣,α 也會隨著時間不斷調整.一般初始值是一個較小的值,隨後會慢慢變大.
7.Nesterov加速梯度(NAG, Nesterov accelerated gradient)
NAG是在動量優化演算法的基礎上又進行了改進.根據下圖可以看出,Nesterov 動量和標准動量之間的區別體現在梯度計算上, Nesterov 動量中,梯度計算在施加當前速度之後.因此,Nesterov 動量可以解釋為往標准動量方法中添加了一個校正因子
8.AdaGrad演算法
AdaGrad演算法,自適應優化演算法的一種,獨立地適應所有模型參數的學習率,縮放每個參數反比於其所有梯度歷史平均值總和的平方根.具有代價函數最大梯度的參數相應地有個快速下降的學習率,而具有小梯度的參數在學習率上有相對較小的下降.通俗一點的講,就是根據實際情況更改學習率,比如模型快要收斂的時候,學習率步長就會小一點,防止跳出最優解.
其中g是梯度,第一行的分母是計算累計梯度的平方根, 是為了防止分母為0加上的極小常數項,α是學習率.
Adagrad的主要優點是不需要人為的調節學習率,它可以自動調節.但是依然需要設置一個初始的全局學習率.缺點是隨著迭代次數增多,學習率會越來越小,最終會趨近於0.
9.RMSProp演算法
RMSProp修改 AdaGrad 以在非凸設定下效果更好,改變梯度積累為指數加權的移動平均.AdaGrad旨在應用於凸問題時快速收斂.
10.AdaDelta演算法
11.Adam演算法
Adam是Momentum和RMSprop的結合體,也就是帶動量的自適應優化演算法.
12.Nadam演算法
13.模擬退火演算法
14.蟻群演算法
15.遺傳演算法
動量是為了加快學習速度,而自適應是為了加快收斂速度,注意學習速度快不一定收斂速度就快,比如步長大學習速度快,但是很容易跳出極值點,在極值點附近波動,很難達到收斂.
未完待定....
參考:
《統計學習方法》 李航 著
《深度學習》 花書