求解不定信賴域子問題的分段三次Hermite插值法

李琳俊，王希云

(太原科技大學(xué)應(yīng)用科學(xué)學(xué)院，太原 030024)

作為一種重要的數(shù)值方法，信賴域算法以其全局收斂性及較強(qiáng)的適定性，一直以來受到最優(yōu)化研究者們的廣泛關(guān)注。

運(yùn)用信賴域算法求解，每一次從點(diǎn)開始迭代時(shí)，對(duì)于如下信賴域子問題,均需分別求解。

(1)

在(1)中，符號(hào)的意義為：B∈Rn×n是目標(biāo)函數(shù)在點(diǎn)x(k)x(k)對(duì)應(yīng)的Hessian矩陣或者其近似形式，g∈Rn是目標(biāo)函數(shù)在點(diǎn)x(k)對(duì)應(yīng)的梯度,δ∈Rn是待求的變量，Δ∈R是信賴域的半徑。假定該算法在點(diǎn)(μk,f(μk)),(k=0,1,…m).進(jìn)行迭代，伴隨著Δ不斷變化，(1)的解δ*也發(fā)生相應(yīng)變化，將各個(gè)變化過程形成的點(diǎn)連線可確定一條空間曲線,叫做最優(yōu)曲線[1]。

由精確求解信賴域子問題方法的思想，易知最優(yōu)曲線的參數(shù)方程為：

δ=-(B+μI)-1g,(μ≥0)

(2)

從而可構(gòu)造如下形式的微分方程模型[2]:

再用分段三次Hermite插值法[3]求解此模型。

在(2)前提下，引入新的函數(shù)：

y=f(μ)=‖δ‖2=‖-(B+μI)-1g‖2,(μ≥0),那么(1)的解δ*如下：

當(dāng)μ=0,δ*=-B-1g;

當(dāng)μ>0，解的確定依賴于求解以下形式的一元非線性方程：

f(μ)-Δ=‖-(B+μI)-1g‖2-Δ=0.

解該方程可確定μ*，則最優(yōu)解：

δ*=-(B+μ*I)-1g.

子問題(1) 在B不定情況下，不一定會(huì)有極小值點(diǎn)。甚至可能會(huì)沒有平穩(wěn)點(diǎn)[4]。一般而言，可用強(qiáng)迫矩陣正定的方法修正B來避免這種情況。近年以來，求解不定信賴域子問題的方法有：修正分段割線法[5]，混合折線法[6]雙割線折線法[7]等。本文中，通過修改Cholesky分解修正不定矩陣B，進(jìn)而構(gòu)造新的對(duì)稱正定矩陣G[2].修正不定矩陣之后，問題已經(jīng)轉(zhuǎn)化為求解正定形式的信賴域子問題。再依據(jù)分段三次Hermite插值法[3]，提出修正分段三次Hermite插值法來解(1).

1 分段三次Hermite插值法的思想

分段三次Hermite法是依據(jù)求解(1)的分段割線法，對(duì)以下的節(jié)點(diǎn)：

(μk,f(μk)),(k=0,1,…m).

運(yùn)用三次Hermite插值法來構(gòu)造m條曲線，

Hk(μ),(k=0,1,…m)為曲線方程。將m條曲線連接起來，就是分段三次Hermite曲線。在最后的兩個(gè)插值點(diǎn)：(μm-1,f(μm-1)),(μm,f(μm))構(gòu)造三次Hermite插值函數(shù)H(μ)近似代替f(μ)，再求方程：f(μ)-Δ=0的解μ*，進(jìn)一步確定信賴域子問題的最優(yōu)解：

δ*=-(B+μ*I)-1g,(μ≥0).

此算法優(yōu)于修正分段割線法之處：用分段三次Hermite插值法確定的曲線，可以避免用修正分段割線法構(gòu)造的曲線在節(jié)點(diǎn)處出現(xiàn)尖點(diǎn)，從而能更好的逼近最優(yōu)曲線。

2 修正不定矩陣

在文獻(xiàn)[4]中，修改Cholesky分解可以修正不定矩陣B，進(jìn)一步將不定問題轉(zhuǎn)化為正定問題。

3 算法框架

Step0 給定梯度g，不定矩陣B,信賴域半徑Δ，步長(zhǎng)h.令n:=0.

Step1用修改Cholesky分解修正B，得新正定矩陣G,且令：B=G.

