前言

生活或者工作中遇到各種各樣的最優(yōu)化問(wèn)題，比如每個(gè)企業(yè)和個(gè)人都要 考慮的一個(gè)問(wèn)題“在一定成本下，如何使利潤(rùn)最大化”等。最優(yōu)化方法是一種數(shù)學(xué)方法，它是研究在給定約束之下如何尋求某些因素(的量)，以使某一(或某些)指標(biāo)達(dá)到最優(yōu)的一些學(xué)科的總稱。隨著學(xué)習(xí)的深入，博主越來(lái)越發(fā)現(xiàn)最優(yōu)化方法的重要性，學(xué)習(xí)和工作中遇到的大多問(wèn)題都可以建模成一種最優(yōu)化模型進(jìn)行求解，比如我們現(xiàn)在學(xué)習(xí)的機(jī)器學(xué)習(xí)算法，大部分的機(jī)器學(xué)習(xí)算法的本質(zhì)都是建立優(yōu)化模型，通過(guò)最優(yōu)化方法對(duì)目標(biāo)函數(shù)（或損失函數(shù)）進(jìn)行優(yōu)化，從而訓(xùn)練出最好的模型。常見的最優(yōu)化方法有梯度下降法、牛頓法和擬牛頓法、共軛梯度法等等。

1. 梯度下降法

梯度下降法是最早最簡(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)生一些問(wè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求解出來(lái)了，那最終要擬合的函數(shù)h(theta)就出來(lái)了。其中m是訓(xùn)練集的樣本個(gè)數(shù)，n是特征的個(gè)數(shù)。

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

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

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

從上面公式可以注意到，它得到的是一個(gè)全局最優(yōu)解，但是每迭代一步，都要用到訓(xùn)練集所有的數(shù)據(jù)，如果m很大，那么可想而知這種方法的迭代速度會(huì)相當(dāng)?shù)穆Ｋ?，這就引入了另外一種方法——隨機(jī)梯度下降。 對(duì)于批量梯度下降法，樣本個(gè)數(shù)m，x為n維向量，一次迭代需要把m個(gè)樣本全部帶入計(jì)算，迭代一次計(jì)算量為m*n^2。

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

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

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

隨機(jī)梯度下降是通過(guò)每個(gè)樣本來(lái)迭代更新一次，如果樣本量很大的情況（例如幾十萬(wàn)），那么可能只用其中幾萬(wàn)條或者幾千條的樣本，就已經(jīng)將theta迭代到最優(yōu)解了，對(duì)比上面的批量梯度下降，迭代一次需要用到十幾萬(wàn)訓(xùn)練樣本，一次迭代不可能最優(yōu)，如果迭代10次的話就需要遍歷訓(xùn)練樣本10次。但是，SGD伴隨的一個(gè)問(wèn)題是噪音較BGD要多，使得SGD并不是每次迭代都向著整體最優(yōu)化方向。隨機(jī)梯度下降每次迭代只使用一個(gè)樣本，迭代一次計(jì)算量為n^2，當(dāng)樣本個(gè)數(shù)m很大的時(shí)候，隨機(jī)梯度下降迭代一次的速度要遠(yuǎn)高于批量梯度下降方法。兩者的關(guān)系可以這樣理解：隨機(jī)梯度下降方法以損失很小的一部分精確度和增加一定數(shù)量的迭代次數(shù)為代價(jià)，換取了總體的優(yōu)化效率的提升。增加的迭代次數(shù)遠(yuǎn)遠(yuǎn)小于樣本的數(shù)量。

1.3 小結(jié)

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

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

2.牛頓法和擬牛頓法

2.1 牛頓法（Newton’s method）

牛頓迭代法（Newton’s method）又稱為牛頓-拉夫遜（拉弗森）方法（Newton-Raphson method），它是牛頓在17世紀(jì)提出的一種在實(shí)數(shù)域和復(fù)數(shù)域上近似求解方程的方法。牛頓法是一種在實(shí)數(shù)域和復(fù)數(shù)域上近似求解方程的方法。方法使用函數(shù)f (x)的泰勒級(jí)數(shù)的前面幾項(xiàng)來(lái)尋找方程f (x) = 0的根。牛頓法最大的特點(diǎn)就在于它的收斂速度很快。 已經(jīng)證明，如果是連續(xù)的，并且待求的零點(diǎn)是孤立的，那么在零點(diǎn)周圍存在一個(gè)區(qū)域，只要初始值位于這個(gè)鄰近區(qū)域內(nèi)，那么牛頓法必定收斂。 并且，如果不為0, 那么牛頓法將具有平方收斂的性能. 粗略的說(shuō)，這意味著每迭代一次，牛頓法結(jié)果的有效數(shù)字將增加一倍。 迭代法也稱輾轉(zhuǎn)法，是一種不斷用變量的舊值遞推新值的過(guò)程，跟迭代法相對(duì)應(yīng)的是直接法（或者稱為一次解法），即一次性解決問(wèn)題。迭代算法是用計(jì)算機(jī)解決問(wèn)題的一種基本方法。它利用計(jì)算機(jī)運(yùn)算速度快、適合做重復(fù)性操作的特點(diǎn)，讓計(jì)算機(jī)對(duì)一組指令（或一定步驟）重復(fù)執(zhí)行，在每次執(zhí)行這組指令（或這些步驟）時(shí)，都從變量的原值推出它的一個(gè)新值。

