×

zbMATH — the first resource for mathematics

ADMM for multiaffine constrained optimization. (English) Zbl 1428.90132
Summary: We expand the scope of the alternating direction method of multipliers (ADMM). Specifically, we show that ADMM, when employed to solve problems with multiaffine constraints that satisfy certain verifiable assumptions, converges to the set of constrained stationary points if the penalty parameter in the augmented Lagrangian is sufficiently large. When the Kurdyka-Łojasiewicz (K-Ł) property holds, this is strengthened to convergence to a single constrained stationary point. Our analysis applies under assumptions that we have endeavoured to make as weak as possible. It applies to problems that involve nonconvex and/or nonsmooth objective terms, in addition to the multiaffine constraints that can involve multiple (three or more) blocks of variables. To illustrate the applicability of our results, we describe examples including nonnegative matrix factorization, sparse learning, risk parity portfolio selection, nonconvex formulations of convex problems and neural network training. In each case, our ADMM approach encounters only subproblems that have closed-form solutions.

MSC:
90C26 Nonconvex programming, global optimization
90C30 Nonlinear programming
Software:
SDPLR
PDF BibTeX XML Cite
Full Text: DOI arXiv
References:
[1] Attouch, H.; Bolte, J.; Redont, P.; Soubeyran, A., Proximal alternating minimization and projection methods for nonconvex problems: an approach based on the Kurdyka-Łojasiewicz inequality, Math. Oper. Res., 35, 438-457 (2010) · Zbl 1214.65036
[2] Attouch, H.; Bolte, J.; Svaiter, B. F., 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
[3] Bai, X. and Scheinberg, K., Alternating direction methods for non convex optimization with applications to second-order least-squares and risk parity portfolio selection, tech. report, 2015. Available at.
[4] Bolte, J.; Sabach, S.; Teboulle, M., Nonconvex Lagrangian-based optimization: monitoring schemes and global convergence, Math. Oper. Res., 43, 1210-1232 (2018)
[5] Bot, R.I. and Nguyen, D.-K., The proximal alternating direction method of multipliers in the non-convex setting: convergence analysis and rates, (2018). Available at arXiv:1801.01994.
[6] Boyd, S.; Parikh, N.; Chu, E.; Peleato, B.; Eckstein, J., Distributed optimization and statistical learning via the alternating direction method of multipliers, Found. Trends Mach. Learn., 3, 1-122 (2011) · Zbl 1229.90122
[7] Burer, S.; Monteiro, R. D.C., A nonlinear programming algorithm for solving semidefinite programs via low-rank factorization, Math. Program., 95, 329-357 (2003) · Zbl 1030.90077
[8] Candès, E. J.; Li, X.; Ma, Y.; Wright, J., Robust principal component analysis?, J. ACM, 58 (2011) · Zbl 1327.62369
[9] 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
[10] Chen, L.; Sun, D.; Toh, K.-C., A note on the convergence of ADMM for linearly constrained convex optimization problems, Comput. Optim. Appl., 66, 327-343 (2017) · Zbl 1367.90083
[11] Chen, L.; Sun, D.; Toh, K.-C., An efficient inexact symmetric Gauss-Seidel based majorized ADMM for high-dimensional convex composite conic programming, Math. Program., 161, 237-270 (2017) · Zbl 1356.90105
[12] Cui, Y.; Li, X.; Sun, D.; Toh, K.-C., On the convergence properties of a majorized alternating direction method of multipliers for linearly constrained convex optimization problems with coupled objective functions, J. Optim. Theory Appl., 169, 1013-1041 (2016) · Zbl 1342.90130
[13] Davis, D.; Yin, W., A three-operator splitting scheme and its optimization applications, Set-Valued and Variational Anal., 25, 829-858 (2017) · Zbl 06834688
[14] Deng, W.; Lai, M.-J.; Peng, Z.; Yin, W., Parallel multi-block ADMM with o(1/k) convergence, J. Sci. Comput., 71, 712-736 (2017) · Zbl 1398.65121
[15] Driggs, D., Becker, S., and Aravkin, A., Adapting regularized low-rank models for parallel architectures, (2017). Available at. · Zbl 1405.65079
[16] Eckstein, J.; Bertsekas, D., On the Douglas-Rachford splitting method and the proximal point algorithm for maximal monotone operators, Math. Program., 55, 293-318 (1992) · Zbl 0765.90073
[17] Eckstein, J.; Yao, W., Understanding the convergence of the alternating direction method of multipliers: theoretical and computational perspectives, Pacific J. Optim., 11, 619-644 (2015) · Zbl 1330.90074
[18] Elad, M.; Aharon, M., Image denoising via sparse and redundant representations over learned dictionaries, IEEE Trans. Image Process., 15, 3736-3745 (2006)
[19] Fazel, M.; Pong, T. K.; Sun, D.; Tseng, P., Hankel matrix rank minimization with applications to system identification and realization, SIAM J. Matrix Anal. Appl., 34, 946-977 (2013) · Zbl 1302.90127
[20] 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
[21] Glowinski, R.; Marroco, A., On the approximation by finite elements of order one, and resolution, penalisation-duality for class of nonlinear Dirichlet problems, ESAIM: Math. Modelling Numer. Anal., 9, 41-76 (1975) · Zbl 0368.65053
[22] Goemans, M. X.; Williamson, D. P., Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming, J. ACM, 42, 1115-1145 (1995) · Zbl 0885.68088
[23] Hajinezhad, D., Chang, T.-H., Wan, X., Shi, Q., and Hong, M., Nonnegative matrix factorization using ADMM: Algorithm and convergence analysis, 2016 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP), 2016, pp. 4742-4746.
[24] Han, D.; Yuan, X., A note on the alternating direction method of multipliers, J. Optim. Theory Appl., 155, 227-238 (2012) · Zbl 1255.90093
[25] Hong, M.; Luo, Z.-Q.; 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
[26] Hubert, M.; Engelen, S., Robust PCA and classification in biosciences, Bioinformatics,, 20, 1728-1736 (2004)
[27] Janin, R., Directional derivative of the marginal function in nonlinear programming, in Sensitivity, Stability, and Parametric Analysis, Mathematical Programming Studies, A. V. Fiacco, ed., Vol. 2, Springer, Berlin, Heidelberg, 1984. · Zbl 0549.90082
[28] Jiang, B.; Lin, T.; Ma, S.; Zhang, S., Structured nonconvex and nonsmooth optimization: algorithms and iteration complexity analysis, Comput. Optim. Appl., 72, 115-157 (2019) · Zbl 1411.90274
[29] Jiang, B.; Ma, S.; Zhang, S., Alternating direction method of multipliers for real and complex polynomial optimization models, Optim., 63, 883-898 (2014) · Zbl 1291.90242
[30] Karp, R.M., Reducibility among combinatorial problems, in Complexity of Computer Computations, IBM Research Symposia Series, R.E. Miller, J.W. Thatcher, and J.D. Bohlinger, eds., Springer, 1972, pp. 85-103.
[31] Lee, D. D.; Seung, H. S., Learning the parts of objects by non-negative matrix factorization, Nature, 401, 788-791 (1999) · Zbl 1369.68285
[32] Lee, D. D.; Seung, H. S., Algorithms for non-negative matrix factorization, Adv. Neural Inform. Process. Sys., 13 (2000)
[33] Li, G.; Pong, T. K., Global convergence of splitting methods for nonconvex composite optimization, SIAM J. Optim., 25, 2434-2460 (2015) · Zbl 1330.90087
[34] Li, M.; Sun, D.; Toh, K.-C., A convergent 3-block semi-proximal ADMM for convex minimization problems with one strongly convex block, Asia-Pac. J. Oper. Res., 32 (2015) · Zbl 1327.90214
[35] Li, M.; Sun, D.; Toh, K.-C., A majorized ADMM with indefinite proximal terms for linearly constrained convex composite optimization, SIAM J. Optim., 26, 922-950 (2016) · Zbl 1338.90305
[36] Li, X.; Sun, D.; Toh, K.-C., A schur complement based semi-proximal ADMM for convex quadratic conic programming and extensions, Math. Program., 155, 333-373 (2016) · Zbl 1342.90134
[37] Lin, T.; Ma, S.; Zhang, S., On the global linear convergence of the ADMM with multi-block variables, SIAM J. Optim., 26, 1478-1497 (2015) · Zbl 1333.90095
[38] Lin, T.; Ma, S.; Zhang, S., On the sublinear convergence rate of multi-block ADMM, J. Oper. Res. Soc. China, 3, 251-271 (2015) · Zbl 1323.90052
[39] Lin, T.; Ma, S.; Zhang, S., Global convergence of unmodified 3-block ADMM for a class of convex minimization problems, J. Sci. Comput., 76, 69-88 (2018) · Zbl 1415.65140
[40] Lin, Z.; Liu, R.; Li, H., Linearized alternating direction method with parallel splitting and adaptive penalty for separable convex programs in machine learning, Mach. Learn., 99, 287-325 (2015) · Zbl 1331.68189
[41] Lions, P.-L.; Mercier, B., Splitting algorithms for the sum of two nonlinear operators, SIAM J. Numer. Anal., 16, 964-979 (1979) · Zbl 0426.65050
[42] Lu, S., Implications of the constant rank constraint qualification, Math. Program., 126, 365-392 (2011) · Zbl 1214.90113
[43] Mairal, J.; Bach, F.; Ponce, J.; Sapiro, G., Online learning for matrix factorization and sparse coding, J. Mac. Learn. Res., 11, 19-60 (2010) · Zbl 1242.62087
[44] Nesterov, Yu., Smooth minimization of non-smooth functions, Math. Program., 103, 127-152 (2005) · Zbl 1079.90102
[45] Nesterov, Yu.; Polyak, B., Cubic regularization of newton method and its global performance, Math. Program., 108, 177-205 (2006) · Zbl 1142.90500
[46] Rockafellar, R.T. and Wets, R.J.-B., Variational Analysis, Grundlehren Der Mathematischen Wissenschaften, Vol. 317, 1st ed., Springer-Verlag, Berlin Heidelberg, 1997. · Zbl 0888.49001
[47] Ryu, E., Uniqueness of DRS as the 2 operator resolvent-splitting and impossibility of 3 operator resolvent-splitting, (2018). Available at.
[48] Shi, W.; Ling, Q.; Yuan, K.; Wu, G.; Yin, W., On the linear convergence of the ADMM in decentralized consensus optimization, IEEE Trans. Sig. Process., 62, 1750-1761 (2014) · Zbl 1394.94532
[49] Sokal, A., A really simple elementary proof of the uniform boundedness theorem, Amer. Math. Monthly, 118, 450-452 (2011) · Zbl 1223.46022
[50] Sun, D.; Toh, K.; Yang, L., A convergent 3-block semiproximal alternating direction method of multipliers for conic programming with 4-type constraints, SIAM J. Optim., 25, 882-915 (2015) · Zbl 1328.90083
[51] Sun, J.; Qu, Q.; Wright, J., Complete dictionary recovery over the sphere i: overview and the geometric picture, IEEE Trans. Information Theory, 63, 853-884 (2017) · Zbl 1364.94164
[52] Sun, J.; Qu, Q.; Wright, J., Complete dictionary recovery over the sphere ii: recovery by Riemannian trust-region method, IEEE Trans. Information Theory, 63, 885-914 (2017) · Zbl 1364.94165
[53] Sun, M.; Sun, H., Improved proximal ADMM with partially parallel splitting for multi-block separable convex programming, J. Appl. Math. Comput., 58, 151-181 (2018) · Zbl 1401.90163
[54] Taylor, G., Burmeister, R., Xu, Z., Singh, B., Patel, A., and Goldstein, T., Training Neural Networks Without Gradients: A scalable ADMM Approach, Proceedings of the 33rd International Conference on Machine Learning (PMLR) Vol. 48, 2016, pp. 2722-2731.
[55] Wang, J. J.; Song, W., An algorithm twisted from generalized ADMM for multi-block separable convex minimization models, J. Comput. Appl. Math., 309, 342-358 (2017) · Zbl 06626253
[56] Wang, Y.; Yin, W.; Zeng, J., Global convergence of ADMM in nonconvex nonsmooth optimization, J. Sci. Comput., 78, 29-63 (2019) · Zbl 07042437
[57] Wang, S., Zhang, L., Liang, Y., and Pan, Q., Semi-coupled dictionary learning with applications to image super-resolution and photo-sketch synthesis, Computer Vision and Pattern Recognition, (2012).
[58] Xu, Y.; Yin, W.; Wen, Z.; Zhang, Y., An alternating direction algorithm for matrix completion with nonnegative factors, Frontiers of Math. China, 7, 365-384 (2012) · Zbl 1323.65044
[59] Zhang, J., Ma, S., and Zhang, S., Primal-dual optimization algorithms over Riemannian manifolds: an iteration complexity analysis, (2017). Available at.
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.