基于新水平向量的錐模型算法

劉曉佳，倪 勤，朱紅蘭

(南京航空航天大學(xué) 理學(xué)院,南京 210016)

0 引言

本文考慮如下非線性無(wú)約束最優(yōu)化問(wèn)題：

(1)

其中f:Rn→R是二次連續(xù)可微函數(shù)，并且有下界。求問(wèn)題(1)的一般算法參見(jiàn)文獻(xiàn)[1]。

1980年，Davidon首次提出錐模型方法求解以上問(wèn)題[2],錐模型定義為：

(2)

其中a∈Rn,g∈Rn,A∈Rn×n,s∈Rn。隨后Sorensen，Ariyawansa等對(duì)線搜索類(lèi)錐模型進(jìn)行了研究[3-4]。1996年，Di和Sun提出了基于錐模型的信賴(lài)域模型[5]，子問(wèn)題為：

(3)

其中，gk=▽f(xk),△k>0,為信賴(lài)域半徑，Ak是f(x)在xk處的近似Hessian陣，ak稱(chēng)為水平向量，‖·‖為歐式范數(shù)。

由于錐模型有更多的自由度，對(duì)于非二次性強(qiáng)、曲率變化劇烈的函數(shù)逼近效果比較好。之后諸多學(xué)者研究ak的選取方法[6-8]。文獻(xiàn)[6]中考慮錐模型滿(mǎn)足下列插值條件：

(4)

為了克服ak的選取具有任意性的缺點(diǎn)，文獻(xiàn)[7]中增加了限制條件ak=t1gk+t2gk-1， 其中，t1和t2是待定的實(shí)參數(shù)。王希云等人還給出了其他選擇ak的策略。

本文從高次模型的角度出發(fā)，通過(guò)錐模型的高次展開(kāi)式的推導(dǎo)，提出了一種新的水平向量的選擇方法。在此基礎(chǔ)上，給出了一個(gè)基于新水平向量的錐模型擬牛頓信賴(lài)域算法，并證明了此算法的收斂性；同時(shí)給出了與其他算法進(jìn)行對(duì)比的數(shù)值結(jié)果。

1 水平向量的選擇及算法

在子問(wèn)題(3)中，ak的選取將對(duì)在當(dāng)前迭代點(diǎn)xk的目標(biāo)函數(shù)逼近產(chǎn)生重要影響。

1.1 水平向量的選擇

為推導(dǎo)方便，先略去水平向量的下標(biāo)。當(dāng)|aTs|<1時(shí)，式(3)中錐模型逼近函數(shù)的展開(kāi)式為：

(5)

這是一個(gè)關(guān)于s的高次模型，對(duì)其兩邊求梯度并令s=-sk-1，▽?duì)?-sk-1)≈gk-1在，略去三次項(xiàng)得

(6)

因此水平向量的一個(gè)新的選取組合為：

a=β1gk-1+=β2gk+=β3Aksk-1

(7)

ζk-ηk+ξk=(3ξk-2ηk)t+3ηkt2

(9)

通過(guò)式(7)～(9)，式(6)可化簡(jiǎn)為：

gk-1-gk+Aksk-1=(ξk-ηk+2ηkt)(β1gk-1+β2gk+β3Aksk-1)-tgk+t2gk+2tAksk-1

(10)

如果ξk-ηk+2ηkt≠0, 則比較等式左右對(duì)應(yīng)系數(shù)得：

其中,tk由式(9)確立，所以在第k迭代步的水平向量的選擇策略如下：

(11)

1.2 Ak的校正公式

(12)

(13)

(14)

其中，ε0∈(0,1)。下面給出求解問(wèn)題(1)的基于新水平向量的錐模型擬牛頓信賴(lài)域法的算法。

1.3 基于新水平向量的錐模型擬牛頓信賴(lài)域法的算法

算法步驟如下：

第一步，選初值。取x0∈Rn，a0=0，A0>0，△0。令ε>0，0<θ1<θ2<1,0<β1 ,ε>0,ρ∈(0,1) ,0<γ1<γ2，k=0。

第二步，檢驗(yàn)終止條件。計(jì)算gk=f(xk),若‖gk‖≤ε，則x*=xk，算法終止。

第五步，校正信賴(lài)域半徑。修正△k+1，

第六步，令k=k+1，根據(jù)公式(11)～(14) 校正Ak，ak和△k。轉(zhuǎn)第二步。

注：第三步中求解子問(wèn)題的方法參考文獻(xiàn)[6], 第四步中的Wolfe-Powell準(zhǔn)則見(jiàn)文獻(xiàn)[1]第二章。

2 算法1.3的收斂性

考慮以下假設(shè)：

H1：函數(shù)f(x)二階連續(xù)可微有下界。

H2：水平集Ω0={x∈Rn|f(x)≤f(x0)}有界。

H3：f(x)在Ω0上Lipschitz連續(xù)，即?x，y∈Rn,存在常數(shù)L>0滿(mǎn)足

