Efficient ADMM-type Algorithms For Two Inverse Problems

Inverse problems have a wide range of important applications,such as geophysics,industrial control,medical imaging,and so on.Inverse problems have important theoretical significance and application value,so numerically solving inverse problems has received extensive attention.In recent years the inverse problem has become one of the fastest developing and most challenging fields in applied mathematics.In this thesis,we consider two inverse problems and design efficient ADMM-type algorithms.Theoretically,we present the convergence analysis and the iteration complexity analysis of the algorithms.The main research ideas and achievements of this thesis are as follows:1.PDE-constrained optimization problems are considered.Specifically,we consider elliptic PDE-constrained optimization problems with box constraints on the control and propose an efficient multi-level alternating direction method of multipliers(mADMM).The total error of the mADMM algorithm consists of two parts:the discretization error resulted from the finite element discretization and the iteration error resulted from solving the discretized subproblems.Both of these two kinds of errors can be regarded as the error of inexactly solving infinitedimensional subproblems.Thus,we regard the mADMM algorithm as an inexact ADMM(iADMM)algorithm in function space.Theoretical results on the global convergence as well as the iteration complexity results o(1/k)for mADMM are given.Specifically,motivated by the efficiency of applying the iADMM algorithm to tackle PDE-constrained optimization problems,the iADMM is applied in the function space first.Then,motivated by the efficiency of applying the multi-grid method to tackle non-linear PDEs by the Newton method,we combine the multi-grid strategy with the iADMM algorithm.The subproblems of the iADMM algorithm are discretized by the strategy of gradually refining the grid.Finally,appropriate numerical methods are applied to solve the discretized subproblems.Thus,we give the 'optimize-discretize-optimize' strategy to numerically solve PDE-constrained optimization problems.Numerical results show that the mADMM algorithm can reduce the computational cost significantly and make the algorithm faster.2.Large scale ill-posed inverse problems arising from image restoration are considered.Specifically,we consider myopic deconvolution problems arising from image restoration.We propose a model with total variation(TV)regularization and propose an efficient alternating direction method of multipliers based on linearize and project method(ADMM-LAP)for the model.The convergence results,as well as the computational complexity analysis of ADMM-LAP are presented.Different from standard deconvolution problems where the point spread function(PSF)is completely known,the PSF in three-dimensional(3D)imaging problems are only partially known.This results in more complicated myopic(mildly blind)deconvolution problems where image restoration also requires recovering or approximating the PSF.Myopic deconvolution problems with TV regularization arising from the image restoration are non-convex,nonsmooth optimization problems with equality constraints and tightly coupled objective function.To solve these problems,we first apply ADMM as an outer optimization method to tackle the TV regularizer.Then,we adopt a variation of the LAP method as an inner optimization method to solve the non-convex and coupled subproblems with point-wise bound constraints arising within each ADMM iteration.Compared to the existing algorithm,ADMM-LAP converges faster and the restored images and the obtained PSFs are more accurate.