基于錐模型的非單調自適應信賴域算法

王開榮， 曾劉拴

(重慶大學 數學與統計學院， 重慶 401331)

?

基于錐模型的非單調自適應信賴域算法

王開榮， 曾劉拴*

(重慶大學 數學與統計學院， 重慶 401331)

針對無約束優化問題提出了一個基于錐模型的非單調信賴域算法.首先提出一種求解子問題的新方法，在此基礎上給出該文算法.算法結合自適應技術，避免信賴域半徑更新的盲目性；并引入濾子技術和新的非單調技術，利用非單調Armijo線搜索得到步長，進而產生新的迭代點.在一定的假設條件下，證明了該算法的全局收斂性，數值實驗表明了算法的有效性．

無約束規劃； 非單調信賴域算法； 自適應方法； 濾子； 全局收斂性

本文考慮無約束最優化問題：

(1)

其中，f(x):R→Rn二階連續可微且有下界．

錐模型方法最初是由Davidon[1]和Sorensen[2]提出的.經典的錐模型如下：

(2)

其中，s=xk+1-xk，gk=f(xk)，對稱陣Bk∈Rn×n是2f(xk)或其近似，hk稱為水平向量.若hk=0或者則錐模型退化為二次模型，因此錐模型是二次模型的推廣，它包含更多的信息，具有二次模型沒有的優勢[3-5]．

考慮到信賴域方法良好的性質，Di和Sun[6]首次提出了錐模型信賴域方法，他們考慮了下面的信賴域子問題：

(3)

近年來非單調線搜索技術[7-10]因其較好的數值效果而得到了廣泛應用.2008年Mo和Gu[11]提出了一種較為簡單的非單調技術，即：

f(xk+αsk)≤Dk+δαf(xk)Tsk,

(4)

其中，

(5)

并將此技術運用到信賴域方法中，獲得了較好的數值效果．

自適應方法[12-14]可以避免信賴域半徑更新的盲目性.2009年，Sang和Sun[15]充分利用當前迭代點的信息提出了一種自適應方法，即令

(6)

其中，

(7)

0<ω1<ω2<1， 0

濾子技術[16]最初的目的是為了克服使用價值函數時選取罰因子的困難.2005年，Gould等[17]將濾子技術應用到一般的無約束優化問題中，提出了一個濾子信賴域方法，2012年，孫文瑜和徐東[18]提出了一種基于錐模型的濾子信賴域方法，證明了其收斂性，并得到較理想的數值效果．

1 基于錐模型的非單調濾子自適應信賴域算法

為了給出求解(3)的簡單算法，首先簡化子問題(3)，在第k步迭代中，用χ(xk)I來逼近Bk，則子問題(3)轉化為下面的形式：

(8)

另外，錐模型應該滿足下面的四個插值條件[5]:

ck(0)=fk，ck(0)=gk,

(9)

ck(-sk-1)=fk-1，ck(-sk-1)=gk-1,

(10)

其中，sk-1=xk-xk-1，由(10)的第一個等式可得

(11)

(12)

因此有

(13)

若χ(xk)≤0，則選取充分小的常數δ1>0，令

(14)

這樣就可以保證Bk=χ(xk)I正定．

錐模型函數ck(s)的嚴格極小點為：

(15)

求解問題(3)的計算步驟為：

算法1

有了算法1，就可以給出求解問題(1)的算法2如下：

算法2(FNTR)

(16)

的最小的非負整數，令αk=λik，xk+1=xk+αksk．

其中，

轉第2步驟．

對算法2的收斂性，首先給出以下假設：

(H1)f(x)在有界閉集H={x|f(x)≤f(x0)}上二階連續可微;

(H2) 算法2產生的序列包含在H中;

證明由Bk+1=χ(xk+1)I和說明(1)很容易得到．

引理2[20]若假設(H1)、(H2)、(H3)成立，sk是子問題(8)的解，則有

(17)

引理4若{xk}是由算法2產生的，則對任意的k有

fk+1≤Dk+1≤Dk

(18)

證明由Dk的定義知Dk+1-fk+1=η(Dk-fk+1)．

現在考慮3種情況：k∈T，k∈S，k∈A．

第1種情況：k∈T.

所以Dk+1-fk+1=η(Dk-fk+1)>0，即Dk+1>fk+1，又因

Dk+1-Dk=(η-1)Dk+(1-η)fk+1=

(1-η)(fk+1-Dk)≤0,

即有Dk+1≤Dk，所以當k∈T時結論成立．

第2種情況：k∈S.

由濾子的定義知fk+1≤fk.若k-1∈T，則有fk≤Dk≤Dk-1，從而有

Dk+1=ηDk+(1-η)fk+1≤

ηDk-1+(1-η)fk=Dk,

即Dk+1≤Dk，又因

Dk+1-fk+1=η(Dk-fk+1)≥

η(fk-fk+1)≥0，

即fk+1≤Dk+1，所以有fk+1≤Dk+1≤Dk．

