Please wait a minute...
Frontiers of Mathematics in China

ISSN 1673-3452

ISSN 1673-3576(Online)

CN 11-5739/O1

Postal Subscription Code 80-964

2018 Impact Factor: 0.565

Front. Math. China    2017, Vol. 12 Issue (5) : 1139-1162    https://doi.org/10.1007/s11464-017-0631-6
RESEARCH ARTICLE
Convergence of ADMM for multi-block nonconvex separable optimization models
Ke GUO1, Deren HAN1(), David Z. W. WANG2, Tingting WU3
1. School of Mathematical Sciences and Key Laboratory for NSLSCS of Jiangsu Province, Nanjing Normal University, Nanjing 210023, China
2. School of Civil and Environmental Engineering, Nanyang Technological University, Singapore 639798, Singapore
3. School of Science, Nanjing University of Posts and Telecommunications, Nanjing 210023, China
 Download: PDF(236 KB)  
 Export: BibTeX | EndNote | Reference Manager | ProCite | RefWorks
Abstract

For solving minimization problems whose objective function is the sum of two functions without coupled variables and the constrained function is linear, the alternating direction method of multipliers (ADMM) has exhibited its efficiency and its convergence is well understood. When either the involved number of separable functions is more than two, or there is a nonconvex function, ADMM or its direct extended version may not converge. In this paper, we consider the multi-block separable optimization problems with linear constraints and absence of convexity of the involved component functions. Under the assumption that the associated function satisfies the Kurdyka- Lojasiewicz inequality, we prove that any cluster point of the iterative sequence generated by ADMM is a critical point, under the mild condition that the penalty parameter is sufficiently large. We also present some sufficient conditions guaranteeing the sublinear and linear rate of convergence of the algorithm.

Keywords Nonconvex optimization      separable structure      alternating direction method of multipliers (ADMM)      Kurdyka-Lojasiewicz inequality     
Corresponding Author(s): Deren HAN   
Issue Date: 30 September 2017
 Cite this article:   
Ke GUO,Deren HAN,David Z. W. WANG, et al. Convergence of ADMM for multi-block nonconvex separable optimization models[J]. Front. Math. China, 2017, 12(5): 1139-1162.
 URL:  
