趙 丹

(連云港師范高等專科學(xué)校 數(shù)學(xué)與應(yīng)用數(shù)學(xué)系,江蘇 連云港 222000)

1 引言

考慮無約束優(yōu)化問題minf(x)，其中f∶Rn→R是二次連續(xù)可微函數(shù).信賴域方法是在每次迭代求信賴域子問題的解δk,

(1)

其中g(shù)k=▽f(xk),Bk∈Rn×n是近似于▽2f(x)的對稱矩陣，△k是信賴域半徑.

本文首先利用本奇-伯利特分解和矩陣的特征值來構(gòu)造一個對稱正定矩陣Gk，提出修正混合折線路徑法解決信賴域子問題，同時利用Gk來確定信賴域子問題的半徑，并將非單調(diào)技術(shù)引入其中，提出了一種新的自適應(yīng)信賴域算法.

2 修正混合折線路徑的構(gòu)造

首先對Bk進行本奇-伯利特分解，把實對稱矩陣Bk分解為

RBkRT=LDkLT

(2)

其中R為置換陣，L為單位下三角矩陣，Dk為一對角塊，對角塊的階數(shù)為1或2.為方便起見，不妨設(shè)置換陣R=I，即

Bk=LDkLT

(3)

基于Dk與Bk具有相同的慣性和文獻[1]，本文利用Dk的特征值來構(gòu)造對稱正定陣Gk.現(xiàn)不妨記Dk的特征值為λ1,λ2,…,λn，p1,p2,…,pn為Dk對應(yīng)于特征值λ1,λ2,…,λn的特征向量，令Pk=(p1,p2,…,pn)T.下面分兩種情況：

(4)

由文獻[1]可知，Gk是對稱正定陣，且-Gkgk是擬牛頓方向.

修正混合折線路徑[2]的構(gòu)造如下：

3 非單調(diào)自適應(yīng)信賴域算法

我們構(gòu)造的信賴域子問題形式如下：

(5)

其中0

算法1 新的非單調(diào)自適應(yīng)信賴域算法：

步1 給定x0∈Rn,B0∈Rn×n對稱，ε≥0,0

步2 如果‖gk‖≤ε，則停；否則構(gòu)造正定矩陣Gk，置信賴域半徑△k=cp‖gk‖‖Gk‖.

步3 利用修正混合折線法解信賴域子問題(5)得到試探步δk.

步5 如果rk>η，令xk+1=xk+δk，p=0，修正Bk+1,k∶=k+1;m(k)=min{m(k)+1,M}，轉(zhuǎn)步2；否則，令p=p+1，△k=cp‖gk‖‖Gk‖，轉(zhuǎn)步2.

說明：①“步2-步5-步2”稱為內(nèi)循環(huán).②矩陣Bk可以由DFP和BFGS等擬牛頓迭代得到.③本文中‖.‖為Eucliden范數(shù).

4 算法收斂性分析

假設(shè)H：(1)對任意的x0∈Rn,水平集L(x0)={x|f(x)≤f(x0)}有界，且函數(shù)f(x)在水平集L(x0)上連續(xù)可微；(2)矩陣序列{Bk}一致有界,即存在N>0,使得對?k,有‖Bk‖≤N.

qk(δk)≤-cpMk‖gk‖2+

引理2 如果假設(shè)H成立，則算法1是適定的，即算法1不會在內(nèi)循環(huán)內(nèi)無限次循環(huán).

證明 假設(shè)算法1在迭代點xk處于步2至步5之間無限次循環(huán)，記k(i)是當(dāng)前迭代點xk處的循環(huán)指標(biāo)，則有rk(i)≤η,i=1,2,…即

(6)

由△k(i)=ci‖gk‖Mk→0,(i→∞)，故|rk(i)-1|→0,(i→∞)，這與(6)矛盾.

引理3[3]如果假設(shè)H成立，則(fl(k))單調(diào)非增且收斂.

定理1 如果假設(shè)H成立，當(dāng)ε=0時算法1有限終止或者產(chǎn)生一個無限序列{xk}滿足

(7)

證明 不妨設(shè)算法1不能有限終止，則當(dāng)(7)式不成立時，存在一個正常數(shù)ε0，無窮序列{ki}，有‖gki‖≥ε0定義T={k|‖gk‖≥ε0}.

再由假設(shè)H中(2)及引理1，fl(k)-fk≥0可知

否則不會在內(nèi)循環(huán)內(nèi)進一步修正得到△k，即

(8)

‖gk‖/‖Bk‖}，由假設(shè)H中(2)，引理3可知，

△k→+0(k→+∞)

(9)

當(dāng)k充分大時，有

(10)

結(jié)合(9)及(10)知，

當(dāng)k充分大時，這與(8)矛盾，故假設(shè)錯誤，定理1成立.

5 數(shù)值實驗

本文選取了文獻[4]中關(guān)于無約束優(yōu)化的13個中小規(guī)模問題，分別對算法1、傳統(tǒng)信賴域方法和文獻[3]中的自適應(yīng)信賴域算法進行了數(shù)值實驗，終止規(guī)則 ‖gk‖<10-5(1+‖g0‖)；若算法在500次迭代內(nèi)仍然沒有找到解，則算法也終止.

實驗中采用BFGS修正Bk，對于文獻[3]的自適應(yīng)信賴域算法，與本文的算法1，我們盡量選取同樣的參數(shù)，其中η=0.1,c=0.5,M=10.

詳細的數(shù)值結(jié)果見表1.在表1中，No.表示測試函數(shù)的編號，n表示測試函數(shù)的維數(shù)，m表示子函數(shù)的個數(shù)，a表示500步內(nèi)算法不收斂，k表示迭代數(shù)，f表示最優(yōu)函數(shù)值.A代表傳統(tǒng)信賴域算法，B代表文獻[3]提出的算法，C代表本文所提出的算法.

從表1可知，本文提出的非單調(diào)自適應(yīng)信賴域算法是有效的.特別是對函數(shù)1,2,13非單調(diào)信賴域算法表現(xiàn)較好.

表1 數(shù)值結(jié)果 (numerical results)

參考文獻：

[1]王建宏,錢峰.基于最速下降曲線的特征值法[J].南通大學(xué)學(xué)報:自然科學(xué)版,2007,6(1):20-22.

[2]趙丹.解信賴域子問題的混合折線法[J].徐州師范大學(xué)學(xué)報:自然科學(xué)版,2009,27(3):38-41.