Step2當(dāng)μ0=0，求f(μ0)與f′(μ0).若：f(μ0)≤Δ，取：δ*=-B-1g，停止計(jì)算。否則使k:=1，轉(zhuǎn)step 3.

Step3計(jì)算f(μk)和f′(μk)，μk=μk-1+h.在插值節(jié)點(diǎn)(μk-1,f(μk-1))和(μk,f(μk))間，應(yīng)用三次Hermite插值法確定曲線Hk(μ),將所有的小區(qū)間結(jié)合起來，形成分段曲線Γ.

Step4若f(μk)≤Δ，則μ*處在曲線Hk(μ)上，求解方程：Hk(μ*)=Δ確定μ*，最優(yōu)解為：δ*=-(B+μ*I)-1g,停止計(jì)算。否則，使k:=k+1,轉(zhuǎn)step3.

注1：在step 0，步長(zhǎng)h越小，由以上算法求得的(1)之解δ*越準(zhǔn)確。

注2：在step 3，分段曲線Γ形式如下：

其中：

(k=1,2,…m).

4 數(shù)值實(shí)驗(yàn)及結(jié)果分析

基于本文提出的修正分段三次Hermite插值法，對(duì)于測(cè)試函數(shù)Function 1和Function 2(見附錄)，選取不同的信賴域半徑Δ，分別用算法4與修正分段割線法來計(jì)算最優(yōu)解，并與精確解進(jìn)行比較。CHDH為修正的分段三次Hermite插值法(即算法4)，CHDF為修正分段割線算法，HD為混合折線法。具體結(jié)果見表1和表2.

表1 測(cè)試函數(shù)1的數(shù)值結(jié)果
Tab.1 Numerical results of Function 1

ΔCHDH(Hermite)CHDF(分段割線)精確解Function11-14．177285-14．3490051-14．1772732-28．5609402-29．4507523-28．5604233．5-50．9305577-54．5986931-50．9140114-58．6560535-63．8000136-58．6453835-74．6836005-83．4756002-74．6108835．28-79．2372724-89．3518536-79．2104076-91．7245303-89．4577778-91．3140317-110．6027419-89．4577778-108．816228-128．8753917-89．4577778-127．162279-147．2780263-89．4577778-146．385179．1-149．1596098-89．4577778-148．356699．2-151．0517361-89．4577778-150．3372610-166．6505065-89．4577778-166．5095312-211．0244466-89．4577778-209．5328114-267．7873558-89．4577778-256．3357416-267．7873558-89．4577778-306．9823818-267．7873558-89．4577778-361．5142919-267．7873558-89．4577778-390．2463521-267．7873558-89．4577778-450．6559922-267．7873558-89．4577778-482．3376822．4-267．7873558-89．4577778-495．2865822．5-267．7873558-89．4577778-498．54849

表2 測(cè)試函數(shù)2的數(shù)值結(jié)果
Tab.2 Numerical results of Function 2

ΔCHDH(Hermite)CHDF(分段割線)精確解Function20．5-7．12368999-7．1236693-7．12368931-14．3491354-14．3490048-14．34910911．5-21．7673119-21．7665767-21．76730272-29．4531297-29．4507524-29．45260502．5-37．4673891-37．4577862-37．46202924-63．8881367-63．8000136-63．80400454．5-73．5592815-73．4099425-73．43375535．5-94．0762014-89．4577778-94．05036706-105．432536-89．4577778-105．054024ΔCHDH(Hermite)CHDF(分段割線)精確解6．5-117．901429-89．4577778-116．5293827-131．8046545-89．4577778-128．48093877．5-131．8046535-89．4577778-140．91229348-131．8046535-89．4577778-153．82635618．5-131．8046535-89．4577778-167．22550259-131．8046535-89．4577778-181．11169359．5-131．8046535-89．4577778-195．486559410-131．8046535-89．4577778-210．351468110．5-131．8046535-89．4577778-225．707573911-131．8046535-89．4577778-241．555859311．5-131．8046535-89．4577778-257．897165812-131．8046535-89．4577778-274．732217812．5-131．8046535-89．4577778-292．0616398

同理，對(duì)于不同的Δ，分別用算法4與混合折線法求解測(cè)試函數(shù)1和2，qHD-qCHDH表示的是：對(duì)于確定的測(cè)試函數(shù)以及信賴域半徑，采用混合折線法得到的最優(yōu)解與采用算法4得到的最優(yōu)解之差，該差值越大說明算法4越好。具體結(jié)果見表3和表4.

