一种求解信赖域子问题的基尔方法

武姝廷，王希云

(太原科技大学 应用科学学院，太原030024)

求解如下形式的二次模型信赖域子问题[1]：

(1)

随着Δ改变，(1)的解δ*在空间形成一条曲线——最优曲线[2]。对于(1)的求解，目前提出的方法主要有精确求解法、折线法、截断共轭梯度法等。其中折线法是求解信赖域子问题最常用和最有效的方法，常用的折线法主要有单折线法[3]、双折线法[4]、切线单折线法[5]以及基于最优曲线微分方程模型的欧拉算法[6-8]。本文根据最优曲线的微分方程模型：

(2)

在Hessian矩阵正定的前提下，利用求解微分方程的基尔方法[9]构造出一条基尔折线，然后利用该折线代替最优曲线来求解问题(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≤Δ，则取：

停止计算，否则令：n:=1转步5.

步5.令：

步6.令：

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

其中：

停止计算，否则令n:=n+1转步5.

5 算法的适定性

由定理1可知下列结论成立。

定理2 设B对称正定，在基尔折线算法中，对任意给定的信赖域半径Δ<‖B-1g‖2，则存在自然数N，使得‖δN‖2≤Δ.

定理1和定理2表明对任意给定的信赖域半径Δ，基尔折线δ(τ)上的近似解存在且唯一。并且用基尔折线算法求解信赖域子问题(*)的最优解δ*时，最优解δ*在信赖域边界上取得。

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时，较库塔三阶算法，用基尔折线算法求得的最优解更好；当信赖域半径Δ≥‖δnp‖2时，两种方法的求解效果一样。对于测试函数Function1和Function2，信赖域半径Δ=4.5及Δ=4的附近两种方法所求的最优解的函数值之差最大。

综上可知：基尔折线算法的求解效果较库塔三阶算法更优。

对于测试函数Function1，‖δnp‖2=15.04.对于测试函数Function2，‖δnp‖2=10.32.