您好,欢迎来到九壹网。
搜索
您的当前位置:首页无约束优化问题的非单调自适应信赖域算法

无约束优化问题的非单调自适应信赖域算法

来源:九壹网
维普资讯 http://www.cqvip.com 第24卷第1期 长沙交通学院学报 . Vo1.24 No.1 2 008年3月 JOURNAL OF CHANGSHA COMMUNICA ̄ONS UNIVERSITY Mar.2oO8 文章编号:1000—9779(2008)O1—0081一o4 无约束优化问题的非单调自适应信赖域算法 李树君 ,张红霞 (1.长沙理工大学数学与计算科学学院,湖南长沙410076; 2.中南大学数学科学与计算技术学院,湖南长沙410075) 摘要:对无约束优化问题提出一种非单调自适应信赖域算法,每次迭代充分利用当前的迭 代点包含的一次导数的信息自动产生一个信赖域半径.在一定的条件下,证明了该算法的收 敛性,并通过数值实验验证了该算法的有效. 关键词:无约束优化;自适应信赖域算法;非单调算法;全局收敛性 中图分类号:0221.2 文献标识码:A Nonmonotone adaptive trust-region method for unconstrained optimization problems LI Shu-jun ,ZHANG Hong—xia (1.College of Mathematics and Computing Science,Changsha University of Science and Technology,Changsha 410076,China; 2.School of Mathematical Science and Computing Technology,Centrla South University,Changsha 410075,China) Abstract:A nonmonotone adaptive trust region algorithm for unconstrained optimization is proposed.The trust radius in this method is automatically determined with first order information.Under certain conditions,the global convergence of the algorithm is proved and the numerical experiments show that the algorithm is effec— tire。 Key words:Unconstrained optimization;adaptive trust region algorihtm;nonmonotone algorihtm;global con— vergence 考虑无约束优化问题 minf(X). (1) 其中f:R 一R是二次连续可微函数.信赖域方法是一种迭代的方法,每次迭代要求计算信赖域子问题 mimp (d)=gTd+ ,s_t_ lI≤△ . (2) 其中g =Vf(x ),B 是近似于Hessian阵V )的对称矩阵,△ 是信赖域半径。 传统的信赖域算法都是根据实际下降量与预测下降量的比值,人为的按常数倍来调节信赖域半径, 完全没有利用当前迭代点 处g ,V X )等信息,初始信赖域半径也只是不加分辨的给出一个常量 基于此,许多自适应信赖域算法被提出 加 ,Sartenaer 提出了一个自动确定初始信赖域半径的ITRR 算法,Zhang[2]等提出了一种新的自适应信赖域算法信赖域半径选取机制为△ = ,其中。<c< 收稿日期:2007—10—21 作者简介:李树君(1980一),男,长沙理工大学硕士生。 维普资讯 http://www.cqvip.com

