一種求解信賴域子問題的多割線折線算法

李 亮

(華中師范大學(xué)附屬息縣高級(jí)中學(xué)，河南 息縣 464300)

在無約束優(yōu)化問題的研究中，信賴域算法不僅具有較好的可靠性，而且具有較強(qiáng)的收斂性，受到無約束優(yōu)化研究界的高度重視，成為優(yōu)化研究界的一個(gè)研究熱點(diǎn).

無約束優(yōu)化問題如下

minf(x),x∈Rn,

(1)

其中f(x)∶Rn→R是目標(biāo)函數(shù)，x∈Rn是待求變量.

因?yàn)樾刨囉蛩惴ㄇ蠼鉄o約束優(yōu)化問題(1)時(shí)，每步迭代都必須求解如下形式的信賴域子問題

(2)

其中，g∈Rn為目標(biāo)函數(shù)f(x)在當(dāng)前迭代點(diǎn)的梯度,B∈Rn×n為目標(biāo)函數(shù)f(x)在當(dāng)前迭代點(diǎn)的Hessian矩陣，Δ∈R為信賴域半徑，δ∈Rn為待求變量.所以信賴域子問題(2)的求解在信賴域算法中至關(guān)重要.

目前已經(jīng)提出了很多求解信賴域子問題(2)的方法，比如趙英良等[1]提出的切線單折線法，趙丹[2]提出的混合折線法,陳爭(zhēng)等[3]提出的光滑牛頓法,王希云等[4]提出的雙割線折線法，李亮等[5]提出的分段割線法,文獻(xiàn)[6]提出的隱式分段折線算法,文獻(xiàn)[7]提出的分段切線算法,文獻(xiàn)[8]提出的改進(jìn)的隱式Euler切線法，賈新輝等[9]提出的改進(jìn)的平均歐拉切線法，武姝廷等[10]提出的基爾方法等.

定理1[11]δ*是信賴域子問題(2)的解,當(dāng)且僅當(dāng)存在μ*≥0,使得如下方程組成立

(3)

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

24例動(dòng)脈瘤患者中CT掃描結(jié)果，小型動(dòng)脈瘤（＜5mm）7例，中型動(dòng)脈瘤（5～10mm）12例，大型動(dòng)脈瘤（11～25mm）4例，巨大型動(dòng)脈瘤（＞25mm）1例，24例動(dòng)脈瘤中21例存在破口。

由定理1可知，信賴域子問題(2)的精確求解方法即是求解如下方程組

(4)

利用牛頓法[11]求解方程組(4)的步驟

當(dāng)μ=0時(shí),則取δ*=-B-1g；

因此為了更精確的求解非線性方程φ(μ)=0的近似根，本文利用線性插值法[12]構(gòu)造了一條多割線折線，并提出了一種求解信賴域子問題的多割線折線算法.

1 多割線折線的構(gòu)造

對(duì)插值節(jié)點(diǎn)(μk,yk)，k=0,1,2,…,M采用文獻(xiàn)[12]中的線性插值法構(gòu)造M條直線,每條直線對(duì)應(yīng)的一次函數(shù)記為lk(μ),k=1,2,…,M.把構(gòu)造的M條直線連接起來構(gòu)成一條多割線折線，符號(hào)記為L(zhǎng)=[y0,y1,…,yM].

2 多割線折線路徑的性質(zhì)

定理2記多割線折線L=[y0,y1,…,yM]對(duì)應(yīng)的分段函數(shù)如下

(5)

則L(μ)滿足

①L(μ)為連續(xù)單調(diào)增函數(shù).

3 算法描述

解信賴域子問題(2)的多割線折線算法的步驟為

步1 給定梯度g,正定矩陣B,信賴域半徑Δ，步長(zhǎng)h.

步3 令μk=kh，計(jì)算yk=f(μk).

4 數(shù)值結(jié)果

采用文末附錄中的測(cè)試函數(shù)，令多割線折線算法中的步長(zhǎng)h=0.1，文獻(xiàn)[7]中的歐拉切線算法步長(zhǎng)中的參數(shù)k=8，然后進(jìn)行數(shù)值實(shí)驗(yàn)，把多割線折線算法求解的測(cè)試函數(shù)在最優(yōu)解處的函數(shù)值分別與文獻(xiàn)[1]中的切線單折線法和文獻(xiàn)[7]中的分段切線算法求解的測(cè)試函數(shù)在最優(yōu)解處的函數(shù)值進(jìn)行比較,并對(duì)數(shù)值實(shí)驗(yàn)結(jié)果進(jìn)行了分析.數(shù)值實(shí)驗(yàn)結(jié)果分別列在表1和表2中,其中Δ表示信賴域半徑，fTDL表示切線單折線法求解的測(cè)試函數(shù)在最優(yōu)解處的函數(shù)值，fSTA表示分段切線算法求解的測(cè)試函數(shù)在最優(yōu)解處的函數(shù)值，fMSD表示多割線折線算法求解的測(cè)試函數(shù)在最優(yōu)解處的函數(shù)值.哪種算法求解的測(cè)試函數(shù)在最優(yōu)解處的函數(shù)值越小，則表明該算法越好.

表1 測(cè)試函數(shù)1的數(shù)值結(jié)果

表2 測(cè)試函數(shù)2的數(shù)值結(jié)果

Δ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

文中所用測(cè)試函數(shù)如下