一種無(wú)約束優(yōu)化的新非單調(diào)自適應(yīng)信賴域算法

邢治業(yè)

（山西工程職業(yè)技術(shù)學(xué)院 基礎(chǔ)部，山西 太原 030009）

引言

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

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

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

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

1 算法的提出

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

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

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

Step1：計(jì)算 gk，如果則停止；否則轉(zhuǎn) Step2；

Step4：若 r≥μ，令 xk+1=xk+dk否則求步長(zhǎng) ?k，滿足非單調(diào)wolfe線搜索：

Step5：信賴域半徑更新：

若：r≥μ,令

若：r<μ1,令

否則令?k+1=?k.

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

2 收斂性分析

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

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

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

引理 3.1[2]令dk是算法2.1產(chǎn)生的解，則有

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

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

引理 3.3 算法產(chǎn)生的點(diǎn)列滿足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）

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

引理 3.4 若假設(shè)A1、A2、A3成立，則：

證明：易知算法2.1產(chǎn)生的迭代點(diǎn)滿足：

將上式k用l（k）-1來(lái)代替得：

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

由引理3.1可知：

定理 3.5 若上述假設(shè)成立，給定初始點(diǎn)x0，初始對(duì)稱陣Bk，設(shè)｛xk｝是由前述算法產(chǎn)生的迭代序列，則。

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

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