無約束優(yōu)化算法比較及其極值點研究

毛巍1， 蘭恒友2

(1.四川理工學院理學院， 四川自貢643000；2.企業(yè)信息化與物聯(lián)網測控技術四川省高校重點實驗室， 四川自貢643000)

摘要：求解無約束優(yōu)化問題是數(shù)值計算方面的重要研究內容，求解無約束優(yōu)化問題的方法較多，選擇一種較為快速且復雜度較小的方法具有重要意義。介紹無約束優(yōu)化問題中7種算法的基本思想和具體步驟，并結合MATLAB軟件編程仿真，依據定量分析對仿真結果進行對比分析，對這7種算法的優(yōu)缺點和極限點的收斂情況進行對比研究，并且根據其收斂迭代次數(shù)和數(shù)值計算結果精確度確定一個相對有效的算法。

關鍵詞：無約束優(yōu)化算法；算法分析；迭代收斂；極限點比較

文章編號：1673-1549(2015)04-0089-06

DOI:10.11863/j.suse.2015.04.19

收稿日期:2015-06-05

基金項目:四川理工學院科研項目(2015RC07);企業(yè)信息化與物聯(lián)網測控技術四川省高校重點實驗室開放

作者簡介:毛巍(1991-)，女，四川眉山人，碩士生，主要從事最優(yōu)化方法方面的研究，(E-mail)mwsuse@126．com

中圖分類號：O224

文獻標志碼：A

引言

隨著計算機近30年的發(fā)展，最優(yōu)化方法發(fā)展成為數(shù)學應用領域一個重要的分支。至于“最優(yōu)”的解釋，就是將某一事件發(fā)展為最好的狀態(tài)。如今，無論人們從事各種活動，都希望能使所要從事的活動達到自己想要的理想狀態(tài)。在現(xiàn)實生活中廣泛存在著最優(yōu)化問題。而將最優(yōu)化問題轉化為比較容易解決的數(shù)學類問題，并快速找出最優(yōu)解的數(shù)學方法就是最優(yōu)化方法。求解目標函數(shù)極大值極小值問題是數(shù)學上的一類問題，并且這也是最優(yōu)化問題。因此求解最優(yōu)化問題的最優(yōu)化方法是一種數(shù)學類方法，而不是工程類方法，其重要意義體現(xiàn)在不僅在經濟管理學、運籌學和系統(tǒng)工程等數(shù)理學領域，而且也日益廣泛地應用在其他領域(如工程設計)[1]。

非線性最優(yōu)化，或者說非線性規(guī)劃，是至少有一個含有自變量的非線性函數(shù)存在于要求解的最優(yōu)化問題的約束條件和目標函數(shù)中。所以相對應的要用非線性規(guī)劃方法求解非線性規(guī)劃問題。而且相比求解線性規(guī)劃問題，其求解難度更大，因為其不同于解線性規(guī)劃問題有單純形算法這一通用方法。解非線規(guī)劃問題到目前為止，還沒有建立起適用于各種問題的一個通用算法對非線性規(guī)劃問題是普遍有效的。各個方法都有自己特定的適用范圍，因而這是需要人們深入研究的一個領域。但由于很多問題需要進一步精確化，以及計算機的發(fā)展，使非線性規(guī)劃在近30年得到迅速的發(fā)展，開始形成最優(yōu)化問題的一個重要分支，有廣泛的應用，特別是為最優(yōu)化設計提供數(shù)學理論基礎[2]。

對于這些方法，可以大致歸類為三大類方法：最速下降法、牛頓法及擬牛頓法。根據這三大類方法，不同研究方向的研究者都有很多研究結論。Fviege J[3]等于2000年對最速下降法進行了分析和完善，并結合眾多學者的研究，總結出最速下降法收斂速度慢以及通常在計算過程前期迭代或者期間插步驟適用[4]。牛頓法是一種求解無約束最優(yōu)化問題的經典方法，但其存在的不足(例如Hesse矩陣的可逆性)也令其進行不斷完善，比如Joseph W[5]等研究出牛頓法和最速下降法的組合方法。擬牛頓法，類似于最速下降法，具有牛頓法的快速收斂性，是一種較為有效的求解最優(yōu)化問題的方法，并且依據其算法思想，研究者將擬牛頓法細分為幾種算法(BFGS和SR1等)，王宜舉等[6]在非線性規(guī)劃與算法中詳細討論了幾種常見的擬牛頓法。

