參考：http://blog.csdn.NET/majinlei121/article/details/47260917

http://www.cnblogs.com/maybe2030/p/4751804.html

http://mp.weixin.qq.com/s?__biz=MzI5NzA3NjIwMA==&mid=2247483799&idx=1&sn=12c549869e05efa17aeb2bd3e4cd03f3&mpshare=1&scene=1&srcid=0222ltGcXjacwXGwwTmYSdzg#rd

1. 前言

熟悉機(jī)器學(xué)習(xí)的童鞋都知道，優(yōu)化方法是其中一個(gè)非常重要的話題，最常見的情形就是利用目標(biāo)函數(shù)的導(dǎo)數(shù)通過多次迭代來求解無約束最優(yōu)化問題。實(shí)現(xiàn)簡(jiǎn)單，coding 方便，是訓(xùn)練模型的必備利器之一。

?

2. 幾個(gè)數(shù)學(xué)概念

1) 梯度（一階導(dǎo)數(shù)）

考慮一座在 (x1, x2) 點(diǎn)高度是 f(x1, x2) 的山。那么，某一點(diǎn)的梯度方向是在該點(diǎn)坡度最陡的方向，而梯度的大小告訴我們坡度到底有多陡。注意，梯度也可以告訴我們不在最快變化方向的其他方向的變化速度（二維情況下，按照梯度方向傾斜的圓在平面上投影成一個(gè)橢圓）。對(duì)于一個(gè)含有 n 個(gè)變量的標(biāo)量函數(shù)，即函數(shù)輸入一個(gè) n 維 的向量，輸出一個(gè)數(shù)值，梯度可以定義為：

2) Hesse 矩陣（二階導(dǎo)數(shù)）

Hesse 矩陣常被應(yīng)用于牛頓法解決的大規(guī)模優(yōu)化問題(后面會(huì)介紹)，主要形式如下：

當(dāng) f(x) 為二次函數(shù)時(shí)，梯度以及 Hesse 矩陣很容易求得。二次函數(shù)可以寫成下列形式：

其中?x為列向量，A 是 n 階對(duì)稱矩陣，b 是 n 維列向量， c 是常數(shù)。 f(x) 梯度是 Ax+b, Hesse 矩陣等于 A 。

3) Jacobi 矩陣

Jacobi 矩陣實(shí)際上是向量值函數(shù)的梯度矩陣，假設(shè)F:Rn→Rm 是一個(gè)從n維歐氏空間轉(zhuǎn)換到m維歐氏空間的函數(shù)。這個(gè)函數(shù)由m個(gè)實(shí)函數(shù)組成:。這些函數(shù)的偏導(dǎo)數(shù)(如果存在)可以組成一個(gè)m行n列的矩陣(m by n)，這就是所謂的雅可比矩陣：

總結(jié)一下,

a)?如果 f(x) 是一個(gè)標(biāo)量函數(shù)，那么雅克比矩陣是一個(gè)向量，等于 f(x) 的梯度， Hesse 矩陣是一個(gè)二維矩陣。如果 f(x) 是一個(gè)向量值函數(shù)，那么Jacobi 矩陣是一個(gè)二維矩陣，Hesse 矩陣是一個(gè)三維矩陣。

b)?梯度是 Jacobian 矩陣的特例，梯度的 jacobian 矩陣就是 Hesse 矩陣（一階偏導(dǎo)與二階偏導(dǎo)的關(guān)系）。

常見的最優(yōu)化方法有梯度下降法、牛頓法和擬牛頓法、共軛梯度法等等。? ? ? ? ? ??

1. 梯度下降法（Gradient Descent）

　　梯度下降法是最早最簡(jiǎn)單，也是最為常用的最優(yōu)化方法。梯度下降法實(shí)現(xiàn)簡(jiǎn)單，當(dāng)目標(biāo)函數(shù)是凸函數(shù)時(shí)，梯度下降法的解是全局解。一般情況下，其解不保證是全局最優(yōu)解，梯度下降法的速度也未必是最快的。梯度下降法的優(yōu)化思想是用當(dāng)前位置負(fù)梯度方向作為搜索方向，因?yàn)樵摲较驗(yàn)楫?dāng)前位置的最快下降方向，所以也被稱為是”最速下降法“。最速下降法越接近目標(biāo)值，步長(zhǎng)越小，前進(jìn)越慢。梯度下降法的搜索迭代示意圖如下圖所示：

　　牛頓法的缺點(diǎn)：

　　（1）靠近極小值時(shí)收斂速度減慢，如下圖所示；

