TY - JOUR
T1 - Alternating Direction Method with Gaussian Back Substitution for Separable Convex Programming
AU - He, Bingsheng
AU - Tao, Min
AU - Yuan, Xiaoming
N1 - Funding information:
Department of Mathematics, Nanjing University, Nanjing, Jiangsu, 210093, People’s Republic of China ([email protected], [email protected]). The first author was supported by NSFC grants 10971095 and 91130007, the Cultivation Fund of KSTIP-MOEC 708044, and the MOEC fund 20110091110004.
$ Corresponding author. Department of Mathematics, Hong Kong Baptist University, Kowloon Tong, Kowloon, Hong Kong, People’s Republic of China ([email protected]). This author was supported by the General Research Fund of Hong Kong: HKBU203311.
Publisher copyright:
Copyright © 2012 Society for Industrial and Applied Mathematics
PY - 2012/4/12
Y1 - 2012/4/12
N2 - 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.
AB - 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.
KW - Alternating direction method
KW - Convex programming
KW - Gaussian back substitution
KW - Separable structure
UR - http://www.scopus.com/inward/record.url?scp=84865692854&partnerID=8YFLogxK
U2 - 10.1137/110822347
DO - 10.1137/110822347
M3 - Journal article
AN - SCOPUS:84865692854
SN - 1052-6234
VL - 22
SP - 313
EP - 340
JO - SIAM Journal on Optimization
JF - SIAM Journal on Optimization
IS - 2
ER -