一种求解信赖域子问题的多割线折线算法

2022-02-22 01:31
宁夏师范学院学报 2022年1期
关键词:割线测试函数折线

李 亮

(华中师范大学附属息县高级中学,河南 息县 464300)

在无约束优化问题的研究中,信赖域算法不仅具有较好的可靠性,而且具有较强的收敛性,受到无约束优化研究界的高度重视,成为优化研究界的一个研究热点.

无约束优化问题如下

minf(x),x∈Rn,

(1)

其中f(x)∶Rn→R是目标函数,x∈Rn是待求变量.

因为信赖域算法求解无约束优化问题(1)时,每步迭代都必须求解如下形式的信赖域子问题

(2)

其中,g∈Rn为目标函数f(x)在当前迭代点的梯度,B∈Rn×n为目标函数f(x)在当前迭代点的Hessian矩阵,Δ∈R为信赖域半径,δ∈Rn为待求变量.所以信赖域子问题(2)的求解在信赖域算法中至关重要.

目前已经提出了很多求解信赖域子问题(2)的方法,比如赵英良等[1]提出的切线单折线法,赵丹[2]提出的混合折线法,陈争等[3]提出的光滑牛顿法,王希云等[4]提出的双割线折线法,李亮等[5]提出的分段割线法,文献[6]提出的隐式分段折线算法,文献[7]提出的分段切线算法,文献[8]提出的改进的隐式Euler切线法,贾新辉等[9]提出的改进的平均欧拉切线法,武姝廷等[10]提出的基尔方法等.

定理1[11]δ*是信赖域子问题(2)的解,当且仅当存在μ*≥0,使得如下方程组成立

(3)

而且(B+μ*I)是半正定矩阵.

24例动脉瘤患者中CT扫描结果,小型动脉瘤(<5mm)7例,中型动脉瘤(5~10mm)12例,大型动脉瘤(11~25mm)4例,巨大型动脉瘤(>25mm)1例,24例动脉瘤中21例存在破口。

由定理1可知,信赖域子问题(2)的精确求解方法即是求解如下方程组

(4)

利用牛顿法[11]求解方程组(4)的步骤

当μ=0时,则取δ*=-B-1g;

因此为了更精确的求解非线性方程φ(μ)=0的近似根,本文利用线性插值法[12]构造了一条多割线折线,并提出了一种求解信赖域子问题的多割线折线算法.

1 多割线折线的构造

对插值节点(μk,yk),k=0,1,2,…,M采用文献[12]中的线性插值法构造M条直线,每条直线对应的一次函数记为lk(μ),k=1,2,…,M.把构造的M条直线连接起来构成一条多割线折线,符号记为L=[y0,y1,…,yM].

2 多割线折线路径的性质

定理2记多割线折线L=[y0,y1,…,yM]对应的分段函数如下

(5)

则L(μ)满足

①L(μ)为连续单调增函数.

3 算法描述

解信赖域子问题(2)的多割线折线算法的步骤为

步1 给定梯度g,正定矩阵B,信赖域半径Δ,步长h.

步3 令μk=kh,计算yk=f(μk).

4 数值结果

采用文末附录中的测试函数,令多割线折线算法中的步长h=0.1,文献[7]中的欧拉切线算法步长中的参数k=8,然后进行数值实验,把多割线折线算法求解的测试函数在最优解处的函数值分别与文献[1]中的切线单折线法和文献[7]中的分段切线算法求解的测试函数在最优解处的函数值进行比较,并对数值实验结果进行了分析.数值实验结果分别列在表1和表2中,其中Δ表示信赖域半径,fTDL表示切线单折线法求解的测试函数在最优解处的函数值,fSTA表示分段切线算法求解的测试函数在最优解处的函数值,fMSD表示多割线折线算法求解的测试函数在最优解处的函数值.哪种算法求解的测试函数在最优解处的函数值越小,则表明该算法越好.

表1 测试函数1的数值结果

表2 测试函数2的数值结果

ΔfTDLfSTAfMSD3.3-22 316.032 885 48-23 386.275 745 38-23 386.343 192 643.8-22 476.231 429 06-23 416.650 080 99-23 416.680 881 784.3-22 616.807 965 29-23 442.274 587 55-23 442.290 486 984.9-22 766.971 341 43-23 469.004 596 76-23 469.013 302 355.3-22 857.938 076 34-23 484.974 157 06-23 484.979 317 365.7-22 942.494 095 14-23 499.702 926 65-23 499.706 710 636.3-23 058.353 283 21-23 519.738 899 23-23 519.741 167 526.8-23 145.533 588 69-23 534.723 779 98-23 534.725 140 857.3-23 224.657 041 60-23 548.266 788 91-23 548.267 101 817.8-23 296.024 927 90-23 560.440 991 88-23 560.440 577 388.2-23 347.685 789 06-23 569.231 407 96-23 569.230 780 988.7-23 405.613 330 47-23 579.067 428 40-23 579.067 194 459.2-23 456.277 227 86-23 587.653 114 57-23 587.652 425 549.8-23 507.631 575 85-23 596.339 869 59-23 596.339 256 5510.2-23 536.210 666 68-23 601.167 162 89-23 601.166 927 6810.7-23 565.629 335 18-23 606.130 751 82-23 606.130 397 9611.2-23 588.091 984 84-23 609.916 574 35-23 609.916 169 1011.8-23 605.926 946 85-23 612.919 381 27-23 612.919 310 3912.3-23 613.231 507 39-23 614.148 100 54-23 614.148 073 09≥12.59-23 614.333 333 33-23 614.333 333 33-23 614.333 333 33

文中所用测试函数如下

猜你喜欢
割线测试函数折线
平面分割问题的探究之旅
解信赖域子问题的多折线算法
一种基于精英选择和反向学习的分布估计算法
基于博弈机制的多目标粒子群优化算法
折线的舞台——谈含绝对值的一次函数的图象
潮流方程的割线法求解
折线
折线图案
具有收缩因子的自适应鸽群算法用于函数优化问题
从一道试题谈圆锥曲线的切割线定理