　　（2）直線搜索時(shí)可能會(huì)產(chǎn)生一些問題；

　　（3）可能會(huì)“之字形”地下降。

　　從上圖可以看出，梯度下降法在接近最優(yōu)解的區(qū)域收斂速度明顯變慢，利用梯度下降法求解需要很多次的迭代。

　　在機(jī)器學(xué)習(xí)中，基于基本的梯度下降法發(fā)展了兩種梯度下降方法，分別為隨機(jī)梯度下降法和批量梯度下降法。

　　比如對(duì)一個(gè)線性回歸（Linear Logistics）模型，假設(shè)下面的h(x)是要擬合的函數(shù)，J(theta)為損失函數(shù)，theta是參數(shù)，要迭代求解的值，theta求解出來了那最終要擬合的函數(shù)h(theta)就出來了。其中m是訓(xùn)練集的樣本個(gè)數(shù)，n是特征的個(gè)數(shù)。

其迭代公式如下：

　　1）批量梯度下降法（Batch Gradient Descent，BGD）

　　（1）將J(theta)對(duì)theta求偏導(dǎo)，得到每個(gè)theta對(duì)應(yīng)的的梯度：

　　（2）由于是要最小化風(fēng)險(xiǎn)函數(shù)，所以按每個(gè)參數(shù)theta的梯度負(fù)方向，來更新每個(gè)theta：

　　（3）從上面公式可以注意到，它得到的是一個(gè)全局最優(yōu)解，但是每迭代一步，都要用到訓(xùn)練集所有的數(shù)據(jù)，如果m很大，那么可想而知這種方法的迭代速度會(huì)相當(dāng)?shù)穆Ｋ?#xff0c;這就引入了另外一種方法——隨機(jī)梯度下降。

　　對(duì)于批量梯度下降法，樣本個(gè)數(shù)m，x為n維向量，一次迭代需要把m個(gè)樣本全部帶入計(jì)算，迭代一次計(jì)算量為m*n²。

　　2）隨機(jī)梯度下降（Stochastic Gradient Descent，SGD）

　　（1）上面的風(fēng)險(xiǎn)函數(shù)可以寫成如下這種形式，損失函數(shù)對(duì)應(yīng)的是訓(xùn)練集中每個(gè)樣本的粒度，而上面批量梯度下降對(duì)應(yīng)的是所有的訓(xùn)練樣本：

　　（2）每個(gè)樣本的損失函數(shù)，對(duì)theta求偏導(dǎo)得到對(duì)應(yīng)梯度，來更新theta：

　　（3）隨機(jī)梯度下降是通過每個(gè)樣本來迭代更新一次，如果樣本量很大的情況（例如幾十萬），那么可能只用其中幾萬條或者幾千條的樣本，就已經(jīng)將theta迭代到最優(yōu)解了，對(duì)比上面的批量梯度下降，迭代一次需要用到十幾萬訓(xùn)練樣本，一次迭代不可能最優(yōu)，如果迭代10次的話就需要遍歷訓(xùn)練樣本10次。但是，SGD伴隨的一個(gè)問題是噪音較BGD要多，使得SGD并不是每次迭代都向著整體最優(yōu)化方向。

　　隨機(jī)梯度下降每次迭代只使用一個(gè)樣本，迭代一次計(jì)算量為n²，當(dāng)樣本個(gè)數(shù)m很大的時(shí)候，隨機(jī)梯度下降迭代一次的速度要遠(yuǎn)高于批量梯度下降方法。兩者的關(guān)系可以這樣理解：隨機(jī)梯度下降方法以損失很小的一部分精確度和增加一定數(shù)量的迭代次數(shù)為代價(jià)，換取了總體的優(yōu)化效率的提升。增加的迭代次數(shù)遠(yuǎn)遠(yuǎn)小于樣本的數(shù)量。

　　對(duì)批量梯度下降法和隨機(jī)梯度下降法的總結(jié)：

　　批量梯度下降---最小化所有訓(xùn)練樣本的損失函數(shù)，使得最終求解的是全局的最優(yōu)解，即求解的參數(shù)是使得風(fēng)險(xiǎn)函數(shù)最小，但是對(duì)于大規(guī)模樣本問題效率低下。

　　隨機(jī)梯度下降---最小化每條樣本的損失函數(shù)，雖然不是每次迭代得到的損失函數(shù)都向著全局最優(yōu)方向， 但是大的整體的方向是向全局最優(yōu)解的，最終的結(jié)果往往是在全局最優(yōu)解附近，適用于大規(guī)模訓(xùn)練樣本情況。

