zbMATH — the first resource for mathematics

Global convergence of ADMM in nonconvex nonsmooth optimization. (English) Zbl 07042437
The authors consider the following optimization problem: $\left\{ \begin{array}{l}\underset{x_{0},\ldots ,x_{p},y}{\mathrm{min}}\mathrm{\quad }\phi (x_{0},\ldots ,x_{p},y) \\ \text{subject to }\, A_{0}x_{0}+A_{1}x_{1}+\ldots +A_{p}x_{p}+By=0 \end{array}\right.$ where $$\phi$$ is a continuous (possibly nonconvex, nonsmooth) function, $$x_{i}\in \mathbb{R}^{n_{i}}$$, $$y\in \mathbb{R}^{q}$$ and $$A_{i}$$, $$B$$ are $$m\times n_{i}$$ (resp. $$m\times q$$) matrices. The authors propose an ADMM (Alternating Direction Method of Multipliers) type algorithm (multi-block version) that updates sucessively each of the primal variables $$x_{0}, \dots, x_{p}, y$$ followed by an update of the dual variable. Under certain assumptions they establish global convergence. This approach applies to problems arising in matrix decomposition, sparse recovery, machine learning and optimization on compact smooth manifolds, covering cases that were not previously covered by any convergence theory. They also discuss relations with the ADL (Augmented Lagrangian Method) and provide an example in which ADMM converges but the latter diverges.

MSC:
 65K05 Numerical mathematical programming methods 90C26 Nonconvex programming, global optimization
Software:
 [1] Attouch, H.; Bolte, J.; Svaiter, B., Convergence of descent methods for semi-algebraic and tame problems: proximal algorithms, forward-backward splitting, and regularized Gauss-Seidel methods, Math. Program., 137, 91-129, (2013) · Zbl 1260.49048 [2] Bach, F.; Jenatton, R.; Mairal, J.; Obozinski, G., Optimization with sparsity-inducing penalties, Found. Trends Mach. Learn., 4, 1-106, (2012) · Zbl 06064248 [3] Bertsekas, D.P.: Constrained Optimization and Lagrange Multiplier Methods. Academic Press, London (2014) · Zbl 0572.90067 [4] Birgin, E.G., Martínez, J.M.: Practical Augmented Lagrangian Methods for Constrained Optimization, vol. 10. SIAM, Philadelphia (2014) · Zbl 1339.90312 [5] Bolte, J.; Daniilidis, A.; Lewis, A., The Lojasiewicz inequality for nonsmooth subanalytic functions with applications to subgradient dynamical systems, SIAM J. Optim., 17, 1205-1223, (2007) · Zbl 1129.26012 [6] Bouaziz, S., Tagliasacchi, A., Pauly, M.: Sparse iterative closest point. In: Computer graphics forum, vol. 32, pp. 113-123. Wiley Online Library (2013) [7] Cai, JF; Candès, EJ; Shen, Z., A singular value thresholding algorithm for matrix completion, SIAM J. Optim., 20, 1956-1982, (2010) · Zbl 1201.90155 [8] Chartrand, R., Nonconvex splitting for regularized low-rank $$+$$ sparse decomposition, IEEE Trans. Signal Process., 60, 5810-5819, (2012) · Zbl 1393.94190 [9] Chartrand, R., Wohlberg, B.: A nonconvex ADMM algorithm for group sparsity with sparse groups. In: 2013 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP), pp. 6009-6013. IEEE (2013) [10] Chen, C.; He, B.; Ye, Y.; Yuan, X., The direct extension of ADMM for multi-block convex minimization problems is not necessarily convergent, Math. Program., 155, 57-79, (2016) · Zbl 1332.90193 [11] Chen C., Yuan, X., Zeng, S., Zhang, J.: Penalty splitting methods for solving mathematical program with equilibrium constraints. Manuscript (private communication) (2016) [12] Conn, AR; Gould, NI; Toint, P., A globally convergent augmented Lagrangian algorithm for optimization with general constraints and simple bounds, SIAM J. Numer. Anal., 28, 545-572, (1991) · Zbl 0724.65067 [13] Cottle, R.; Dantzig, G., Complementary pivot theory of mathematical programming, Linear Algebra Appl., 1, 103-125, (1968) · Zbl 0155.28403 [14] Daubechies, I.; DeVore, R.; Fornasier, M.; Güntürk, CS, Iteratively reweighted least squares minimization for sparse recovery, Commun. Pure Appl. Math., 63, 1-38, (2010) · Zbl 1202.65046 [15] Davis, D.; Yin, W.; Glowinski, R. (ed.); Osher, S. (ed.); Yin, W. (ed.), Convergence rate analysis of several splitting schemes, (2016), New York [16] Davis, D.; Yin, W., Convergence rates of relaxed Peaceman-Rachford and ADMM under regularity assumptions, Math. Oper. Res., 42, 783-805, (2017) · Zbl 1379.65035 [17] Deng, W.; Lai, MJ; Peng, Z.; Yin, W., Parallel multi-block ADMM with $$o (1/k)$$ convergence, J. Sci. Comput., 71, 712-736, (2017) · Zbl 1398.65121 [18] Ding, C.; Sun, D.; Sun, J.; Toh, KC, Spectral operators of matrices, Math. Program., 168, 509-531, (2018) · Zbl 1411.90264 [19] Gabay, D.; Mercier, B., A dual algorithm for the solution of nonlinear variational problems via finite element approximation, Comput. Math. Appl., 2, 17-40, (1976) · Zbl 0352.65034 [20] Glowinski, R.: Numerical Methods for Nonlinear Variational Problems. Springer Series in Computational Physics. Springer, New York (1984) · Zbl 0536.65054 [21] Glowinski, R.; Marroco, A., On the approximation by finite elements of order one, and resolution, penalisation-duality for a class of nonlinear dirichlet problems, ESAIM Math. Model. Numer. Anal., 9, 41-76, (1975) · Zbl 0368.65053 [22] He, B.; Yuan, X., On the $$o(1/n)$$ convergence rate of the Douglas-Rachford alternating direction method, SIAM J. Numer. Anal., 50, 700-709, (2012) · Zbl 1245.90084 [23] Hestenes, MR, Multiplier and gradient methods, J. Optim. Theory Appl., 4, 303-320, (1969) · Zbl 0174.20705 [24] Hong, M.; Luo, ZQ; Razaviyayn, M., Convergence analysis of alternating direction method of multipliers for a family of nonconvex problems, SIAM J. Optim., 26, 337-364, (2016) · Zbl 1356.49061 [25] Hu, Y.; Chi, E.; Allen, GI; Glowinski, R. (ed.); Osher, S. (ed.); Yin, W. (ed.), ADMM algorithmic regularization paths for sparse statistical machine learning, (2016), New York [26] Ivanov, M.; Zlateva, N., Abstract subdifferential calculus and semi-convex functions, Serdica Math. J., 23, 35p-58p, (1997) · Zbl 0937.49007 [27] Iutzeler, F., Bianchi, P., Ciblat, P., Hachem, W.: Asynchronous distributed optimization using a randomized alternating direction method of multipliers. In: 2013 IEEE 52nd Annual Conference On Decision and Control (CDC), pp. 3671-3676. IEEE (2013) [28] Jiang, B.; Ma, S.; Zhang, S., Alternating direction method of multipliers for real and complex polynomial optimization models, Optimization, 63, 883-898, (2014) · Zbl 1291.90242 [29] Knopp, K.: Infinite Sequences and Series. Courier Corporation, Chelmsford (1956) · Zbl 0070.05807 [30] Kryštof, V., Zajíček, L.: Differences of two semiconvex functions on the real line. Preprint (2015) [31] Lai, R.; Osher, S., A splitting method for orthogonality constrained problems, J. Sci. Comput., 58, 431-449, (2014) · Zbl 1296.65087 [32] Li, G.; Pong, TK, Global convergence of splitting methods for nonconvex composite optimization, SIAM J. Optim., 25, 2434-2460, (2015) · Zbl 1330.90087 [33] Li, RC; Stewart, G., A new relative perturbation theorem for singular subspaces, Linear Algebra Appl., 313, 41-51, (2000) · Zbl 0962.15012 [34] Liavas, AP; Sidiropoulos, ND, Parallel algorithms for constrained tensor factorization via the alternating direction method of multipliers, IEEE Trans. Signal Process., 63, 5450-5463, (2015) · Zbl 1394.94321 [35] Łojasiewicz, S., Sur la géométrie semi-et sous-analytique, Ann. Inst. Fourier (Grenoble), 43, 1575-1595, (1993) · Zbl 0803.32002 [36] Lu, Z.; Zhang, Y., An augmented lagrangian approach for sparse principal component analysis, Math. Program., 135, 149-193, (2012) · Zbl 1263.90093 [37] Magnússon, S.; Weeraddana, PC; Rabbat, MG; Fischione, C., On the convergence of alternating direction Lagrangian methods for nonconvex structured optimization problems, IEEE Trans. Control Netw. Syst., 3, 296-309, (2015) · Zbl 1370.90196 [38] Mifflin, R., Semismooth and semiconvex functions in constrained optimization, SIAM J. Control Optim., 15, 959-972, (1977) · Zbl 0376.90081 [39] Miksik, O., Vineet, V., Pérez, P., Torr, P.H., Cesson Sévigné, F.: Distributed non-convex ADMM-inference in large-scale random fields. In: British Machine Vision Conference. BMVC (2014) [40] Möllenhoff, T.; Strekalovskiy, E.; Moeller, M.; Cremers, D., The primal-dual hybrid gradient method for semiconvex splittings, SIAM J. Imaging Sci., 8, 827-857, (2015) · Zbl 1328.68278 [41] Oymak, S., Mohan, K., Fazel, M., Hassibi, B.: A simplified approach to recovery conditions for low rank matrices. In: 2011 IEEE International Symposium on Information Theory Proceedings (ISIT), pp. 2318-2322. IEEE (2011) [42] Peng, Z.; Xu, Y.; Yan, M.; Yin, W., ARock: an algorithmic framework for asynchronous parallel coordinate updates, SIAM J. Sci. Comput., 38, a2851-a2879, (2016) · Zbl 1350.49041 [43] Poliquin, R.; Rockafellar, R., Prox-regular functions in variational analysis, Trans. Am. Math. Soc., 348, 1805-1838, (1996) · Zbl 0861.49015 [44] Powell, M.J.: A method for non-linear constraints in minimization problems. UKAEA (1967) [45] Rockafellar, R.T., Wets, R.J.B.: Variational Analysis. Springer Science & Business Media (2009) · Zbl 0888.49001 [46] Rosenberg, J., et al.: Applications of analysis on Lipschitz manifolds. In: Proceedings of Miniconferences on Harmonic Analysis and Operator Algebras (Canberra, t987), Proceedings Centre for Mathematical Analysis, vol. 16, pp. 269-283 (1988) [47] Shen, Y.; Wen, Z.; Zhang, Y., Augmented Lagrangian alternating direction method for matrix separation based on low-rank factorization, Optim. Methods Softw., 29, 239-263, (2014) · Zbl 1285.90068 [48] Slavakis, K.; Giannakis, G.; Mateos, G., Modeling and optimization for big data analytics: (statistical) learning tools for our era of data deluge, IEEE Sig. Process. Mag., 31, 18-31, (2014) [49] Sun, D.L., Fevotte, C.: Alternating direction method of multipliers for non-negative matrix factorization with the beta-divergence. In: 2014 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP), pp. 6201-6205. IEEE (2014) [50] Sun, R., Luo, Z.-Q., Ye, Y.: On the expected convergence of randomly permuted ADMM. arXiv preprint arXiv:1503.06387 (2015) [51] Wang, F., Cao, W., Xu, Z.: Convergence of multi-block Bregman ADMM for nonconvex composite problems. arXiv preprint arXiv:1505.03063 (2015) [52] Wang, F., Xu, Z., Xu, H.K.: Convergence of Bregman alternating direction method with multipliers for nonconvex composite problems. arXiv preprint arXiv:1410.8625 (2014) [53] Wang, X., Hong, M., Ma, S., Luo, Z.Q.: Solving multiple-block separable convex minimization problems using two-block alternating direction method of multipliers. arXiv preprint arXiv:1308.5294 (2013) [54] Wang, Y.; Zeng, J.; Peng, Z.; Chang, X.; Xu, Z., Linear convergence of adaptively iterative thresholding algorithm for compressed sensing, IEEE Trans. Signal Process., 63, 2957-2971, (2015) · Zbl 1394.94632 [55] Watson, GA, Characterization of the subdifferential of some matrix norms, Linear Algebra Appl., 170, 33-45, (1992) · Zbl 0751.15011 [56] Wen, Z., Peng, X., Liu, X., Sun, X., Bai, X.: Asset allocation under the basel accord risk measures. arXiv preprint arXiv:1308.1321 (2013) [57] Wen, Z.; Yang, C.; Liu, X.; Marchesini, S., Alternating direction methods for classical and ptychographic phase retrieval, Inverse Prob., 28, 115010, (2012) · Zbl 1254.78037 [58] Wen, Z.; Yin, W., A feasible method for optimization with orthogonality constraints, Math. Program., 142, 397-434, (2013) · Zbl 1281.49030 [59] Wikipedia: Schatten norm—Wikipedia, the free encyclopedia (2015). (Online; Accessed 18 Oct 2015) [60] Xu, Y.; Yin, W., A block coordinate descent method for regularized multiconvex optimization with applications to nonnegative tensor factorization and completion, SIAM J. Imaging Sci., 6, 1758-1789, (2013) · Zbl 1280.49042 [61] Xu, Y.; Yin, W.; Wen, Z.; Zhang, Y., An alternating direction algorithm for matrix completion with nonnegative factors, Front. Math. China, 7, 365-384, (2012) · Zbl 1323.65044 [62] Yan, M.; Yin, W.; Glowinski, R. (ed.); Osher, S. (ed.); Yin, W. (ed.), Self equivalence of the alternating direction method of multipliers, 165-194, (2016), New York · Zbl 1372.65186 [63] Yang, L.; Pong, TK; Chen, X., Alternating direction method of multipliers for nonconvex background/foreground extraction, SIAM J. Imaging Sci., 10, 74-110, (2017) · Zbl 1364.90278 [64] You, S., Peng, Q.: A non-convex alternating direction method of multipliers heuristic for optimal power flow. In: 2014 IEEE International Conference on Smart Grid Communications (SmartGridComm), pp. 788-793. IEEE (2014) [65] Zeng, J.; Lin, S.; Xu, Z., Sparse regularization: convergence of iterative jumping thresholding algorithm, IEEE Trans. Signal Process., 64, 5106-5117, (2016) · Zbl 1371.81090 [66] Zeng, J.; Peng, Z.; Lin, S., A Gauss-Seidel iterative thresholding algorithm for $$\ell_q$$ regularized least squares regression, J. Comput. Appl. Math., 319, 220-235, (2017) · Zbl 1361.65041 [67] Zeng, J.; Lin, S.; Wang, Y.; Xu, Z., $$L_{1/2}$$ regularization: convergence of iterative half thresholding algorithm, IEEE Trans. Signal Process., 62, 2317-2329, (2014) · Zbl 1393.90145