Convergence of ADMM for multi-block nonconvex separable optimization models

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

References

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

[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

[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

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

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

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

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

[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

[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

[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

[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

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

[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

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

[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

[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

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

[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

[21] HongM, LuoZ Q. On the linear convergence of alternating direction method of multipliers.Math Program, 2016, DOI: 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

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

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

[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

[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

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

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

[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

[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

RIGHTS & PERMISSIONS

Higher Education Press and Springer-Verlag GmbH Germany