Convergence Rate Analysis Of Proximal Generalized Alternating Direction Methods Of Multipliers

Many problems in signal processing,image denoising,data mining and compressed sensing can be formulated as convex composite optimization problem with linear equality constraint.It is a hot topic in the field of optimization to design efficient and convergent algorithms by taking advantage of the separable structure of problem and the characteristics of each function.By alternately minimizing the augmented Lagrangian function in a Gauss-Seidel manner,the alternating direction method of multipliers(ADMM)distributes the difficulty of the problem to each subproblem.Due to its simplicity and effectiveness,ADMM has attracted more and more attention.Many scholars have proposed many variants to improve the efficiency of ADMM.Despite the excellent numerical performance,there is relatively little on the theoretical analysis of asymptotic convergence rate.Therefore,it is of great theoretical value to study the asymptotic convergence rate of the ADMM for convex composite optimization problem.In this thesis,we focus on the Q-convergence rate of two types of generalized ADMM with proximal terms,and prove that they locally Q-linear converge to the Karush-Kuhn-Tucher(KKT)point under mild conditions.Furthermore,we strengthen the assumption to extend the local convergent properties to the global.The thesis is divided into four chapters as follows:In Chapter one,we summarize some basic concepts and related conclusions involved in the thesis.Then we review the convex composite optimization problem,and the ADMM,the generalized ADMM and the Douglas-Rachford splitting method for soving the optimization problem.Finally,we briefly describe the main contributions of this thesis,and give some symbols used in the subsequent developments.In Chapter two,based on the KKT system,we construct a key inequality for the semi-proximal generalized ADMM(sPGADMM),and establish the global convergence of sPGADMM.Using this inequality,and according to the special structure of KKT mapping,we prove that sPGADMM is locally Q-linear convergent under mild conditions.By analyzing the connections between the piecewise polyhedral mapping and calmness,we deduce the global Q-linear convergence rate of sPGADMM under certain conditions.In Chapter three,we consider a type of generalized alternating direction method of multipliers with proximal terms(p-GADMM)proposed by Xiao,Chen and Li[Math.Program.Comput.,2018].By constructing a new type of KKT mapping based on relaxation factors,we prove that p-GADMM is Q-linear convergent under the calmness condition.In Chapter four,we summarize this thesis,and give some further research topics.