求解非線性無約束優(yōu)化問題的修正BFGS方法

孫威

（綏化學(xué)院 信息工程學(xué)院，黑龍江 綏化 152061）

求解非線性無約束優(yōu)化問題的修正BFGS方法

孫威

（綏化學(xué)院 信息工程學(xué)院，黑龍江 綏化 152061）

在非線性無約束優(yōu)化上常用的方式有兩種，即共軛梯度與擬牛頓，其中共軛梯度方法具備低內(nèi)存需求以及簡(jiǎn)單迭代形式，擬牛頓法則是借助于Hesse矩陣正定近似的方式進(jìn)行牛頓法的近似，因此其收斂速度相對(duì)較快，通過大量數(shù)值實(shí)驗(yàn)證明相對(duì)于其他的Broyden族公式而言，BFGS公式數(shù)值所具穩(wěn)定性更好，且將其和非精確搜索方式有機(jī)結(jié)合應(yīng)用可獲得更為顯著的計(jì)算效果，因此目前在實(shí)踐實(shí)踐計(jì)算過程中經(jīng)常會(huì)采用這種方式來進(jìn)行計(jì)算.因傳統(tǒng)擬牛頓方程公式中所用梯度信息僅僅只有兩步，忽視了函數(shù)值信息，因此，有很大部分學(xué)者均在擬牛頓方程中添加了函數(shù)值，以此希望獲得更為顯著的計(jì)算結(jié)果.本文針對(duì)求解非線性無約束優(yōu)化問題的修正BFGS法進(jìn)行了研究與分析.

非線性；BFGS；優(yōu)化；求解；方法

1 修正BEGS方法的分析

為獲得修正BFGS算法局部超線性收斂性以及全局收斂性，下面筆者基于Aiping Liao所給參數(shù)（δk，γk）的修正，對(duì)tr（Bk+1）與det（Bk+1）兩個(gè)量進(jìn)行估計(jì)，明確新參數(shù)以及該參數(shù)一般條件，基于此再給出一個(gè)參數(shù)具體選擇與其數(shù)值結(jié)果.

1.1 修正BEGS方法的算法

1.1.1 準(zhǔn)備工作

在本次研究中，所用Bk迭代公式如下，即Bk-1=Bk-δk，在參數(shù)選擇上，明確了常數(shù)γ大于等于0且小于等于1.其算法主要如下：首先進(jìn)行初始點(diǎn)和初始矩陣的選取，即x1∈Rn和B1∈Rn×n，其中B1大于0，明確終止誤差大于0（即ε大于0）且K等于1；若||gk||小于等于ε，則迭代停止；對(duì)Bkdk=-gk這一方程組進(jìn)行求解以獲得搜索方向.接著借助于Wolfe準(zhǔn)則來進(jìn)行αk的計(jì)算.在獲得Xk+1以后，基于上述所選參數(shù)來進(jìn)行參數(shù)（δk,γk）的計(jì)算，接著進(jìn)一步計(jì)算Bk+1，最后令k和k+1相等，再重新轉(zhuǎn)入到上述步驟來進(jìn)行計(jì)算.

1.1.2 全局收斂性

假設(shè)f（x）一致凸和二階連續(xù)可微，為便于后文闡述，在此將該假設(shè)定義為假設(shè)a，其中前者這一假設(shè)條件存在m＞0，基于此可得m||z||2≤zTG(x)z，?x,z∈Rn，此時(shí)上述公式中水平集存在有界閉凸集，即m大于0且小于等于M，用公式表示為m||z||2≤zTG(x)z≤M||z||2，?z∈Rn，x∈L(x0).基于上述內(nèi)容，在此假設(shè)若Bk大于0同時(shí)ykTSk也大于0，利用Wolfe準(zhǔn)則來明確ak，當(dāng)δk大于等于0且小于等于1時(shí)，則Bk+1大于0.如果（f x）符合上述兩個(gè)假設(shè)，則可獲得M.如果B大于0，基于此則可得到xTBx·yTB-1y≥(xTy)2，當(dāng)Bx和y線性有關(guān)時(shí)，則等號(hào)成立.

1.1.3 局部超線性收斂

假設(shè)b：g為零，G·為正定；f（x）中Hessian矩陣于x.位置Lipschitz，則有||G(x)-G*||≤L||x-x*||，L>0，上述假設(shè)中，xe某一個(gè)領(lǐng)域中全部x均成立.基于此引理1，若參數(shù)（δk，γk）中，K大于等于ko.

1.2 雙參數(shù)修正BFGS法一般性結(jié)論

1.2.1 算法條件

參數(shù)選擇2：給定常數(shù)τo大于0且小于等于1，常數(shù)po大于且小于p1.基于此可知δk大于等于τo且小于等于1，γk大于等于po且小于p1.在計(jì)算過程中，首先進(jìn)行初始矩陣以及初始點(diǎn)的選取，令種終止誤差大于0且K為1；若||gk||小于等于ε，則迭代停；并對(duì)Bkdk=-gk這一方程組進(jìn)行求解獲得搜索方向，借助于Wolfe來進(jìn)行αk的計(jì)算，且利用上述公式來進(jìn)行參數(shù)（δk，γk）、xk+1以及Bk+1的計(jì)算，最后令k和k+1相等，則又轉(zhuǎn)入至上述步驟來計(jì)算.

1.2.2 全局收斂性

第一，如果Bk迭代公式如上述所示，其參數(shù)條件滿足上述參數(shù)選擇2，基于此可得到

