Symmetric ADMM with Positive-Indefinite Proximal Regularization for Linearly Constrained Convex Optimization

Bin Gao (feimaxiao123gmail.com)
Feng Ma ( mafengnjugmail.com)

Abstract: The proximal ADMM which adds proximal regularizations to ADMM’s subproblems is a popular and useful method for linearly constrained separable convex problems, especially its linearized case. A well-known requirement on guaranteeing the convergence of the method in the literature is that the proximal regularization must be positive semidefinite. Recently it was shown by He et al. (Optimization Online, 2016) that the proximal term regularized on ADMM is not necessarily positive semidefinite without any additional assumptions, while it is still unknown whether the indefinite setting is valid for the proximal version of the symmetric ADMM. In this paper, we confirm that the symmetric ADMM can also be regularized with positive-indefinite proximal term. Theoretically, we prove global convergence of the improved method and establish the worst-case nonasymptotic O(1/t) convergence rate result in ergodic sense, where t counts the iteration. In addition, the generalized ADMM proposed by Eckstein and Bertsekas is a special case of our discussion. Finally, we demonstrate the improvements of using the positive-indefinite proximal term by some experimental results.

Keywords: Convex programming, alternating direction method of multipliers, positive indefinite proximal, iteration-complexity

Category 1: Convex and Nonsmooth Optimization (Convex Optimization )

Category 2: Optimization Software and Modeling Systems (Parallel Algorithms )

Category 3: Complementarity and Variational Inequalities

Citation:

Download: [PDF]

Entry Submitted: 03/21/2017
Entry Accepted: 03/21/2017
Entry Last Modified: 03/22/2017

Modify/Update this entry