邢治業(yè)

（山西工程職業(yè)技術學院 基礎部，山西 太原 030009）

引言

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

其中：f（x）是二階連續(xù)可微函數(shù).信賴域算法[1-4]是求解（1.1）式一類重要的數(shù)值計算方法，其基本思想為：在每一步迭代中，求解如下信賴域子問題：

這里dk為所求子問題的解，其中Bk為f（x）在Xk處的Hesse矩陣或其近似；Δk是信賴域半徑。

眾所周知，將非單調技術應用于信賴域算法，算法結果取得良好的計算效果，并且加快了收斂速度。雖然傳統(tǒng)的非單調技術存在很多優(yōu)點，但也存在遺漏丟失最優(yōu)迭代點等缺點，基于此，文章在文獻[10]的基礎上，利用新的非單調技術，并結合自適應技術和wolfe線搜索[5-7]，提出一種新的求解無約束優(yōu)化問題的自適應信賴域算法。

1 算法的提出

在本節(jié)中，采用的新的非單調技術為[8-10]：

現(xiàn)在將新的非單調信賴域算法描述如下：

Step0：給定 x0∈Rn，B0∈Rn×n，Δ0＞0，令 β0＞0，0＜η1＜ω＜1，0＜μ1＜μ＜1，ε＞0，M≥1，令 k=0；

Step1：計算 gk，如果則停止；否則轉 Step2；

Step4：若 r≥μ，令 xk+1=xk+dk否則求步長 ?k，滿足非單調wolfe線搜索：

Step5：信賴域半徑更新：

若：r≥μ,令

若：r<μ1,令

否則令?k+1=?k.

Step6：k=k+1，更新 Bk，若 ρk≥μ，則令 Mk+1=M+1，轉Step1；

2 收斂性分析

為了分析算法的收斂性，我們作如下假設：

（A1）f（x）在水平集S上二次連續(xù)可微，且存在M≥0，使得

（A3）Δf（x）是 lipschitz連續(xù)函數(shù)即存在常數(shù)L＞0，使得：

引理 3.1[2]令dk是算法2.1產生的解，則有

引理3.2若假設（A1）（A3）成立，｛xk］是算法產生的點列，則數(shù)列｛fl（k）｝非增且收斂。

證由m（k+1）≤m（k）+1及｛fl（k）｝的定義知fl（k+1）≤fl（k），所以｛fl（k）｝非增。由假設（A1）（A2）知有下界，而fl（k+1）≤fl（k），所以｛fl（k）｝收斂。

引理 3.3 算法產生的點列滿足fk+1≤Dk+1≤fl（k+1）

證明：由fl（k）的定義可知fl（k+1）≥fk+1。

而fk+1=rk+1fk+1+（1-rk+1）fk+1≤rk+1fk+1+（1-rk+1）fl（k+1）=Dk+1。顯然再由Dk的定義可得：fk+1≤Dk+1≤fl（k+1）

為了證明算法的收斂性，假設存在c＞0,使得dk滿足

引理 3.4 若假設A1、A2、A3成立，則：

證明：易知算法2.1產生的迭代點滿足：

將上式k用l（k）-1來代替得：

兩邊取極限并由引理3.2可得：

由引理3.1可知：

定理 3.5 若上述假設成立，給定初始點x0，初始對稱陣Bk，設｛xk｝是由前述算法產生的迭代序列，則。

?k（其中 θk∈（0，1））

故對充分大的 k，（Dk-fk+1）/predk≥μ≥μ1，由算法 2.1可知對充分大的k，Δk+1≥Δk。結合引理3.1可知，與3.2式矛盾，假設不成立，即，定理得證。