郭勛誠(chéng)

【摘要】為提高最優(yōu)化問(wèn)題中的求解效率找到最佳求解路徑，在認(rèn)識(shí)、學(xué)習(xí)和初步研究了最速下降法和牛頓法后，大致了解了其求解原理及求解規(guī)律，對(duì)其進(jìn)行了進(jìn)一步的思考和研究，試圖探究在一定的條件范圍或某種特定的條件下，能否將二者相結(jié)合，從而達(dá)到更高的求解效率和更好的求解途徑。經(jīng)過(guò)我的思考和研究，個(gè)人認(rèn)為在解決較為簡(jiǎn)單的最優(yōu)化問(wèn)題時(shí)，我們可以在初始階段使用最速下降法，在接近極值點(diǎn)時(shí)可以運(yùn)用牛頓法，將兩者結(jié)合起來(lái)從而提高求解效率和求解途徑。

【關(guān)鍵詞】最優(yōu)化問(wèn)題 ?最速下降法 ?牛頓法

【中圖分類(lèi)號(hào)】G63 【文獻(xiàn)標(biāo)識(shí)碼】A 【文章編號(hào)】2095-3089（2018）40-0157-02

1.引言

最優(yōu)化方法主要應(yīng)用于各種管理問(wèn)題以及生產(chǎn)經(jīng)營(yíng)活動(dòng)中遇到的需要進(jìn)行優(yōu)化的各類(lèi)問(wèn)題[1]。只要存在資源有限的限制，就需要對(duì)資源做合理配置和規(guī)劃，所以需要用到最優(yōu)化方法。最優(yōu)化方法主要是通過(guò)合理利用如人力、物力等各類(lèi)資源，不斷提升系統(tǒng)的運(yùn)行效率，并最終使其達(dá)到最優(yōu)的狀態(tài)。在最優(yōu)化問(wèn)題中其常見(jiàn)思路一般為目標(biāo)函數(shù)f（x）求極值，并求解出對(duì)應(yīng)極值點(diǎn)x及f（x）的最大或最小值。一般情況下，我們將最優(yōu)化問(wèn)題分為兩類(lèi)：無(wú)約束的優(yōu)化問(wèn)題，即對(duì)自變量x不進(jìn)行限制;有約束的優(yōu)化問(wèn)題，即自變量x有約束，其中包括不等式約束和等式約束問(wèn)題。

本文主要討論無(wú)約束問(wèn)題，在第2節(jié)討論和分析最速下降法（第2.1節(jié)）和牛頓法（第2.2節(jié)）的求解過(guò)程、求解原理和求解規(guī)律，并針對(duì)兩個(gè)算法來(lái)進(jìn)行比較，試圖討論出在一定條件范圍或某種特定的條件下的最優(yōu)方法。

2.算法原理

本文主要研究無(wú)約束優(yōu)化問(wèn)題中的兩種基本算法——最速下降法和牛頓法。

2.1最速下降法

最速下降法主要是運(yùn)用了多元函數(shù)求導(dǎo)的數(shù)學(xué)原理，在無(wú)約束最優(yōu)化問(wèn)題的多個(gè)解法中屬于較為原始也是較為簡(jiǎn)單易行的[2]。對(duì)于一個(gè)給定的優(yōu)化函數(shù)，其負(fù)梯度方向總是當(dāng)前位置的最快方向，故選取該方向作為我們進(jìn)行更新迭代的方向，這就是梯度下降法也就是我們常說(shuō)的“最速下降法”的主要思想。 在高中的學(xué)習(xí)中，我們可以知道對(duì)f（x）求導(dǎo)函數(shù)的基本定義式。我們以一元函數(shù)為例，推導(dǎo)最速下降法。設(shè)一元函數(shù)為f（x），自變量x的取值范圍為（-∞，+∞），求函數(shù)f（x）的極小值。若需要進(jìn)行求最大值時(shí)，可運(yùn)用轉(zhuǎn)換的思想將其變成-f（x）進(jìn)行運(yùn)算。對(duì)函數(shù)f（x）求導(dǎo)，

f '（x）=■■ ? ? ? ? ? ? ? （1）

即在Δx→0的情況下，由（1）近似有

f（x+Δx）-f（x）=f '（x）Δx ? ? ? ? ? ? （2）