第二，如果f（x）符合假設(shè)a，則可利用上述算法獲得迭代數(shù)列{xk}，在這種情況下，任意P均存在相關(guān)的常數(shù)，同時(shí)任何自然數(shù)均大于1，那么此時(shí)于[1,k]這一區(qū)間中最少有[pk]個(gè)左右的i符合以下條件，即COSθ1大于等于β1'，q1大于等于β2'且小于等于β3'.

1.2.3 局部超線性收斂性

第一，如果參數(shù)（δk，γk）符合參數(shù)選擇3，即給定數(shù)列δk大于0且小于等于1，γk大于0且小于等于與.則可獲得，其中

第二，如果f（x）符合假設(shè)a與假設(shè)b，則利用上述算法所獲得的迭代序列超線性收斂至xe.對(duì)τ0和P0兩個(gè)常數(shù)，若其均存在常數(shù)k4，該自然數(shù)較大.

針對(duì)上述內(nèi)容，為考察所設(shè)參數(shù)（δk，γk）是否滿足參數(shù)選擇3中的算法，下面筆筆者取參數(shù)（δk，γk）為，在這之中p大于1.基于此來實(shí)施數(shù)值試驗(yàn)，在維數(shù)上分別取4、100、12以及80.從實(shí)驗(yàn)結(jié)果來看，當(dāng)p為50與100的時(shí)候，上述兩種算法所得數(shù)值結(jié)構(gòu)相同，就該結(jié)果來看，當(dāng)p大于等于50的時(shí)候，全部數(shù)值結(jié)果在某種意義上均一樣；當(dāng)p大于等于100的時(shí)候，全部數(shù)值結(jié)果同樣也應(yīng)一樣.對(duì)此，當(dāng)參數(shù)（δk，γk）為的時(shí)候，在此時(shí)P可不用取得太大，若解決維數(shù)小于100的問題，最好令P小于100.

2 雙參數(shù)修正BFGS法對(duì)非線性無約束問題的求解

2.1 準(zhǔn)備工作

在上述內(nèi)容，對(duì)參數(shù)γk已明確了這樣的一個(gè)限制，即γk大于0且小于等于1.基于此，在本次計(jì)算中，所設(shè)δk同樣也應(yīng)該大于0且小于等于1，明確這一要求的主要原因在于這是確保Bk保持正定性的必要條件，而要求參數(shù)γk大于0且小于等于1，則是由于證明過程的需求來明確的，下面筆者就這方面的問題進(jìn)行詳細(xì)地闡述.

2.2 全局收斂性

第一，如果f（x）符合假設(shè)a，αk符合Wolfe準(zhǔn)則，利用迭代格式，則，繼而獲得kl→im∞||sk||=0.其證明過程如下：利用Taylor展式獲得(xk+θsk)skdθ，基于上述內(nèi)容已知αk符合Wolfe準(zhǔn)則，且f（x）符合假設(shè)a，則可得到[f1-f*]，在此基礎(chǔ)上可進(jìn)一步獲得

第二，如果Bk迭代公式為，且參數(shù)選擇為參數(shù)選擇3，則可得到tr(Bk+1)≤tr(Bk)-

第三，如果存在常數(shù)M*與m*，且符合0＜m*＜M*，則可獲得m*小于等于mk*，M*≥Mk*，有上述雙參數(shù)修正BFGS法中全局收斂性引理1可知因此對(duì)常數(shù)m+小于min{m,1}，所存自然數(shù)k5相對(duì)比較大，對(duì)任意K大于等于k5，則可獲得-m0≤ηk=O(||sk||)≤m0.如果uk等于sk，則可得到相等，且x不等于0，?x∈Rn，則因此如果uk等于yk，則可得到以下結(jié)論，即M(1+m0).在證明中，令(1+m0)}且m*=min{m-m0,m(1-m0)}，則可對(duì)該定理進(jìn)行證明.

第四，如果f（x）符合假設(shè)a，且{xk}為上述算法所得到的迭代數(shù)列，則對(duì)于任意p∈(0,1)均存在相應(yīng)的常數(shù)，即β1'.而這也使得任意自然數(shù)即k大于1，且于[1，K]這一區(qū)間最少有[pk]個(gè)i符合

3 結(jié)束語

綜上所述，文章就求解非線性無約束優(yōu)化問題的修正BFGS法進(jìn)行了詳細(xì)地闡述，基于Aiping Liao的研究上，假設(shè)了一個(gè)比較特殊的參數(shù)并提出了該闡述一般性條件，最后再于修正BFGS公式中引入了新擬的牛頓方程，獲得了該參數(shù)的另外一個(gè)條件.望通過本文內(nèi)容的闡述可為今后非線性無約束優(yōu)化問題的求解提供相應(yīng)的理論參考.

〔1〕李文敬,劉之家,藍(lán)貞雄等.無約束最優(yōu)化問題的BFGS松弛異步并行算法[J].計(jì)算機(jī)工程與應(yīng)用,2012,48(17):44-47.

〔2〕李文敬,王汝涼,廖偉志等.無約束最優(yōu)化問題的BFGS并行算法與實(shí)現(xiàn)[J].計(jì)算機(jī)工程,2009,35(15):58-60,63.

〔3〕吳紅梅.非線性不等式約束優(yōu)化問題的一個(gè)修正BFGS信賴域算法 [J].科學(xué)技術(shù)與工程,2010,10(12):2820-2821,2828.

〔4〕馮迎春,鄭列.一般約束非線性規(guī)劃問題的光滑牛頓法[J].湖南理工學(xué)院學(xué)報(bào)（自然科學(xué)版）,2010,23(1):20-23.

〔5〕王開榮,劉奔.建立在修正BFGS公式基礎(chǔ)上的新的共軛梯度法[J].計(jì)算數(shù)學(xué),2012,34(1):81-92.

O224

A

1673-260X（2014）10-0005-02