本文考慮如下無約束優(yōu)化問題：

求解這類無約束優(yōu)化問題的算法很多，包括使用導數(shù)的算法以及不使用導數(shù)的算法。本文主要研究的算法為最速下降法、阻尼牛頓法、修正牛頓法、對稱秩1算法(SR1)、BFGS算法、DFP算法和Broyden族算法，運用MATLAB軟件對算法進行編程，詳細介紹了7種算法的算法思想和算法步驟，并對各種算法的計算過程和結果進行分析，總結各類算法的優(yōu)缺點，并比較算法優(yōu)劣，最終得到相對有效的求解算法[7]。此外，在相同的初始條件下，計算和分析7種無約束優(yōu)化算法對同一算例產生的迭代點能否同時收斂到相同一個點的可行性。

1算法分析

1.1　最速下降法

1.1.1算法思想

最速下降法又稱梯度法，它是極小化算法中一種下降方向為負梯度方向的算法，雖然目前不再具有實用性，但其是研究其他算法的基礎。最速下降法的關鍵就是選取最速下降的方向，且負梯度方向就是最速下降方向，進行一維搜索，直至滿足精度要求，停止計算[8]。

1.1.2算法步驟

步0設定初始點x0∈Rn，容許誤差0≤ε?1，設k∶=1。

步2取方向dk=-gk。

步3依據線搜索技術來選取步長因子ak。

步4令xk+1∶=xk+akdk,k∶=k+1，轉步1。

1.2　擬牛頓法

1.2.1算法思想

擬牛頓法的基本算法思想是利用目標函數(shù)值與一階導數(shù)信息，構造目標函數(shù)近似曲率，并且同時具有類似牛頓法的快速收斂性的優(yōu)點。擬牛頓法不用求逆矩陣，而是用Hesse矩陣的某個近似矩陣取代，是一種較為有效的求解無約束問題的算法[9]。

1.2.2算法步驟

(1)SR1算法步驟

步0設定初始點x0∈Rn，終止誤差0≤ε?1，對稱正定矩陣H0(通常取單位矩陣In)，令k∶=0。

步2計算搜索方向dk=-Hkgk。

步3依據線搜索技術來選取步長因子ak。

步4令xk+1∶=xk+akdk，確定對稱正定矩陣Hk+1，

步5令k∶=k+1，轉步1。

(2)BFGS算法步驟[2,10]

步0給定參數(shù)δ∈(0,1)，σ∈(0,0.5)，初始點x0∈Rn，終止誤差0≤ε?1，對稱正定矩陣B0(通常取為G(x0)或單位矩陣In)，令k∶=0。

步2解線性方程組，得解dk，Bdk=-gk。

步3設mk滿足如下不等式中的非負最小整數(shù)m：

令

ak=δmk,xk+1=xk+akdk

步4由校正公式確定Bk+1，

步5令k∶=k+1，轉步1。

(3)DFP算法步驟[7]

步0給定參數(shù)δ∈(0,1)，σ∈(0,0.5)，初始點x0∈Rn，終止誤差0≤ε<<1。初始對稱正定矩陣B0(通常取為G-1(x0)或單位矩陣In)，令k∶=0。

步2計算搜索方向dk=-Hkgk。

步3設mk滿足如下不等式中的非負最小整數(shù)m：

令

ak=δmk,xk+1=xk+akdk

步4由校正公式確定Hk+1，

步5令k∶=k+1，轉步1。

(4)Broyden族算法步驟[11-12]