令x'=x+Δx，則f（x'）-f（x）=f '（x）Δx，若Δx=-ηf '（x），其中η表示學(xué)習(xí)率，則

f '（x）-f（x）=f '（x）Δx=-η（f '（x））2 ≤0 ? ? ? （3）

所以，以負(fù)梯度方向作為我們每一次更新迭代的方向可以保證函數(shù)單調(diào)遞減，并最終可以趨近函數(shù)f（x）的極小值。

在最速下降法的數(shù)學(xué)原理基礎(chǔ)上，可以得到應(yīng)用該方法求解極值的步驟。以一元函數(shù)求極小值為例。

Step0：隨機(jī)初始化x0，并求出f '（x0）;

Step1：令x1=x0-ηf '（x0），并求出f（x1），f '（x1）;

……

Step（k+1）：令xk+1=xk-ηf '（xk），并求出f（xk+1），f '（xk+1）。

以此類(lèi)推，算法停止條件有多種。明確最大迭代次數(shù)、極值的精度都可以用來(lái)確定算法的停止。

2.2牛頓法

牛頓法作為近似求解方程的一種方法[3]，一般首先將函數(shù)f（x）進(jìn)行泰勒展開(kāi)，最高次為二次，并且尋找方程f（x）=0的解。牛頓法相較于最速下降法，由于考慮了二階導(dǎo)數(shù)，所以收斂速度更快。下面就是牛頓算法的基本求解原理和過(guò)程。

我們由泰勒展開(kāi)式可得

f（x）=f（xk）+f '（xk）（x-xk）+■f ''（xk）（x-xk）2+…+■f（n）（xk）（x-xk）n+ο（xkn）， ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? （4）

但在一般情況下，只需要取

f（x）≈f（xk）+f '（xk）（x-xk）+■f ''（xk）（x-xk）2 ? ? （5）

由（5）對(duì)自變量x求導(dǎo)，令其為0可得：

f '（xk）+f ''（xk）（x-xk）=0 ? ? ? ? ? ? ? ? ? ? （6）

并看成連續(xù)迭代可得

xk+1=xk-η■ （7）

2.3算法的比較及其聯(lián)系

首先就最速下降法來(lái)說(shuō)，這是一種較為原始的算法，在最優(yōu)化問(wèn)題的幾種解題方法上是被選頻率較高的。其最主要的優(yōu)點(diǎn)有：每次迭代的計(jì)算量較小，儲(chǔ)存的變量少，對(duì)初始點(diǎn)的要求不高;但其缺點(diǎn)也較為明顯，如在接近極值點(diǎn)時(shí)，收斂速度會(huì)急劇下降，有時(shí)甚至不能夠找到極值點(diǎn)[4]。而對(duì)于牛頓法來(lái)說(shuō)，二者幾乎是相反的。牛頓法收斂速度快，但對(duì)初始點(diǎn)的要求很高，幾乎要求在所求極值點(diǎn)附近，并且牛頓法的步驟較為繁雜，結(jié)構(gòu)復(fù)雜。打個(gè)很簡(jiǎn)單的比方，這兩種方法就似兩個(gè)人去爬同一座山，最速下降法永遠(yuǎn)都是去找坡度最陡的那塊臺(tái)階，而不去管這樣走的路程是多少;牛頓法會(huì)去找坡度不那么陡，但是在所有方法中效率最高的那條路。也就是說(shuō)最速下降法的目光在當(dāng)下，牛頓法的目光在未來(lái)。

正如前面所說(shuō)，牛頓法需要一個(gè)極其精準(zhǔn)的初始點(diǎn)，而在現(xiàn)實(shí)生活中，這樣的初始點(diǎn)往往是很難找到的，但是其收斂速度較快;最速下降法不需要一個(gè)精準(zhǔn)的初始點(diǎn)，但是其收斂速度較慢。對(duì)此我認(rèn)為，可以將二者結(jié)合起來(lái)使用。在開(kāi)始計(jì)算時(shí)，可以先使用最速下降法，這樣對(duì)初始點(diǎn)的要求不是那么高，在用最速下降法計(jì)算的過(guò)程中，若發(fā)現(xiàn)其收斂速度急速下降，設(shè)這個(gè)點(diǎn)為x，我們可以換用牛頓法，并且將所得的x看作是一個(gè)初始點(diǎn)，然后用牛頓法繼續(xù)進(jìn)行運(yùn)算。這樣就可以使整個(gè)計(jì)算過(guò)程相比其分開(kāi)計(jì)算時(shí)效率更高，操作更為簡(jiǎn)單。

