郭勛誠

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

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

【中圖分類號】G63 【文獻標識碼】A 【文章編號】2095-3089（2018）40-0157-02

1.引言

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

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

2.算法原理

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

2.1最速下降法

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

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），其中η表示學習率，則

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

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

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

Step0：隨機初始化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）。

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

2.2牛頓法

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

我們由泰勒展開式可得

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）對自變量x求導，令其為0可得：

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

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

xk+1=xk-η■ （7）

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

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

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

3.應用

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

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

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

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

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

4.總結(jié)

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

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

參考文獻：

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

[2]劉穎超，張紀元.梯度下降法[J].南京理工大學學報，1993（2）：12-16.

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

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

[5]孫婭楠，林文斌.梯度下降法在機器學習中的應用[J].蘇州科技學院學報（自然科學版），2018（2）.