基于简单二次函数模型的求解无约束规划问题的信赖域算法

1基于简单二次函数模型的求解无约束规划问题的信赖域算法孙清滢,刘秋中国石油大学数学与计算科学学院，山东，东营257061王长钰曲阜师范大学(日照校区)运筹与管理学院山东日照276826摘要基于简单二次函数模型，建立了一个求解无约束规划问题的新的信赖域算法，证明了算法的全局收敛性。数值例子表明算法是有效的，适合求解大规模问题。关键词：无约束最优化；信赖域算法；收敛性；数值实验中图分类号：O221.21.引言考虑无约束最优化问题)(minxfnRx（1）其中)(xf是连续可微函数。众所周知，信赖域算法[1~4]是求解问题（1）的重要算法，具有较强的全局收敛性质和较快的局部收敛速度。信赖域子问题的求解是信赖域算法的一个关键问题，算法的工作量大部分集中在子问题的求解上。通常的信赖域子问题基于如下二次模型：kkTTkkkstssBssgxfsq..21)()(min（2）其中kxxs，)(kkxfg是目标函数)(xf在当前点的梯度。kB是目标函数)(xf在当前点的Hesse矩阵或其近似。0k是信赖域半径。为某一范数，通常采用2-范数。易见，求解问题（2）之困难在于kB是一个一般的实对称矩阵，如果kB是一个实对称正定对角矩阵，则可以较方便求出子问题（2）的最优解。即：若kkkgB1，则kkgBs1*。若kkkgB1，求解kkkgB1得kkkgB1*，国家自然科学基金（10571106）资助项目，中国石油大学博士基金资助项目（Y040804）2则kkkkkkkgBgBgBs111**.为了实现这一想法，结合时贞军[6]的稀疏对角拟牛顿方法，保证kB是一个实对角矩阵及kB较好的近似)(xf在kx点的Hesse矩阵，取),,,(21nkkkkbbbdiagB近似满足拟牛顿方程，即为下列问题的解：211minkkksBy,（3）其中11kkkxxs，11kkkggy。同时为保证kB是正定矩阵，限制ikb在一定范围内取值，即要求niLbLik,,3,2,1,0.为此需要求解如下问题211,,3,2,1,minkkkniLbLsByik.（4）即2111,,3,2,1,)(minikikikniniLbLsbyik.（4’）解之得,对ni,,3,2,1，当01iks时，若LsyLikik11，则取ikikiksyb11；若Lsyikik11，则取Lbik；若Lsyikik11，则取Lbik.当01iks时，则取2LLbik.本文取信赖域子问题模型为：...21)()(minkkTTkkkstssBssgxfsq（5）其中)(,1kkkkxfgxxs。kB是一实对称正定对角矩阵，满足（4）。3本文基于简单二次函数模型（5），建立了一个求解无约束规划问题的新的信赖域算法，证明了算法的全局收敛性。数值例子表明算法是有效的，适合求解大规模问题。2.算法保证信赖域算法全局收敛性的关键在于迭代过程中信赖域半径的调整策略。如何选择k呢？一般地，当)()(sqk与)(sxfk之间的一致性满足某种要求时，应尽可能选取较大的k，否则选取较小的k。设子问题（5）的解为ks，则目标函数在第k步的实际下降量为)()(kkkksxfxfsAre（6）模型（5）的预估下降量为)()0(Prkkkksqqse（7）定义比值)()0()()(PrkkkkkkkkksqqsxfxfsesArer（8）它衡量二次模型)(kksq近似目标函数)(kksxf的程度。如果kr接近1，表明在当前点)(kksq与)(kksxf的近似程度较好，因此在下一迭代时，可适当增大信赖域半径k。如果0kr或接近于0，表明在当前点)(kksq与)(kksxf的近似程度较差，因此适当减少信赖域半径k，以提高)(kksq与)(kksxf的近似程度。新的信赖域算法（NTR）：Step0取初始点nnIBLLRx100,0,0),41,0[),,0(,0,。令0:k；Step1若kg，算法终止。得到问题（1）的解为kxx*。否则，转Step2；Step2求解信赖域子问题（5），得解ks；Step3由（8）式计算kr，若43kr，则令},2min{1kk；若41kr，则令kk211；若4341kr，则令kk1；4Step4：若kr，令kkxx1，1:kk，kk21:，转Step2；否则，令kkksxx1，求解问题（4）得1kB，令1:kk，转Step1。引理1设ks是问题（5）的解，若0kg，则0)()0()(kkkkksqqsq。证明注意到0s是问题（5）的可行点，故)()0()(kkkkxfqsq。即0)(kksq。若0)(kksq，即)0()()(kkkkqxfsq，故0是子问题（5）的最优解。但0是可行域的内点，故0)0(kq，即0kg，矛盾。故0)(kksq。[]引理2设}{kx是由算法产生的无穷迭代数列，则序列)}({kxf单调非增。证明对k，若kr，则kkxx1，此时)()(1kkxfxf；若kr，则由引理1及kr的定义知.0)()()()()(1kkkkkkksqsxfxfxfxf故)()(1kkxfxf。因此序列)}({kxf单调非增。[]为得到算法的下降性条件，引入Cauchy点：kkkkckggs（9）其中}1,min{3kkTkkkkgBgg（10）引理3对Cauchy点cks满足：},min{21)()0(kkkkckkkBggsqq.（11）5证明由（10）知，k有两种取值，下面分别讨论：1）13kkTkkkgBgg，此时，kkTkkkkgBgg3，因此有}.,min{21222)(21)()(21)()()0()()0(22442442222kkkkkkkkkkkTkkkkTkkkkTkkkTkkkkkTkkkTkkkTkkkkkTkkTkkkkTkkkkckkkBggBgBgggBgggBgggBggBggggBggBggBggggBgggggBggqqsqq2）13kkTkkkgBgg，此时1k，因此有)12(.21)()(21)(21)()0(222kkTkkkkkkkkkkTkkkkkkTkckkTckckTkckkkgBggggggBgggggsBssgsqq因为13kkTkkkgBgg，故kkkkTkggBg3，即kkkkTkggBg3。再由（12）知6[]}.,min{212121)()0(322kkkkkkkkkkkkckkkBggggggsqq引理4设ks是问题（5）的精确解，则},min{21kkkkkBggspre.证明由ks问题（5）的精确最优解，则)()(ckkkksqsq，故有[]}.,min{21)()0()()0(kkkkckkkkkkkBggsqqsqqspre3.算法的全局收敛性定理1设1)(Cxf，且在水平集)}()(|{)(00xfxfRxxLn上有下界。若在算法中取0，则算法产生的无穷迭代点列}{kx满足0inflimkkg.证明由kr的定义知)()0()()(1kkkkkkkksqqsxfsqr.由Taylor定理有dtsxftsxfsgxfsxfkTkkkkTkkkk10)]()([)()(.又因为kkTkkTkkkksBssgxfsq21)()(故有7)13(.)(2)()(2)]()([21)()(210210kkkkkkkkTkkkkkTkkkkksosLdtxftsxfssLdtsxftsxfsBssqsxf其中)(kso随着ks的减少而任意减少，满足0)(lim0kksssok.假设0inflimkkg，则0k和0，使得对0kk有kg.由引理4及kB的有界性知，对0kk有)14(.},min{21},min{21)()0(LBggsqqkkkkkkkk结合（13）得)15(.},min{))(2(},min{21))(2(},min{21)(221LscLLscLLsscsLrkkkkkkkkkkkkk由)(ksc的性质知，存在充分小的),0(~，使当~k时有4)(2kkscL;Lk~.再由（15）得84141kkkr.故43kr。因此由算法知信赖域半径k发生在~k时，因此0},2~,min{0kkkk.（16）若存在一个无限指标集K，使得对Kk有41kr。由（14）及算法Step3知，对0,kkKk有)17(.},min{81)]()0([41)()()()(1Lsqqsxfxfxfxfkkkkkkkkk又因为)}({kxf单调非增有下界及（17）知0lim,kkKk.此与（16）矛盾。故这样的k不存在，故对充分大的k必有41kr.另一方面，由算法Step3知，当41kr时，k按21比率缩小，故0limkk。这同样与（16）矛盾。故而0inflimkkg.定理2设1)(Cxf，在水平集)}()(|{)(00xfxfRxxLn上有下界，且)(xf为Lipschitz连续（常数为L），若在算法中取)41,0(，则算法产生的无穷迭代点列}{kx满足0limkkg.证明只需考虑对任意的k，0kg的情况。任取一个0k，记.2,0210000LLggkk9则对}|{),(00knkxxRxxNx,000)()()()(xgxgxgxg.故如果序列),(}{00kkkkxNx，则对0kk成立0kg。由定理1的证明过程知，这种情况不会发生，所以序列0}{kkkx最终会离开),(0kxN。设1kx是满足0kk的第一个离开),(0kxN的迭代点，对110kkk，由引理4知1111010))()(()()(kxxkkkkkkkkxfxfxfxf1110))()0((kxxkkkkkkksqq100110,min21kxxkkkkkL.如果对110kkk，Lk0，则)18(.22121)()(2001011010Lxfxfkkxxkkkkkk否则存在110kkk使得Lk0，则)19(.21},min{21)()(0000111010LLxfxfkkxxkkkkkk由于序列)}({kxf单调下降有下界，故有极限，即*)(limfxfkk.10由（18），（19）知.}1,1min{81}1,1min{21)()()(220*0100kkkkgLLLLxfxffxf因而))((})1,1min{81(*1200fxfLLgkk.令0k得0limkkg.4.数值试验本节选择了文献[6]的全部算例，利用matlab编制程序在PIII.933机器上对本文算法进行数值试验，如果算法中kB用DFP公式或BFGS公式校正，分别记为DFPTR和BFGSTR，计算结果表明新算法（NTR）有效.取9.1，497.00，01.0，310。以下在精