The Proximal Alternating Direction Method of Multipliers in the Nonconvex Setting: Convergence Analysis and Rates

References

• [1] Ames B, Hong M (2016) Alternating direction method of multipliers for penalized zero-variance discriminant analysis. Comput. Optim. Appl. 64(3):725–754.Crossref, Google Scholar
• [2] Attouch H, Bolte J (2009) On the convergence of the proximal algorithm for nonsmooth functions involving analytic features. Math. Programming 116(1):5–16.Crossref, Google Scholar
• [3] Attouch H, Bolte J, Svaiter BF (2013) Convergence of descent methods for semi-algebraic and tame problems: Proximal algorithms, forward-backward splitting, and regularized Gauss-Seidel methods. Math. Programming 137(1–2):91–129.Crossref, Google Scholar
• [4] Attouch H, Bolte J, Redont P, Soubeyran A (2010) Proximal alternating minimization and projection methods for nonconvex problems: An approach based on the Kurdyka-Łojasiewicz inequality. Math. Oper. Res. 35(2):438–457.Google Scholar
• [5] Banert S, Boţ RI, Csetnek ER (2016) Fixing and extending some recent results on the ADMM algorithm. Working paper, KTH Royal Institute of Technology, Stockholm, Sweden.Google Scholar
• [6] Beck A (2017) First-Order Methods in Optimization. MOS-SIAM Series on Optimization (Society for Industrial and Applied Mathematics, Philadelphia).Crossref, Google Scholar
• [7] Bolte J, Daniilidis A, Lewis A (2006) The Łojasiewicz inequality for nonsmooth subanalytic functions with applications to subgradient dynamical systems. SIAM J. Optim. 17(4):1205–1223.Crossref, Google Scholar
• [8] Bolte J, Sabach S, Teboulle M (2014) Proximal alternating linearized minimization for nonconvex and nonsmooth problems. Math. Programming 146(1):459–494.Crossref, Google Scholar
• [9] Bolte J, Sabach S, Teboulle M (2018) Nonconvex Lagrangian-based optimization: monitoring schemes and global convergence. Math. Oper. Res. 43(4):1210–1232.Link, Google Scholar
• [10] Bolte J, Daniilidis A, Lewis A, Shiota M (2007) Clarke subgradients of stratifiable functions. SIAM J. Optim. 18(2):556–572.Crossref, Google Scholar
• [11] Bolte J, Daniilidis A, Ley M, Mazet L (2010) Characterizations of Łojasiewicz inequalities: Subgradient flows, talweg, convexity. Trans. Amer. Math. Soc. 362(6):3319–3363.Crossref, Google Scholar
• [12] Boţ RI, Csetnek ER (2016) An inertial alternating direction method of multipliers. Minimax Theory Appl. 1(1):29–49.Google Scholar
• [13] Boţ RI, Csetnek ER (2016) An inertial Tseng’s type proximal algorithm for nonsmooth and nonconvex optimization problems. J. Optim. Theory Appl. 171(2):600–616.Crossref, Google Scholar
• [14] Boţ RI, Csetnek ER (2019) ADMM for monotone operators: Convergence analysis and rates. Adv. Comput. Math. 45(1):327–359.Crossref, Google Scholar
• [15] Boţ RI, Csetnek ER, Heinrich A (2013) A primal-dual splitting algorithm for finding zeros of sums of maximal monotone operators. SIAM J. Optim. 23(4):2011–2036.Crossref, Google Scholar
• [16] Boţ RI, Csetnek ER, László SC (2016) An inertial forward-backward algorithm for the minimization of the sum of two nonconvex functions. EURO J. Comput. Optim. 4(1):3–25.Crossref, Google Scholar
• [17] Boyd S, Parikh N, Chu E, Peleato B, Eckstein J (2010) Distributed optimization and statistical learning via the alternating direction method of multipliers. Found. Trends Machine Learn. 3(1):1–122.Crossref, Google Scholar
• [18] Chambolle A, Pock T (2011) A first-order primal-dual algorithm for convex problems with applications to imaging. J. Math. Imaging Vision 40(1):120–145.Crossref, Google Scholar
• [19] Combettes PL, Vũ BC (2014) Variable metric quasi-Fejér monotonicity. Nonlinear Anal.: Theory Methods Appl. 78:17–31.Crossref, Google Scholar
• [20] Combettes PL, Ways VR (2005) Signal recovery by proximal forward-backward splitting. Multiscale Model. Simulation 4(4):1168–1200.Crossref, Google Scholar
• [21] Condat L (2013) A primal-dual splitting method for convex optimization involving Lipschitzian, proximable and linear composite terms. J. Optim. Theory Appl. 158(2):460–479.Crossref, Google Scholar
• [22] Cui Y, Li XD, Sun DF, Toh KC (2016) On the convergence properties of a majorized ADMM for linearly constrained convex optimization problems with coupled objective functions. J. Optim. Theory Appl. 169(3):1013–1041.Crossref, Google Scholar
• [23] Fazel M, Pong TK, Sun DF, Tseng P (2013) Hankel matrix rank minimization with applications to system identification and realization. SIAM J. Matrix Anal. Appl. 34(3):946–977.Crossref, Google Scholar
• [24] Fortin M, Glowinski R (1983) On decomposition-coordination methods using an augmented Lagrangian. Fortin M, Glowinski R, eds. Augmented Lagrangian Methods: Applications to the Solution of Boundary-Value Problems (North-Holland, Amsterdam), 97–146.Google Scholar
• [25] Frankel P, Garrigos G, Peypouquet J (2015) Splitting methods with variable metric for Kurdyka-Łojasiewicz functions and general convergence rates. J. Optim. Theory Appl. 165(3):874–900.Crossref, Google Scholar
• [26] Gabay D (1983) Applications of the method of multipliers to variational inequalities. Fortin M, Glowinski R, eds. Augmented Lagrangian Methods: Applications to the Solution of Boundary-Value Problems (North-Holland, Amsterdam), 299–331.Google Scholar
• [27] Gabay D, Mercier B (1976) A dual algorithm for the solution of nonlinear variational problems via finite element approximation. Comput. Math. Appl. 2(1):17–40.Crossref, Google Scholar
• [28] Guo K, Han DR, Wu TT (2017) Convergence of alternating direction method for minimizing sum of two nonconvex functions with linear constraints. Internat. J. Comput. Math. 94(8):1653–1669.Crossref, Google Scholar
• [29] Hare W, Sagastizábal C (2009) Computing proximal points of nonconvex functions. Math. Programming 116(1–2):221–258.Crossref, Google Scholar
• [30] Hong M, Luo ZQ (2017) On the linear convergence of the alternating direction method of multipliers. Math. Programming 162(1–2):165–199.Crossref, Google Scholar
• [31] Hong M, Luo ZQ, Razaviyayn M (2016) Convergence analysis of alternating direction method of multipliers for a family of nonconvex problems. SIAM J. Optim. 26(1):337–364.Crossref, Google Scholar
• [32] Kurdyka K (1998) On gradients of functions definable in o-minimal structures. Annales de l'Institut Fourier 48(3):769–783.Crossref, Google Scholar
• [33] Lewis A, Malick J (2008) Alternating projection on manifolds. Math. Oper. Res. 33(1):216–234.Link, Google Scholar
• [34] Li G, Pong TK (2015) Global convergence of splitting methods for nonconvex composite optimization. SIAM J. Optim. 25(4):2434–2460.Crossref, Google Scholar
• [35] Lin Z, Liu R, Li H (2015) Linearized alternating direction method with parallel splitting and adaptive penalty for separable convex programs in machine learning. Machine Learn. 99(2):287–325.Crossref, Google Scholar
• [36] Liu Q, Shen X, Gu Y (2017) Linearized ADMM for non-convex non-smooth optimization with convergence analysis.Google Scholar
• [37] Łojasiewicz S (1963) Une propriété topologique des sous-ensembles analytiques réels. Colloques internationaux du CNRS, 1962: Les équations aux dérivées partielles (Centre National de la Recherche Scientifique, Paris).Google Scholar
• [38] Mordukhovich B (2006) Variational Analysis and Generalized Differentiation, 2 vols. (Springer, Berlin).Crossref, Google Scholar
• [39] Moreau JJ (1962) Fonctions convexes duales et points proximaux dans un espace Hilbertien. Comptes rendus Acad. Sci. Ser. A 255:2897–2899.Google Scholar
• [40] Ouyang Y, Chen Y, Lan G, Pasiliao E Jr (2015) An accelerated linearized alternating direction method of multipliers. SIAM J. Imaging Sci. 8(1):644–681.Crossref, Google Scholar
• [41] Ren X, Lin Z (2013) Linearized alternating direction method with adaptive penalty and warm starts for fast solving transform invariant low-rank textures. Internat. J. Comput. Vision 104(1):1–14.Crossref, Google Scholar
• [42] Rockafellar RT, Wets RJB (1998) Variational Analysis. Fundamental Principles of Mathematical Sciences, vol. 317 (Springer, Berlin).Crossref, Google Scholar
• [43] Shefi R, Teboulle M (2014) Rate of convergence analysis of decomposition methods based on the proximal method of multipliers for convex minimization. SIAM J. Optim. 24(1):269–297.Crossref, Google Scholar
• [44] Sun D, Toh KC, Yang L (2015) A convergent 3-block semi-proximal alternating direction method of multipliers for conic programming with 4-type constraints. SIAM J. Optim. 25(2):882–915.Crossref, Google Scholar
• [45] Vũ BC (2013) A splitting algorithm for dual monotone inclusions involving cocoercive operators. Adv. Comput. Math. 38(3):667–681.Crossref, Google Scholar
• [46] Wang Y, Xu Z, Xu HK (2015) Convergence of Bregman alternating direction method with multipliers for nonconvex composite problems. Report 15-62, Computational and Applied Mathematics, University of California, Los Angeles.Google Scholar
• [47] Wang Y, Yin W, Zeng J (2019) Global convergence of ADMM in nonconvex nonsmooth optimization. J. Sci. Comput. 78(1):29–63.Crossref, Google Scholar
• [48] Xu MH, Wu T (2011) A class of linearized proximal alternating direction methods. J. Optim. Theory Appl. 151(2):321–337.Crossref, Google Scholar
• [49] Yang J, Yuan X (2013) Linearized augmented Lagrangian and alternating direction methods for nuclear norm minimization. Math. Comput. 82:301–329.Crossref, Google Scholar
• [50] Yang L, Pong TK, Chen X (2017) Alternating direction method of multipliers for a class of nonconvex and nonsmooth problems with applications to background/foreground extraction. SIAM J. Imaging Sci. 10(1):74–110.Crossref, Google Scholar