大型稀疏无约束优化的分划组修正算法

摘要

本文考虑求解无约束优化问题 minx∈Rnf(x), (1) 其中f:Rn→R二次连续可微.f(x)的Hesse阵H(x)稀疏.为了求解问题,我们考虑下列Newton型方法 xk+1=xk-(Bk)-1▽f(xk),k=0,1,…, (2) 其中,Bk是和Hesse阵H(xk)具有相同稀疏性的近似. 对于更有效地求解大型稀疏无约束优化问题,Powell和Toint把CPR算法的思想引入对称的情况,提出了两种实际有效的算法(直接法和间接下三角形替换法)以获得Hesse阵的一个好的廉价近似,这使得不得不计算的一阶导向量的估计次数变小了.直接法是基于Hesse阵的对称相容分划.Coleman和Moré把分划问题同图着色联系起来,给出了某些分划算法,这些算法使得梯度估计值优化或接近优化。