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 (5)

• A Convergent 3-Block Semi-Proximal Alternating Direction Method of Multipliers for Conic Programming with $4$-Type of Constraints
• Parallel Multi-Block ADMM with o(1/k) Convergence
• On the convergence properties of a majorized ADMM for linearly constrained convex optimization problems with coupled objective functions
• On the Sublinear Convergence Rate of Multi-Block ADMM
• On the Global Linear Convergence of the ADMM with Multi-Block Variables

Cited by in corpus (2)

• Linear Rate Convergence of the Alternating Direction Method of Multipliers for Convex Composite Quadratic and Semi-Definite Programming
• Inexact indefinite proximal ADMMs for 2-block separable convex programs and applications to 4-block DNNSDPs