一类带有二阶线搜索的非单调信赖域算法

冯 琳,段复建

(桂林电子科技大学数学与计算科学学院,广西桂林541004)

1 引 言

对于无约束最优化问题：

其中 f(x)连续可微且有下界,Rn是Euclidean空间,信赖域算法是一种良好的数值计算方法,许多数学工作者对它进行了研究,并在一定条件下分析了其全局收敛性和超线性收敛性,但为了保证算法的全局收敛性,大多数算法是单调算法,即要求在迭代过程中目标函数值单调递减[1,2,3-6].数值试验表明当迭代进入弯曲细长的峡谷时,单调算法的有效性会大大降低,于是非单调算法引起了学者们的注意.Grippo[7,8]等首先为求解无约束最优化问题的牛顿法提出了一种非单调线搜索技术,其用于产生非单调性的参考函数值是 fl(k)max f(k-j),其中0≤j≤m(k),m(k)=min(m(k-1)+1,M)(k≥1),M为一与迭代无关的非负整数,m(0)=0,这种算法也就是在某一步后,每试探一步,都要把当前点的函数值与前固定(如M+1)个点中函数值最大的进行比较.数值试验表明非单调算法在一定程度上优于单调算法[9,10].由于非单调算法的有效性,许多学者尝试把非单调技术应用于信赖域算法中,提出了许多非单调信赖域算法,并且数值试验表明了算法是有效的[11-16].随着非单调算法研究的深入,柯小伍[17]等提出了一种不同于Grippo[7]等的非单调技术的非单调信赖域算法,其用于产生非单调性的参考函数值是 fl(k)max f(k-j),其中0≤j≤m(k),m(k)=min(m(k-1)+1,Mk) (k≥1),Mk为一与迭代有关的非负整数变量,m(0)_=0,该算法也就是在某一步后,每试探一步,都要把当前点的函数值与前不固定 (如 Mk+1)个点中函数值最大的进行比较,而且Mk可以进行调整.当目标函数的性态较好时,Mk减少甚至为零,即算法采用单调下降步;反之,Mk增大,即算法采用非单调下降步.数值试验表明了这种算法有利于找到全局最优解,加快收敛速度.信赖域算法有其优点,但其也存在着缺点：当不接受试探步时,须重解子问题,直到找到一个可被接受的试探步,得到下一个迭代点,这样计算量往往加大.线搜索方法在求得下一个迭代点时须较小的计算量[18-20].为使算法简便有效,Nocedal和 Yuan[1],Fan Jinyan等[21]、Sang Zhaoyang等[6]将信赖域算法和线搜索方法结合起来,提出了一种求解无约束最优化问题的信赖域算法：当不接受试探步时,沿着试探步的方向采用回溯线搜索,得到下一个迭代点,这样不重新求解子问题,减少了计算量.

本文基于文献 [17]的非单调技术和文献 [1]的思想提出了一种求解 (1)的带有新的非单调二阶线搜索的非单调信赖域算法：当试探步不被接受时,沿着试探步的方向采用新的非单调二阶线搜索求得步长,得到下一个迭代点,避免了重新反复地求解子问题,减少了计算量.并在适当的条件下分析了算法的全局收敛性.

2 算 法

其中 fk=f(xk),gk=▽f(xk),Bk∈Rn×n是对称矩阵,它是目标函数在点 xk处的 Hessian矩阵▽2f(xk)或其近似拟牛顿矩阵,Δk≻0是信赖域半径,‖·‖是 Euclidean范数.子问题的最优解或其近似最优解 xk称为试探步,它是目标函数在点 xk处的搜索方向.

本文所用的非单调二阶线搜索是基于Shi[22,23]线搜索的改进,其形式是：

求解 (1)的信赖域算法通常是在当前迭代点 xk处,由二次逼近构造如下的信赖域子问题：

