Analysis Of Sublinear Convergence Rate Of A Class Of Algorithms In ADMM Framework

Alternating direction method of multipliers(ADMM)and other algorithms in its framework are classical methods for solving separable convex optimization problems,which are suitable for solving large-scale distributed problems.ADMM is widely used in machine learning,image processing,statistical learning and related fields.Compared with ADMM proximal point algorithm alternating proximal gradient method and the proximal alternating direction method of multipliers,the subproblem is easier to solve and has the advantage of closed form solution.For the separable convex programming problem with linear constraints and the sum of multiple convex functions,this paper mainly studies some sufficient conditions for the sublinear convergence rates of the 3-block alternating proximal gradient method and multi-block proximal alternating direction method of multipliers in the ergodic and non-ergodic sense respectively.1.In chapter 1,we briefly describe the separable convex programming problem and the research significance of the algorithm under the ADMM framework.We also give a brief overview of the separable convex programming problem and its related research directions,and then propose the main research contents of this paper.2.In Chapter 2,we give sufficient conditions to guarantee the sublinear convergence rate of the 3-blocks alternating proximal gradient method.Especially when one of the functions is convex(not necessarily strongly convex),and the other two functions are strongly convex,and the penalty parameter is in a certain region,the convergence rate of the 3-block alternating proximal gradient method in ergodic sense is 0(1/t),and the convergence rate in the non-ergodic sense is o(1/t),where t represents the number of iterations.A simple proof of the convergence of two-block alternating proximal gradient methods without requiring strong convexity of any function is given.3.In Chapter 3,we consider a class of convex programming problems with linear constraints for multi-block separable structures whose objective function is the sum of m(m?3)convex functions.Proximal alternating direction methods of multiplier(P-ADMM)is an effective method to solve this problem.This note gives a sufficient condition to ensure that the m(m?3)block P-ADMM has a sublinear convergence rate of 0(1/t)and o(1/t)in ergodic sense and non-ergodic sense,respectively.A simple proof of the convergence of two-block proximal alternating direction method of multipliers without requiring strong convexity of any function is given.