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

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块结构线性系统、经典鞍点问题以及优化问题中非线性方程组的求解算法的设计经验，通过矩阵分裂或维数分裂的办法，在保持原有的稀疏性及特殊结构的基础上，构造交错或非交错方向的迭代算法。对新算法产生的分裂矩阵进行合适的修正，进一步得到这类非线性鞍点问题的计算复杂度小、空间存储量少的预处理子。本项目的研究成果将得到一类特殊非线性鞍点问题的高效预处理子，并为优化问题中大规模非线性鞍点问题的快速求解提供一定的思路，进而为相关领域实际问题的有效求解提供算法保障。

本项目的研究主题为优化问题中的非线性鞍点问题，包括快速算法与预处理技术。在项目执行过程中，进行了如下三方面研究： (1) 针对从空间分数阶扩散方程离散化得到的具有对角加Toeplitz结构的线性系统，探讨了基于tau-矩阵逼近的逆预条件技术； (2) 在正则性条件下，建立了松弛邻近点算法的紧的线性收敛率； (3) 为双线性鞍点问题设计了基于凸组合技术的原始-对偶全分裂算法，将决定凸组合系数的参数从原来的取值范围(1, 1.618)扩大到了(1, 2.732), 并将算法推广应用到了更为一般的可分凸优化问题和非线性鞍点问题。上述关于原始-对偶全分裂算法方面的研究成果为结构型凸优化和非线性凸-凹鞍点问题的有效求解提供了基础算法框架，具有重要理论意义和应用价值。