張 杰，朱子旋，芮紹平，曾 柔

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

考慮無約束最優(yōu)化問題[1]

其中：f:Rn→R為連續(xù)可微函數(shù)。信賴域方法是求解無約束優(yōu)化問題的一類重要的數(shù)值方法，由Powell[2]提出，該方法具有良好的適應(yīng)性與穩(wěn)定性。對(duì)于無約束優(yōu)化問題，傳統(tǒng)的信賴域方法利用二次函數(shù)逼近函數(shù)f，得到信賴域算法的子問題[3]：

其中：gk=?f(xk)；Bk為Hesse 矩陣?2f(xk)的第k次近似；Δk為信賴域半徑；‖ ? ‖是Euclidean范數(shù)。

引入Aredk=f(xk)-f(xk+dk)和Predk=φk(0)-φk(dk)分別代表目標(biāo)函數(shù)的實(shí)際下降量和預(yù)測(cè)下降量[4]。

另外，近年來非單調(diào)技術(shù)得到廣泛應(yīng)用[9-10]，其中Ahookhosh[11]提出的非單調(diào)方法中，步長(zhǎng)αk滿足條件：

這里δ∈(0,1),γk∈[γmin,γmax],γmax∈[γmin,1)γmin∈(0,1)。

非單調(diào)項(xiàng)fl(k)定義為：

其中：m(0)=0,m(k)=max{m(k-1)+1,2M}，對(duì)于k≥1，M為給定的非負(fù)整數(shù)[12]。在此技術(shù)中，當(dāng)前非單調(diào)項(xiàng)是前一非單調(diào)項(xiàng)和當(dāng)前目標(biāo)函數(shù)的凸組合。

利用L-函數(shù)，設(shè)計(jì)信賴域半徑迭代依賴比值rk的連續(xù)變化而變化的自適應(yīng)算法。同時(shí)采用非單調(diào)wolfe 線搜索技術(shù)，得到迭代步長(zhǎng)。算法的全局收斂性得到證明，數(shù)值實(shí)驗(yàn)表明算法穩(wěn)定可靠。

1 算法

借助L-函數(shù)，給出更新信賴域半徑策略，設(shè)計(jì)新算法。L-函數(shù)定義如下：

定義1[8]函數(shù)L(t)稱為L(zhǎng)-函數(shù)，如果它滿足下列條件：

(1)L(t)在(-∞,η1)中非減，在(2 -η1,+∞)中非增，當(dāng)t∈[η1,2 -η1]，L(t)=β1，

這里的常數(shù)滿足:0 2 -η1。由文獻(xiàn)[8]可知L-函數(shù)有界。

采用的信賴域半徑更新規(guī)則為Δk+1=L(rk)Δk，其中L(rk)是一個(gè)關(guān)于比值rk的L-函數(shù)，結(jié)合非單調(diào)技術(shù)將比率rk更改為：

基于此更新策略，設(shè)計(jì)算法1。

算法1 非單調(diào)自適應(yīng)線搜索信賴域算法(NTTR)

步0 給定x0∈Rn,B0∈Rn×n和Δ0>0，γ∈(0,1)，0 0，M≥1，令k=0；

步1 計(jì)算gk=?f(xk),如果‖gk‖≤ε，則算法終止；否則轉(zhuǎn)步2；

步2 求解信賴域子問題 (2) 的近似解dk，‖ dk‖≤ Δk；

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

令xk+1=xk+αkdk；

根據(jù)林雪川的說法，黎永蘭倒下之后，左邊耳朵就流血出來了，嘴里也吐白沫，他自己也嚇倒了。林雪川將倒地的黎永蘭通過出租車送到了廣安市人民醫(yī)院。

步5 更新信賴域半徑：Δk+1=L(rk)Δk；

步6 更新Bk，令k=k+1，轉(zhuǎn)步1。

2 收斂性分析

為了證明算法的收斂性，以下假設(shè)條件成立：

A1：水平集

L(x0)={x∈Rn|f(x) ≤f(x0)}。

有界且f(x)在水平集上連續(xù)可微有下界；

A2：g(x)=?f(x)在水平集上是Lipschitz連續(xù)，即存在常數(shù)L>0，使?x,y∈Rn,‖ ?f(x) -?f(y) ‖≤L‖x-y‖；

A3:序列{Bk} 一致有界，即?M1>0 使得?k∈N，有‖Bk‖

引理1[13]子問題(2)的解中dk滿足φk(0) -其中σ∈(0,1]。

引理2[14]算法1產(chǎn)生的點(diǎn)列{xk} 滿足：

引理3[11]算法1 產(chǎn)生的點(diǎn)列{xk} 滿足：fk+1≤Dk+1≤fl(k+1)。

證明 由假設(shè)條件A1 可知，點(diǎn)列{f(xk)}有下界。假設(shè)定理1 不成立，即存在一個(gè)常數(shù)ε>0，使得下證

由算法1，產(chǎn)生的迭代點(diǎn)列滿足：

又由m(k+1) ≤m(k)+1 及{fl(k)} 定義知：fl(k+1)≤fl(k)，即{fl(k)} 單調(diào)遞減，再由假設(shè)條件A2 和A3 知有其有下界，所以{fl(k)} 收斂。因此對(duì)(6)式兩邊取極限可得

又據(jù)引理2，引理3有：

3 數(shù)值實(shí)驗(yàn)

給出基于L-函數(shù)的非單調(diào)自適應(yīng)信賴域算法（NTTR）的數(shù)值結(jié)果，并且和傳統(tǒng)的信賴域算法(TTR) 進(jìn)行比較。算法運(yùn)行環(huán)境是MATLAB(R2022a)。參數(shù)選取如下：

Δ0=‖g(x0) ‖,B0=I。

計(jì)算結(jié)果見表1 和表2，其中dim 代表測(cè)試的維數(shù)，num 代表算法迭代次數(shù)，val 代表最優(yōu)值。算例1和算例2來自文獻(xiàn)[15]。

表1 算例1 數(shù)值實(shí)驗(yàn)結(jié)果

表2 算例2 數(shù)值實(shí)驗(yàn)結(jié)果

算例1 測(cè)試函數(shù)為：

算例2 測(cè)試函數(shù)為：

初始點(diǎn)x0=(3,-1,0,3,...3,-1,0,3)T。

從表1 可以看出，對(duì)于不同的初始點(diǎn)選擇，由于非單調(diào)技術(shù)的引入，降低了算法的計(jì)算量，迭代次數(shù)小于傳統(tǒng)的信賴域算法。從表2可以看出，隨著測(cè)試問題從低維到高維，新的非單調(diào)自適應(yīng)信賴域算法能快速有效地得到最優(yōu)解，并且具有良好的穩(wěn)定性，說明算法NTTR適合求解較大規(guī)模問題。

4 結(jié)語(yǔ)

信賴域方法是求解無約束優(yōu)化問題的經(jīng)典方法之一，對(duì)該方法改進(jìn)具有重要的實(shí)際意義和應(yīng)用價(jià)值?；贚-函數(shù)的非單調(diào)自適應(yīng)信賴域算法很好地解決傳統(tǒng)信賴域方法中信賴域半徑更新問題，實(shí)現(xiàn)了自動(dòng)更新迭代，非單調(diào)技術(shù)的使用也大大減少了算法的計(jì)算量，調(diào)高了算法效率，因此這種方法豐富和推廣了現(xiàn)有結(jié)果。