A majorized ADMM with indefinite proximal terms for linearly constrained convex composite optimization

M. Li, Defeng Sun, K.-C. Toh

Research output: Journal article publicationJournal articleAcademic researchpeer-review

39 Citations (Scopus)

Abstract

© 2016 Societ y for Industrial and Applied Mathematics.This paper presents a majorized alternating direc tion 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??, y?y{p(x) + f(x) + q(y) + g (y) | 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 ? ? (0, (1 + ?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.
Original languageEnglish
Pages (from-to)922-950
Number of pages29
JournalSIAM Journal on Optimization
Volume26
Issue number2
DOIs
Publication statusPublished - 1 Jan 2016
Externally publishedYes

Keywords

  • Alternating direction method of multipliers
  • Convex composite optimization
  • Indefinite proximal terms
  • Iteration-complexity
  • Majorization

ASJC Scopus subject areas

  • Software
  • Theoretical Computer Science

Cite this