优化问题中非线性鞍点问题的快速算法与预处理

Nonlinear saddle-point problems arising from optimization problems with elliptic equations constraints usually preserve weakly nonlinearity, large scale sparsity and special block structures. Designing fast algorithms and preconditioners for this class of special 3-by-3 block structural and weakly nonlinear saddle-point problems plays an extremely important role in solving optimization problems of this kind and related application problems. However, till now, highly efficient algorithms tailored for this kind of nonlinear saddle-point problems are rarely seen. To solve this kind of problems efficiently, we will firstly examine the designing experience of the existing efficient methods for classical saddle-point problems, large sparse block 3-by-3 structured linear systems and nonlinear equations from optimization problems. Then, by adopting the matrix splitting and the dimensional splitting techniques, which preserve sparsity and block structure, we will construct new alternating or non-alternating direction iterative methods. Furthermore, by properly modifying the splitting matrix from the new iterative methods, we will obtain a new preconditioner, whose computational complexity and storage requirements are low. The results of this project will supply a new preconditioning technique for a class of special 3-by-3 block structured nonlinear saddle-point problems and provide new insights in solving large and sparse nonlinear saddle-point problems and algorithmic guarantee for the fast solution of relevant practical problems.

椭圆方程约束优化问题产生的非线性鞍点问题具有弱非线性、大规模稀疏性和特殊分块结构的特点。设计这类具有特殊3×3块结构的弱非线性方程组的快速算法及预处理对解决优化问题和相关实际问题起着至关重要的作用。然而，到目前为止，适合这类非线性鞍点问题的高效算法并不多见。为了有效地求解这类问题，本项目拟借鉴大型稀疏3×3块结构线性系统、经典鞍点问题以及优化问题中非线性方程组的求解算法的设计经验，通过矩阵分裂或维数分裂的办法，在保持原有的稀疏性及特殊结构的基础上，构造交错或非交错方向的迭代算法。对新算法产生的分裂矩阵进行合适的修正，进一步得到这类非线性鞍点问题的计算复杂度小、空间存储量少的预处理子。本项目的研究成果将得到一类特殊非线性鞍点问题的高效预处理子，并为优化问题中大规模非线性鞍点问题的快速求解提供一定的思路，进而为相关领域实际问题的有效求解提供算法保障。

近几十年PDE约束优化问题是数学研究领域中非常活跃的研究热点，高效求解该问题在科学和工程领域发挥着越来越重要的作用。其中，椭圆方程约束优化问题产生的非线性鞍点问题具有弱非线性、大规模稀疏性和特殊3×3分块结构的特点。设计这类具有特殊3×3块结构的弱非线性方程组的快速算法及预处理技术是一个很有挑战性的课题。.本项目研究了一类PDE约束优化问题得到的非线性鞍点结构系统的快速求解算法及预处理子。针对椭圆约束优化问题得到的非线性鞍点问题进行求解，研究了所求问题的特殊性质，分析得到其具有线性部分强占优、系数矩阵线性部分的特殊块结构以及大规模稀疏性质等特点的基础上，设计了改进的预处理的Uzawa算法框架，提出、分析并测试了这种算法框架的可行性与有效性，在理论上给出了收敛性结论，分析了算法的计算复杂度；针对图像恢复、图像去噪等优化问题得到的非线性鞍点结构系统的求解，设计了非线性的正则化Hermitian与反Hermitian分裂（NRHSS）迭代法以及不精确的NRHSS迭代方法，在实验上，将新算法与一些已有的经典算法进行的大量数值结果对比，体现了新算法的可行性与有效性；我们也针对结构化的分数阶PDE离散系统的快速求解也进行了探讨，设计了一种新的快速求解算法。.这些研究成果，包括设计得到的新算法、得到的理论结果以及用到的程序和实验可供优化问题中大规模非线性鞍点问题的快速求解提供一定的思路，进而为相关领域实际问题的有效求解提供算法保障。