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.
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
References
Attouch H, Bolte J. On the convergence of the proximal algorithm for nonsmooth functions involving analytic features. Math Program, 2009, 116: 5–16
Attouch H, Bolte J, Redont P, Soubeyran A. Proximal alternating minimization and projection methods for nonconvex problems: an approach based on the Kurdyka-Lojasiewicz inequality. Math Oper Res, 2010, 35: 438–457
Attouch H, Bolte J, Svaiter B 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
Boley D. Local linear convergence of ADMM on quadratic or linear programs. SIAM J Optim, 2013, 23: 2183–2207
Bolte J, Daniilidis A, Lewis A. The Lojasiewicz inequality for nonsmooth subanalytic functions with applications to subgradient dynamical systems. SIAM J Optim, 2007, 17: 1205–1223
Bolte J, Daniilidis A, Lewis A, Shiota M. Clarke subgradients of stratifiable functions. SIAM J Optim, 2007, 18: 556–572
Bolte J, Sabach S, Teboulle M. Proximal alternating linearized minimization for non-convex and nonsmooth problem. Math Program, 2014, 146: 459–494
Cai X J, Han D R, Yuan X 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
Chen C H, He B S, Ye Y Y, Yuan X M. The direct extension of ADMM for multi-block convex minimization problems is not necessarily convergent. Math Program, 2016, 155: 57–79
Du B, Wang D 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
Gabay D. 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
Gabay D, Mercier B. A dual algorithm for the solution of nonlinear variational problems via finite element approximations. Comput Math Appl, 1976, 2: 17–40
Glowinski R, Marrocco A. Approximation par éeléements finis d'ordre un et réesolution par péenalisation dualitée d'une classe de problèmes non linéeaires. RAIRO, Analyse numéerique, 1975, 9(2): 41–76
Guo K, Han D R, Wu T 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
Han D R, Yuan X M. A note on the alternating direction method of multipliers. J Optim Theory Appl, 2012, 155: 227–238
Han D R, Yuan X M. Local linear convergence of the alternating direction method of multipliers for quadratic programs. SIAM J Numer Anal, 2013, 51: 3446–3457
Han D R, Yuan X M, Zhang W X. An augmented-Lagrangian-based parallel splitting method for separable convex programming with applications to image processing. Math Comp, 2014, 83: 2263–2291
He B S, Tao M, Yuan X M. Alternating direction method with Gaussian back substitution for separable convex programming. SIAM J Optim, 2012, 22: 313–340
He B S, Tao M, Yuan X M. Convergence rate and iteration complexity on the alternating direction method of multipliers with a substitution procedure for separable convex programming. Preprint
He B S, Yuan X M. On the O(1=n) convergence rate of the Douglas-Rachford alternating direction method. SIAM J Numer Anal, 2012, 50: 700–709
Hong M, Luo Z Q. On the linear convergence of alternating direction method of multipliers. Math Program, 2016, DOI: 10.1007/s10107-016-1034-2
Hong M, Luo Z Q, Razaviyayn M. Convergence analysis of alternating direction method of multipliers for a family of nonconvex problems. SIAM J Optim, 2016, 26: 337–364
Kurdyka K. On gradients of functions definable in o-minimal structures. Ann Inst Fourier (Grenoble), 1998, 48: 769–783
Li G, Pong T K. Global convergence of splitting methods for nonconvex composite optimization. SIAM J Optim, 2015, 25: 2434–2460
Li M, Sun D F, Toh K 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
Lojasiewicz S. Une propriéetée topologique des sous-ensembles analytiques réeels. Les éequations aux déerivéees partielles, 1963, 117: 87–89
Mordukhovich B. Variational Analysis and Generalized Differentiation, I. Basic Theory. Grundlehren Math Wiss, Vol 330. Berlin: Springer, 2006
Nesterov Y. Introductory Lectures on Convex Optimization: A Basic Course. Boston: Kluwer Academic Publishers, 2004
Rockafellar R T. Convex Analysis. Princeton Univ Press, 2015
Rockafellar R T, Wets R J B. Variational Analysis. Berlin: Springer, 1998
Wang D Z W, Xu L L. Equilibrium trip scheduling in single bottleneck traffic ows considering multi-class travellers and uncertaintya complementarity formulation. Transportmetrica A: Transport Science, 2016, 12(4): 297–312
Wen Z W, Yang C, Liu X, Marchesini S. Alternating direction methods for classical and ptychographic phase retrieval. Inverse Problems, 2012, 28: 115010
Yang L, Pong T K, Chen X J. Alternating direction method of multipliers for non-convex background/foreground extraction. 2015, arXiv: 1506.07029
Yang W H, Han D R. Linear convergence of alternating direction method of multipliers for a class of convex optimization problems. SIAM J Numer Anal, 2016, 54: 625–640
Author information
Authors and Affiliations
Corresponding author
Rights and permissions
About this article
Cite this article
Guo, K., Han, D., Wang, D.Z.W. et al. Convergence of ADMM for multi-block nonconvex separable optimization models. Front. Math. China 12, 1139–1162 (2017). https://doi.org/10.1007/s11464-017-0631-6
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s11464-017-0631-6
Keywords
- Nonconvex optimization
- separable structure
- alternating direction method of multipliers (ADMM)
- Kurdyka-Lojasiewicz inequality