若k-1∈S，令M={i|1

下面用數學歸納法證明Dk+1≤Dk.

因f0=D0，所以k=1時有

D1=ηD0+(1-η)f1≤

ηf0+(1-η)f0=f0=D0.

假設k=n時，有Dn+1≤Dn下證k=n+1時有Dn+2≤Dn+1，而

Dn+2=ηDn+1+(1-η)fn+2≤

ηDn+(1-η)fn+1=Dn+1,

所以Dk+1≤Dk成立.

再證fk+1≤Dk+1，因Dk+1-Dk=(η-1)Dk+(1-η)fk+1=(1-η)(fk+1-Dk)，而由上面的證明可知Dk+1≤Dk，又(1-η)>0 ，所以有(fk+1-Dk)≤0，即fk+1≤Dk，從而有

Dk+1=ηDk+(1-η)fk+1≥

ηfk+1+(1-η)fk+1=fk+1.

如果M≠Φ，設m=min{i|i∈M}，則有fk+1≤fk≤…≤fk-m+1，因k-m∈T，由第一種情況可知fk-m+1≤Dk-m+1≤Dk-m，而

Dk-m+2=ηDk-m+1+(1-η)fk-m+2≤

ηDk-m+(1-η)fk-m+1=Dk-m+1,

由歸納法可得Dk+1≤Dk，同上可得fk+1≤Dk+1．

綜上可得當k∈S時，有fk+1≤Dk+1≤Dk．

第3種情況：k∈A.

即Dk>fk+1,所以Dk+1-fk+1=η(Dk-fk+1)>0，

即Dk+1>fk+1，而

Dk+1-Dk=(η-1)Dk+(1-η)fk+1=

(1-η)(fk+1-Dk)<0,

則有Dk+1≤Dk,

所以有fk+1≤Dk+1≤Dk．

綜合上面3種情況可知，對任意的k都有fk+1≤Dk+1≤Dk．

引理5若假設(H1)、(H2)、(H3)成立，則存在常數M>0，使得對任意的k有

(19)

證明由假設(H1)可知gk和2f(x)是一致有界的，即分別存在Mg>0和Mf>0使得對任意的k有和再由Taylor展式可得：

(20)

(21)

因fk有界，故Dk有界，所以有

(22)

(23)

由引理4知{Dk}單調下降，又{Dk}有界，故其收斂，再由引理3和引理6得

又由Dk+m+1的定義知Dk+m+1是fk+1，fk+2，…，fk+m+1的凸組合，因此有

定理4若假設(H1)、(H2)、(H3)成立，算法2產生的點列{xk}收斂于x*，2f(x*)正定，2f(x)在x*的鄰域內Lipschitz連續，其中，Lipschitz常數為L，如果有

(24)

(25)

0

從而

又

所以

因此

2 數值試驗

表1 檢驗函數對應編號

表2 算法2(FNTR)和算法(TR)、算法(FilterTR)、算法(CRFTR)的數值結果

續表2

3 結束語

從表2的數據可以看出，算法2(FNTR)與算法(TR)相比，對于函數Penalty Ⅰ，Penalty Ⅱ，Variably，Broyden tridiagonal的高維情況，后者失效，且對于函數Broyden banded，后者無法求解，而算法2(FNTR)在這些函數上都有出色的表現，說明算法2(FNTR)的構造是可行的.算法2(FNTR)與算法(FilterTR)相比，對于函數Box 3-D，Osborne 2，Penalty Ⅰ，Penalty Ⅱ和Broyden banded，后者基本上無法求解，對于函數Variably，Broyden tridiagonal和Linear full rank的高維情況，后者基本失效，而前者卻可以很好的求解，并且在其它函數的數值表現上，算法2(FNTR)也有很大的優勢，說明對于大多數測試函數，錐模型與濾子方法的結合在數值表現上具有優勢.算法2(FNTR)與算法(CRFTR)相比，在函數Gaussian，Box 3-D，Osborne 2，Penalty Ⅰ，Penalty Ⅱ的數值表現上，前者具有明顯的優勢，在函數Jensam，Gulf，Discrete integral，Broyden tridiagonal，Linear full rank的數值表現上，兩者同樣優秀，而在函數Variably， Broyden banded的數值表現上，前者稍顯不足，說明在在信賴域方法框架下，線搜索、錐模型、非單調、自適應以及濾子等技術是可以混合使用的.上述結果表明本文提出的算法2(FNTR)是可靠有效的．

[1] Davidon W C. Conic approximation and collinear scaling for optimizers[J]. SIAM Journal on Numerical Analysis， 1980， 17:268-281．

[2] Sorensen D C.The Q-superlinear convergence of a collinear scaling algorithm for unconstrained optimization [J].SIAM Journal on Numerical Analysis， 1980， 17:84-114．

[3] Ni Q. Optimization conditions for trust-region subproblems involving a conic model [J]. SIAM J Optim， 2005， 15:826- 837．

[4] Qu Shaojian， Jiang Suda.A trust-region method with a conic model for unconstrained optimization[J]．Math Meth Appl Sci， 2008， 31:1780-1808．

[5] Sun W Y, Yuan Y X.Optimization Theory and Methods[M]. New York：Springer, 2006.

[6] Di S S. Stregion method for conic model to solve unconstrained optimization [J]. Optim Methods Softw， 1996， 6:237-263．

[7] Grippo L， Lampariello F， Lucidi S. A nonmonotone line search technique for Newton’s method[J].SIAM Journal on Numerical Analysis， 1986， 23(4) :707-716．

[8] Deng N Y， Xiao Y， Zhou F J. Nonmonotone trust region algorithm[J]. Journal of Optimization Theory and Applications，1993， 76 (2) :259-285．

[9] Zhang H， Hager W W. A nonmonotone line search technique and its application to unconstrained optimization[J].SIAM Journal on Optimization， 2004， 14(4):1043-1056．

[10] Mo J， Liu C， Yan S. A nonmonotone trust region method based on nonincreasing technique of weighted average of the successive function values[J].Journal of Computational and Applied Mathematics， 2007， 209(1):97-108．

[11] Gu Nengzhu， Mo Jiangtao.Incorporating nonmonotone strategies into the trust region method for unconstrained optimization[J].Computers and Mathematics with Applications， 2008， 55(9):2158-2172．

[12] Sartenaer A. Automatic determination of an initial trust-region in nonlinear programming [J]. SIAM Journal on Scientific Computing， 1997， 18(6):1788-1803．

[13] Fan J Y， Yuan Y X. A new trust region algorithm with trustregion radius converging to zero[C]//Proceedings of the 5th International Conference on Optimization:Techniquesand Applications，Hongkong， Dec， 2001．

[14] Zhang X S， Zhang J L， Liao L Z. An adaptive trust method and its convergence [J].Computers and Mathematics with Applications， 2003， 45(10-11):1469-1477．

[15] Sang Zhaoyang， Sun Qingying. A self-adaptive trust region method with line search based on a simple subproblem model[J].Journal of Computational and Applied Mathematics， 2009， 232(2):514-522．

[16] Fletcher R，Leyffer S. Nonlinear programming without a penalty function [J].Mathematical Programming， 2002， 91(2):239-269．

[17] Gould N I M， Sainvitu C. Toint P H L.A filter-trust-region method for constrained optimization[J].SIAM Journal on Optimization， 2005， 16(2):341-357．

[18] 孫文瑜， 徐 東. 解無約束最優化的基于錐模型的過濾集-信賴域方法[J].中國科學， 2012， 42(5):527-543．

[19] 諸梅芳， 薛 毅， 張鳳圣. 錐模型的擬NEWTON型信賴域方法[J].高等學校計算學報， 1995， 17:36-47．

[20] Qu Shaojian， Zhang Kecun， Zhang Jian. A nonmonotone trust-region method of conic model for unconstrained optimization[J]. Journal of Computational and Applied Mathematics. 2008， 220:119-128．

[21] 馮 琳， 段復建， 和文龍. 基于簡單二次函數模型的濾子非單調信賴域方法[J].山東大學學報:理學版， 2012(5):1-8．

[22] 袁亞湘， 孫文瑜. 最優化理論與方法[M].北京:科學出版社， 1997．

[23] 繆衛華， 孫文瑜. 一個解無約束優化問題的過濾信賴域方法[J].高等學校計算數學學報， 2007， 29(1):88-96．

[24] 葛恒武. 無約束優化問題的錐模型回溯過濾信賴域算法[J].蘇州大學學報:自然科學版， 2010, 26(2):8-11．

[25] More J J， Garbow B S， Hillstrom K E. Testing uncontrained optimization software[J]. ACM Trans Math Softw， 1981， 7(1):136-140．

Nonmonotone adaptive trust-region algorithm with a conic model for unconstrained optimization

WANG Kairong， ZENG Liushuan

(College of Mathematics and Statistics， Chongqing University， Chongqing 401331)

A non-monotone filter trust-region algorithm is proposed based on a conic model for solving unconstrained optimization. Firstly, a new method for solving the sub-problem is proposed in this paper; then a new algorithm is put forwarded. In the algorithm, a self-adaptive technology is employed to avoid the blind updating of the trust region radius; a filter-set technique and a new non-monotone technique is also introduced，and then a step size is obtained making use of non-monotone Armijo line search rule，thus a new iterative point is achieved. The global convergence of this new algorithm is shown under certain conditions. Finally, the numerical experiments are carried out to demonstrate the effect of our algorithm.

unconstrained optimization; nonmonotone trust-region algorithm; self-adaptive; filter; global convergence

2014-06-27.

重慶市高等教育教學改革研究項目(102104).

1000-1190(2015)02-0171-08

O221.2

A

*通訊聯系人. E-mail: zengliushuanxi@163.com．