RESEARCH ARTICLE

Convergence of ADMM for multi-block nonconvex separable optimization models

  • Ke GUO 1 ,
  • Deren HAN , 1 ,
  • David Z. W. WANG 2 ,
  • Tingting WU 3
Expand
  • 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

Received date: 05 Jul 2016

Accepted date: 16 Jan 2017

Published date: 30 Sep 2017

Copyright

2017 Higher Education Press and Springer-Verlag GmbH Germany

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.

Cite this article

Ke GUO , Deren HAN , David Z. W. WANG , Tingting WU . Convergence of ADMM for multi-block nonconvex separable optimization models[J]. Frontiers of Mathematics in China, 2017 , 12(5) : 1139 -1162 . DOI: 10.1007/s11464-017-0631-6

1
AttouchH, BolteJ. On the convergence of the proximal algorithm for nonsmooth functions involving analytic features.Math Program, 2009, 116: 5–16

DOI

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

DOI

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

DOI

4
BoleyD. Local linear convergence of ADMM on quadratic or linear programs.SIAM J Optim, 2013, 23: 2183–2207

DOI

5
BolteJ, DaniilidisA, LewisA. The Lojasiewicz inequality for nonsmooth subanalytic functions with applications to subgradient dynamical systems.SIAM J Optim, 2007, 17: 1205–1223

DOI

6
BolteJ, DaniilidisA, LewisA, ShiotaM. Clarke subgradients of stratifiable functions.SIAM J Optim, 2007, 18: 556–572

DOI

7
BolteJ, SabachS, TeboulleM. Proximal alternating linearized minimization for nonconvex and nonsmooth problem.Math Program, 2014, 146: 459–494

DOI

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

DOI

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

DOI

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

DOI

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

DOI

12
GabayD, MercierB. A dual algorithm for the solution of nonlinear variational problems via finite element approximations.Comput Math Appl, 1976, 2: 17–40

DOI

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

DOI

15
HanD R, YuanX M. A note on the alternating direction method of multipliers.J Optim Theory Appl, 2012, 155: 227–238

DOI

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

DOI

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

DOI

18
HeB S, TaoM, YuanX M. Alternating direction method with Gaussian back substitution for separable convex programming.SIAM J Optim, 2012, 22: 313–340

DOI

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

DOI

21
HongM, LuoZ Q. On the linear convergence of alternating direction method of multipliers.Math Program, 2016, DOI: 10.1007/s10107-016-1034-2

DOI

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

DOI

23
KurdykaK. On gradients of functions definable in o-minimal structures.Ann Inst Fourier (Grenoble), 1998, 48: 769–783

DOI

24
LiG, PongT K. Global convergence of splitting methods for nonconvex composite optimization.SIAM J Optim, 2015, 25: 2434–2460

DOI

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

DOI

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

DOI

29
RockafellarR T. Convex Analysis.Princeton Univ Press, 2015

30
RockafellarR T, WetsR J B. Variational An alysis.Berlin: Springer, 1998

DOI

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

DOI

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

DOI

Outlines

/