Abstract: The alternating direction method of multipliers (ADMM) is an effective and widely used first-order method for solving composite problems. Nonetheless, existing convergence conditions on ADMM in non-convex settings are too restrictive, limiting ADMM's practical applicability. The main contribution of this paper is the relaxation of existing convergence results of the multi-block proximal ADMM (PADMM) for non-convex optimization problems. Whereas existing results require that there exists a smooth objective term and the associated coefficient matrix has full row rank, we only assume the existence of some smooth terms such that the concatenation of their coefficient matrices is full row rank. Under the weakened conditions, we establish the convergence of PADMM and characterize its convergence rate. Furthermore, for more general cases where the relaxed condition does not hold, we propose a method to equivalently reformulate the original problem such that it satisfies the required full row rank condition and PADMM can be applied.

Key words: multi-block ADMM, non-convex optimization, convergence analysis