INEXACT GENERALIZED PROXIMAL ALTERNATING DIRECTION METHODS OF MULTIPLIERS AND THEIR CONVERGENCE RATES

The alternating direction method of multiplies (ADMM) has been well studied in the literature; and it has inspired some variants such as inexact versions, generalized versions and proximal versions which are efficient for different circumstances. We propose a general algorithmic framework of ADMM by combining these variants together, in the setting of convex minimization model with linear constraints and a separable objective function. Some ADMM type methods in the literature are subsumed by this general algorithmic framework. More specifically, we allow ADMM's subproblems to be regularized by proximal terms and solved approximately; and then the output is further relaxed by a generalized scheme as suggested by Eckstein and Bertsekas. By choosing different inexactness criteria for the proximal subproblems, two concrete algorithms of the inexact generalized proximal ADMM kind can be derived. We prove the global convergence for these new ADMM type algorithms; and establish their worst-case O(1/t) convergence rates in both ergodic and nonergodic senses. This is a more general and comprehensive work than existing convergence rate results in ADMM literature.