The Alternating Direction Multiplier Method For Solving Multi-block Separable Convex Programming Problem

The separable convex programming problem subject to linear constraints is a kind of optimization problem with the special structure,which is widely used in many fields,such as signal processing,machine learning,low-rank sparse decomposition,and so on.It is a hot topic to design a convergent and effective solving algorithm in the field of optimization by using the separable structure of the objective function.Because of making full use of the separation characteristic of the objective function,the alternating direction multiplier method(ADMM)becomes a classical method to solve the two-block separable convex programming problem.However,it is not necessarily convergent when it is extended to multi-block case directly.In this thesis,based on prediction-correction frame and variational inequality,we design two ADMM-based improved algorithms for multi-block separable convex programming problem and study the global convergence,convergence rate and numerical efficiency of these two algorithms.The main work of this thesis is as follow:By utilizing the linearized technique and the inertial information,a partial parallel inertial alternating direction multiplier method(PPIADMM)is proposed to solve the multi-block separable convex programming problem.Firstly,this PPIADMM partitions the data into two group variables where the variables within each group are iterated in a Jacobi scheme and two grouped variables are iterated in a Gauss-Seidel scheme,which make it very effective for solving large-scale data problems.Secondly,this PPIADMM only adds appropriate proximal terms to the first group of subproblems and uses the linearized technique for the second group of subproblems.In addition,this PPIADMM updates the Lagrangian multipliers twice in different forms and utilizes the inertia information to correct the output sequence.Further with the aid of prediction-correction frame,we find out the relationship between the relaxation factor and the inertia coefficient,analyze the global convergence of the introduced method and derive the convergence rate in ergodic sense.Finally,taking the linear constrained quadratic programming problem and the latent variable gaussian graphical model selection problem as examples,some experimental results demonstrate the efficiency of the introduced method.The ADMM-based improved algorithms with proximal regularization term have been fully studied and widely used.However,the positive definiteness of the proximal matrix usually make small step sizes and lower the overall convergence rate of this type method.Therefore,by adding indefinite proximal terms to the second group of subproblems,we construct a partial parallel indefinite inertial alternating direction multiplier method(PPIIADMM)to improve PPIADMM for solving the multi-block separable convex minimization problem.This PPIIADMM updates the Lagrangian multipliers twice in different iteration steps based on linearized technique,and divides the data variables into two groups,which are updated by using a combination the Gauss-Seidel and the Jacobi two iterative strategies.At the end of each iteration,this PPIIADMM utilizes the substitution step to modify the output sequence with the help of inertial information.According to prediction-correction frame,we explore the relationship between the relaxation factor,the proximal parameters and the inertia coefficient.And we study the global convergence and iteration complexity of this method based on variational inequality.By solving the linear constrained quadratic programming problem and the latent variable gaussian graphical model selection problem,numerical experiments show the improvement effect of the introduced method compared with the existing mature algorithms.