H4：水平向量序列{ak}及矩陣序列{Ak}一致有界，即存在M>0，N>0使得，‖ak‖≤M，‖Ak‖≤N。

以下引理2.1和2.2可容易從文獻(xiàn)[9]中的定理4.2得出，故此處證明從略。為簡(jiǎn)便起見(jiàn)，記I={k|ρk<θ1}。

引理2.1 若假設(shè)H1、H2與H4成立，則算法1.3中子問(wèn)題的解sk帶來(lái)的估計(jì)下降量滿(mǎn)足

(15)

下面給出算法1.3的收斂定理。

定理2.3 若假設(shè)H1～H4成立，{xk}由算法1.3得出，則有l(wèi)iminf‖gk‖=0。

證明：假設(shè)結(jié)論不成立，則存在δ>0，使得對(duì)?k,‖gk‖≥δ。根據(jù)引理2.2可知

(16)

(17)

又因?yàn)橛杉僭O(shè)H1得，存在一個(gè)正數(shù)N0使得：

(18)

又根據(jù)式(16)知，存在足夠大的k0，當(dāng)k≥k0時(shí)有△k≤δ/N，從而

(19)

由式(17)～(19), 我們推出當(dāng)k≥k0時(shí)，有：

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

我們分別運(yùn)用算法1.3與文獻(xiàn)[6]中的算法5.1對(duì)5個(gè)標(biāo)準(zhǔn)試驗(yàn)函數(shù)進(jìn)行計(jì)算，維數(shù)取為60，計(jì)算結(jié)果見(jiàn)表1，其中表示為初始點(diǎn)，iter、func、dfunc分別表示迭代次數(shù)、函數(shù)值及導(dǎo)數(shù)值的計(jì)算次數(shù)。控制精度取為ε=10-6，信賴(lài)域算法中各個(gè)初始參數(shù)選取為：A0=I，△0=1；線搜索過(guò)程中參數(shù)取為：μ=0.1，σ=0.3；其它參數(shù)為：θ1=0.01，θ2=0.75，γ1=0.5，γ2=2.0，τ=0.75，ρ=0.2，ε0=0.8。

表1 算法1.3的比較結(jié)果

由于每個(gè)試驗(yàn)函數(shù)取了2個(gè)不同的初始點(diǎn)，從而5個(gè)試驗(yàn)函數(shù)形成了10組試驗(yàn)問(wèn)題。兩個(gè)算法都能順利地求解這10組試驗(yàn)問(wèn)題。除了第一個(gè)試驗(yàn)函數(shù)，算法1.3的結(jié)果比算法5.1略差外，其余四個(gè)函數(shù)的結(jié)果均優(yōu)于算法5.1。其中算法1.3的平均迭代次數(shù)為135次，函數(shù)值平均計(jì)算次數(shù)為678次，導(dǎo)數(shù)值的平均計(jì)算次數(shù)是191次；算法5.1的平均迭代次數(shù)為161次，函數(shù)值平均計(jì)算次數(shù)為749次，導(dǎo)數(shù)值的平均計(jì)算次數(shù)是214次。

以上結(jié)果表明，算法1.3的效果優(yōu)于算法5.1，這從數(shù)值上顯示了基于新水平向量的錐模型算法是一種更合理的選擇。

參考文獻(xiàn)：

[1] 倪勤.最優(yōu)化方法與程序設(shè)計(jì)[M].北京:科學(xué)出版社,2009.

[2] Davidon W C.Conic approximations and collinear scaling for optimizers[J].SIAM J Numer Anal,1980,17(2):268-281.

[3] Sorensen,D C.The Q-superlinear convergence of a collinear scaling algorithm for unconstrained optimization[J].SIAM J.Numer.Anal.,1980,17(1):84-114.

[4] Ariyawansa,K A.Deriving collinear scaling algorithms as extension of Quasi-Newton methods and the local convergence of DFP and BFGS related collinear scaling algorithms[J].Math. Prog.,1990,49(1):23-48.

[5] Di S,Sun W Y.A trust region method for conic model to solve unconstrained optimization[J].Optimization methods and software,1996,6(4):237-263.

[6] 諸梅芳,薛毅,張鳳圣.錐模型的擬NEWTON型信賴(lài)域方法[J].高等學(xué)校計(jì)算數(shù)學(xué)學(xué)報(bào), 1995,17(1):36-47.

[7] 楊富貴,盛松柏.錐模型擬牛頓法[J].高等學(xué)校計(jì)算數(shù)學(xué)學(xué)報(bào),1995,17(4):323-331.

[8] 王慶,王希云.錐模型信賴(lài)域方法中水平向量的選取[J].太原科技大學(xué)學(xué)報(bào)，2008,29(6): 447-449.

[9] Xu C X,Yang X Y.Convergence of conic quasi-Newton trust region methods for unconstrained minimization[J].Mathematica Applicata,1998,11(2):71-76.