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

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.

Many optimization problems are solved by repeatedly updating several groups of variables and adjusting them until they become consistent with one another. Although such methods are widely used, their reliability depends on convergence guarantees: one needs to know whether the method is truly approaching a valid solution rather than merely producing numerical iterates. This paper focuses on proving such guarantees for problems with block anti-upper triangular constraints. Informally, this means that the constraints linking different groups of variables follow a special one-way block structure, where certain later groups are only connected to earlier groups in a restricted pattern. This structure appears in problems that can be naturally handled block by block, but it is not fully captured by previous convergence analyses. Earlier analyses often treat all linking constraints as one large object, which leads to assumptions that can be too restrictive. Some problems with block anti-upper triangular constraints do not satisfy these standard assumptions, even though the proximal ADMM can still solve them effectively. To address this gap, we introduce a new condition that better reflects this block structure. Under this new condition, we prove that the proximal ADMM converges for nonconvex problems. For problems with stronger curvature, we further prove global convergence and establish a predictable linear convergence rate in several important cases. Overall, this work provides a more refined convergence theory for proximal ADMM and explains why the method remains reliable for a broader class of structured multi-block optimization problems.