一種基于R-函數(shù)的自適應(yīng)線搜索信賴域算法

李德華，芮紹平

（淮北師范大學(xué) 數(shù)學(xué)科學(xué)學(xué)院，安徽 淮北235000）

0 引言

信賴域方法最早由Powell［1］提出，具有較為理想的全局收斂性和穩(wěn)定性.傳統(tǒng)信賴域算法通常利用二次模型連續(xù)逼近目標(biāo)函數(shù)，以期獲得理想最優(yōu)值.算法構(gòu)建信賴域子問(wèn)題

確定迭代步dk.其中：gk=?f(xk)；Bk為Hesse矩陣?2f(xk)的近似；Δk為信賴域半徑；‖‖·是Euclidean范數(shù).

信賴域方法就是通過(guò)這一比值ρk來(lái)衡量二次模型與目標(biāo)函數(shù)的擬合程度.若ρk趨近于1，則表明目標(biāo)函數(shù)的實(shí)際降幅與估計(jì)降幅接近，當(dāng)前迭代效果好，需要考慮擴(kuò)大下次迭代的信賴域半徑；若ρk的值趨近于0或者小于0，表明迭代效果較差，試探步不可接受，需要縮小下次迭代的信賴域半徑.

傳統(tǒng)的信賴域方法根據(jù)比值ρk的大小放縮信任區(qū)域半徑Δk，一般是原信任區(qū)域半徑Δk常數(shù)倍增減，很大程度上依賴以往的經(jīng)驗(yàn)來(lái)確定.為了克服這種缺陷，學(xué)者們引入自適應(yīng)技術(shù).Sartenaer［2］構(gòu)造一類自動(dòng)確定初始信賴域半徑的ITTR算法.Zhang［3］等借鑒這一思想，把這種自適應(yīng)策略應(yīng)用到整個(gè)信賴域半徑更新規(guī)則上.Hei［4］提出當(dāng)前迭代的信賴域半徑是關(guān)于比值ρk的R-函數(shù)與搜索步長(zhǎng)‖ ‖dk-1的乘積.文獻(xiàn)［3］給出信賴域半徑的更新與Bk的關(guān)系.為了避免在每次迭代過(guò)程中計(jì)算矩陣Bk的逆，李改弟［5］提出新的信賴域半徑更新規(guī)則，即，這里yk-1=gk-gk-1.在此基礎(chǔ)上，文獻(xiàn)［6-12］提出一些改進(jìn)的自適應(yīng)信賴域算法.

本文在基于李改弟［5］和Hei［4］的信賴域半徑自動(dòng)更新策略的基礎(chǔ)上，把兩者的更新策略結(jié)合起來(lái)，基于R-函數(shù)得到一個(gè)改進(jìn)的信賴域半徑自動(dòng)更新策略.具體行文如下，在第2部分給出新算法，在第3部分證明新算法的收斂性，最后通過(guò)數(shù)據(jù)實(shí)驗(yàn)驗(yàn)證算法的穩(wěn)定性與有效性.

1 算法

本節(jié)中，借助于R-函數(shù)，給出一個(gè)新的信賴域半徑自動(dòng)更新策略，并設(shè)計(jì)新算法.R-函數(shù)定義如下［4］：

定義1Rλ(t)定義在(-∞,+∞)上，參數(shù)λ∈(0,1)，C是一個(gè)常數(shù)集，R-函數(shù)Rλ(t)滿足以下條件：

①Rλ(t)在(-∞,+∞)上是非減的；

③Rλ(t)≤1-r1（?t∈λ，r1∈( 0,1-ζ)且r1∈C）；

④Rλ(λ)≤1+r2（r2∈( 0,+∞)且r2∈C）；

顯然上述R-函數(shù)Rλ(t)（λ∈(0,1)）滿足：

（i）0＜ζ≤Rλ(t)≤1-r1＜1,?t∈(-∞,λ)；

（ii）1＜1+r2≤Rλ(t)≤M＜+∞,?t∈[λ,+∞).

基于李［5］和Hei［4］的信賴域半徑自動(dòng)更新策略，本文提出一個(gè)改進(jìn)的信賴域半徑更新規(guī)則如下：

