Convergence of alternating direction method for minimizing sum of two nonconvex functions with linear constraints

References

• P.A. Absil, R. Mahony, and B. Andrews, Convergence of the iterates of descent methods for analytic cost functions, SIAM J. Optim. 16 (2005), pp. 531–547.
   Web of Science ®Google Scholar
• H. Attouch and J. Bolte, On the convergence of the proximal algorithm for nonsmooth functions involving analytic features, Math. Program. 116 (2009), pp. 5–16.
   Web of Science ®Google Scholar
• H. Attouch, J. Bolte, P. Redont, and A. Soubeyran, Proximal alternating minimization and projection methods for nonconvex problems: An approach based on the Kurdyka–Łojasiewicz inequality, Math. Oper. Res. 35 (2010), pp. 438–457.
   Web of Science ®Google Scholar
• H. Attouch, J. Bolte, and B.F. Svaiter, Convergence of descent methods for semi-algebraic and tame problems: Proximal algorithms, forward-backward splitting, and regularized Gauss–Seidel methods, Math. Program. 137 (2013), pp. 91–129.
   Web of Science ®Google Scholar
• D. Boley, Local linear convergence of ADMM on quadratic or linear programs, SIAM J. Optim. 23 (2013), pp. 2183–2207.
   Web of Science ®Google Scholar
• J. Bolte, A. Daniilidis, O. Ley, and L. Mazet, Characterization of Łojasiewicz inequalities: Subgradient flows, talweg, convexity, Trans. Amer. Math. Soc. 362 (2010), pp. 3319–3363.
   Web of Science ®Google Scholar
• J. Bolte, A. Daniilidis, and A. Lewis, The Łojasiewicz inequality for nonsmooth subanalytic functions with applications to subgradient dynamical systems, SIAM J. Optim. 17 (2006), pp. 1205–1223.
   Web of Science ®Google Scholar
• J. Bolte, A. Daniilidis, A. Lewis, and M. Shiota, Clarke subgradients of stratifiable functions, SIAM J. Optim. 18 (2007), pp. 556–572.
   Web of Science ®Google Scholar
• J. Bolte, S. Sabach, and M. Teboulle, Proximal alternating linearized minimization for nonconvex and nonsmooth problem, Math. Program. 146 (2014), pp. 459–494.
   Web of Science ®Google Scholar
• X.J. Cai, Y.N. Chen, and D.R. Han, Nonnegative tensor factorizations using an alternating direction method, Front. Math. China. 8 (2013), pp. 3–18.
   Web of Science ®Google Scholar
• E. Chouzenoux, J.C. Pesquet, and A. Repetti, Variable metric forward-backward algorithm for minimizing the sum of a differentiable function and a convex function, J. Optim. Theory Appl. 162 (2014), pp. 107–132.
   Web of Science ®Google Scholar
• P. Frankel, G. Garrigos, and J. Peypouquet, Splitting methods with variable metric for Kurdyka–Łojasiewicz functions and general convergence rates, J. Optim. Theory Appl. 165 (2015), pp. 874–900.
   Web of Science ®Google Scholar
• D. Gabay, Applications of the method of multipliers to variational inequalities, in Augmented Lagrangian Methods: Applications to the Numerical Solution of Boundary-Value Problems, M. Fortin and R. Glowinski, eds., North-Holland, Amsterdam, 1983, pp. 299–331.
   Google Scholar
• D. Gabay and B. Mercier, A dual algorithm for the solution of nonlinear variational problems via finite element approximations, Comput. Math. Appl. 2 (1976), pp. 17–40.
   Google Scholar
• R. Glowinski and A. Marrocco, Sur l'approximation par e´le´ments finis d'ordre un et la re´solution par pe´nalisation-dualite´ d'une classe de proble`mes de Dirichlet non line´aires, Revue Fr. Autom. Inform. Rech. Op$\acute{\mathrm{e}}$r., Anal. Num$\acute{\mathrm{e}}$r. 2 (1975), pp. 41–76.
   Google Scholar
• D.R. Han and X.M. Yuan, Local linear convergence of the alternating direction method of multipliers for quadratic programs, SIAM J. Numer. Anal. 51 (2013), pp. 3446–3457.
   Web of Science ®Google Scholar
• B.S. He and X.M. Yuan, On the O(1/n) convergence rate of the Douglas–Rachford alternating direction method, SIAM J. Num. Anal. 50 (2012), pp. 700–709.
   Web of Science ®Google Scholar