82 长沙交通学 院学报 第24卷 1, =rain… l,1}.之后,他fiLE提出△ = g kD暹 的信赖域选取机制 ],其中P为非负整数, 是 使得 =B + 是正定矩阵的最小非负整数.其他的自适应半径选取机制可参考文献[4—7].作者修 正了Li 提出的信赖域选取机制,该选取机制充分利用前面迭代点的信息,且不需要计算含 就能获得 个自适应的信赖域半径,与文献[2,3,5—7]相比,在一定程度上减少了算法的计算量,同时也避免了 文献[4]中当g =g ≠0时△ :。。的情形.结合自适应信赖技术和非单调的思想给出了求解问题式 一(1)的一种新算法. 1非单调自适应信赖域算法 通过求解信赖域子问题式(2)可以得到试探步d ,在此基础上,引入非单调的思想,定义 ( )= f(x姒)) m。 , ax  H),其中re(O):0,0≤m(尼)< ̄min{m(k一1)+1, },尼≥1,M是非负常整数・实 际下降量定义为Ared ̄=厂( m))一厂( +d ),预测下降量为Pred : (0)一 (d ).具体算法为: 步骤1 给定X0∈R“,Bo∈R “, >0,0<叼<1,0<A<1,M>0,令m(o)=0,i=0,尼::0. 步骤2若lI g lI≤ ,则终止算法. 步骤3 取△ =A min{可 l l'l I),求解信赖域子问题式(2)得到试探步 ,计 酋Ared ̄ 畀 .一Pred一‘ k步骤4若 ≥叼,则 = +d ,m(k+1):rain{m(k)+1,M};否则,i=i+1,转步骤2. 步骤5修正 , 0,尼:=k+1,转步骤2. 2算法的收敛性分析 假设1 H )对任意的k,存在有界闭集 使得 , ㈩∈ . ) )是一致连续的, )和 是一致有界的.即对Vk, K>0使得:ll ll<K成立,且II )ll<K也成立. 1[1。 。( )≥ I arin ). 引理2 Ared —Pre =0(J IlI ). 引理3非单调自适应信赖域算法是适定的,即该算法中步骤2和步骤4之间的内循环有限终止. 证明假设结论不成立,即该算法中步骤2和步骤4之间的内循环不有限终止.令k( )为 处第i 次内循环,则Fkff)≤叼, =1,2,…,而且△ ( ) , _÷。。. 又由引理1,2得: -Jl Pr ed 『“) l _ 0l (  )一 (d ( ))ll ≤。 lm0i(n△ , ) 而I g ̄I)… 故当i-- ̄oo时,I ( )一1 I ,即 ( )---+I,与 )≤叼<1矛盾.所以假设不成立,该算法是适定的. 引理4若假设1成立,则对v尼, 一Ck>0满足:一 ( )≥ lJ g II 2. 证明 由假设1和引理1得: ( ≥ 1 II arin }≥ min A ̄min{ ), )≥ 维普资讯 http://www.cqvip.com

第1期 李树君,等:无约束优化问题的非单调自适应信赖域算法 1 I lg I[2min{A min{ ,-), )≥ Il g l I・ 其中 = in{A min{1, },1},A 表示 处内循环结束时A的值・故引理4是成立的・ 引理5 引 If, }是单调非增且收敛的.  .定理1若假设1成立且 =O,则该算法要么有限终止于某个lI g lI=O,要么产生无穷点列,使 得: l帅infl Ig lI=O. ∞ 证明若结论不成立, ̄li.minf lI g lI≠o,则对任意后,存在 o>9使得l Ig lI≥ o.由引理4可知: Pre =一 ( )≥ Il lI ≥ in{A min{1, },1} >o・ (3) 由非单调自适应信赖域算法的步骤4和式(3)可得: f(xf(^))一f(x + ) ̄>-qPred ≥ in{A^min{1,tq,l} z>o・ 即 f(^)) + )+&in{A min{1, },1} ,故可得: ( + ))≤ ( ( )))一2 ̄anin{A ( )min{1, },1} ・ (4) 而{ ( )}是收敛的,故式(4)表明:Af(^) . 令d令f 是子问题式((^)是子问题式(2)在△ = =△f(^)= A÷Ajl(”^) min{ -i I)时的解.由 算法的机制可知: :—Ar edt( ̄)<'7.类似引理3中当i一∞时l r^㈤一1 l— 的证明,可得当z(后)一∞时 Pre d ( ) , 、, 、, 、 . ( 一1,则当k充分大时有 '7,这-- ̄r,(”<'7矛盾.故假设不成立,即有l nf lI g^lI=o. 3数值实验 由给出的非单调自适应信赖域算法对文献[11,12]中1O个模型的数值实验结果,实验中采用 BFGS修正曰 ,其他参数的取法为: =10~,田=O.75,A=O.15,m(O)=O.在表1中,给出了文献[9,1O] 中提供的模型名称,Ⅳ表示模型中变量的数量,f-iter和g-iter分别表示实验中目标函数及其梯度的迭代 次数, 表示非单调参数 表示按非单调自适应信赖域算法得到的目标函数的最优值. 表1数值实验结果 模型名称 Ⅳ M=0 M=5 .1 .1。 AIRCRFTB 6.821 4 X10一 6.022 0 X10一 ALUNITU 5.715 0 X10。 5.715 4 X 10。 BEALE 6.213 1 X10— 6.213 1 X10—15 BIGGS6 2.421 8 X10一 2.259 6 X10一 B0X3 6.955 9 X 10一 6.955 9 X10一 PENAI Y—I 2.500 0 X10一 3.665 1 X10-5 CHEBYQUA 7 1.450 2 X10-13 1.895 6 X10一“ 0SB0RNEA 22 4.013 8 X10— 4.013 8 X10‘ MANCIN0 100 3.497 0 X10— 8.659 1 X10-12 VARGIVAL 50 7.849 7 X 10。 7.126 5 X 100 维普资讯 http://www.cqvip.com

长 沙交通学院学报 第24卷 ] ] ]]] ] ]]) 三- 数值结果表明,非单调信赖域算法求解此类问题具有较高的效率,特别是在迭代次数和精度上较之 传统的信赖域算法具有更好的结果,数值实验表明算法是稳定、可行的. 参考文献: . [1]Sartenaer A.Automatic determination of an initial trust region in nonlinear programming[J].Journal on Scientific Compu. irng,1997,18(5):1 788—1 803. Zhang X S,Chen z W,Liao L z.A self-adaptive tusrt reion gmethod for unconstrained optimization[J].Operate Reserch Transactions,2001,5(2):53—62. Zhang X S,Zhang J L,Liao z.An adaptive tusrt egrion method and its convergence[J].Science in China"(Series A), 2002,45(4):620—631. 李改弟.一个自动确定信赖域半径的信赖域方法[J].工程数学学报,2006,23(5):843—848. 宇振盛,罗成新.带记忆信赖域方法的收敛性分析[J].运筹与管理,2004,13(2):16—19. Fu J H,Sun W.Nonmonotone adaptive trust-region method for unconstrained optimization problems[J].App ̄ed Mathe- matics and Computation,2005,163(5):489—504. Shi z J,Guo J HI A new tustr reion metghod for unconstrained optimization[J].Journal of Computational and Applied Mathematics,2007,22(6):126—128. 杨润生,李树君.一类优化问题的非单调信赖域算法[J].运筹与管理,2007,16(5):53—57. 袁亚湘,孙文瑜.最优化理论与方法[M].北京:科学出版社,1997. 陈小军,张1—7. 超.非线性方程组在几类计算问题中的应用[J].长沙理工大学学报(自然科学版),2006,3(4): Di S and Sun W.Trust region method of optimization problems[J].Optimization methods and model to solve uneon- strained software,1999,12(6):237—263. [12] More J J,Grabow B S,Hillstrom K E.Test unconstrained optimization software[J].ACM Transactions on Mathematical softwhre,1981,7(1):17—24. (上接第76页) 参考文献: [1]陈新.机械结构动态设计理论方法及应用[M].北京:机械工业出版社,1997 [2]Trench W F.Characterization and properties of matrices with generalized symmetry or skew symmety[J].Lirnear Algebra nd Itas Application,2004,377:207—218. [3]周富照.几类约束矩阵方程及其最佳逼近[D].长沙:湖南大学,2002. [4]彭振赞.几类矩阵扩充问题和几类矩阵方程问题[D].长沙:湖南大学,2003. [5] 伍华凤.一类约束矩阵方程问题和一类矩阵扩充问题[D].长沙:湖南大学,2006. 关于子矩阵约束下矩阵方程问题的研究[D].长沙:湖南大学,2006. [6] 龚丽莎.2005. [7] 彭亚新.求解约束矩阵方程及其最佳逼近的迭代法的研究[D].长沙:湖南大学,vability conditions for the inverse eigenvalue problems of eento‘symmetrric matrices [8] Zhou F Z,Hu X Y,Zhang L.The sol[J].Linear Algebra nd aIts Application,2003,364:147—160. ao A P.Bai Z Z.Least-square solution ofAXB=D over symmetirc positive semi-definite matirces [J].Journal fo Com [9] Liputafional Mathematics,2003,21(2):175—182. 2002,24(1):9—20・ [1O] 廖安平,白中治.矩阵方程A XA=D的双对称最小二乘解[J].计算数学,[11] [12] Xie D X,Sheng Y P,Zhang Z Z.Computing the nearest bisymmetric positive semi-definite matrix under the special re‘ 8triction[J].Numerical Mathematics,2003,12(1):71—82. 田兆禄,谭艳祥,刘仲云.中心对称M一阵的线性方程组的迭代解法[J].长沙交通学院学报,2005,21(2):1-4. 周富照.中心对称矩阵的左右逆特征值问题[J].长沙交通学院学报,2004,2O(2):1—6・ [13] 赵人可,lub G H.Matirx Computations[M].Baltimore:The Johns Hopkins University Press,1996・ [14] Go

因篇幅问题不能全部显示,请点此查看更多更全内容

Copyright © 2019- 91gzw.com 版权所有 湘ICP备2023023988号-2

违法及侵权请联系:TEL:199 18 7713 E-MAIL:2724546146@qq.com

本站由北京市万商天勤律师事务所王兴未律师提供法律服务