2022年常見(jiàn)的幾種最優(yōu)化方法

優(yōu)選文檔常見(jiàn)的幾種最優(yōu)化方法〔梯度下降法、牛頓法、擬牛頓法、共軛梯度法等】我們每個(gè)人都會(huì)在我們的生活或者工作中遇到各種各樣的最優(yōu)化問(wèn)題，比方每個(gè)企業(yè)和個(gè)人都要考慮的一個(gè)問(wèn)題“在肯定本錢(qián)下，如何使利潤(rùn)最大化〃等。最優(yōu)化方法是一種數(shù)學(xué)方法，它是研究在給定約束之下如何尋求某些因素（的量），以使某一（或某些）指標(biāo)到達(dá)最優(yōu)的一些學(xué)科的總稱。隨著學(xué)習(xí)的深刻，博主越來(lái)越發(fā)覺(jué)最優(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)練出最好的模型。常見(jiàn)的最優(yōu)化方法有梯度下降法、牛頓法和擬牛頓法、共軛梯度法等等。.梯度下降法〔6「/，曲1Descent]梯度下降法是最早最簡(jiǎn)單，也是最為常用的最優(yōu)化方法。梯度下降法完成簡(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)選文檔從上圖可以看出，梯度下降法在接近最優(yōu)解的地域收斂速度明顯變慢，利用梯度下降法求解需要很屢次的迭代。在機(jī)器學(xué)習(xí)中，基于根本的梯度下降法開(kāi)展了兩種梯度下降方法，分別為隨機(jī)梯度下降法和批量梯度下降法。比方對(duì)一個(gè)線性回歸〔LinearLogistics〕模型，假設(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)批量梯度下降法[BatchGradientDescent,BGD〕⑴將J(theta)對(duì)theta求偏導(dǎo)，得到每個(gè)theta對(duì)應(yīng)的的梯度：〔2〕由于是要最小化風(fēng)險(xiǎn)函數(shù)，所以按每個(gè)參數(shù)theta的梯度負(fù)方向，來(lái)更新每個(gè)theta：〔3〕從上面公式可以注意到，它得到的是一個(gè)全局最優(yōu)解，但是每迭代一步，都要用到訓(xùn)練集全部的數(shù)據(jù)，如果m很大，那么可想而知這種方法的迭代速度會(huì)相當(dāng)?shù)穆?。所以，這就引入了其它一種方法——隨機(jī)梯度下降。對(duì)于批量梯度下降法，樣本個(gè)數(shù)m，x為n維向量，一次迭代需要把m個(gè)樣本全部帶入計(jì)算，迭代一次計(jì)算量為mxn2。2〕隨機(jī)梯度下降6七。的25配GradientDescent,SGD]〔1〕上面的風(fēng)險(xiǎn)函數(shù)可以寫(xiě)成如下這種形式，損失函數(shù)對(duì)應(yīng)的是訓(xùn)練集中每個(gè)樣本的粒度，而上面批量梯度下降對(duì)應(yīng)的是全部的訓(xùn)練樣本：〔2〕每個(gè)樣本的損失函數(shù)，對(duì)theta求偏導(dǎo)得到對(duì)應(yīng)梯度，來(lái)更新theta：優(yōu)選文檔〔3〕隨機(jī)梯度下降是通過(guò)每個(gè)樣本來(lái)迭代更新一次，如果樣本量很大的情況〔例如幾十萬(wàn)〕，那么可能只用其中幾萬(wàn)條或者幾千條的樣本，就已經(jīng)將theta迭代到最優(yōu)解了，比照上面的批量梯度下降，迭代一次需要用到十幾萬(wàn)訓(xùn)練樣本，一次迭代不可能最優(yōu)，如果迭代10次的話就需要遍歷訓(xùn)練樣本10次。但是，SGD伴隨的一個(gè)問(wèn)題是噪音較BGD要多，使得SGD并不是每次迭代都向著整體最優(yōu)化方向。隨機(jī)梯度下降每次迭代只使用一個(gè)樣本，迭代一次計(jì)算量為n2，當(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ī)模樣本問(wèn)題效率低下。隨機(jī)梯度下降---最小化每條樣本的損失函數(shù)，雖然不是每次迭代得到的損失函數(shù)都向著全局最優(yōu)方向，但是大的整體的方向是向全局最優(yōu)解的，最終的結(jié)果往往是在全局最優(yōu)解附近，適用于大規(guī)模訓(xùn)練樣本情況。.牛頓法和擬牛頓法，?W0口'6method&Quasi-NewtonMethods)1)牛頓法3。亞1。門(mén)、method)牛頓法是一種在實(shí)數(shù)域和復(fù)數(shù)域上近似求解方程的方法。方法使用函數(shù)￡(x)的泰勒級(jí)數(shù)的前面幾項(xiàng)來(lái)尋覓方程f(x)=0的根。牛頓法最大的特點(diǎn)就在于它的收斂速度很快。具體步驟：優(yōu)選文檔首先，選擇一個(gè)接近函數(shù)f(X)零點(diǎn)的x0，計(jì)算相應(yīng)的f(x0)和切線斜率f'(x0)〔這里f'表示函數(shù)￡的導(dǎo)數(shù)〕。然后我們計(jì)算穿過(guò)點(diǎn)(x0,f(x0))并且斜率為f'(x0)的直線和x軸的交點(diǎn)的x坐標(biāo)，也就是求如下方程的解：我們將新求得的點(diǎn)的x坐標(biāo)命名為x1，通常x1會(huì)比x0更接近方程f(x)=0的解。因此我們現(xiàn)在可以利用x1開(kāi)始下一輪迭代。迭代公式可化簡(jiǎn)為如下所示：已經(jīng)證明，如果f’是連續(xù)的，并且待求的零點(diǎn)x是孤立的，那么在零點(diǎn)x周?chē)嬖谝粋€(gè)地域，只要初始值x0位于這個(gè)鄰近地域內(nèi)，那么牛頓法必定收斂。并且，如果f'(x)不為0,那么牛頓法將具有平方收斂的性能.粗略的說(shuō)，這意味著每迭代一次，牛頓法結(jié)果的有效數(shù)字將增加一倍。下列圖為一個(gè)牛頓法執(zhí)行過(guò)程的例子。由于牛頓法是基于當(dāng)前位置的切線來(lái)確定下一次的位置，所以牛頓法又被很形象地稱為是“切線法"。牛頓法的搜索路徑〔二維情況〕如下列圖所示：牛頓法搜索動(dòng)態(tài)例如圖：關(guān)于牛頓法和梯度下降法的效率比照：從本質(zhì)上去看，牛頓法是二階收斂，梯度下降是一階收斂，所以牛頓法就更快。如果更通俗地說(shuō)的話，比方你想找一條最短的路徑走到一個(gè)盆地的最底部，梯度下雌每次只從你當(dāng)前所處位置選一個(gè)坡度最大的方向走一步，牛頓法在選擇方向時(shí)，不僅會(huì)考慮坡度是否夠大，還會(huì)考慮你走了一步之后，坡度是否會(huì)變得更大。所以，可以說(shuō)牛頓法比梯度下雌看得更遠(yuǎn)一點(diǎn)，能更快地走到最底部?！才ｎD法目光更加長(zhǎng)遠(yuǎn)，所以少走彎;相對(duì)而言，梯度下雌只考慮了局部的最優(yōu)，沒(méi)有全局思加長(zhǎng)遠(yuǎn)，所以少走彎優(yōu)選文檔依據(jù)wiki上的解釋，從幾何上說(shuō)，牛頓法就是用一個(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ù)雜。2〕擬牛頓法〔Quasi-NewtonMethods]擬牛頓法是求解非線性優(yōu)化問(wèn)題最有效的方法之一，于20世紀(jì)50年代由美國(guó)Argonne國(guó)家實(shí)驗(yàn)室的物理學(xué)家所提出來(lái)。Davidon設(shè)計(jì)的這種算法在當(dāng)時(shí)看來(lái)是非線性優(yōu)化領(lǐng)域X制造性的制造之一。不久R.Fletcher和M.J.D.Powell證實(shí)了這種新的算法遠(yuǎn)比其他方法快速和可靠，使得非線性優(yōu)化這門(mén)學(xué)科在一夜之間突飛猛進(jìn)。擬牛頓法的本質(zhì)思想是改善牛頓法每次需要求解復(fù)雜的Hessian矩陣的逆矩陣的缺陷，它使用正定矩陣來(lái)近似Hessian矩陣的逆，從而簡(jiǎn)化了運(yùn)算的復(fù)雜度。擬牛頓法和最速下降法一樣只要求每一步迭代時(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ù)的信息，優(yōu)選文檔所以有時(shí)比牛頓法更為有效。如今，優(yōu)化軟件中包含了大量的擬牛頓算法用來(lái)解決無(wú)約束，約束，和大規(guī)模的優(yōu)化問(wèn)題。具體步驟：擬牛頓法的根本思想如下。首先構(gòu)造目標(biāo)函數(shù)在當(dāng)前迭代xk的二次模型：K這里BK是一個(gè)對(duì)稱正定矩陣，于是我們?nèi)∵@個(gè)二次模型的最優(yōu)解作為搜索方向，并且得到新的迭代點(diǎn)：其中我們要求步長(zhǎng)aK滿足Wolfe條件。這樣的迭代與牛頓法類似，區(qū)別就在于用近似的Hesse矩陣BkK替代真實(shí)的Hesse矩陣。所以擬牛頓法最關(guān)鍵的地方就是每一步迭代中矩陣BkK的更新?，F(xiàn)在假設(shè)得到一個(gè)新的迭代xK+1，并得到一個(gè)新的二次模型：我們盡可能地利用上一步的信息來(lái)選取BK。具體地，我們要求K從而得到這個(gè)公式被稱為割線方程。常用的擬牛頓法有DFP算法和BFGS算法。.共軛梯度法［ConjugateGradient)共軛梯度法是介于最速下雌與牛頓法之間的一個(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ù)。具體的完成步驟請(qǐng)參加wiKi百科共軛梯度法下列圖為共軛梯度法和梯度下降法搜索最優(yōu)解的路徑比照示意圖：優(yōu)選文檔注：綠色為梯度下降法，紅色代表共軛梯度法4,啟發(fā)式優(yōu)化方法啟發(fā)式方法指人在解決問(wèn)題時(shí)所采取的一種依據(jù)經(jīng)驗(yàn)規(guī)則進(jìn)行發(fā)覺(jué)的方法。其特點(diǎn)是在解決問(wèn)題時(shí)，利用過(guò)去的經(jīng)驗(yàn),選擇已經(jīng)行之有