李德華,芮紹平
(淮北師范大學(xué) 數(shù)學(xué)科學(xué)學(xué)院,安徽 淮北235000)
信賴域方法最早由Powell[1]提出,具有較為理想的全局收斂性和穩(wěn)定性.傳統(tǒng)信賴域算法通常利用二次模型連續(xù)逼近目標(biāo)函數(shù),以期獲得理想最優(yōu)值.算法構(gòu)建信賴域子問題
確定迭代步dk.其中:gk=?f(xk);Bk為Hesse矩陣?2f(xk)的近似;Δk為信賴域半徑;‖‖·是Euclidean范數(shù).
信賴域方法就是通過這一比值ρk來衡量二次模型與目標(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)來確定.為了克服這種缺陷,學(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ù)與搜索步長‖ ‖dk-1的乘積.文獻(xiàn)[3]給出信賴域半徑的更新與Bk的關(guān)系.為了避免在每次迭代過程中計(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é)合起來,基于R-函數(shù)得到一個(gè)改進(jìn)的信賴域半徑自動(dòng)更新策略.具體行文如下,在第2部分給出新算法,在第3部分證明新算法的收斂性,最后通過數(shù)據(jù)實(shí)驗(yàn)驗(yàn)證算法的穩(wěn)定性與有效性.
本節(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,對稱陣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求解子問題(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.
為證明算法收斂性,本文所需假設(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是子問題(1)的解,則有
定理1若假設(shè)A成立,算法1有限終止或迭代點(diǎn)列{xk}滿足
證明由假設(shè)(i)可知,序列有下界.用反證法,假設(shè)定理1不成立.故存在εˉ>0和一個(gè)無限子列滿足.定義集合
根據(jù)引理1和算法1步驟3有
根據(jù)假設(shè)條件A可知,對任意的ki,一定存在M1>0,使得Mki≤M1,且{f(xk)}有下界.故由式(5)可得到
也就是說,當(dāng)ki(∈G)→+∞時(shí),有為了不失一般性,假設(shè)對所有的ki∈G,都有著其中pki是前一次迭代到當(dāng)前可接受的迭代間信賴域子問題計(jì)算的次數(shù),所以對ζ都滿足依據(jù)ζ的定義對應(yīng)于下面的信賴域子問題不能接受
另一方面,根據(jù)引理2有
利用G的定義、假設(shè)A(ii)以及{f(xk)}單調(diào)遞減有下界,可以得到Δki→0(ki∈G).又
因此,對于充分大的ki∈G,
令ki→∞,有,這與式(7)矛盾.故假設(shè)錯(cuò)誤,定理成立.
本節(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.兩種算法中測試函數(shù)均來自于文獻(xiàn)[14].
算法在Matlab9.0中編程實(shí)現(xiàn),實(shí)驗(yàn)數(shù)據(jù)如下表:
表1 數(shù)值結(jié)果
從數(shù)值結(jié)果可以看出,對于相同的初始點(diǎn),算法1所需迭代次數(shù)比傳統(tǒng)算法小,目標(biāo)函數(shù)值下降的快,這表明算法1穩(wěn)定有效.