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

基于新锥模型的带固定步长的非单调自适应信赖域算法 朱帅 （太原科技大学应用科学学院,太原, 030024）中图分类号：221.2 文献标识码： A,其中二次连续可微. 传统的信赖域算法一般采用二次模型逼近,但对于一些非二次性态较强、曲率变化剧烈的函数,用二次函数模型逼近效果较差.为此,于1980年提出了锥模型方法.倪勤[2]提出了锥模型信赖域子问题的一种新可行集,后将形成的子问题称为新锥模型信赖域子问题.ShaoJian Qu和Ke Cun Zhang[3]等人提出了一类基于锥模型的非单调信赖域算法.最近,Ju-Liang Zhang、Xiang-Sun Zhang[4]提出了一种非单调自适应信赖域算法.另外,王希云、仝建[6]提出了一种带固定步长的非单调自适应信赖域算法.本文将带固定步长的信赖域算法应用到新锥模型信赖域算法中,提出了一种新的算法,数值试验表明算法是有效的. 算法 选取下面的子问题计算试探步： (1) 其中,为一个在0到1之间的正数,，为在处的梯度和分别是维向量和矩阵是信赖域半径时,子问题转换为 ⑵ 当时,子问题转换为 ⑶ 当时,子问题转换为 令 , (2) 其中,而定义为: (3) 其中,是常数. (4) 其中是非负整数.采用修正. 算法1 Step0 给定,,,令 其中是阶单位矩阵. Step1 计算,如果满足,则终止;否则转step2. Step2 用折线法[5]求解子问题(1)得近似解. Step3 依据(2)式计算. Step4 令 , Step5 利用公式(4)计算 Step6 令,更新[7]和[7]: 其中,.依据(3)式计算,转Step1. 全局收敛性 记:,. H1 水平集是有界的. H2 在上Lipschitz 连续. H3 序列,一致有界,即对有. H4 假设. 引理3.1[3] . 引理3.2 设H1?满足单调下降且收敛. 证明: (5) 由 所以 则 (6) 代入 因此,序列单调非增,由可知,所以收敛证毕满足: (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.5[4] 设H1-H4满足,则有 定理3.1 设H1-H4满足,则有: . (19) 证明:反证法.若和无限子列使得,令.,使得对于有,,由引理3.1知,有下式成立: . 这表明对于,, 这与引理3.4中(18)式矛盾, 故定理成立.证毕 超线性收敛性 下面,讨论本章算法的超线性收敛性,假设下面条件成立. H5 当充分大时