一種求解信賴域子問題的基爾方法

武姝廷，王希云

(太原科技大學 應用科學學院，太原030024)

求解如下形式的二次模型信賴域子問題[1]：

(1)

隨著Δ改變，(1)的解δ*在空間形成一條曲線——最優(yōu)曲線[2]。對于(1)的求解，目前提出的方法主要有精確求解法、折線法、截斷共軛梯度法等。其中折線法是求解信賴域子問題最常用和最有效的方法，常用的折線法主要有單折線法[3]、雙折線法[4]、切線單折線法[5]以及基于最優(yōu)曲線微分方程模型的歐拉算法[6-8]。本文根據最優(yōu)曲線的微分方程模型：

(2)

在Hessian矩陣正定的前提下，利用求解微分方程的基爾方法[9]構造出一條基爾折線，然后利用該折線代替最優(yōu)曲線來求解問題(1)，并且證明了基爾折線路徑的性質，分析了基爾切線算法的適定性。數值結果表明新算法較庫塔三階算法[10]具有很好的效果。

1 基爾折線的構造

微分方程形式的基爾公式如下：

(3)

(4)

基爾折線構造法如下：

(5)

(6)

(7)

(8)

(9)

其中ε是限制步長。

3 基爾折線路徑的性質

定理1設B對稱正定，且當n=1,2,…,N-1時，有(10)式成立。

(10)

則δ(τ)滿足：

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

(2)q(δ(τ))關于τ為單調非減函數。

注：引理1和定理1的證明過程見文獻[11]。

4 算法描述

下面給出基爾折線算法的具體步驟：

步0. 給定梯度g，正定矩陣B，信賴域半徑Δ.令n:=0。

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

步2.如果Δ≥‖δn‖2，則取δ*=δ0，停止計算。否則，令n:=n+1，轉步3.

步3.令：

步4.令：

若‖δ1‖2≤Δ，則?。?/p>

停止計算，否則令：n:=1轉步5.

步5.令：

步6.令：

若‖δn+1‖2≤Δ，則取：

其中：

停止計算，否則令n:=n+1轉步5.

5 算法的適定性

由定理1可知下列結論成立。

定理2 設B對稱正定，在基爾折線算法中，對任意給定的信賴域半徑Δ<‖B-1g‖2，則存在自然數N，使得‖δN‖2≤Δ.

定理1和定理2表明對任意給定的信賴域半徑Δ，基爾折線δ(τ)上的近似解存在且唯一。并且用基爾折線算法求解信賴域子問題(*)的最優(yōu)解δ*時，最優(yōu)解δ*在信賴域邊界上取得。

6 數值實驗

取限制步長ε=0.5，對于信賴域子問題，在不同的信賴域半徑Δ的條件下，分別運用基爾折線算法和庫塔三階折線算法對如下給定的測試函數Function1和Function2

其中：

進行數值實驗，對所求得的相應數值結果進行比較，如下表：

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

Tab.1 The numerical results of test Function 1

ΔFunction1庫塔三階qKL基爾折線qGLqKL-qGL0.5-18.157 329 13-18.175 210 040.017 880 911-33.923 275 59-33.976 098 540.0528 229 51.5-47.724 540 07-47.800 925 310.0763 852 42-59.413 500 81-59.498 124 560.0846 237 52.3-66.420 988 04-66.566 798 930.145 810 892.7-75.124 016 37-75.351 761 590.227 745 222.99-78.790 794 98-79.024 312 050.233 517 073.5-87.204 142 07-87.489 876 090.285 734 024.5-102.112 410 3-102.690 047 90.577 637 585-108.743 180 1-109.101 098 20.357 918 096-119.967 123 6-120.241 890 90.274 767 286.5-125.342 658 4-125.604 011 90.261 353 517-130.100 430 5-130.350 5980.250 167 547.5-134.823 566 9-134.992 654 40.169 087 468-138.900 987 7-139.015 321 70.114 333 989-146.590 877 8-146.701 143 10.110 265 2910-152.936 487 8-153.032 412 60.095 924 7511-157.989 926 2-158.070 336 10.080 409 9212-162.003 165 8-162.061 809 20.058 643 4413-164.897 301 4-164.930 045 20.032 743 8214-166.632 109 9-166.650 290 20.018 180 2915-167.439 087 7-167.439 902 10.000 814 41Δ≥15.04-167.496 000 0-167.496 000 00

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

Tab.2 The numerical results of test Function 2

ΔFunction1庫塔三階qKL基爾折線qGLqKL-qGL0.5-26.459 338 47-26.484 321 660.024 983 191-49.997 730 67-50.026 008 440.0282 777 71.5-68.466 879 02-68.499 781 660.032 902 642-84.582 442 48-84.669 786 530.087 344 052.5-97.920 239 43-98.010 002 410.089 762 983-108.902 141 3-109.023 3310.121 189 673.5-117.999 064 4-118.174 312 10.175 247 653.58-120.208 268 3-120.409 976 40.201 708 054-125.494 048-125.700 283 40.206 235 444.5-131.828 408 6-131.990 872 60.162 463 955-137.217 199 4-137.351 090 70.1338 912 65.5-141.438 723 2-141.540 718 10.101 994 916-145.823 433 7-145.921 124 60.097 690 856.5-149.693 733 4-149.776 098 80.082 365 397-151.223 392 5-151.289 769 10.066 376 597.5-154.751 440 8-154.790 618 80.039 177 998-156.857 627 5-156.876 509 90.018 882 379-160.115 811 2-160.125 098 10.009 286 9210-161.799 504 4-161.807 241 20.007 736 83Δ≥10.32-161.032 700 0-161.032 700 00

表1和表2的數值結果表明，當信賴域半徑Δ≤‖δnp‖2時，較庫塔三階算法，用基爾折線算法求得的最優(yōu)解更好；當信賴域半徑Δ≥‖δnp‖2時，兩種方法的求解效果一樣。對于測試函數Function1和Function2，信賴域半徑Δ=4.5及Δ=4的附近兩種方法所求的最優(yōu)解的函數值之差最大。

綜上可知：基爾折線算法的求解效果較庫塔三階算法更優(yōu)。

對于測試函數Function1，‖δnp‖2=15.04.對于測試函數Function2，‖δnp‖2=10.32.