大规模非线性方程组和优化问题的稀疏拟牛顿算法研究

Quasi-Newton methods are quite welcome in the solution of nonlinear equations as well as optimization. An attractive property of those methods is their superlinear convergence without computation of the Jacobian or Hessian matrices. If some line search or trust region technique is used, the methods can be even globally convergent. Unfortunately, the quasi-Newton matrices generated by a quasi-Newton method are generally dense. As a result, ordinary quasi-Newton methods are not able to solve large scale problems directly. . This project will mainly focus on the following issues: (1) For the large scale nonlinear equations, using the new secant conditions and automatic differentiation, we will propose a class of new quasi-Newton methods and give the related sparse forms. Under appropriate conditions, we will establish the global convergence and superlinear convergence. For the symmetric nonlinear equations, we will derive symmetric and sparse quasi-Newtonupdates and study the global convergence and convergence rate. (2) For the large scale unconstrained optimization problems, we will study the global convergence of MCQN method. Besides, we will design a class of rank two quasi-Newton updates based on secant conditions and study the convergence of the related MCQN methods. (3) For the nonlinear equations and unconstrained optimization problems, we will consider the sparse quasi-Newton methods which can preserve the sparse structures accurately or approximately. We also will study the quasi-Newton methods with one column or one row updating. This project will further enrich numerical algorithms of large scale nonlinear equations and unconstrained optimization problems and provide effective quasi-Newton methods for solving large scale nonlinear problems.

拟牛顿法是求解非线性方程组和最优化问题颇受欢迎的一类算法，本项目将围绕着求解大规模非线性方程组和优化问题的拟牛顿算法设计和应用展开研究。主要研究内容包括：(1) 对于非线性方程组，利用新型的切线条件和自动微分，提出具有全局收敛性的拟牛顿算法和稀疏拟牛顿算法；方程组具有对称结构时，考虑具有全局收敛性和超线性收敛性的对称稀疏拟牛顿算法。(2) 对于无约束优化问题，我们将进一步考虑MCQN算法的全局收敛性；将提出可与BFGS和DFP修正公式相媲美的新型对称拟牛顿修正公式，并考虑其相应的MCQN算法的全局收敛性。(3) 对于大规模非线性方程组和无约束优化问题的稀疏拟牛顿算法，我们还将考虑能够精确保持或者部分保持问题的稀疏结构、每次迭代只部分修正拟牛顿矩阵和具有二次终止性的稀疏拟牛顿算法。本项目的工作将会进一步丰富求解大规模问题的数值算法，为用拟牛顿法求解大规模非线性问题提供算法支持。

拟牛顿法是求解非线性方程组和最优化问题颇受欢迎的一类算法，本项目围绕着求解大规模非线性方程组和优化问题的拟牛顿算法设计及其应用展开研究，主要内容包括：(1)对于非线性方程组，利用直接切线条件和自动微分，构造出一种新型的拟牛顿修正公式并建立了算法的全局收敛性。在此基础上，我们将该算法稀疏化，提出相应的列修正算法并进行数值验证。对于对称非线性方程组，我们将上述拟牛顿修正公式对称化，证明了全局收敛性。(2) 对于无约束优化问题，采用直接切线条件和自动微分，构造出一种新型对称秩二拟牛顿修正公式。在此基础上，我们提出一种基于矩阵完备的秩二拟牛顿算法，在适当假设条件下建立了局部收敛性并进行数值验证。(3) 对于特殊格式的稀疏拟牛顿算法，我们重点考虑了对角修正，即采用对角矩阵逼近Jacobian矩阵或Hessian矩阵及其逆矩阵。通过采用约化参数，使用不同的范数或加权范数，弱割线条件，最小割线改变和最小化迭代矩阵的迹等构造拟牛顿对角矩阵，建立了相关的收敛性分析，并进行数值验证。(4) 虽然自动微分能够精确计算矩阵与向量的乘积，但是也会有舍入误差的影响。因此我们对上述研究的内容进行了推广，在直接切线条件中加入近似项，在合适的误差下分析算法的收敛性和计算效果。同时还结合了近似求解线性方程组的数值代数算法如广义最小残差法(GMRES)或共轭梯度法(CG)。(5) 在算法应用方面：首先，我们将高阶稀疏复张量的U-特征值和US-特征值问题转化为带复变量的大规模稀疏非线性方程组和最优化问题，并借鉴现有的稀疏拟牛顿算法的思想设计新型算法求解；其次，研究Hermitian张量的代数结构和Hermitian秩一分解，设计了快速有效的分解算法；最后，我们将复张量分解和特征值计算应用到量子纠缠计算以及可分态的判别当中。本项目一系列的工作，进一步丰富了求解大规模问题的拟牛顿算法，为用拟牛顿法求解大规模非线性问题提供算法支持。