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

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

毛巍1， 蘭恒友2

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

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

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

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

DOI:10.11863/j.suse.2015.04.19

收稿日期:2015-06-05

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

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

中圖分類號：O224

文獻標(biāo)志碼：A

引言

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

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

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

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

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

1算法分析

1.1　最速下降法

1.1.1算法思想

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

1.1.2算法步驟

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

步2取方向dk=-gk。

步3依據(jù)線搜索技術(shù)來選取步長因子ak。

步4令xk+1∶=xk+akdk,k∶=k+1，轉(zhuǎn)步1。

1.2　擬牛頓法

1.2.1算法思想

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

1.2.2算法步驟

(1)SR1算法步驟

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

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

步3依據(jù)線搜索技術(shù)來選取步長因子ak。

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

步5令k∶=k+1，轉(zhuǎn)步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設(shè)mk滿足如下不等式中的非負最小整數(shù)m：

令

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

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

步5令k∶=k+1，轉(zhuǎn)步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設(shè)mk滿足如下不等式中的非負最小整數(shù)m：

令

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

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

步5令k∶=k+1，轉(zhuǎn)步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設(shè)mk滿足如下不等式中的非負最小整數(shù)m：

令

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

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

步5令k∶=k+1，轉(zhuǎn)步1。

1.3　牛頓法

1.3.1算法思想

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

1.3.2 算法步驟

(1)阻尼牛頓法

步0設(shè)定參數(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，

轉(zhuǎn)步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，轉(zhuǎn)步1。

2仿真結(jié)果以及分析

2.1　數(shù)值計算結(jié)果

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

并得出結(jié)果(表1)。

表1　仿真運行結(jié)果

2.2　數(shù)值分析

最速下降法求得的最優(yōu)解為(1,1)T，迭代次數(shù)為1159，最優(yōu)值為1.1630e-10，迭代時間為0.4343s。從仿真結(jié)果知，雖然最速下降法精準(zhǔn)求得最優(yōu)點，但是其迭代次數(shù)太多，所以效率不高。最速下降法程序設(shè)計簡單，存儲小，對初始點沒有特定的要求，即使從一個不理想的初始點出發(fā)也收斂到局部極小點。綜合上述分析結(jié)果，得出以下結(jié)論：(1)在遠離極小點的迭代點，目標(biāo)函數(shù)每一次迭代都會導(dǎo)致其函數(shù)值下降幅度較大；(2)在接近極小點的迭代點，由于牛頓法鋸齒現(xiàn)象，會導(dǎo)致目標(biāo)函數(shù)每一次前進的距離逐漸縮短，從而使目標(biāo)函數(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。相比較最速下降法，雖然沒有精準(zhǔn)求得目標(biāo)值，但是這兩種算法的迭代次數(shù)減少了許多，相對應(yīng)的運行時間也會減少很多。而且發(fā)現(xiàn)在程序運行過程中，牛頓法由于求得Hesse矩陣的逆矩陣，而在計算過程中并不能確切保證Hesse矩陣一直是可逆的。所以，當(dāng)選取初始點為一定值時，就可能出現(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種算法的運行結(jié)果，迭代次數(shù)以及相對應(yīng)的運行時間都相差不大，但是BFGS算法在迭代次數(shù)以及相對應(yīng)的運行時間上均有優(yōu)勢。所以，只要精度足夠高，該方法很理想[15]。

3極限點比較

3.1　計算收斂結(jié)果

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

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

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

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

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

3.2　收斂結(jié)果分析

由表2～表5可知，最速下降法的迭代次數(shù)始終是最多的，為8330次和8299次，在4個不同的初始點中，當(dāng)初始點設(shè)定為(1,3)、(0.5,2)時，極限點為(1,1)；當(dāng)初始點設(shè)定為(-1,-3)、(-0.5,-2)時，極限點為(-1，-1)。牛頓法算法求函數(shù)極值時，4個不同初始點產(chǎn)生的點列均收斂到點(0，0)，而且收斂速度較快。擬牛頓法迭代次數(shù)相對更快，其中SR1算法在初始點設(shè)定為(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算法產(chǎn)生的極限點具有變化的不穩(wěn)定性，而另外4種算法均產(chǎn)生同一趨勢。

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

4結(jié)束語

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

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

參 考 文 獻：

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

[2]吳祈宗,侯福均.運籌學(xué)與最優(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)化問題的算法研究.西安:電子科技大學(xué),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ī)劃理論與算法.西安:陜西科學(xué)技術(shù)出版社,2004.

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

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

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

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

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

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

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

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

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

[16]經(jīng)紅霞.無約束最優(yōu)化問題的算法研究與實現(xiàn).北京:北京郵電大學(xué),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