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

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.

Article

Download

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