一種基于L-函數(shù)的非單調自適應信賴域算法

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

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

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

其中：f:Rn→R為連續(xù)可微函數(shù)。信賴域方法是求解無約束優(yōu)化問題的一類重要的數(shù)值方法，由Powell[2]提出，該方法具有良好的適應性與穩(wěn)定性。對于無約束優(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)分別代表目標函數(shù)的實際下降量和預測下降量[4]。

另外，近年來非單調技術得到廣泛應用[9-10]，其中Ahookhosh[11]提出的非單調方法中，步長αk滿足條件：

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

非單調項fl(k)定義為：

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

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

1 算法

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

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

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

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

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

基于此更新策略，設計算法1。

算法1 非單調自適應線搜索信賴域算法(NTTR)

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

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

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

步4 若rk≥μ，令xk+1=xk+dk,否則求步長αk，滿足非單調wolfe線搜索：

令xk+1=xk+αkdk；

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

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

步6 更新Bk，令k=k+1，轉步1。

2 收斂性分析

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

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)生的點列{xk} 滿足：

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

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

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

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

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

3 數(shù)值實驗

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

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

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

表1 算例1 數(shù)值實驗結果

表2 算例2 數(shù)值實驗結果

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

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

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

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

4 結語

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