無約束優化問題

郭勛誠

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

【關鍵詞】最優化問題 ?最速下降法 ?牛頓法

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

1.引言

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

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

2.算法原理

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

2.1最速下降法

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

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

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

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）。

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

2.2牛頓法

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

我們由泰勒展開式可得

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）

并看成連續迭代可得

xk+1=xk-η■ （7）

2.3算法的比較及其聯系

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

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

3.應用

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

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

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

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

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

4.總結

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

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

參考文獻：

[1]陳宇.基于物流配送路徑優化問題的最優化方法研究[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）.