https://academic.hep.com.cn/fmc/EN/10.1007/s11464-017-0631-6
https://academic.hep.com.cn/fmc/EN/Y2017/V12/I5/1139
1 AttouchH, BolteJ. On the convergence of the proximal algorithm for nonsmooth functions involving analytic features.Math Program, 2009, 116: 5–16
https://doi.org/10.1007/s10107-007-0133-5
2 AttouchH, BolteJ, RedontP, SoubeyranA. Proximal alternating minimization and projection methods for nonconvex problems: an approach based on the Kurdyka-Lojasiewicz inequality.Math Oper Res, 2010, 35: 438–457
https://doi.org/10.1287/moor.1100.0449
3 AttouchH, BolteJ, SvaiterB F. Convergence of descent methods for semi-algebraic and tame problems: proximal algorithms, forward-backward splitting, and regularized Gauss-Seidel methods.Math Program, 2013, 137: 91–129
https://doi.org/10.1007/s10107-011-0484-9
4 BoleyD. Local linear convergence of ADMM on quadratic or linear programs.SIAM J Optim, 2013, 23: 2183–2207
https://doi.org/10.1137/120878951
5 BolteJ, DaniilidisA, LewisA. The Lojasiewicz inequality for nonsmooth subanalytic functions with applications to subgradient dynamical systems.SIAM J Optim, 2007, 17: 1205–1223
https://doi.org/10.1137/050644641
6 BolteJ, DaniilidisA, LewisA, ShiotaM. Clarke subgradients of stratifiable functions.SIAM J Optim, 2007, 18: 556–572
https://doi.org/10.1137/060670080
7 BolteJ, SabachS, TeboulleM. Proximal alternating linearized minimization for nonconvex and nonsmooth problem.Math Program, 2014, 146: 459–494
https://doi.org/10.1007/s10107-013-0701-9
8 CaiX J, HanD R, YuanX M. The direct extension of ADMM for three-block separable convex minimization models is convergent when one function is strongly convex.Comput Optim Appl, 2017, 66: 39–73
https://doi.org/10.1007/s10589-016-9860-y
9 ChenC H, HeB S, YeY Y, YuanX M. The direct extension of ADMM for multi-block convex minimization problems is not necessarily convergent.Math Program, 2016, 155: 57–79
https://doi.org/10.1007/s10107-014-0826-5
10 DuB, WangD Z W. Continuum modeling of park-and-ride services considering travel time reliability and heterogeneous commuters—A linear complementarity system approach.Transportation Research Part E: Logistics and Transportation Review, 2014, 71: 58–81
https://doi.org/10.1016/j.tre.2014.08.008
11 GabayD. Applications of the method of multipliers to variational inequalities. In: Fortin M, Glowinski R, eds. Augmented Lagrangian Methods: Applications to the Numerical Solution of Boundary-Value Problems. Amsterdam: North-Holland, 1983, 299–331
https://doi.org/10.1016/S0168-2024(08)70034-1
12 GabayD, MercierB. A dual algorithm for the solution of nonlinear variational problems via finite element approximations.Comput Math Appl, 1976, 2: 17–40
https://doi.org/10.1016/0898-1221(76)90003-1
13 GlowinskiR, MarroccoA. Approximation par éléments finis d’ordre un et résolution par pénalisation dualité d’une classe de probl`emes non linéaires.RAIRO, Analyse numérique, 1975, 9(2): 41–76
14 GuoK, HanD R,WuT T. Convergence of alternating direction method for minimizing sum of two nonconvex functions with linear constraints.Int J Comput Math, 2016, DOI: 10.1080/00207160.2016.1227432
https://doi.org/10.1080/00207160.2016.1227432
15 HanD R, YuanX M. A note on the alternating direction method of multipliers.J Optim Theory Appl, 2012, 155: 227–238
https://doi.org/10.1007/s10957-012-0003-z
16 HanD R, YuanX M. Local linear convergence of the alternating direction method of multipliers for quadratic programs.SIAM J Numer Anal, 2013, 51: 3446–3457
https://doi.org/10.1137/120886753
17 HanD R, YuanX M, ZhangW X. An augmented-Lagrangian-based parallel splitting method for separable convex programming with applications to image processing.Math Comp, 2014, 83: 2263–2291
https://doi.org/10.1090/S0025-5718-2014-02829-9
18 HeB S, TaoM, YuanX M. Alternating direction method with Gaussian back substitution for separable convex programming.SIAM J Optim, 2012, 22: 313–340
https://doi.org/10.1137/110822347
19 HeB S, TaoM, YuanX M. Convergence rate and iteration complexity on the alternating direction method of multipliers with a substitution procedure for separable convex programming.Preprint
20 HeB S, YuanX M. On the O(1/n) convergence rate of the Douglas-Rachford alternating direction method.SIAM J Numer Anal, 2012, 50: 700–709
https://doi.org/10.1137/110836936
21 HongM, LuoZ Q. On the linear convergence of alternating direction method of multipliers.Math Program, 2016, DOI: 10.1007/s10107-016-1034-2
https://doi.org/10.1007/s10107-016-1034-2
22 HongM, LuoZ Q, RazaviyaynM. Convergence analysis of alternating direction method of multipliers for a family of nonconvex problems.SIAM J Optim, 2016, 26: 337–364
https://doi.org/10.1137/140990309
23 KurdykaK. On gradients of functions definable in o-minimal structures.Ann Inst Fourier (Grenoble), 1998, 48: 769–783
https://doi.org/10.5802/aif.1638
24 LiG, PongT K. Global convergence of splitting methods for nonconvex composite optimization.SIAM J Optim, 2015, 25: 2434–2460
https://doi.org/10.1137/140998135
25 LiM, SunD F, TohK C. A convergent 3-block semi-proximal ADMM for convex minimization problems with one strongly convex block.Asia-Pac J Oper Res, 2015, 32: 1550024
https://doi.org/10.1142/S0217595915500244
26 LojasiewiczS. Une propriété topologique des sous-ensembles analytiques réels.Les équations aux dérivées partielles, 1963, 117: 87–89
27 MordukhovichB. Variational Analysis and Generalized Differentiation, I. Basic Theory.Grundlehren Math Wiss, Vol 330. Berlin: Springer, 2006
28 NesterovY. Introductory Lectures on Convex Optimization: A Basic Course.Boston: Kluwer Academic Publishers, 2004
https://doi.org/10.1007/978-1-4419-8853-9
29 RockafellarR T. Convex Analysis.Princeton Univ Press, 2015
30 RockafellarR T, WetsR J B. Variational An alysis.Berlin: Springer, 1998
https://doi.org/10.1007/978-3-642-02431-3
31 WangD Z W, XuL L. Equilibrium trip scheduling in single bottleneck traffic flows considering multi-class travellers and uncertainty—a complementarity formulation.Transportmetrica A: Transport Science, 2016, 12(4): 297–312
32 WenZ W, YangC, LiuX, MarchesiniS. Alternating direction methods for classical and ptychographic phase retrieval.Inverse Problems, 2012, 28: 115010
https://doi.org/10.1088/0266-5611/28/11/115010
33 YangL, PongT K, ChenX J. Alternating direction method of multipliers for nonconvex background/foreground extraction.2015, arXiv: 1506.07029
34 YangW H, HanD R. Linear convergence of alternating direction method of multipliers for a class of convex optimization problems.SIAM J Numer Anal, 2016, 54: 625–640
https://doi.org/10.1137/140974237
[1] Bingsheng HE, Zheng PENG, Xiangfeng WANG. Proximal alternating direction-based contraction methods for separable linearly constrained convex optimization[J]. Front Math Chin, 2011, 6(1): 79-114.
Viewed
Full text


Abstract

Cited

  Shared   
  Discussed