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

Min Li, Defeng Sun, Kim-Chuan Toh

SIAM Journal on Optimization · 2016 · 92 citations · 25 references

Concepts

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 nonsmooth convex function ($p(x)$ or $q(y)$) and a smooth convex function ($f(x)$ or $g(y)$), i.e., $\min_{x \in {\mathcal X}, \; y \in {\mathcal Y}}\{p(x)+f(x) + q(y)+g(y)\mid A^* x+B^* y = c\}$. By choosing the indefinite proximal terms properly, we establish the global convergence and the iteration-complexity in the nonergodic sense 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

25