Alternating direction method with Gaussian back substitution for separable convex programming

Bingsheng He, Min Tao, Xiaoming YUAN*

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review

209 Citations (Scopus)

Abstract

We consider the linearly constrained separable convex minimization problem whose objective function is separable into m individual convex functions with nonoverlapping variables. A Douglas-Rachford alternating direction method of multipliers (ADM) has been well studied in the literature for the special case of m = 2. But the convergence of extending ADM to the general case of m ≥ 3 is still open. In this paper, we show that the straightforward extension of ADM is valid for the general case of m ≥ 3 if it is combined with a Gaussian back substitution procedure. The resulting ADM with Gaussian back substitution is a novel approach towards the extension of ADM from m = 2 to m ≥ 3, and its algorithmic framework is new in the literature. For the ADM with Gaussian back substitution, we prove its convergence via the analytic framework of contractive-type methods, and we show its numerical efficiency by some application problems.

Original languageEnglish
Pages (from-to)313-340
Number of pages28
JournalSIAM Journal on Optimization
Volume22
Issue number2
DOIs
Publication statusPublished - 2012

Scopus Subject Areas

  • Software
  • Theoretical Computer Science

User-Defined Keywords

  • Alternating direction method
  • Convex programming
  • Gaussian back substitution
  • Separable structure

Fingerprint

Dive into the research topics of 'Alternating direction method with Gaussian back substitution for separable convex programming'. Together they form a unique fingerprint.

Cite this