Optimization Online


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

Bingsheng He (hebma***at***nju.edu.cn)
Hong-Kun Xu (xuhk***at***math.nsysu.edu.tw)
Xiaoming Yuan (xmyuan***at***hkbu.edu.hk)

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 [10] 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 [20], 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.

Keywords: Convex optimization, Alternating direction method of multipliers, Augmented Lagrangian method, Jacobian decomposition, Parallel computation, Proximal point algorithm, Variational inequality problem.

Category 1: Convex and Nonsmooth Optimization (Convex Optimization )


Download: [PDF]

Entry Submitted: 11/29/2013
Entry Accepted: 11/29/2013
Entry Last Modified: 12/05/2013

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Optimization Society