A proximal ADMM for multiblock problems with block anti-upper triangular constraints

Abstract

In this paper, we present the convergence analysis of the proximal Alternating Direction Method of Multipliers (ADMM) for problems with block anti-upper triangular constraints. While the linear constraints can be treated separately, most analyses of ADMM and its variants predominantly regard the linear constraints as one. Hence, it relies on assumptions related to the entire constraint matrix, such as the full column rank. However, some problems with block anti-upper triangular constraints that can be solved by ADMM do not satisfy these assumptions. To fill this gap, a new assumption is proposed and used to guarantee the global convergence of the proximal ADMM for nonconvex problems. In the strongly convex setting, we also prove the global convergence of the proximal ADMM and establish the linear convergence under four different scenarios. This work extends the theoretical understanding of the multi-block ADMM to more general cases with block anti-upper triangular constraints.