回到頂部

2. 牛頓法和擬牛頓法（Newton's method &?Quasi-Newton Methods）

　　1）牛頓法（Newton's method）

　　相比最速下降法，牛頓法通常有更快的收斂速度，并且具有一定的全局預(yù)測(cè)性。其算法利用局部的一階和二階偏導(dǎo)信息，推測(cè)整個(gè)函數(shù)的性狀，進(jìn)而求得近似函數(shù)的全局最小值。然后將當(dāng)前最小值設(shè)定成近似函數(shù)的最小值。

　　具體步驟：

　第一步，利用Taylor級(jí)數(shù)切得原函數(shù)的二階近似：

第二步，把x看作是自變量，所有帶x^k的項(xiàng)看做常量，令一階倒數(shù)為0，即可求近似函數(shù)的最小值：

即：

第三步，將當(dāng)前的最小值設(shè)定近似函數(shù)的最小值（或乘以步長(zhǎng)）。

　　關(guān)于牛頓法和梯度下降法的效率對(duì)比：

　　從本質(zhì)上去看，牛頓法是二階收斂，梯度下降是一階收斂，所以牛頓法就更快。如果更通俗地說的話，比如你想找一條最短的路徑走到一個(gè)盆地的最底部，梯度下降法每次只從你當(dāng)前所處位置選一個(gè)坡度最大的方向走一步，牛頓法在選擇方向時(shí)，不僅會(huì)考慮坡度是否夠大，還會(huì)考慮你走了一步之后，坡度是否會(huì)變得更大。所以，可以說牛頓法比梯度下降法看得更遠(yuǎn)一點(diǎn)，能更快地走到最底部。（牛頓法目光更加長(zhǎng)遠(yuǎn)，所以少走彎路；相對(duì)而言，梯度下降法只考慮了局部的最優(yōu)，沒有全局思想。）

　　根據(jù)wiki上的解釋，從幾何上說，牛頓法就是用一個(gè)二次曲面去擬合你當(dāng)前所處位置的局部曲面，而梯度下降法是用一個(gè)平面去擬合當(dāng)前的局部曲面，通常情況下，二次曲面的擬合會(huì)比平面更好，所以牛頓法選擇的下降路徑會(huì)更符合真實(shí)的最優(yōu)下降路徑。

注：紅色的牛頓法的迭代路徑，綠色的是梯度下降法的迭代路徑。

　　牛頓法的優(yōu)缺點(diǎn)總結(jié)：

　　優(yōu)點(diǎn)：二階收斂，收斂速度快；

　　缺點(diǎn)：牛頓法是一種迭代算法，每一步都需要求解目標(biāo)函數(shù)的Hessian矩陣的逆矩陣，計(jì)算比較復(fù)雜。Hesse 矩陣不可逆時(shí)無法計(jì)算；矩陣的逆的計(jì)算復(fù)雜度為n的立方，當(dāng)問題規(guī)模比較大時(shí)，計(jì)算量很大，解決方法是采用擬牛頓法，比如 BFGS，L-BFGS,DFP,Broyden’s Algorithm 進(jìn)行近似；

　　2）擬牛頓法（Quasi-Newton Methods）

　　擬牛頓法是求解非線性優(yōu)化問題最有效的方法之一，于20世紀(jì)50年代由美國(guó)Argonne國(guó)家實(shí)驗(yàn)室的物理學(xué)家W.C.Davidon所提出來。Davidon設(shè)計(jì)的這種算法在當(dāng)時(shí)看來是非線性優(yōu)化領(lǐng)域最具創(chuàng)造性的發(fā)明之一。不久R. Fletcher和M. J. D. Powell證實(shí)了這種新的算法遠(yuǎn)比其他方法快速和可靠，使得非線性優(yōu)化這門學(xué)科在一夜之間突飛猛進(jìn)。

　　擬牛頓法的本質(zhì)思想是改善牛頓法每次需要求解復(fù)雜的Hessian矩陣的逆矩陣的缺陷，它使用正定矩陣來近似Hessian矩陣的逆，從而簡(jiǎn)化了運(yùn)算的復(fù)雜度。擬牛頓法和最速下降法一樣只要求每一步迭代時(shí)知道目標(biāo)函數(shù)的梯度。通過測(cè)量梯度的變化，構(gòu)造一個(gè)目標(biāo)函數(shù)的模型使之足以產(chǎn)生超線性收斂性。這類方法大大優(yōu)于最速下降法，尤其對(duì)于困難的問題。另外，因?yàn)閿M牛頓法不需要二階導(dǎo)數(shù)的信息，所以有時(shí)比牛頓法更為有效。如今，優(yōu)化軟件中包含了大量的擬牛頓算法用來解決無約束，約束，和大規(guī)模的優(yōu)化問題。

