On the Proximal Jacobian Decomposition of ALM for Multiple-Block Separable Convex Minimization Problems and Its Relationship to ADMM

Bingsheng He, Hong Kun Xu, Xiaoming Yuan*

*Corresponding author for this work

Research output: Contribution to journalJournal articlepeer-review

57 Citations (Scopus)

Abstract

The augmented Lagrangian method (ALM) is a benchmark for solving convex minimization problems with linear constraints. When the objective function of the model under consideration is representable as the sum of some functions without coupled variables, a Jacobian or Gauss–Seidel decomposition is often implemented to decompose the ALM subproblems so that the functions’ properties could be used more effectively in algorithmic design. The Gauss–Seidel decomposition of ALM has resulted in the very popular alternating direction method of multipliers (ADMM) for two-block separable convex minimization models and recently it was shown in He et al. (Optimization Online, 2013) that the Jacobian decomposition of ALM is not necessarily convergent. In this paper, we show that if each subproblem of the Jacobian decomposition of ALM is regularized by a proximal term and the proximal coefficient is sufficiently large, the resulting scheme to be called the proximal Jacobian decomposition of ALM, is convergent. We also show that an interesting application of the ADMM in Wang et al. (Pac J Optim, to appear), which reformulates a multiple-block separable convex minimization model as a two-block counterpart first and then applies the original ADMM directly, is closely related to the proximal Jacobian decomposition of ALM. Our analysis is conducted in the variational inequality context and is rooted in a good understanding of the proximal point algorithm.

Original languageEnglish
Pages (from-to)1204-1217
Number of pages14
JournalJournal of Scientific Computing
Volume66
Issue number3
Early online date29 Jun 2015
DOIs
Publication statusPublished - Mar 2016

Scopus Subject Areas

  • Software
  • Theoretical Computer Science
  • Numerical Analysis
  • General Engineering
  • Computational Theory and Mathematics
  • Computational Mathematics
  • Applied Mathematics

User-Defined Keywords

  • Alternating direction method of multipliers
  • Augmented Lagrangian method
  • Convex optimization
  • Jacobian decomposition
  • Parallel computation
  • Proximal point algorithm
  • Variational inequality problem

Fingerprint

Dive into the research topics of 'On the Proximal Jacobian Decomposition of ALM for Multiple-Block Separable Convex Minimization Problems and Its Relationship to ADMM'. Together they form a unique fingerprint.

Cite this