论文部分内容阅读
拟Newton法是求解最优化问题的一类十分有效的算法。该类算法的主要优点有,在一定条件下算法具有全局收敛性和超线性收敛速度,并且无需计算目标函数的二阶导数。因而拟Newton法已成为求解中小规模最优化问题的一类最受欢迎的算法。然而拟Newton法产生的矩阵通常稠密的。因此,该类算法难以直接用于求解大规模最优化问题。为了使得拟Newton法能用于求解大规模最优化问题,学者们提出了多种形式的稀疏拟Newton法。这些稀疏拟Newton法充分利用目标函数的Hessian矩阵的结构和稀疏性,使得拟Newton矩阵具有与目标函数的Hessian阵相同或相似的稀疏结构。从而可用于求解大规模最优化问题。
迄今为止,关于稀疏拟Newton法的研究主要集中于关于算法的局部收敛性方面,并已取得许多重要成果。关于稀疏拟Newton法的全局收敛性研究尚不多见。本文主要研究具有部分可分结构的最优化问题的稀疏拟Newton法。侧重于BFGS和DFP拟Newton法的研究。该算法能保证拟Newton矩阵具有与目标函数的Hessian阵相同的稀疏性。算法产生的方向是目标函数的下降方向。在一定的条件下,证明算法DFP算法局部超线性收敛性和CBFGS算法用于求解非凸函数极小化问题时具有全局收敛性和超线性收敛性。而且,单位步长最终可以取得,研究的问题包括目标函数的Hessian矩阵为三对角矩阵和五对角矩阵这两类特殊问题。还进行了数值试验.结果表明本文提出的部分可分稀疏拟Newton法明显优于通常BFGS算法和某些稀疏BFGS(SBFGS)算法。特别是在求解大规模稀疏优化问题时,尤为明显。