一种非单调自适应信赖域法 A Nonmonotonic Self-Adaptive Trust Region Algorithm

doi:10.12677/PM.2013.35048

设为首页加入收藏期刊导航网站地图

期刊菜单

文章导航

Pure Mathematics 理论数学, 2013, 3, 312-316

http://dx.doi.org/10.12677/PM.2013.35048 Published Online September 2013 (http://www.hanspub.org/journal/pm.html)

A Nonmonotonic Self-Adaptive Trust Region Algorithm*

Dan Hang, Xiaoyan Wang, Jianzhong Hao, Ya Wang

Department of Basic Education, Air Force Logistics College, Xuzhou

Email: hazel-hang@sohu.com

Received: Jun. 18th, 2013; revised: Jul. 24th, 2013; accepted: Aug. 3rd, 2013

permits unrestricted use, distribution, and reproduction in any medium, provided the original work is properly cited.

Abstract: We propose an improved nonmonotonic trust region algorithm. Our method is to use the non-

monotone technique and if the trial step is rejected, the stepsize is computed by a fixed formula. The trust re-

gion radius is updated at a variable rate. Numerical experiment results show that the new algorithm is effec-

tive. Under mild conditions, we prove that the algorithm is global convergence.

Keywords: Unconstrained Optimization; Trust Region; Fixed Stepsize; Nonmonotonic Technique; Global

Convergence

一种非单调自适应信赖域法*

杭丹，王晓燕，郝建忠，王娅

空军勤务学院基础部，徐州

Email: hazel-hang@sohu.com

收稿日期：2013 年6月18日；修回日期：2013 年7月24 日；录用日期：2013年8月3日

摘要：求解无约束优化问题，本文给出了一种改进的非单调信赖域算法。采用了非单调技术，当试

探步不被接受时，下一步的迭代步长由一个固定公式给出。并直接给出调整信赖域半径公式。数值试

验结果表明新算法的有效性。在适当的条件下，证明了算法的全局收敛性。

关键词：无约束最优化；信赖域；固定步长；非单调技术；全局收敛性

1. 引言

求解无约束优化问题：





min

 (1)

其中



xR R是二阶连续可微的函数,信赖域方法是解决问题(1)一类有效的迭代方法，而且保证了很强的

收敛性。在每个迭代点 k

，通过解如下的子问题产生一个试探步：



min 2

dgd dBd



 K

(2)

s.t. k



 (3)

其中 k

是目标函数在当前点 k

处的梯度。为精确Hessian 阵或其近似



是信赖域的半径。

*基金项目：安徽省教育厅自然科学研究项目(编号：KJ2012B125)，安徽省高等学校省级优秀青年人才基金项目(编号：2012SQRL155)。

312

杭丹等  一种非单调自适应信赖域法

d是子问题(2)~(3)的一个精确或近似解，得到后计算比率：











Are

Pre (0)

kkkkk

xfxd

rdd





  (4)

检验试探步是否被接受，然后信赖域半径



根据值调整。对于传统的信赖域方法，信赖域半径



在

给定的比率下调整，然而，HEI LONG[1]中提出了自适应信赖域方法，其中 k



根据的一个函数值进行调整，

数值结果显示是有效的。本文在其启示下，改进 Hei Long[1]中调整信赖域半径的公式即采用







12kc



 k

公

式进行调整信赖域半径；同时采用了非单调技术，且当试探步不被接受时，不再重解子问题，而是通过一个

固定的公式1

kkk

dBd



 d



直接得到下一个迭代点。数值试验表明，这样做大大减少了计算量。在适当的

条件下，证明了新算法的全局收敛性。

2. 算法[2]: 算法中的选取有多种方法(如文[2]-[4]).

定义 1设一维函数定义在，其中







,R





0,1



，







是R-函数当且仅当它满足：

1) 在



不是下降的；







, 



lim

tRt





 ，其中是小常数；



10, 1









1Rt





 ，对所有 t



，这里





0,1 1





是一常数；



1Rt





 ，其中是一常数；



20,









lim

tRt





，其中是一常数。





 



定理 2 R-函数







(其中





0,1



)满足：









011,Rt t







 

，

。求解子问题(2)~(3)获得试探步满足下面条件：



11 ,Rt t



 











 







0min,

kkk kkg

dg gB



  k

(5)





min ,

kkkkgk

dggg B  (6)

其中是一个常数。采用非单调技术，设



0, 1



 











0max kj

lklk jmk

ffx fx





 这里，



00m

 



min1 1,mkmk M





，M是一个非负整数。故获得试探步实际下降量，由(4)计

算比率，检验试探步是否被接受，当试探步不被接受时，不再重解子问题，而是用固定公式直接给出步长





Are kk

df fxd 

kkkkk

kkk

xdx d

dBd





 ，然后信赖域半径 k



根据值调整。

算法：

步0。给定0001112 22

,,0,0, 01, 01,0,1xB





 



0cc，1



，，

。置

0M



0,1 ,0,



1







0, 00km



。

步1。计算



gx。如果 k



，则终止。否则计算。



klk

Bf和

步2。解子问题(2)~(3)使满足(4 )~(5)。

步3。计算，，和

Are k

dPre k

dAre

Pre

。

步4。如果，转Step 5。否则计算

rc

kkk

dBd





 ，置 1,

kkkk







转Step 6。

步5。置 1kkk

。步 6。





12kck



 

。置













1min1, ,1mkmkM kk,



转Step 1。

注：我们注意到在[1]中信赖域半径由





12 2

kckk

Rrd



 确定。但当很小时会造成下一步迭代的信赖域半

杭丹等  一种非单调自适应信赖域法

314

