Researches On Numerical Solutions For Three Kinds Of Saddle-point Problems With Different Block Structures And One Kind Of Constrained Optimization Problem

This thesis is mainly focused on the iterative solution methods for large,sparse linear systems with two-by-two block saddle-point form(saddle-point problems)and the numerical solution method for a kind of constraint optimization problem arising from graph matching.Saddle-point problems arise in many application areas,such as computational fluid dynamics,optimal control,image processing,electronic networks,mixed or hybrid finite element discretization of elliptic partial differential equations.Graph matching problem has great importance in the applications of computer vision and machine learning.It is of great practical significance to construct efficient numerical solutions for these two kinds of problems.We mainly consider the iterative solution of three kinds of singular and nonsingular saddle-point problems with different(1,1)block submatrices.Considering that the coefficient matrix sub-blocks of singular and nonsingular saddle-point problems differ in structure and properties,we will propose singular matrix splitting forms for the coefficient matrices of singular saddle-point problems.It makes the splitting matrix has a better approximation to the coefficient matrix than the nonsingular splitting matrix.Based on the singular matrix splittings,we propose three iteration methods for solving singular saddle-point problems.The first one is the generalized parameterized inexact Uzawa(GPIU)iteration method for solving consistent singular saddle-point problem.Meanwhile,we have proved the semi-convergence of this method and verified its effectiveness by numerical experiments.Then,in order to approximate some meaningful solutions for singular saddle-point problems,we propose two iteration methods,named modified parameterized inexact Uzawa(MPIU)iteration method and modified preconditioned generalized shift-splitting(MPGSS)iteration method,respectively,for solving two kinds of singular saddle-point problems with different(1,1)block submatrices.We have proved that for any initial guess vector,these two methods can converge to the least squares solution with minimum norm of both consistent and inconsistent singular saddle-point problems,and with appropriate initial guess vectors,the corresponding preconditioned GMRES methods can also converge to the least squares solution with minimum norm for consistent singular saddle-point problem.Numerical results are presented to show the feasibility and effectiveness of the proposed methods.For the nonsingular saddle-point problem,based on a preconditioned shift-splitting of the non-Hermitian positive definite(1,1)block of the coefficient matrix and the parameterized inexact Uzawa iteration method,we provide a preconditioned shiftsplitting Uzawa(UPSS)iteration method and a corresponding preconditioner.The convergence properties of this iteration method and the spectral properties of the preconditioned matrix are analyzed.Numerical results are presented to verify the robustness and effectiveness of the iteration method and preconditioner.To solve the problem that the spectral matching with affine constraint(SMAC)formulation cannot cover all the graph matching problems,we present a bounded SMAC(BSMAC)formulation by adding an upper bound constraint on the solution norm,which also can be viewed as a constraint optimization problem.We demonstrate the existence of a unique solution of BSMAC formulation and develop an effective numerical solution method.By comparing the numerical performance of the two formulations and the corresponding solving methods,we verify the feasibility and effectiveness of the proposed formulation and numerical method for solving the graph matching problems.