A Majorized ADMM with Indefinite Proximal Terms for Linearly Constrained Convex Composite Optimization

Abstract

This paper presents a majorized alternating direction method of multipliers (ADMM) with indefinite proximal terms for solving linearly constrained $2$-block convex composite optimization problems with each block in the objective being the sum of a non-smooth convex function and a smooth convex function, i.e., ${\min }_{x\in \mathcal{X},y\in \mathcal{Y}}\{p(x)+f(x)+q(y)+g(y)\mid A^{\ast }x+B^{\ast }y=c\}$. By choosing the indefinite proximal terms properly, we establish the global convergence and $O(1/k)$ ergodic iteration-complexity of the proposed method for the step-length $\tau \in (0,(1+\sqrt{5})/2)$. The computational benefit of using indefinite proximal terms within the ADMM framework instead of the current requirement of positive semidefinite ones is also demonstrated numerically. This opens up a new way to improve the practical performance of the ADMM and related methods.

References in corpus (3)

• A Convergent 3-Block Semi-Proximal Alternating Direction Method of Multipliers for Conic Programming with $4$-Type of Constraints
• On the Sublinear Convergence Rate of Multi-Block ADMM
• On the Global Linear Convergence of the ADMM with Multi-Block Variables