其中Rλ(ρk)是一個(gè)關(guān)于比值ρk的R-函數(shù).新策略把Rλ(ρk)作為調(diào)節(jié)信賴域半徑的依據(jù)，使得信賴域半徑的變化取決于自身，基于此更新策略，設(shè)計(jì)算法1.

算法1（自適應(yīng)線搜索信賴域算法）

步聚0取初始點(diǎn)x0∈Rn，對(duì)稱陣B0∈Rn×Rn，ε＞0，0＜u＜1，Δ0=‖g0‖，0＜ζ＜1，0＜r1＜1-ζ，r2＞0，M＞1+r2，k:=0.

步驟1如果‖gk‖≤ε，則停止.否則轉(zhuǎn)步聚2.

步驟2求解子問(wèn)題（1）得到dk.

步驟3計(jì)算ρk的值.若ρk≥u，則令xk+1=xk+dk；否則求αk，使其滿足Armijo準(zhǔn)則，令xk+1=xk+αkdk，轉(zhuǎn)步聚4.

步驟5更新矩陣Bk到Bk+1，令k:=k+1，轉(zhuǎn)步聚1.

2 算法的收斂性分析

為證明算法收斂性，本文所需假設(shè)條件A如下：

（i）水平集L(x0)={x∈Rn|f(x)≤f(x0)}有界.

（ii）序列{Bk}一致有界，即?M1＞0使得?k有‖Bk‖≤M1.

引理1若當(dāng)前迭代點(diǎn)xk是由算法1生成的，那么其中Mk=‖Bk‖

證明根據(jù)算法1步驟4所定義的信賴域半徑，當(dāng)前Δk滿足關(guān)系式因此，根據(jù)是式（1）的一個(gè)可行解，則

引理得證.

引理2［13］若試探步dk是子問(wèn)題（1）的解，則有

定理1若假設(shè)A成立，算法1有限終止或迭代點(diǎn)列{xk}滿足

證明由假設(shè)（i）可知，序列有下界.用反證法，假設(shè)定理1不成立.故存在εˉ＞0和一個(gè)無(wú)限子列滿足.定義集合

根據(jù)引理1和算法1步驟3有

根據(jù)假設(shè)條件A可知，對(duì)任意的ki，一定存在M1＞0，使得Mki≤M1，且{f(xk)}有下界.故由式（5）可得到

也就是說(shuō)，當(dāng)ki(∈G)→+∞時(shí)，有為了不失一般性，假設(shè)對(duì)所有的ki∈G，都有著其中pki是前一次迭代到當(dāng)前可接受的迭代間信賴域子問(wèn)題計(jì)算的次數(shù)，所以對(duì)ζ都滿足依據(jù)ζ的定義對(duì)應(yīng)于下面的信賴域子問(wèn)題不能接受

另一方面，根據(jù)引理2有

利用G的定義、假設(shè)A（ii）以及{f(xk)}單調(diào)遞減有下界，可以得到Δki→0（ki∈G）.又

因此，對(duì)于充分大的ki∈G，

令ki→∞，有，這與式（7）矛盾.故假設(shè)錯(cuò)誤，定理成立.

3 數(shù)據(jù)結(jié)果

本節(jié)給出算法1的數(shù)值實(shí)驗(yàn)，并和傳統(tǒng)的牛頓型信賴域算法進(jìn)行比較.為行文方便，把新算法和傳統(tǒng)的信賴域算法分別記為ALG1和NTTR.ALG1中所取的R-函數(shù)為

其中參數(shù)取值為：γ1=γ2=0.01，ζ=0.1，u=0.25，M=5.兩種算法都取相同初始信賴域半徑Δ0=1，精度為ε=10-6.兩種算法中測(cè)試函數(shù)均來(lái)自于文獻(xiàn)［14］.

算法在Matlab9.0中編程實(shí)現(xiàn)，實(shí)驗(yàn)數(shù)據(jù)如下表：

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

從數(shù)值結(jié)果可以看出，對(duì)于相同的初始點(diǎn)，算法1所需迭代次數(shù)比傳統(tǒng)算法小，目標(biāo)函數(shù)值下降的快，這表明算法1穩(wěn)定有效.