一類新的錐模型信賴域自適應算法

趙 絢,朱 帥

(1.運城師范高等專科學校 數學與計算機系,山西 運城 044000;2.山西大同大學 數學與統計學院,山西 大同 037009)

考慮無約束優化問題

(1)

其中，f:Rn→R二次連續可微.

求解此問題的大部分新算法是采用二次模型逼近f(x),但是對于一些非二次形態較強、曲率變化劇烈的函數,效果不是很理想.為此,Dnvidon[1]于1980年提出了錐模型,錐模型是二次模型的推廣.Di和Sun[2]給出了錐模型信賴域子問題的最優性條件.文獻[3]和[4]提出了基于錐模型的擬牛頓信賴域算法.

為了克服原目標函數在1-bTd>0的附近可能無界的情況,Ni[5]取消了對水平向量b的限制,對錐模型信賴域的子問題考慮了更為一般的情況,提出了一種新錐模型信賴域子問題

(2)

文獻[6]中定義了關于ρk的R-函數以變化的速率來調節信賴域半徑的大小,充分利用了ρk的信息,使信賴域半徑的調節取決于問題本身,更具客觀性.本文將R-函數以變化的速率來調節信賴域半徑的大小的自適應和非單調技術[7-8]相結合,提出了一種基于錐模型的非單調自適應信賴域算法.

1 算法

定義1[6]Rμ(t)定義在(-∞,+∞)上,參數μ∈(0,1),Rμ(t)是一個R-函數,當且僅當它滿足

(i)Rμ(t)在(-∞,+∞)上非減;

(iii)Rμ(t)≤1-γ1,(?t<μ,γ1∈(0,1-ω)是一個常數);

(iv)Rμ(μ)=1+γ2,(γ2∈(0,+∞)是一個常數);

對于自動調節信賴域半徑的R-函數,本文定義為[6]

算法1

step0 給定x0∈Rn,對稱陣

step2 用折線法[9]求解子問題(2)得近似解dk.

step4 若ρk≥μ,令xk+1=xk+dk;否則取λk為

(3)

令xk+1=xk+λkdk.

step6 令k∶=k+1,更新bk[3]和Bk[3]

若ρk≥μ,令Mk+1=M;若μ<ρk<1,Mk+1=M+1.轉step1.

2 算法的收斂性

2.1 本文假設

H1 水平集L(x0)={x|f(x)≤f(x0),x∈Rn}有界,且{xk}∈L(x0);

H2 數列{fk}有下界；

H3 ?f(x)在Rn上一致連續；

2.2 全局收斂性

引理1[8]若假設H2成立，則數列{fl(k)}非增且收斂.

(4)

(5)

取ε=τδ(1-μ)/2,其中0<μ<1,τ>0,則

(6)

令

m=min{Δ1,Z1,ε0δ,ωδ,ωδZ1,τδω(1-μ)/2},

下面分兩種情況證明(4)式.

(7)

(8)

(9)

f(xk+dk)-fl(k)>-μpredk.

(10)

由(6)式知

(11)

(12)

從而有……