On the convergence of the direct extension of ADMM for three-block separable convex minimization models with one strongly convex function

Xingju Cai, Deren Han, Xiaoming YUAN*

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review

43 Citations (Scopus)

Abstract

The alternating direction method of multipliers (ADMM) is a benchmark for solving a two-block linearly constrained convex minimization model whose objective function is the sum of two functions without coupled variables. Meanwhile, it is known that the convergence is not guaranteed if the ADMM is directly extended to a multiple-block convex minimization model whose objective function has more than two functions. Recently, some authors have actively studied the strong convexity condition on the objective function to sufficiently ensure the convergence of the direct extension of ADMM or the resulting convergence when the original scheme is appropriately twisted. We focus on the three-block case of such a model whose objective function is the sum of three functions, and discuss the convergence of the direct extension of ADMM. We show that when one function in the objective is strongly convex, the penalty parameter and the operators in the linear equality constraint are appropriately restricted, it is sufficient to guarantee the convergence of the direct extension of ADMM. We further estimate the worst-case convergence rate measured by the iteration complexity in both the ergodic and nonergodic senses, and derive the globally linear convergence in asymptotical sense under some additional conditions.

Original languageEnglish
Pages (from-to)39-73
Number of pages35
JournalComputational Optimization and Applications
Volume66
Issue number1
DOIs
Publication statusPublished - 1 Jan 2017

Scopus Subject Areas

  • Control and Optimization
  • Computational Mathematics
  • Applied Mathematics

User-Defined Keywords

  • Alternating direction method of multipliers
  • Convergence analysis
  • Convex programming
  • Separable structure

Fingerprint

Dive into the research topics of 'On the convergence of the direct extension of ADMM for three-block separable convex minimization models with one strongly convex function'. Together they form a unique fingerprint.

Cite this