求解信賴域子問題的Adams四階預報校正格式算法

范曉宇，李丹琳，王希云

(1.太原科技大學應用科學學院，太原 030024；2.合肥工業大學數學學院，合肥 230601)

求解二次模型信賴域子問題[1-2]是信賴域算法中極其重要的步驟，也就是求解如下形式：

(1)

當Δ變化時，(1)的解δ在空間構成一條曲線，稱為最優曲線[3]。

傳統的精確求解方法可以求解二次模型子問題，但過程較為繁復。利用該方法，可得到最優曲線的參數方程。在參數方程的基礎上，可建立最優曲線的微分方程模型。模型如下所示[4]：

(2)

此時求解信賴域子問題就變成了求解微分方程問題。據此思想，文獻[4]-[9]在求解微分方程模型時，聯合一些常見、簡單的單步法公式構造折線，進而替代最優曲線。分別提出了求解二次模型子問題的顯式歐拉算法、隱式歐拉算法、平均歐拉算法以及R-K類算法。為了充分利用已有的信息，文獻[10]聯合多步法公式構造折線，進而替代最優曲線。提出了求解二次模型子問題的Adams多步法算法。求解子問題時，文獻[10]中的Adams四階顯式算法計算簡單，Adams四階隱式算法精度高，為發揮各自優點，進一步提高精度，本文聯合求解微分方程時常用的Adams四階預報—校正格式[11]：

(3)

fk=-(B+μkI)-1δk，(k=n，n-1，n-2，n-3)

提出了Adams四階預報—校正格式算法，求解信賴域子問題。文章分析了算法對應折線的性質，在理論上給予證明，在實驗上給予驗證。通過與文獻[10]提出的Adams四階顯式算法、Adams四階隱式算法的數值實驗比較，驗證了該算法的數值解可達到更高的精度，是可行的且是一種數值效果較好的新算法。

1 Adams四階預報—校正格式折線的構造

第一步：從初始點P0(μ0，δ0)開始，其中μ0=0，δ0=-B-1g，選取步長h，用公式：

(4)

第二步：由常用的經典Runge-Kutta公式：

計算δ1.記:

則記為:

(5)

從而得到下一個節點P1(μ1，δ1)，其中μ1=μ0+h.同理可得到節點P2(μ2，δ2)，P3(μ3，δ3).

δ(τ)=

(6)

則步長h需滿足下式：

h=

(7)

2 Adams四階預報—校正格式折線的性質

引理1設B對稱正定，則當0≤n≤2時，不等式①成立。

則當3≤n≤N-1時，不等式②成立。

由引理1，可知步長h為正。

定理1設B對稱正定，且0≤n≤2時有(8)式成立；

gT(fn1+2fn2+2fn3+fn4)+

(8)

n≥3時有(9)式成立。

(9)

則δ(τ)滿足：

(1)‖δ(τ)‖2關于τ為單調減函數。

(2)q[δ(τ)]關于τ為單調增函數。

證明：(1)當τ∈[μ0，μ1]，即τ∈[0，h0]時，

則：

由(7)式與引理1可知，

同理τ∈(μ1，μ2]，τ∈(μ2，μ3]時，

因而，‖δ(τ)‖2在區間[μ0，μ1]，(μ1，μ2]，(μ2，μ3]上遞減。

當?τ∈(μi，μi+1]即(τ-μi)∈(0，hi]，3≤i≤N-1

則:

由(7)式與引理1可知，

(2)當τ∈[μ0，μ1]，即τ∈[0，h0]時，

B(f01+2f02+2f03+f04)

2f03+f04)+δ0TB(f01+2f02+2f03+f04))

由已知條件(8)，可得(q[δ(τ)])′≥0，τ∈[μ0，μ1].同理(q[δ(τ)])′≥0，τ∈(μ1，μ2]，(μ2，μ3].因而，q[δ(τ)]在區間[μ0，μ1]，(μ1，μ2]，(μ2，μ3]為遞增，得證。

當?τ∈(μi，μi+1]即(τ-μi)∈(0，hi]，3≤i≤N-1時，

q[δ(τ)]=

由已知條件(9)得(q[δ(τ)])′≥0，τ∈(μi，μi+1].

因而，q[δ(τ)]在區間(μi，μi+1]，i=3，…，N-1為遞增，得證。證畢。

3 Adams四階預報—校正格式算法

步0.給定g，B，Δ.令n=0.

步1.令δ0=-B-1g.

步2.若Δ≥‖δ0‖2，則取δ*=δ0，此時計算終止。否則，令n=n+1，轉步3.

(R-K法計算起步值)對n=1，2，3，做步3到步4.

步3.計算δn。由公式(4)和經典RK公式計算

步4.若Δ≥‖δn‖2，則:

其中：

計算終止。否則令n=n+1轉步3.(Adams四階預報-校正法計算δn) 對n=4，5…做步5到步6.

步6.若Δ≥‖δn‖2，

計算終止。否則令n=n+1轉步5.

4 Adams四階預報—校正格式算法的適定性

定理2在定理1成立的情況下，B對稱正定，利用Adams四階預報—校正格式折線δ(τ)求解信賴域子問題的極小點，解在信賴域邊界上，且η滿足：

其中:

證明：分情況進行討論：

①當n=1，2，3時，η滿足方程：

其中：

②當n=4，5，…時，η滿足方程：

其中：

5 數值實驗

對于子問題(1)的求解，步長固定為h=0.1，信賴域半徑Δ依次改變，依據本文提出的新算法，對附錄中選取的兩個簡單的測試函數，分別進行數值實驗(參考文獻[12]).算法獲得最優解的時間復雜度O(n2).表1和表2為該算法的數值結果，以及與文獻[10]提出的Adams四階顯式算法、Adams四階隱式算法數值結果的比較。

表1 測試函數1的數值結果

表2 測試函數2的數值結果

比照表1和表2的數值結果，有如下結論：當信賴域半徑Δ≥‖B-1g‖2時，三種算法求得的數值結果是完全相同的(此時為牛頓算法)。在信賴域半徑Δ<‖B-1g‖2時，對Funtion1進行實驗，Adams四階預報-校正格式算法的效果一直比Adams四階顯式算法的效果要好。當信賴域半徑Δ=9和9.2時，Adams四階隱式算法的效果略微好于Adams四階預報-校正格式算法的效果；而信賴域半徑取其他值時，通過對比數值結果，發現Adams四階預報-校正格式算法比Adams四階隱式算法更好。對于Funtion2，Adams四階預報-校正格式算法的數值結果均好于Adams四階顯式算法、Adams四階隱式算法。因而本文提出的Adams四階預報-校正格式算法是一種有效且可行，數值效果較好的新算法。

其中，對于測試函數Funtion1

‖B-1g‖2=9.42，

對于測試函數Funtion2‖B-1g‖2=10.46

附錄：測試函數

Function1: Powell’s 4-variable function在初始點(2,5,3,6)T處的信賴域子問題。

s.t.‖δ‖2≤Δ

Function2: Wood-Colville’s function在初始點

(3,8,2,4)T處的信賴域子問題.

s.t.‖δ‖2≤Δ