步0給定參數(shù)δ∈(0,1)，σ∈(0,0.5)，初始點x0∈Rn，終止誤差0≤ε?1。初始對稱正定矩陣B0(通常取為G-1(x0)或單位矩陣In)，令k∶=0。

步2計算搜索方向dk=-Hkgk。

步3設mk滿足如下不等式中的非負最小整數(shù)m：

令

ak=δmk,xk+1=xk+akdk

步4由校正公式確定Hk+1，

步5令k∶=k+1，轉步1。

1.3　牛頓法

1.3.1算法思想

將在迭代點xk處的目標函數(shù)f(x)進行二次泰勒展開，且將其展開式作為目標模型函數(shù)，并利用目標函數(shù)梯度和海森矩陣逆矩陣得到后續(xù)迭代點xk+1。在適當條件下，序列xk收斂，依據該二次目標模型函數(shù)極小點序列而近似求得相應的目標函數(shù)極小點。

1.3.2 算法步驟

(1)阻尼牛頓法

步0設定參數(shù)0≤ε?1，δ∈(0,1)，σ∈(0,0.5)，初始點x0∈Rn，且k∶=0。

步2計算Gk=▽2f(xk)，求解dk，GKd=-gk。

步3記mk滿足如下不等式中的非負最小整數(shù)m，

步4令

ak=δmk,xk+1∶=xk+akdk,k∶=k+1，

轉步1。

(2)修正牛頓法

σ∈(0,0.5)，初始點x0∈Rn，令k∶=0。

步2計算Hesse矩陣Gk=▽2f(xk)，求解dk，(GK+μkI)d=-gk。

步3記mk滿足如下不等式中的非負最小整數(shù)m，

令

ak=δmk,xk+1∶=xk+akdk

步4k∶=k+1，轉步1。

2仿真結果以及分析

2.1　數(shù)值計算結果

運用MATLAB對7個算法進行仿真求解無約束最優(yōu)化問題：

并得出結果(表1)。

表1　仿真運行結果

2.2　數(shù)值分析

最速下降法求得的最優(yōu)解為(1,1)T，迭代次數(shù)為1159，最優(yōu)值為1.1630e-10，迭代時間為0.4343s。從仿真結果知，雖然最速下降法精準求得最優(yōu)點，但是其迭代次數(shù)太多，所以效率不高。最速下降法程序設計簡單，存儲小，對初始點沒有特定的要求，即使從一個不理想的初始點出發(fā)也收斂到局部極小點。綜合上述分析結果，得出以下結論：(1)在遠離極小點的迭代點，目標函數(shù)每一次迭代都會導致其函數(shù)值下降幅度較大；(2)在接近極小點的迭代點，由于牛頓法鋸齒現(xiàn)象，會導致目標函數(shù)每一次前進的距離逐漸縮短，從而使目標函數(shù)收斂速度較慢[13]。

阻尼牛頓法和修正牛頓法求得的最優(yōu)解為(0.8033,0.6436)T和(0.7946,0.6293)T，迭代次數(shù)為100和150，最優(yōu)值為0.0390和0.0426，運行時間為0.0574s和0.0834s。相比較最速下降法，雖然沒有精準求得目標值，但是這兩種算法的迭代次數(shù)減少了許多，相對應的運行時間也會減少很多。而且發(fā)現(xiàn)在程序運行過程中，牛頓法由于求得Hesse矩陣的逆矩陣，而在計算過程中并不能確切保證Hesse矩陣一直是可逆的。所以，當選取初始點為一定值時，就可能出現(xiàn)程序不能運行的問題，這也是牛頓法最大的缺陷[14]。

擬牛頓法中SR1、BFGS、DFP、Broyden族4種方法的最優(yōu)解均為(1,1)T，迭代次數(shù)分別為22、20、27、23，最優(yōu)值為7.0304e-19、2.2005e-11、7.0983e-15、2.1465e-17，運行時間為0.0286s、0.0278s、0.0735s、0.0291s。比較最速下降法和牛頓法，可以明顯地發(fā)現(xiàn)不論是最優(yōu)點還是迭代次數(shù)，均比上述兩種方法有較大的提升。再比較擬牛頓法中4種算法的運行結果，迭代次數(shù)以及相對應的運行時間都相差不大，但是BFGS算法在迭代次數(shù)以及相對應的運行時間上均有優(yōu)勢。所以，只要精度足夠高，該方法很理想[15]。

