Volume 37, Issue 6
A Unified Algorithmic Framework of Symmetric Gauss-Seidel Decomposition Based Proximal ADMMs for Convex Composite Programming

Liang Chen, Defeng Sun, Kim-Chuan Toh & Ning Zhang

J. Comp. Math., 37 (2019), pp. 739-757.

Published online: 2019-11

Preview Full PDF 398 6037
Export citation
  • Abstract

This paper aims to present a fairly accessible generalization of several symmetric Gauss-Seidel decomposition based multi-block proximal alternating direction methods of multipliers (ADMMs) for convex composite optimization problems. The proposed method unifies and refines many constructive techniques that were separately developed for the computational efficiency of multi-block ADMM-type algorithms. Specifically, the majorized augmented Lagrangian functions, the indefinite proximal terms, the inexact symmetric Gauss-Seidel decomposition theorem, the tolerance criteria of approximately solving the subproblems, and the large dual step-lengths, are all incorporated in one algorithmic framework, which we named as sGS-imiPADMM. From the popularity of convergent variants of multi-block ADMMs in recent years, especially for high-dimensional multi-block convex composite conic programming problems, the unification presented in this paper, as well as the corresponding convergence results, may have the great potential of facilitating the implementation of many multi-block ADMMs in various problem settings.

  • Keywords

Convex optimization, Multi-block, Alternating direction method of multipliers, Symmetric Gauss-Seidel decomposition, Majorization.

  • AMS Subject Headings

90C25, 90C22, 90C06, 65K05

  • Copyright

COPYRIGHT: © Global Science Press

  • Email address

chl@hnu.edu.cn (Liang Chen)

defeng.sun@polyu.edu.hk (Defeng Sun)

mattohkc@nus.edu.sg (Kim-Chuan Toh)

ningzhang_2008@yeah.net (Ning Zhang)

  • BibTex
  • RIS
  • TXT
@Article{JCM-37-739, author = {Chen , Liang and Sun , Defeng and Toh , Kim-Chuan and Zhang , Ning}, title = {A Unified Algorithmic Framework of Symmetric Gauss-Seidel Decomposition Based Proximal ADMMs for Convex Composite Programming}, journal = {Journal of Computational Mathematics}, year = {2019}, volume = {37}, number = {6}, pages = {739--757}, abstract = {

This paper aims to present a fairly accessible generalization of several symmetric Gauss-Seidel decomposition based multi-block proximal alternating direction methods of multipliers (ADMMs) for convex composite optimization problems. The proposed method unifies and refines many constructive techniques that were separately developed for the computational efficiency of multi-block ADMM-type algorithms. Specifically, the majorized augmented Lagrangian functions, the indefinite proximal terms, the inexact symmetric Gauss-Seidel decomposition theorem, the tolerance criteria of approximately solving the subproblems, and the large dual step-lengths, are all incorporated in one algorithmic framework, which we named as sGS-imiPADMM. From the popularity of convergent variants of multi-block ADMMs in recent years, especially for high-dimensional multi-block convex composite conic programming problems, the unification presented in this paper, as well as the corresponding convergence results, may have the great potential of facilitating the implementation of many multi-block ADMMs in various problem settings.

}, issn = {1991-7139}, doi = {https://doi.org/10.4208/jcm.1803-m2018-0278}, url = {http://global-sci.org/intro/article_detail/jcm/13372.html} }
TY - JOUR T1 - A Unified Algorithmic Framework of Symmetric Gauss-Seidel Decomposition Based Proximal ADMMs for Convex Composite Programming AU - Chen , Liang AU - Sun , Defeng AU - Toh , Kim-Chuan AU - Zhang , Ning JO - Journal of Computational Mathematics VL - 6 SP - 739 EP - 757 PY - 2019 DA - 2019/11 SN - 37 DO - http://doi.org/10.4208/jcm.1803-m2018-0278 UR - https://global-sci.org/intro/article_detail/jcm/13372.html KW - Convex optimization, Multi-block, Alternating direction method of multipliers, Symmetric Gauss-Seidel decomposition, Majorization. AB -

This paper aims to present a fairly accessible generalization of several symmetric Gauss-Seidel decomposition based multi-block proximal alternating direction methods of multipliers (ADMMs) for convex composite optimization problems. The proposed method unifies and refines many constructive techniques that were separately developed for the computational efficiency of multi-block ADMM-type algorithms. Specifically, the majorized augmented Lagrangian functions, the indefinite proximal terms, the inexact symmetric Gauss-Seidel decomposition theorem, the tolerance criteria of approximately solving the subproblems, and the large dual step-lengths, are all incorporated in one algorithmic framework, which we named as sGS-imiPADMM. From the popularity of convergent variants of multi-block ADMMs in recent years, especially for high-dimensional multi-block convex composite conic programming problems, the unification presented in this paper, as well as the corresponding convergence results, may have the great potential of facilitating the implementation of many multi-block ADMMs in various problem settings.

Liang Chen, Defeng Sun, Kim-Chuan Toh & Ning Zhang. (2019). A Unified Algorithmic Framework of Symmetric Gauss-Seidel Decomposition Based Proximal ADMMs for Convex Composite Programming. Journal of Computational Mathematics. 37 (6). 739-757. doi:10.4208/jcm.1803-m2018-0278
Copy to clipboard
The citation has been copied to your clipboard