其中 fl(k)=max f(k-j),0≤j≤m(k),m(k)=min(m(k-1)+1,Mk)(k≥1),Mk是一非负整数变量,m(0) =0,L≻0是常数,ρ∈(0],λk=max{sk,sβk,sβk2,…},β∈(0,1),

下面给出带有非单调二阶线搜索的非单调信赖域算法 (L N TR):

步骤0 给定 x0∈Rn,0＜ε＜1,τ∈(],B0∈Rn×n是对称正定矩阵,Δ0＞0,0 ＜μ1＜μ2＜1,η＞0,

步骤1 计算 gk,若‖gk‖≤ε,则终止,x＊=xk.否则转步骤2.

步骤2 计算 fk、Bk,近似求解子问题 (2),得试探步 wk.

步骤4 如果 rk≥μ1,则 xk+1=xk+wk.转步骤6.

步骤 5 求λk,使其满足(3),则 xk+1=xk+λkwk,Δk+1∈(0,γ1Δk],Mk+1=Mk+1. 转步骤 7.

步骤6 当 rk≥μ2时,Δk+1∈(Δk,γ2Δk],Mk+1=0; 当μ1≤rk＜μ2时,Δk+1=(λ1Δk,Δk],Mk+1=M.

步骤7 计算 gk+1,校正 Bk得Bk+1,Bkwk＞0时,Bk+1=Bk;否则,Bk+1=Bk+iI,其中 i是使Bk+1

正定的最小正整数,I是单位矩阵.Bk+1=◇Bk.转步骤1.

注:(1)子问题 (2)的近似解wk满足:

(2)如果 rk≥μ1,则 xk+1=xk+wk,称为成功的迭代.

如果 rk＜μ1,则 xk+1=xk+λkwk,称为非成功的迭代.

(3)[5]在非单调信赖域算法 (LNTR)中,当迭代成功且 k充分大时,有 f(xk+wk)=f(xk+1)≤fl(k)-μ1τ‖gk‖Δk.

(4)当M=0时,此算法为一般单调信赖域算法.

(5)当 Bk正定且‖-B-1kgk‖≤Δk时,可取 wk=-B-1kgk.

3 全局收敛性

为了分析算法的全局收敛性,先作出如下假设:

H1:水平集Ω={x|f(x)≤f(x0)}是有界闭凸集.

H2:g(x)在Ω上一致连续.

H3:{‖Bk‖}一致有界,即存在常数 H,使得‖Bk‖≤H,k是任意正整数.

H4:∃正常数c1,使得‖wk‖≤c1‖gk‖.

引理1 fl(k)≥fk.

引理2 非单调线搜索准则 (3)是合理的.

证明 由引理1知:

引理3 如果假设 H1成立,{xk}是算法LNTR产生的点列,则 {xk} ⊂Ω.

证明 用数学归纳法证明:k=0时,有 f(xk)≤f(x0),因此 x0∈Ω.

假设 {xi} ⊂Ω,i=1、2、3、…k,则 fl(k)≤f(x0),

故 f(xk+1)≤f(xk),因而有 f(xk+1)≤f(xk)≤fl(k)≤f(x0).

由 (1)、(2)知 xk+1∈Ω.

由以上知,{xk} ⊂Ω.

注: f(xk+1)≤fl(k).

引理4 如果假设 H1成立,则序列 {fl(k)}是非增数列且收敛.

证明 由 fl(k)的定义和 m(k+1)≤m(k)+1及 f(xk+1)≤fl(k)知:

引理5 如果 H1、H3、H4成立且算法LN TR有无穷次成功的迭代,则=0且 {f (xk)}收敛.

证明 证明和文 [11]方法相似.证明过程要用到 (4)和引理4.

定理 如果假设 H1—H4成立且算法LNTR有无穷次成功的迭代,则lxi→m∞inf‖gk‖=0

证明 假设结论不成立,则存在常数ζ＞0,对∀k,有‖gk‖≥ζ.

4 结 语