3.應(yīng)用

最優(yōu)化問(wèn)題在實(shí)際生活中有著十分廣泛的應(yīng)用[5]，如交通運(yùn)輸、計(jì)算機(jī)計(jì)算、資源分配等等。在高中的數(shù)學(xué)學(xué)習(xí)中，我們就曾學(xué)過(guò)相類(lèi)似的數(shù)學(xué)知識(shí)——線(xiàn)性規(guī)劃。

某市的車(chē)輛生產(chǎn)廠(chǎng)準(zhǔn)備甲、乙兩種汽車(chē)，生產(chǎn)一批甲汽車(chē)需要A鋼材400kg，B鋼材150kg，生產(chǎn)一種乙種汽車(chē)的主要原料是A種鋼材100kg，B種鋼材150kg，現(xiàn)汽車(chē)生產(chǎn)場(chǎng)中存A種鋼材1000kg，B種鋼材660kg，若生產(chǎn)一批甲汽車(chē)可以得到10000元利潤(rùn)，生產(chǎn)一批乙汽車(chē)可以得到5000元利潤(rùn)，為使得該汽車(chē)廠(chǎng)的利潤(rùn)達(dá)到最大化，應(yīng)該如何安排甲乙兩種汽車(chē)的生產(chǎn)計(jì)劃？

設(shè)該汽車(chē)廠(chǎng)生產(chǎn)A汽車(chē)x輛，生產(chǎn)B汽車(chē)y輛，可獲得z萬(wàn)元利潤(rùn)，所以可以求得目標(biāo)線(xiàn)型函數(shù)z=x+0.5y再用線(xiàn)性規(guī) ? 劃畫(huà)出相應(yīng)的圖形即可進(jìn)行求解。

z=x+0.5y400x+100y≤1000且x≥0，y≥0180x+150y≤660 ? ? ? ? （8）

根據(jù)不等式可作出可行區(qū)域圖，根據(jù)圖形可以看出在（2，2）處目標(biāo)函數(shù)取得最大值。

4.總結(jié)

本篇論文中主要是對(duì)無(wú)約束優(yōu)化問(wèn)題中的兩種解法——最速下降法和牛頓法進(jìn)行了研究，具體地解釋了兩種算法的基本定義，求解中運(yùn)用到的數(shù)學(xué)原理。并且簡(jiǎn)要地闡述了兩種算法的優(yōu)缺點(diǎn)及其異同，自我得出了在算法的開(kāi)始使用最速下降法，在收斂速度急劇下降的那個(gè)點(diǎn)使用牛頓法的結(jié)論，在理論上可以將兩種算法相結(jié)合起來(lái)，從而提高求解速率及效率。并且在全文的最后也進(jìn)行了應(yīng)用上的舉例說(shuō)明。

值得注意的是，在實(shí)際生活中，在資源有限的現(xiàn)實(shí)條件下，我們時(shí)時(shí)刻刻都在解決著最優(yōu)化問(wèn)題，在這個(gè)方面的研究我們應(yīng)當(dāng)更為深入，從而可以讓生活貼近數(shù)學(xué)，數(shù)學(xué)改變生活。

參考文獻(xiàn)：

[1]陳宇.基于物流配送路徑優(yōu)化問(wèn)題的最優(yōu)化方法研究[J]. 今日南國(guó)旬刊，2008（12）：8-9.

[2]劉穎超，張紀(jì)元.梯度下降法[J].南京理工大學(xué)學(xué)報(bào)，1993（2）：12-16.

[3]黃海，林穗華.幾種修正擬牛頓法的比較[J].廣西民族師范學(xué)院學(xué)報(bào)，2011（3）：8-11.

[4]郭躍東，宋旭東.梯度下降法的分析和改進(jìn)[J].科技展望， 2016，（15）.

[5]孫婭楠，林文斌.梯度下降法在機(jī)器學(xué)習(xí)中的應(yīng)用[J].蘇州科技學(xué)院學(xué)報(bào)（自然科學(xué)版），2018（2）.