基于新锥模型的带固定步长的非单调自适应信赖域算法.doc

基于新锥模型的带固定步长的非单调自适应信赖域算法朱帅基金项目：山西省自然科学基金（2008011013）作者简介：朱帅（1980），男，硕士，研究方向为非线性规划。 赵绚2 王希云3（1.山西大同大学工学院,山西大同,037003；2，3.太原科技大学应用科学学院,山西太原, 030024）摘要：本文对无约束优化问题提出了一类基于新锥模型的带固定步长的非单调自适应信赖域算法.利用文6提出的固定步长算法,在适当的条件下,证明了此算法的全局收敛性和超线性收敛性.关键词：无约束优化；非单调技术；自适应信赖域算法；固定步长；新锥模型中图分类号：O221.2 文献标识码： A1. 引言考虑无约束优化问题: ,其中二次连续可微.传统的信赖域算法一般采用二次模型逼近,但对于一些非二次性态较强、曲率变化剧烈的函数,用二次函数模型逼近效果较差.为此,于1980年提出了锥模型方法.倪勤2提出了锥模型信赖域子问题的一种新可行集,后将形成的子问题称为新锥模型信赖域子问题.ShaoJian Qu和Ke Cun Zhang3等人提出了一类基于锥模型的非单调信赖域算法.最近,Ju-Liang Zhang、Xiang-Sun Zhang4提出了一种非单调自适应信赖域算法.另外,王希云、仝建6提出了一种带固定步长的非单调自适应信赖域算法.本文将带固定步长的信赖域算法应用到新锥模型信赖域算法中,提出了一种新的算法,数值试验表明算法是有效的.2. 算法选取下面的子问题计算试探步： (1)其中,为一个在0到1之间的一个正数,，为在处的梯度,和分别是维向量和矩阵,是信赖域半径.由文献2我们知道,上述问题可以分成如下三种情况考虑: 当时,子问题转换为 当时,子问题转换为 当时,子问题转换为令, (2) 其中,而定义为: (3)其中,是常数. (4)其中是非负整数.采用修正.算法1 Step0 给定,令其中是阶单位矩阵.Step1 计算,如果满足,则终止;否则转step2.Step2 用折线法5求解子问题(1)得近似解.Step3 依据(2)式计算.Step4 令 ,Step5 利用公式(4)计算 Step6 令,更新7和7: 其中,.依据(3)式计算,转Step1.3. 全局收敛性记:,.H1 水平集是有界的.H2 在上Lipschitz 连续. H3 序列,一致有界,即对有.H4 假设.引理3.13 .引理3.2 设H1满足,则单调下降且收敛.证明: (5)由(3)式有 所以 则 (6)代入(5)得 因此,序列单调非增,由H3.1可知,所以收敛.证毕引理3.34 设H3满足,则满足: (7)引理3.4 设H3和 H4满足,则有: . (8)证明:当时,由H4知(8)成立.当时,根据Step4,知: ,由于, 所以. (9)对于, 若, 则由上式得: (10)根据引理3.2,单调下降且收敛,因此 (11)若的情况由H4可得引理结论.根据(10)和引理3.3得:其中.由(11)式知:. (12)由引理3.2知:. (13)令,由数学归纳法,可得:, . (14)采用推导(12)式和(13)式的方法可得(14)式对于有. (15)由,所以有: (16)由的连续性,可得:. (17)又由式,两边取极限可得:. (18)所以有.结合假设H3.4, 对, 有.证毕. 引理3.54 设H1-H4满足,则有 定理3.1 设H1-H4满足,则有:. (19)证明:反证法.若和无限子列使得,令.,使得对于有,由引理3.1知,有下式成立:.这表明对于, 这与引理3.4中(18)式矛盾, 故定理成立.证毕4. 超线性收敛性下面,讨论本章算法的超线性收敛性,假设下面条件成立.H5 当充分大时,矩阵是可逆的,若,则本算法中.H 6 成立.定理4.1 若H1-H6成立,算法产生的序列收敛于, 且 正定,在的邻域内Lipschitz连续,则序列 超线性收敛于 .证明: 根据H5,当充分大时, 因为,所以 且有界，所以有所以当充分大时 (20) 令 由引理3.5可得 (21)则由(20)、(21)式得. (22)所以. (23)由引理3.1, 有. (24)由式(23)和式(24)知,当充分大时.因此,算法退化为拟牛顿算法,根据文8中定理5.5.1得:算法产生的序列超线性收敛于.证毕5. 数值试验本节我们对以下三个函数进行了数值试验,在相同的条件下与文献6中的算法2进行了比较,在Matlab7.0环境下编制程序,试验结果见表1.参数选择如下:.终止条件为:.例1 Rosenbrock function例2 Extended rosen brock function；例3 Extended powell singular function；说明:表1中,分别表示函数值和梯度值的迭代次数.n表示问题的维数. Problem表示所选择的测试函数,表示试验所求得的最优值,运行时间为CPU(单位为秒).表1 数值试验结果比较Teb1 The numerical results of the comparison of the two algorithmsproblemn算法1算法2CPUCPURosenbrock function2871.0314e-0180.078019192.2540e-0180.0560Extended rosen brock function20991.5106e-0140.078050503.3940e-0130.149540884.2921e-0140.063069692.2621e-0130.25308010102.7925e-01207812e-040.2983100993.2764e-0140.0780#20016163.1982e-0140.4060#100032325.7262e-010116.2660#Extended powell singular function2020202.1364e-0140.235033330.1855e-0130.58408020202.2245e-0130.219056562.2583e-0130.468020042426.1538e-0130.10601021034.6685e-072.4156数值结果分析:本文在文献6的基础上改用新锥模型对原问题进行逼近求解,针对上三个代表性的函数，从表1的数值结果可以看出,无论从迭代次数上，还是从计算结果上以及运行时间上比较,都较有很大的改进,因此基于新锥模型的带固定步长的信赖域算法在解决某些问题上式很有效的一种算法,特别是对于非二次性态强的函数有很好的试验结果.另外,我们在进行数值试验的过程中发现,固定步长的计算公式中的选取对试验结果影响很大,所以我们认为如何选取更能改进算法的试验结果是值得进一步深入研究的. 参考文献:1 Davidon WC. Conic approximation and collinear scaling for optimizers. SIAM J. Number. Anal,1980,17:268-2812 Ni Q. Optimality Conditions for trust-region subproblems involving a conic model. SIAM J. Optim.,2005,15(3):826-8373 Shao-Jian Qu,Ke-Cun Zhang, Jian Zhang.A nonmonotone trust-region method of conic model for unconstrained optimization.Journal of Computational and Applied Mathematics.2007,64 Ju-Liang Zhang,Xiang-Sun Zhang, Jian Zhang.A nonmonotone adaptive trust region method and its coonvergence.Computers and Mathematics with Applications 45(2003)1469-14775 陆晓平,倪勤,刘浩.解新锥模型信赖域子问题的折线法J.应用数学学报, 2007,(05)6 王希云,仝建.带有固定步长的非单调自适应信赖域算法M.应用数学,2009,22(3):496-5007 诸梅芳,薛毅,张凤圣.锥模型的拟NEWTON 型信赖域方法.高等学校计算学学报,1995,17:36-478 袁亚湘,孙文瑜.最优化理论与方法M.北京:科学出版社,1997,263-365A Nonmonotone Self-adaptive Trust Region Algorithm withFixed Stepsize Based on the New Conic ModelZHU Shuai 1 ZHAO Xuan 2 WANG XI-Yun3 (1. Shanxi Datong University Institute of Technology, Shanxi Datong, 037003; 2,3. Taiyuan University of Technology, Applied Science, Shanxi, Taiyuan, 030024) Abstract：A new nonmonotonic self-adaptive trust region method with fixed stepsize for unconstrained optimization problems is presented. Use of the algorithm based on literature 6.When the trial step is not accepted,the next iterative point is got by fixed step. The global and superlinear convergence is proved under certain co