Efficient Numerical Algorithms For Several Types Of Inverse Problems

Inverse problems have a wide range of important applications,such as medical imaging,mod-ern industry,weather forecast and so on.Therefore,numerically solving inverse problems has caused much attention.In this dissertation,we consider several types of PDE-constrained opti-mization problems:elliptic control problems with pointwise box constraints on the state;elliptic control problems with integral constraint on the gradient of the state and box constraints on the control;ill-posed linear inverse problems arising from image restoration.Motivated by the suc-cess of first order algorithms in large finite dimensional optimization problems,we try to study how to use some first order algorithms to numerically solve these problems more efficiently based on their structures,and the main results obtained are as following:1.Elliptic control problems with pointwise box constraints on the state are considered.For the pointwise state constraints,the corresponding Lagrange multipliers are Borel measure functions,which results in the complementarity condition in the optimality conditions cannot be represented in a pointwise form.Lavrentiev regularization is used to tackle this difficulty,then the piecewise linear finite element full discretization is employed to discretize the resulted prob-lem.Estimation of the error from regularization and discretizatiion is done,from which we can see that the error order of full discretization is not inferior to that of variational discretization.To numerically solve the discretized problem,a heterogeneous alternating direction method of mul-tipliers(hADMM)and a two-phase strategy are proposed,which are employed to get solution of moderate accuracy and of high accuracy,respectively.2.Elliptic optimal control problems with integral constraint on the gradient of the state are considered.We first prove the optimality conditions for the problem and then propose a finite element duality-based inexact majorized accelerated block coordinate descent(FE-dABCD)al-gorithm to solve it.Specifically,we use the standard piecewise linear finite element to discretize the problem and give the dual problem of the discretized problem,which is a multi-block un-constrained convex optimization problem.Then an inexact majorized ABCD algorithm is used to solve the dual problem.Some efficient strategies are employed to solve the subproblems,which makes the FE-dABCD algorithm enjoy O(1/k2)iteration complexity.Moreover,we also propose a multi-level FE-dABCD(mFE-dABCD)algorithm based on the mesh-independence of the ABCD method.3.Linear inverse problems arising from image restoration are considered.We utilize two hidden structures of the problem to extend the fast iterative shrinkage-thresholding algorithm(FISTA)and call the proposed algorithm structured FISTA(sFISTA).The first structure to be exploited is the Kronecker product approximation of the coefficient matrix,which can not only introduce one more level of parallelism but also enables computationally intensive matrix-matrix multiplications in the subsequent optimization procedure.The second one is that the matrices in the Kronecker product approximation are all structured matrices(Toeplitz,Hankel,etc.),which enables us to exploit their fast matrix-vector multiplication at each iteration.Moreover,we show that the error introduced by the Kronecker product approximation is well under control and sFISTA can reach the same accuracy level as FISTA.