　　具體步驟：

　　擬牛頓法的基本思想如下。首先構(gòu)造目標(biāo)函數(shù)在當(dāng)前迭代x_k的二次模型：

　　這里B_k是一個(gè)對(duì)稱正定矩陣，于是我們?nèi)∵@個(gè)二次模型的最優(yōu)解作為搜索方向，并且得到新的迭代點(diǎn)： 　　其中我們要求步長(zhǎng)a_k?? 滿足Wolfe條件。這樣的迭代與牛頓法類似，區(qū)別就在于用近似的Hesse矩陣B_k?? 代替真實(shí)的Hesse矩陣。所以擬牛頓法最關(guān)鍵的地方就是每一步迭代中矩陣B_k ?? ? 的更新。現(xiàn)在假設(shè)得到一個(gè)新的迭代x_k+1，并得到一個(gè)新的二次模型： ??? ??? ??? ??? 　　我們盡可能地利用上一步的信息來選取B_k。具體地，我們要求 　　從而得到 　　這個(gè)公式被稱為割線方程。常用的擬牛頓法有DFP算法和BFGS算法。 回到頂部

3. 共軛梯度法（Conjugate Gradient）

　　共軛梯度法是介于最速下降法與牛頓法之間的一個(gè)方法，它僅需利用一階導(dǎo)數(shù)信息，但克服了最速下降法收斂慢的缺點(diǎn)，又避免了牛頓法需要存儲(chǔ)和計(jì)算Hesse矩陣并求逆的缺點(diǎn)，共軛梯度法不僅是解決大型線性方程組最有用的方法之一，也是解大型非線性最優(yōu)化最有效的算法之一。在各種優(yōu)化算法中，共軛梯度法是非常重要的一種。其優(yōu)點(diǎn)是所需存儲(chǔ)量小，具有步收斂性，穩(wěn)定性高，而且不需要任何外來參數(shù)。 　　具體的實(shí)現(xiàn)步驟請(qǐng)參加wiki百科共軛梯度法。 　　下圖為共軛梯度法和梯度下降法搜索最優(yōu)解的路徑對(duì)比示意圖： 注：綠色為梯度下降法，紅色代表共軛梯度法 　　MATLAB代碼： function [x] = conjgrad(A,b,x)r=b-A*x;p=r;rsold=r'*r;for i=1:length(b)Ap=A*p;alpha=rsold/(p'*Ap);x=x+alpha*p;r=r-alpha*Ap;rsnew=r'*r;if sqrt(rsnew)<1e-10break;endp=r+(rsnew/rsold)*p;rsold=rsnew;end end 回到頂部

4. 啟發(fā)式優(yōu)化方法

　　啟發(fā)式方法指人在解決問題時(shí)所采取的一種根據(jù)經(jīng)驗(yàn)規(guī)則進(jìn)行發(fā)現(xiàn)的方法。其特點(diǎn)是在解決問題時(shí),利用過去的經(jīng)驗(yàn),選擇已經(jīng)行之有效的方法，而不是系統(tǒng)地、以確定的步驟去尋求答案。啟發(fā)式優(yōu)化方法種類繁多，包括經(jīng)典的模擬退火方法、遺傳算法、蟻群算法以及粒子群算法等等。

　　還有一種特殊的優(yōu)化算法被稱之多目標(biāo)優(yōu)化算法，它主要針對(duì)同時(shí)優(yōu)化多個(gè)目標(biāo)（兩個(gè)及兩個(gè)以上）的優(yōu)化問題，這方面比較經(jīng)典的算法有NSGAII算法、MOEA/D算法以及人工免疫算法等。

　　這部分的內(nèi)容會(huì)在之后的博文中進(jìn)行詳細(xì)總結(jié)，敬請(qǐng)期待。這部分內(nèi)容的介紹已經(jīng)在博客《[Evolutionary Algorithm] 進(jìn)化算法簡(jiǎn)介》進(jìn)行了概要式的介紹，有興趣的博友可以進(jìn)行參考（2015.12.13）。

回到頂部

?5. 解決約束優(yōu)化問題——拉格朗日乘數(shù)法

　　有關(guān)拉格朗日乘數(shù)法的介紹請(qǐng)見我的另一篇博客：《拉格朗日乘數(shù)法》

總結(jié)

以上是生活随笔為你收集整理的常见的几种最优化方法的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。