3極限點比較

3.1　計算收斂結果

由于算法的仿真結果在一定程度上會受計算機編寫相關程序的影響。因此在編寫程序中出現(xiàn)的微小細節(jié)都會使某一個算法的性能以及結果產生比較大的差異性，如初始步長和一維搜索策略的不同，因此為了消除影響，在編程時對這7種無約束最優(yōu)化算法運用定量分析，即這7種算法具有相同的一維搜索策略、初始步長以及終止條件，盡最大可能使算法本身成為判斷算法有效性唯一依據[16]。因為研究的問題都是連續(xù)且可導的，并且依據無約束最優(yōu)化問題的條件，迭代點趨于最優(yōu)的快慢可以通過梯度趨于0的快慢近似地反映出來。本文終止條件為梯度，通過仿真結果分析評估這7種無約束最優(yōu)化算法的有效性。

無約束最優(yōu)化問題為：

顯然(0,0),(1,1),(-1,-1)均是該問題的最優(yōu)解，對于初始點分別為(1,3)、(0.5,2)、(-1,-3)和(-0.5,-2)時，7種無約束優(yōu)化算法的計算結果見表2～表5。

表2　初始點為(1,3)的計算結果

表3　初始點為(0.5,2)的計算結果

表4　初始點為(-1,-3)的計算結果

表5　初始點為(-0.5,-2)的計算結果

3.2　收斂結果分析

由表2～表5可知，最速下降法的迭代次數(shù)始終是最多的，為8330次和8299次，在4個不同的初始點中，當初始點設定為(1,3)、(0.5,2)時，極限點為(1,1)；當初始點設定為(-1,-3)、(-0.5,-2)時，極限點為(-1，-1)。牛頓法算法求函數(shù)極值時，4個不同初始點產生的點列均收斂到點(0，0)，而且收斂速度較快。擬牛頓法迭代次數(shù)相對更快，其中SR1算法在初始點設定為(1，3)、(-1，-3)時，均收斂到點(0，0)，而BFGS、DFP和Broyden族算法在初始點為(1，3)、(-1，-3)時，分別收斂到(1,1)和(-1，-1)，但初始點為(0.5，2)、(-0.5，-2)時，SR1算法和BFGS算法則分別收斂到點(1，1)和(-1，-1)，而DFP和Broyden族算法均收斂到(0，0)。因此可知阻尼牛頓法、修正牛頓法和SR1算法產生的極限點具有變化的不穩(wěn)定性，而另外4種算法均產生同一趨勢。

當極小化目標函數(shù)采用最速下降法時，彼此相鄰兩個搜索方向存在正交性，因而產生的迭代點列路徑表現(xiàn)為“之”字路線。最速下降法有兩個特點：局部收斂很快和全局收斂很慢，尤其是快要到最優(yōu)點時，收斂速度最慢。牛頓法與擬牛頓法是按照固定的設定坐標方向依次搜索，其搜索方向具有固定性。牛頓法有較快的收斂速度，但在初始點離極小點比較遠的時候，是否有下降的方向不能確定。擬牛頓法和最速下降法一樣只要求每一步迭代時知道目標函數(shù)的梯度。相比較最速下降法，這類方法具有巨大的優(yōu)勢，尤其針對較為困難的問題。

4結束語

無約束最優(yōu)化問題的計算方法是數(shù)值計算領域的重要研究課題，快速求解無約束最優(yōu)化問題具有重要意義。本文針對這個問題，比較了其中的7種算法，通過單最優(yōu)點和多最優(yōu)點兩個數(shù)值例子的MATLAB分析，可以發(fā)現(xiàn)每一種方法的優(yōu)點和其缺陷。通過分析仿真結果，相比于最速下降法和牛頓法，可以明顯地發(fā)現(xiàn)擬牛頓法不論是最優(yōu)點還是迭代次數(shù)，均比上述兩種方法有較大的提升。

