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.

Key words： 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