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

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

毛巍1， 蘭恒友2

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

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

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

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

DOI:10.11863/j.suse.2015.04.19

收稿日期:2015-06-05

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

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

中圖分類號(hào)：O224

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

引言

隨著計(jì)算機(jī)近30年的發(fā)展，最優(yōu)化方法發(fā)展成為數(shù)學(xué)應(yīng)用領(lǐng)域一個(gè)重要的分支。至于“最優(yōu)”的解釋，就是將某一事件發(fā)展為最好的狀態(tài)。如今，無論人們從事各種活動(dòng)，都希望能使所要從事的活動(dòng)達(dá)到自己想要的理想狀態(tài)。在現(xiàn)實(shí)生活中廣泛存在著最優(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)濟(jì)管理學(xué)、運(yùn)籌學(xué)和系統(tǒng)工程等數(shù)理學(xué)領(lǐng)域，而且也日益廣泛地應(yīng)用在其他領(lǐng)域(如工程設(shè)計(jì))[1]。

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

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

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

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

1算法分析

1.1　最速下降法

1.1.1算法思想

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

1.1.2算法步驟

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

步2取方向dk=-gk。

步3依據(jù)線搜索技術(shù)來選取步長(zhǎng)因子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ù)近似曲率，并且同時(shí)具有類似牛頓法的快速收斂性的優(yōu)點(diǎn)。擬牛頓法不用求逆矩陣，而是用Hesse矩陣的某個(gè)近似矩陣取代，是一種較為有效的求解無約束問題的算法[9]。

1.2.2算法步驟

(1)SR1算法步驟

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

步2計(jì)算搜索方向dk=-Hkgk。

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

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

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

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

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

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

步3設(shè)mk滿足如下不等式中的非負(fù)最小整數(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)，初始點(diǎn)x0∈Rn，終止誤差0≤ε<<1。初始對(duì)稱正定矩陣B0(通常取為G-1(x0)或單位矩陣In)，令k∶=0。

步2計(jì)算搜索方向dk=-Hkgk。

步3設(shè)mk滿足如下不等式中的非負(fù)最小整數(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)，初始點(diǎn)x0∈Rn，終止誤差0≤ε?1。初始對(duì)稱正定矩陣B0(通常取為G-1(x0)或單位矩陣In)，令k∶=0。

步2計(jì)算搜索方向dk=-Hkgk。

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

令

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

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

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

1.3　牛頓法

1.3.1算法思想

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

1.3.2 算法步驟

(1)阻尼牛頓法

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

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

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

步4令

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

轉(zhuǎn)步1。

(2)修正牛頓法

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

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

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

令

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

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

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

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

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

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

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

2.2　數(shù)值分析

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

3極限點(diǎn)比較

3.1　計(jì)算收斂結(jié)果

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

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

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

表2　初始點(diǎn)為(1,3)的計(jì)算結(jié)果

表3　初始點(diǎn)為(0.5,2)的計(jì)算結(jié)果

表4　初始點(diǎn)為(-1,-3)的計(jì)算結(jié)果

表5　初始點(diǎn)為(-0.5,-2)的計(jì)算結(jié)果

3.2　收斂結(jié)果分析

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

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

4結(jié)束語

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

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

參 考 文 獻(xiàn)：

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

[2]吳祈宗,侯福均.運(yùn)籌學(xué)與最優(yōu)化方法.2版.北京:機(jī)械工業(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)化問題的算法研究與實(shí)現(xiàn).北京:北京郵電大學(xué),2013.

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

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

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

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

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

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

[14]王越.牛頓法的一種改進(jìn).邢臺(tái)學(xué)院學(xué)報(bào),2014(4):163-164.

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

[16]經(jīng)紅霞.無約束最優(yōu)化問題的算法研究與實(shí)現(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