利用迭代算法解決問(wèn)題，需要做好以下三個(gè)方面的工作：

一、確定迭代變量 在可以用迭代算法解決的問(wèn)題中，至少存在一個(gè)可直接或間接地不斷由舊值遞推出新值的變量，這個(gè)變量就是迭代變量。

二、建立迭代關(guān)系式 所謂迭代關(guān)系式，指如何從變量的前一個(gè)值推出其下一個(gè)值的公式（或關(guān)系）。迭代關(guān)系式的建立是解決迭代問(wèn)題的關(guān)鍵，通?？梢允褂眠f推或倒推的方法來(lái)完成。

三、對(duì)迭代過(guò)程進(jìn)行控制 在什么時(shí)候結(jié)束迭代過(guò)程？這是編寫迭代程序必須考慮的問(wèn)題。不能讓迭代過(guò)程無(wú)休止地執(zhí)行下去。迭代過(guò)程的控制通?？煞譃閮煞N情況：一種是所需的迭代次數(shù)是個(gè)確定的值，可以計(jì)算出來(lái)；另一種是所需的迭代次數(shù)無(wú)法確定。對(duì)于前一種情況，可以構(gòu)建一個(gè)固定次數(shù)的循環(huán)來(lái)實(shí)現(xiàn)對(duì)迭代過(guò)程的控制；對(duì)于后一種情況，需要進(jìn)一步分析得出可用來(lái)結(jié)束迭代過(guò)程的條件。

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

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

matlab代碼：

定義函數(shù)
function y=f(x)
y=f(x）；%函數(shù)f(x）的表達(dá)式
end
function z=h(x)
z=h(x）；%函數(shù)h(x）的表達(dá)式，函數(shù)h(x)是函數(shù)f(x)的一階導(dǎo)數(shù)
end
主程序
x=X;%迭代初值
i=0;%迭代次數(shù)計(jì)算
while i
x0=X-f(X)/h(X);%牛頓迭代格式
if abs(x0-X)>0.01；%收斂判斷
X=x0;
else break
end
i=i+1;
end
fprintf('\n%s%.4f\t%s%d'，'X='，X，'i='，i) %輸出結(jié)果

Python代碼以實(shí)例展示求解方程的根。

py文件

def f(x):
    return (x-3)**3        '''定義 f(x) = (x-3)^3'''
def fd(x):
    return 3*((x-3)**2)    '''定義 f'(x) = 3*((x-3)^2）'''
def newtonMethod(n,assum):
    time = n
    x = assum
    Next = 0
    A = f(x)
    B = fd(x)
    print('A = ' + str(A) + ',B = ' + str(B) + ',time = ' + str(time))
    if f(x) == 0.0:
        return time,x
    else:
        Next = x - A/B
        print('Next x = '+ str(Next))
    if abs(A - f(Next)) < 1e-6: 
        print('Meet f(x) = 0,x = ' + str(Next)) '''設(shè)置迭代跳出條件，同時(shí)輸出滿足f(x) = 0的x值'''
    else:
        return newtonMethod(n+1,Next)
newtonMethod(0,4.0)    '''設(shè)置從0開始計(jì)數(shù)，x0 = 4.0'''

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

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

缺點(diǎn)：牛頓法是一種迭代算法，每一步都需要求解目標(biāo)函數(shù)的Hessian矩陣的逆矩陣，計(jì)算比較復(fù)雜。

2.2擬牛頓法（Quasi-Newton Methods）

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

擬牛頓法的本質(zhì)思想是改善牛頓法每次需要求解復(fù)雜的Hessian矩陣的逆矩陣的缺陷，它使用正定矩陣來(lái)近似Hessian矩陣的逆，從而簡(jiǎn)化了運(yùn)算的復(fù)雜度。擬牛頓法和最速下降法一樣只要求每一步迭代時(shí)知道目標(biāo)函數(shù)的梯度。

擬牛頓法和最速下降法(Steepest Descent Methods)一樣只要求每一步迭代時(shí)知道目標(biāo)函數(shù)的梯度。通過(guò)測(cè)量梯度的變化，構(gòu)造一個(gè)目標(biāo)函數(shù)的模型使之足以產(chǎn)生超線性收斂性。這類方法大大優(yōu)于最速下降法，尤其對(duì)于困難的問(wèn)題。

另外，因?yàn)閿M牛頓法不需要二階導(dǎo)數(shù)的信息，所以有時(shí)比牛頓法(Newton’s Method)更為有效。如今，優(yōu)化軟件中包含了大量的擬牛頓算法用來(lái)解決無(wú)約束，約束，和大規(guī)模的優(yōu)化問(wèn)題。

擬牛頓法是解非線性方程組及最優(yōu)化計(jì)算中最有效的方法之一，它是一類使每步迭代計(jì)算量少而又保持超線性收斂的牛頓型迭代法。

通過(guò)測(cè)量梯度的變化，構(gòu)造一個(gè)目標(biāo)函數(shù)的模型使之足以產(chǎn)生超線性收斂性。這類方法大大優(yōu)于最速下降法，尤其對(duì)于困難的問(wèn)題。另外，因?yàn)閿M牛頓法不需要二階導(dǎo)數(shù)的信息，所以有時(shí)比牛頓法更為有效。如今，優(yōu)化軟件中包含了大量的擬牛頓算法用來(lái)解決無(wú)約束，約束，和大規(guī)模的優(yōu)化問(wèn)題。

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

這里Bk是一個(gè)對(duì)稱正定矩陣，于是我們?nèi)∵@個(gè)二次模型的最優(yōu)解作為搜索方向，并且得到新的迭代點(diǎn)：

其中我們要求步長(zhǎng)ak 滿足Wolfe條件。這樣的迭代與牛頓法類似，區(qū)別就在于用近似的Hesse矩陣Bk 代替真實(shí)的Hesse矩陣。所以擬牛頓法最關(guān)鍵的地方就是每一步迭代中矩陣Bk的更新?，F(xiàn)在假設(shè)得到一個(gè)新的迭代xk+1，并得到一個(gè)新的二次模型：

盡可能地利用上一步的信息來(lái)選取Bk。具體地

也是割線方程。常用的擬牛頓法有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)定性高，而且不需要任何外來(lái)參數(shù)。