第一個(gè)測(cè)試函數(shù)Function 1的擬牛頓步為：

‖Gg‖2=22.398,

第二個(gè)測(cè)試函數(shù)Function 2的擬牛頓步為：

‖Gg‖2=11.47.

數(shù)值實(shí)驗(yàn)：

表3 測(cè)試函數(shù)1的數(shù)值結(jié)果
Tab.3 Numerical results of Function 1

ΔqHD-qCHDHCHDH(Hermite)HD(混合折線)Function110．035149834-14．17728546-14．1421356220．276668954-28．5609402-28．284271253．51．433083012-50．9305577-49．4974746842．087511041-58．65605354-56．5685424953．972922454-74．68360057-70．710678125．284．566796383-79．23727248-74．6704760966．871716555-91．7245303-84．85281374711．60779257-110．6027419-98．99494937815．73830672-128．8753917-113．137085919．99880567-147．2780263-127．27922069．120．46617565-149．1596098-128．69343429．220．94408835-151．0517361-130．107647710256．7824772-166．650506590．1319707812315．9009656-211．0244466104．87651914385．5490951-267．7873558117．761739316396．6248606-267．7873558128．837504818405．9183677-267．7873558138．131011922-183．4633192-267．7873558-451．25067522．4-183．4633192-267．7873558-451．25067522．5-183．4633192-267．7873558-451．250675

從表1與表2，易知：CHDH(Hermite)比CHDF(分段割線)更接近精確解，且CHDF(分段割線)在Δ為很小的半徑(Function 1中，Δ=5.28；Function 2中，Δ=5.5)便陷入局部最優(yōu)，而CHDH(Hermite)在整個(gè)求解過程較為穩(wěn)定。

從表3與表4，易知：CHDH(Hermite)所得最優(yōu)解明顯優(yōu)于HD (混合折線法) 。

綜上所述，修正分段三次Hermite插值法求解信賴域子問題有效可行，從而拓寬了對(duì)于不定信賴域子問題求解的研究。

表4 測(cè)試函數(shù)2的數(shù)值結(jié)果
Tab.4 Numerical results of Function 2

ΔqHD-qCHDHCHDH(Hermite)HD(混合折線)Function20．50．0173547-7．123689899-7．10633520210．13646502-14．3491354-14．21267041．50．44830633-21．7673119-21．3190056121．02778884-29．4531296-28．425340812．51．93571312-37．4673891-35．5316760133．21301798-45．8510292-42．638011213．54．87166578-54．6160122-49．7443464147．03745504-63．8881366-56．850681614．59．6022647-73．5592815-63．957016825129．192398-83．54344245．648955835．5143．609435-94．076201449．533233876158．615946-105．43253653．183410186．5174．505935-117．90142956．604505458197．328791-131．80465465．524137928．5199．860679-131．80465468．0560256100-131．804654-131．804654120-131．804654-131．80465412．50-131．804654-131．804654

附錄：測(cè)試函數(shù)

Function 1:

s.t.‖δ‖2≤Δ.

Function2:

s.t.‖δ‖2≤Δ.

參考文獻(xiàn)：

[1] 徐成賢，陳志平，李乃成.近代優(yōu)化方法[M].北京：科學(xué)出版社，2002.

[2] 李亮，王希云，張雅琦，等.一種求解二次模型信賴域子問題的休恩算法[J].太原科技大學(xué)學(xué)報(bào)，2014,35(2)：151-155.

[3] 于海波，王希云，李亮.解信賴域子問題的分段Hermite插值法[J].太原科技大學(xué)學(xué)報(bào)，2014,35(3):226-230.

[4] 袁亞湘，孫文瑜.最優(yōu)化理論與方法[M].北京：科學(xué)出版社，2010.

[5] 于海波，王希云，李亮.一種求解不定信賴域子問題的精確解法[J].太原科技大學(xué)學(xué)報(bào)，2015,35(2):156-160.

[6] 趙丹.解信賴域子問題的混合折線法[J].徐州師范大學(xué)學(xué)報(bào)：自然科學(xué)版,2009,27(3) :38-41.

[7] 邵安，王希云.一種求解不定信賴域子問題的雙割線折線法[J].太原科技大學(xué)學(xué)報(bào)，2011,32(6):483-487.

[8] 楊蕊.矩陣的Cholesky分解的Matlab實(shí)現(xiàn)[J].中國(guó)科技信息：基礎(chǔ)及前沿研究，2007(4)：273-274.