• M. Hong, Z.Q. Luo, and M. Razaviyayn, Convergence analysis of alternating direction method of multipliers for a family of nonconvex problems, SIAM J. Optim. 26 (2016), pp. 337–364.
   Web of Science ®Google Scholar
• K. Kurdyka, On gradients of functions definable in o-minimal structures, Annales de l'institut Fourier. 48 (1998), pp. 769–783.
   Web of Science ®Google Scholar
• G. Li and T.K. Pong, Global convergence of splitting methods for nonconvex composite optimization, SIAM J. Optim. 25 (2015), pp. 2434–2460.
   Web of Science ®Google Scholar
• A.P. Liavax and N.D. Sidiropoulos, Parallel algorithms for constrained tensor factorization via the alternating direction method of multipliers, IEEE Trans. Signal Process. 63 (2015), pp. 5450–5463.
   Web of Science ®Google Scholar
• P.L. Lions and B. Mercier, Splitting algorithms for the sum of two nonlinear operators, SIAM J. Numer. Anal. 16 (1979), pp. 964–979.
   Web of Science ®Google Scholar
• J. Liu, J. Chen, and J. Ye, Large-scale sparse logistic regression, Proceedings of the 15th ACM SIGKDD international conference on Knowledge discovery and data mining, ACM, Paris, 2009, pp. 547–556.
   Google Scholar
• S. Łojasiewicz, Une proprie´te´ topologique des sous-ensembles analytiques re´els, Les E´quations aux De´rive´es partielles. E´ditions du centre National de la Recherche Scientifique, Paris, 1963, pp. 8–89.
   Google Scholar
• B. Merlet and M. Pierre, Convergence to equilibrium for the backward Euler scheme and applications, Commun. Pure Appl. Anal. 9 (2010), pp. 685–702.
   Web of Science ®Google Scholar
• B. Mordukhovich, Variational analysis and generalized differentiation I: Basic theory, Grundlehren der Mathematischen Wissenschaften, Vol. 330, Springer, Berlin, 2006.
   Google Scholar
• Y. Nesterov, Introductory Lectures on Convex Optimization: A Basic Course, Kluwer Academic Publishers, Boston, 2004.
   Google Scholar
• D. Noll, Convergence of non-smooth descent methods using the Kurdyka–Łojasiewicz inequality, J. Optim. Theory Appl. 160 (2014), pp. 553–572.
   Web of Science ®Google Scholar
• D.W. Peaceman and H.H. Rachford, The numerical solution of parabolic and elliptic differential equations, J. Soc. Indust. Appl. Math. 3 (1955), pp. 28–41.
   Google Scholar
• R.T. Rockafellar and R.J.-B. Wets, Variational Analysis, Springer, Berlin, 1998.
   Google Scholar
• D.L. Sun and C. Fevotte, Alternating direction method of multipliers for non-negative matrix factorization with the beta-divergence, 2014 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP), IEEE, Florence, 2014, pp. 6201–6205.
   Google Scholar
• F.H. Wang, Z.B. Xu, and H.K. Xu, Convergence of alternating direction method with multipliers for non-convex composite problems, arXiv:1410.8625.
   Google Scholar
• Z.W. Wen, C. Yang, X. Liu, and S. Marchesini, Alternating direction methods for classical and ptychographic phase retrieval, Inverse Probl. 28 (2012), pp. 1–18.
   Web of Science ®Google Scholar
• Z.B. Xu, X.Y. Chang, F.M. Xu, and H. Zhang, ℓ1/2 Regularization: A thresholding representation theory and a fast solver, IEEE Trans. Neural Netw. Learn. Syst. 23 (2012), pp. 1013–1027.
   PubMed Web of Science ®Google Scholar
• Y. Xu, W.T. Yin, Z.W. Wen, and Y. Zhang, An alternating direction algorithm for matrix completion with nonnegative factors, Front. Math. China. 7 (2011), pp. 365–384.
   Web of Science ®Google Scholar
• W.H. Yang and D.R. Han, Linear convergence of alternating direction method of multipliers for a class of convex optimization problems, SIAM J. Numer. Anal. 54 (2016), pp. 625–640.
   Web of Science ®Google Scholar
• Y. Zhang, An alternating direction algorithm for nonnegative matrix factorization, Citeseer, Preprint (2010).
   Google Scholar
• R. Zhang and J.T. Kwok, Asynchronous distributed ADMM for consensus optimization, Proceedings of the 31st International Conference on Machine Learning, Beijing, 2014, pp. 1701–1709.
   Google Scholar