綜合而言，主要是因為這7種無約束優(yōu)化算法算法具有差異的搜索方法構造，所以在相同的初始條件情況下，這7種算法的迭代點列就會使其對應的極限點不相同。因此，當求解含有多個最優(yōu)解的優(yōu)化問題時，要根據問題需要測驗多個初始點，最終達到尋求最優(yōu)解多解的目的。

參 考 文 獻：

[1]李志軍.非線性最優(yōu)化方法研究.數(shù)學學習與研究,2013(5):61-63.

[2]吳祈宗,侯福均.運籌學與最優(yōu)化方法.2版.北京:機械工業(yè)出版社,2013.

[3]Fliege J,Svaiter B F.Steepest descent methods for multicriteria optimization.Mathematical Methods of Operational Research,2000,51(3):479-494.

[4]李欣.求解無約束優(yōu)化問題的算法研究.西安:電子科技大學,2009.

[5]So J,Wu J,Zou X.A reaction-diffusion model for a single species with age structure.I Traveling wavefronts on unbounded domains.Royal Society of London Proceedings,2001,457(2012):1841.

[6]王宜舉,修乃華.非線性規(guī)劃理論與算法.西安:陜西科學技術出版社,2004.

[7]經紅霞.無約束最優(yōu)化問題的算法研究與實現(xiàn).北京:北京郵電大學,2013.

[8]劉盎然.線性方程組的迭代和最速下降法.赤峰學院學報:自然科學版,2014(2):10-13.

[9]屈曉軍.非凸無約束優(yōu)化問題的修正擬牛頓算法.長沙:湖南大學,2014.

[10]蔣華杰.BFGS算法的最優(yōu)化問題及在MATLAB中的實現(xiàn).科技創(chuàng)新導報,2014(19):88.

[11]王娜.求解奇異問題幾種迭代格式的收斂性.哈爾濱:哈爾濱理工大學,2014.

[12]景書杰,趙建衛(wèi),韓學鋒.一種改進的逆Broyden算法.吉林師范大學學報:自然科學版,2015,36(1):66-68.

[13]高蒙.求解無約束最優(yōu)化問題算法比較.市場周刊:理論研究,2014(5):155-156.

[14]王越.牛頓法的一種改進.邢臺學院學報,2014(4):163-164.

[15]陳姍.求解無約束最優(yōu)化問題的一個新的擬牛頓方法.南京:南京理工大學,2013.

[16]經紅霞.無約束最優(yōu)化問題的算法研究與實現(xiàn).北京:北京郵電大學,2013.

The Comparison of Unconstrained Optimization Algorithms and Their Extreme Point Study

MAOWei1,LANHengyou2

(1.Institude of Nonlinear Science and Engineering Computing, Sichuan University of Science & Engineering,

Zigong 643000, China; 2.Enterprise Informatization and Network Measurement and Control Technology Sichuan

Provincial Key Laboratory of University, Sichuan University of Science & Engineering, Zigong 643000, China)

Abstract:Solving unconstrained optimization problems is an important research problem in numerical calculations. At present, there are many ways to solve the unconstrained optimization problem, so choosing a rapid method that with small complexity is significant. Firstly, the basic ideas and concrete steps of seven algorithms in unconstrained optimization problems are introduced. Then combined with the MATLAB software programming simulation, according to the quantitative analysis, the simulation results are contrasted and analyzed. Finally, the advantages and disadvantages, the convergence situations of extreme points of seven algorithms are contrasted and studied, and a relatively efficient algorithm is determined according to the convergence iterations and the accuracy of numerical computing results.

Key words: unconstrained optimization algorithm; algorithm analysis; the iterative convergence;comparing the limit point