下圖為共軛梯度法和梯度下降法搜索最優(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-10 break;
end
p=r+(rsnew/rsold)*p;
rsold=rsnew;
end
end

共軛梯度法（Conjugate Gradient） 它的每一個(gè)搜索方向是互相共軛的，而這些搜索方向d僅僅是負(fù)梯度方向與上一次迭代的搜索方向的組合，因此，存儲(chǔ)量少，計(jì)算方便。

優(yōu)點(diǎn)：所需存儲(chǔ)量小，具有步收斂性，穩(wěn)定性高，而且不需要任何外來(lái)參數(shù)。可以用于無(wú)約束凸二次規(guī)劃問(wèn)題，節(jié)省存儲(chǔ)空間。

缺點(diǎn)：收斂性依賴K矩陣。

建議：不是大型運(yùn)算不用使用。

更多內(nèi)容可以參看數(shù)值分析、最優(yōu)化之類課程和書籍教材。

分別利用最速下降和共軛梯度法來(lái)解一個(gè)線性方程

%% linear equation Ax=b
A = [4,-2,-1;-2,4,-2;-1,-2,3];
b = [0;-2;3];

最速下降法

%% 最速下降法
x0 = [0;0;0];
iter_max = 1000;
for i = 1:iter_max
    r = A*x0 - b;
    alpha = (r'*r)/(r'*A*r);
    x = x0 - alpha*r;
    if norm(x-x0)<=10^(-8)
        break
    end
    x0 = x;
end

共軛梯度法

```csharp
%% 共軛梯度法
x0 = [0;0;0];
r0 = A*x0 - b;
p0 = -r0;
iter_max = 1000;
for i = 1:iter_max
    alpha = (r0'*r0)/(p0'*A*p0);
    x = x0 + alpha*p0;
    r = r0 + alpha*A*p0;
    beta = (r'*r)/(r0'*r0);
    p = -r + beta*p0;
    if norm(x-x0)<=10^(-8)
        break
    end
    x0 = x;
    r0 = r;
    p0 = p;
end

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

啟發(fā)式算法（heuristic algorithm)是相對(duì)于最優(yōu)化算法提出的?，F(xiàn)階段，啟發(fā)式算法以仿自然體算法為主，主要有蟻群算法、模擬退火法、神經(jīng)網(wǎng)絡(luò)等。

現(xiàn)代啟發(fā)式算法的各種具體實(shí)現(xiàn)方法是相對(duì)獨(dú)立提出的,相互之間有一定的區(qū)別。從歷史上看,現(xiàn)代啟發(fā)式算法主要有:模擬退火算法(SA)、遺傳算法(GA)、列表搜索算法(ST)、進(jìn)化規(guī)劃(EP)、進(jìn)化策略(ES)、蟻群算法(ACA)、人工神經(jīng)網(wǎng)絡(luò)(ANN)。如果從決策變量編碼方案的不同來(lái)考慮,可以有固定長(zhǎng)度的編碼(靜態(tài)編碼)和可變長(zhǎng)度的編碼(動(dòng)態(tài)編碼)兩種方案。 詳情可以參考百度百科或者維基百科，或者是相關(guān)高手的博客。

到此這篇關(guān)于Matlab常見最優(yōu)化方法的原理和深度分析的文章就介紹到這了,更多相關(guān)Matlab原理和深度分析內(nèi)容請(qǐng)搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！

最新評(píng)論