一类非线性互补问题的高性能数值算法和理论研究

The complementarity problem is one of the most important and popular problems in the cross area of computational mathematics and operational research. Study on the fast, exact and stable numerical algorithms is a very challenging research subject with great importance in theory and high value in practice. We further study deeply and systematically not only by constructing a series of modulus-based matrix splitting iteration methods, which are simple, practical and highly efficient, for large and sparse nonlinear complementarity problems, especially a class of nonlinear complementarity problem with special structure, but also by demonstrating the corresponding convergence theory. Specifically, our aims are to improve the convergence theorem of modulus-based matrix splitting iteration method for nonlinear complementarity problems by weakening the H-compatible splitting of an H-matrix to be H-splitting; to establish the convergence theory of two-step modulus-based matrix splitting iteration method when the coefficient matrix is an H-matrix; to construct accelerated modulus-based matrix splitting iteration method and accelerated two-step modulus-based matrix splitting iteration method, as well as analyzing the corresponding convergence conditions; to combine the modulus-based matrix splitting iteration method with the Newton method for nonlinear systems to solve nonlinear complementarity problems with special structure, and establish the corresponding convergence theory.

互补问题是计算数学和运筹学交叉领域中一个非常重要且十分热门的问题之一。研究求解该问题的快速、准确且稳定的数值算法，是一项具有重要理论意义和很高实用价值，且富有挑战性的研究课题。本研究针对大型稀疏非线性互补问题，特别是一类具有特殊结构的非线性互补问题进一步展开深入系统的研究，设计一系列简单、实用、高效的模基矩阵分裂迭代法，并阐明这些迭代法的收敛原理，包括：将求解非线性互补问题的模基矩阵分裂迭代法收敛定理进行改进，由H矩阵的H相容分裂条件减弱为H分裂；建立两步模基矩阵分裂迭代法在系数矩阵为H矩阵时的收敛理论；构造加速的模系矩阵分裂迭代法和加速的两步模系矩阵分裂迭代法，并分析相应的收敛条件；将模系矩阵分裂迭代法与求解一般非线性方程组的牛顿法结合求解特殊结构的非线性互补问题，建立相应的收敛性理论。

互补问题广泛来源于数学、物理、工程、金融等领域，在计算数学和运筹学交叉学科中占有十分重要的地位。因此，研究求解该问题的快速且稳定的数值算法具有重要理论意义和很高实用价值。. 本项目针对大型稀疏非线性互补问题，特别是一类具有特殊结构的非线性互补问题开展了进一步深入系统的研究，包括对已有的模基矩阵分裂迭代法收敛定理进行了改进，将H+矩阵的H相容分裂条件减弱为了H分裂；建立了两步模基矩阵分裂迭代法在系数矩阵为H+矩阵时的收敛理论；考虑了采用松弛模基矩阵分裂迭代法求解一类非线性互补问题，并将模系矩阵分裂迭代法与求解一般非线性方程组的牛顿法结合来求解一类特殊结构的非线性互补问题，建立相应的收敛性理论。另外，本项目还将两步模基矩阵分裂迭代法和加速的模基矩阵分裂迭代法应用于隐互补问题的求解中，获得了较好的数值效果。由于美式期权定价问题可以等价地转化为线性互补问题，项目组成员也对在机制转化下跳扩散欧式和美式期权定价问题进行了研究。