径太小，使下一步试探步长过小，影响算法的效率.因此在我们的算法中采用



12kck





公式进行迭代来避

免这种缺陷。事实上，后面的数值试验也验证了这种修改的有效性。

3. 收敛性

假设 1。1) 函数



x在是即存在

LC 0



有









,xgyx



y,n

yR

，其中









xfx (7)

2) 给定 0

属于，水平集





Rfx fx 是紧集。

3) 矩阵正定且存在实数



使得

dBd dd



n

dR 0,1,k



 (8)

定义两个指标集：



kr c





kr c

。

引理 2[3]假设



是由算法产生的序列.如果假设3.1 满足且有





0, .





 (9)

则











112,

lk kk

xf gdk

 

 J

(10)

引理 3[3] 算法产生的序列 k

定义在。如果假设3.1 和(8)成立，则





是下降的。

引理 4 如果假设 3.1 和(9)满足，且存在 0



使得对所有的有k







，那么存在一个常数0



有



 0, 1,k

这里 k

定义为

max 1





。 (11)

证明：令



12c





 ，由



x是一致连续的，对任意0k



，





0, 1



，k



有



 

121

kkkk kkkk

dfx dfxdcdcd





 

 2



(12)

用归纳法证明(11)成立。设









0010121

min,,, 1MM c













 (13)

当由(13)知0,k



 即(11)对成立。假设(11)对k成立，因

0kk

递增，只要证明：

1kk







 (14)

当时，由

rc





kck

Rr 

知1kk



k

 ，故(14)成立。 

当时，知

rc11kk





 如果 k



，则 111110kkk k

dMM





 k

。

设2



，得



















202

kkk kkkkkkk

fxdfcdc gddBd



  (15)



 



TTTT

kkkkkk kkkkkkk

f xdfgdgdggdgddgdcd

 

 2 (16)

其中





kkkkkk

dxxd



 。根据(14)和(15)，得到







kkkk kk

cgd dcdBd





(17)

此外，由(5)和k



得到

杭丹等  一种非单调自适应信赖域法





2min,

kk kkkkk

ddBd B



  (18)

上式两边乘与(17)相加得到

1c





















222

21min ,11min ,

1min,2

kkkkkk kkk kk

kkk

BdBdcBcc B

 



 

  (19)

于是









1min1,2

kk k

BcB



 1 (20)

若kk



，则





，否则 kk





，因而由(16)有









min 1,

Bc 1





 ， (21)

于是 11kkk

 



 k

。

定理 5如果假设 1和(9)满足，同时





B满足







 (22)

这里

max 1



，则由算法产生的序列





x ，且满足

inf 0

lim k





(23)

证明：假设(23)不成立，则存在 0



使得对任意均有



。当 kI



时，由(4)和(6)得到



















11 1

0min

kkkkk

ffxcdcB





 ,

(24)

当时，由(6)和(10)得到 kJ

























112 12min,

kkk

lk kk

fx gdB

 



 (25)

令







min,12c







，则由(24)和(25)得到对任意 k都有











1min ,

lk k

fx B





 (26)

由引理 3知对任意均有





min ,





M (27)

其中



min , .





由递减及(26)和(27)知，对



f0,1, ,



，均有

 





min ,

ksk ks ksks

lklk s

fffB fM

 

 



 

(28)

根据引理 2和k

递增知



 

111

max: 0

kskM kMkM

ffsMMfM

 

 



(29)

再根据假设 1和引理 2，即是单调下降且收敛的故由(29)得



 



 



 



101

kM lklk M

lk slk slklk

ks k

Mff

ffM ff



 



 



 

 







 

(30)

显然(30)和(22)矛盾，定理得证。

杭丹等  一种非单调自适应信赖域法

316

4. 数值结果

本节中，算法用[5]的标准无约束优化问题测试。使用和[5]同样的编号。此外，假设，系数的选择

为：。

BH

12 12

10 ,0.01,0.25.0.1,5,0.1cc









0.15,10M





。

其中用表示问题的维数，用ng 表示梯度迭代次数，nf 表示函数值的迭代维数，表示最终的函数值，L

是标准初始点的常用对数因子，即，如果

是标准初始点，则实际的初始点为10 0



.算法与黑龙[1]进行比较.

结果在表 1中，可以发现我们的算法更有效。

Table 1. Numerical results

表1. 数值结果

本文算法(M = 10) 文[2]算法

NO. n L

nf ng f nf ng f

8 50 0 34 34 4.3179e−004 46 46 4.3179e−004

100 0 37 37 9.0249e−004 47 47 9.0249e−004

200 0 41 41 0.0019 53 53 0.0019

14 50 0 16 15 2.1526e−022 27 27 0

100 0 15 14 7.11102e−023 27 27 0

200 0 19 17 0 27 27 0

参考文献 (References)

[1] Long Hei, A self-adaptive trust regional gorithm, Journal of Computational Mathematics, 2003, 21: 229-236.

[2] J. Nocedal, Y. Yuan, Combing trust region and line search techniques. In: Y. Yuan, Ed., Advances in Nonlinear Programming, Kluver:

Springer, 1998: 153-175.

[3] J. T. Mo, K. Zhang and Z. X. Wei. A nonmonotone trust region method for unconstrained optimization. Applied Mathematics and Computation,

2005, 171(1): 371-384.

[4] L. Grippo, F. Lampariello and S. Lucidi. A nonmonotonic line search technique for Newton’s method. SIAM Journal on Numerical Analy- sis,

1986, 23(4): 707-716.

[5] J. J. Mor, B. S. Garbow and K. E. Hillstrom. Testing unconstrained optimization software. ACM Transactions on Mathematical Software, 1981,

7(1): 17-41.