本文提出了一个带有新的非单调二阶线搜索的非单调信赖域算法.这种算法在理论上比一般的信赖域算法计算量小[24,25],并且能加快收敛速度,有利于找到全局最优解.在一定的条件下建立了算法的全局收敛性.其非单调技术对于优化问题的处理是有效的,它可以推广到非二次模型的情形和其他优化问题诸如最大值问题等.

[1] Nocedal J,Yuan YX.Combining trust region and line search technique[J].Advances Nonlin Prog,1998,153-175

[2] 柯小伍,韩继业.一类新的信赖域算法的全局收敛性 [J].应用数学学报,1995,18(04)：608-615

[3] Shultz GA,Schnabel RB,Byrd ARH.A family of trust-region-based for unconstrained minimization with strong global convergence properties[J].SIAM J Numer Anal,1985,22：47-67

[4] Powell MJD.On the global convergence of trust region algorithms for unconstrained optimization[J].Math Prog,1984,29：297-303

[5] Michael E,Gertz E.A quasi-Newton trust-region method[M].Berlin：Springer,Math Program,2004

[6] Gertz EM.Combination trust-region line-search methodsfor unconstrained optimization[M].San Diego：University of California,1999

[7] Grippo L,Lamperiello F,Lucidi S.A nonmontone line search technique for Newton’s method[J].SIAM J Num A-nal,1986,23：707-716

[8] Grippo L,Lamperiello F,Lucidi S.A truncated Newton method with nonmontone line search for unconstrained optimization[J].J Optim Theory Appl,1989,60：401-419

[9] Wen YS,Han JY,Sun J.Global convergenceof nonmontone descent methodsfor unconstrained optimization problems[J].J Appl Math Comput,2002,146：89-98

[10] Grippo L,Lamperiello F,Lucidi S.A nonmonnotonic line search technique for Newton’s method[J].Siam J Numer Anal,1986,23(04)：707-716

[11] Sun WY.Nonmontone trust region method for solving optimization problems[J].J Appl Math Comput,2004,156：159-174

[12] 姚升保,施宝昌,彭叶辉.一类带线搜索的非单调信赖域算法 [J].数学杂志,2003,23(03)：290-294

[13] Zhu ZW.A modified trust region algorithm[J].Optim Methods Software,2002,7：587-604

[14] 莫降涛,刘春燕,颜世翠.带有固定步长的非单调信赖域算法 [J].曲阜师范大学学报,2006,32(03)：30-34

[15] Mo JT,Zhang KC,Wei ZX.A nonmonotone trust region method for unconstrained optimization[J].Appl Math Comput,2005(171)：371-384

[16] 赵英良.一种新的非单调信赖域算法 [J].西安电子科技大学学报,1997,24(04)：486-491

[17] 柯小伍,韩继业.无约束最优化的一类非单调信赖域算法 [J].中国科学 (A辑),1998,28(06)：488-492

[18] 呙林兵.一种改进的记忆梯度算法及其全局收敛性 [J].河北北方学院学报：自然科学版,2009,25(03)：4-6

[19] Dennis JE,Schbenal RB.Numerical methods for unconstrained optimization and nonlinear equations[M].Englewood Cliffs：Prentice-Hall Inc,1983

[20] Hestens M.Conjugate direction methods in optimization[M].New York：Springer-Verlag,1980

[21] Fan JY,Ai WB,Zhang QY.A line search and trust region algorithm with trust region radius converging to zero[J].J Comput Math,2004,22(06)：865-872

[22] Shi ZJ,Shen J.Convergence of descent method with line search[J].J Appl Math Comput,2006,20(12)：239-254

[23] Shi ZJ.Convergence of quasi-Newton method with new inexact line search[J].J Math Anal Appl,2006,315：120-131

[24] 王希云,仝健.带有固定步长的非单调自适应信赖域算法 [J].应用数学,2009,22(03)：496-500

[25] Sang ZY,Sun QY.A self-adaptive trust region method with line search based on a simple subproble model[J].J Appl Math,2009(232)：514-522