×

zbMATH — the first resource for mathematics

On the equivalence of inexact proximal ALM and ADMM for a class of convex composite programming. (English) Zbl 1458.90509
Summary: In this paper, we show that for a class of linearly constrained convex composite optimization problems, an (inexact) symmetric Gauss-Seidel based majorized multi-block proximal alternating direction method of multipliers (ADMM) is equivalent to an inexact proximal augmented Lagrangian method. This equivalence not only provides new perspectives for understanding some ADMM-type algorithms but also supplies meaningful guidelines on implementing them to achieve better computational efficiency. Even for the two-block case, a by-product of this equivalence is the convergence of the whole sequence generated by the classic ADMM with a step-length that exceeds the conventional upper bound of \((1+\sqrt{5})/2\), if one part of the objective is linear. This is exactly the problem setting in which the very first convergence analysis of ADMM was conducted by D. Gabay and B. Mercier [Comput. Math. Appl. 2, 17–40 (1976; Zbl 0352.65034)], but, even under notably stronger assumptions, only the convergence of the primal sequence was known. A collection of illustrative examples are provided to demonstrate the breadth of applications for which our results can be used. Numerical experiments on solving a large number of linear and convex quadratic semidefinite programming problems are conducted to illustrate how the theoretical results established here can lead to improvements on the corresponding practical implementations.
MSC:
90C25 Convex programming
65K05 Numerical mathematical programming methods
90C06 Large-scale problems in mathematical programming
49M27 Decomposition methods
90C20 Quadratic programming
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Bai, M.; Zhang, X.; Ni, G.; Cui, C., An adaptive correction approach for tensor completion, SIAM J. Imaging Sci., 9, 1298-1323 (2016) · Zbl 1456.90104
[2] Bai, S.; Qi, H-D, Tackling the flip ambiguity in wireless sensor network localization and beyond, Digit. Signal Process., 55, 85-97 (2016)
[3] Bertsekas, DP; Tsitsiklis, JN, Parallel and Distributed Computation: Numerical Methods (1997), Belmont: Athena Scientific, Belmont · Zbl 1325.65001
[4] 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
[5] Chen, L.; Sun, DF; 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
[6] Chen, L.; Sun, DF; Toh, K-C, An effcient inexact symmetric Gauss-Seidel based majorized ADMM for high-dimensional convex composite conic programming, Math. Program., 161, 1-2, 237-270 (2017) · Zbl 1356.90105
[7] Chen, SS; Donoho, DL; Saunders, MA, Atomic decomposition by basis pursuit, SIAM Rev., 43, 129-159 (2001) · Zbl 0979.94010
[8] Clarke, FH, Optimization and Nonsmooth Analysis (1983), New York: Wiley, New York · Zbl 0582.49001
[9] Ding, C.; Qi, H-D, Convex optimization learning of faithful Euclidean distance representations in nonlinear dimensionality reduction, Math. Program., 164, 1-2, 341-381 (2017) · Zbl 1391.90472
[10] Ding, C.; Sun, DF; Sun, J.; Toh, K-C, Spectral operators of matrices, Math. Program., 168, 509-531 (2018) · Zbl 1411.90264
[11] Dontchev, AL; Rockafellar, RT, Implicit Functions and Solution Mappings (2014), New York: Springer, New York · Zbl 1337.26003
[12] Du, M.Y.: A two-phase augmented Lagrangian method for convex composite quadratic programming. Ph.D. thesis, Department of Mathematics, National University of Singapore (2015)
[13] Eckstein, J.: Augmented Lagrangian and alternating direction methods for convex optimization: a tutorial and some illustrative computational results. RUTCOR Research Reports (2012)
[14] Eckstein, J.; Yao, W., Understanding the convergence of the alternating direction method of multipliers: theoretical and computational perspectives, Pac. J. Optim., 11, 619-644 (2015) · Zbl 1330.90074
[15] Eisenblätter, A.; Grötschel, M.; Koster, A., Frequency planning and ramification of coloring, Discuss. Math. Graph Theory, 22, 51-88 (2002) · Zbl 1055.05147
[16] Fazel, M.; Pong, TK; Sun, DF; Tseng, P., Hankel matrix rank minimization with applications to system identification and realization, SIAM J. Matrix Anal., 34, 3, 946-977 (2013) · Zbl 1302.90127
[17] Ferreira, J.; Khoo, Y.; Singer, A., Semidefinite programming approach for the quadratic assignment problem with a sparse graph, Comput. Optim. Appl., 69, 3, 677-712 (2018) · Zbl 1415.90071
[18] Gabay, D.; Mercier, B., A dual algorithm for the solution of nonlinear variational problems via finite element approximation, Comput. Math. Appl., 2, 1, 17-40 (1976) · Zbl 0352.65034
[19] Gaines, BR; Kim, J.; Zhou, H., Algorithms for fitting the constrained lasso, J. Comput. Graph. Stat., 27, 4, 861-871 (2018)
[20] Glowinski, R.: Lectures on Numerical Methods for Non-Linear Variational Problems. Bombay. Springer, Published for the Tata Institute of Fundamental Research (1980) · Zbl 0456.65035
[21] Glowinski, R.; Marroco, A., Sur l’approximation, par éléments finis d’ordre un, et la résolution, par pénalisation-dualité d’une classe de problèmes de Dirichlet non linéaires, Revue française d’atomatique, Informatique Recherche Opérationelle. Analyse Numérique, 9, 2, 41-76 (1975) · Zbl 0368.65053
[22] Han, DR; Sun, DR; Zhang, LW, Linear rate convergence of the alternating direction method of multipliers for convex composite programming, Math. Oper. Res., 43, 2, 622-637 (2018) · Zbl 1440.90047
[23] Hestenes, M., Multiplier and gradient methods, J. Optim. Theory Appl., 4, 5, 303-320 (1969) · Zbl 0174.20705
[24] Huber, PJ, Robust estimation of a location parameter, Ann. Math. Stat., 35, 73-101 (1964) · Zbl 0136.39805
[25] James, G.M., Paulson, C., Rusmevichientong, P.: Penalized and constrained optimization: an application to high-dimensional website advertising. J. Amer. Stat. Asso. (2019). doi:10.1080/01621459.2019.1609970 · Zbl 1437.62687
[26] Klopp, O., Noisy low-rank matrix completion with general sampling distribution, Bernoulli, 20, 1, 282-303 (2014) · Zbl 1400.62115
[27] Lam, XY; Marron, JS; Sun, DF; Toh, K-C, Fast algorithms for large scale generalized distance weighted discrimination, J. Comput. Graph. Stat., 27, 2, 368-379 (2018)
[28] Lemaréchal, C.; Sagastizábal, C., Practical aspects of the Moreau-Yosida regularization: theoretical preliminaries, SIAM J. Optim., 7, 2, 367-385 (1997) · Zbl 0876.49019
[29] Li, M.; Sun, DF; Toh, K-C, A majorized ADMM with indefinite proximal terms for linearly constrained convex composite optimization, SIAM J. Optim., 26, 2, 922-950 (2016) · Zbl 1338.90305
[30] Li, XD; Sun, DF; 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
[31] Li, XD; Sun, DF; Toh, K-C, QSDPNAL: a two-phase augmented Lagrangian method for convex quadratic semidefinite programming, Math. Program. Comput., 10, 4, 703-743 (2018) · Zbl 1411.90213
[32] Li, XD; Sun, DF; Toh, K-C, A block symmetric Gauss-Seidel decomposition theorem for convex composite quadratic programming and its applications, Math. Program., 175, 395-418 (2019) · Zbl 1412.90086
[33] Liu, J.; Musialski, P.; Wonka, P.; Ye, J., Tensor completion for estimating missing values in visual data, IEEE Trans. Pattern Anal. Mach. Intell., 35, 208-220 (2013)
[34] Malick, J.; Povh, J.; Rendl, F.; Wiegele, A., Regularization methods for semidefinite programming, SIAM J. Optim., 20, 336-356 (2009) · Zbl 1187.90219
[35] Mateos, G.; Bazerque, J-A; Giannakis, GB, Distributed sparse linear regression, IEEE Trans. Signal Proces., 58, 5262-5276 (2010) · Zbl 1391.62133
[36] Miao, WM; Pan, SH; Sun, DF, A rank-corrected procedure for matrix completion with fixed basis coefficients, Math. Program., 159, 289-338 (2016) · Zbl 1356.90178
[37] Negahban, S.; Wainwright, MJ, Restricted strong convexity and weighted matrix completion: optimal bounds with noise, J. Mach. Learn. Res., 13, 1665-1697 (2012) · Zbl 1436.62204
[38] Nie, J.; Wang, L., Regularization methods for SDP relaxations in large-scale polynomial optimization, SIAM J. Optim., 22, 408-428 (2012) · Zbl 1250.65080
[39] Nie, J.; Wang, L., Semidefinite relaxations for best rank-\(1\) tensor approximations, SIAM J. Matrix Anal. Appl., 35, 1155-1179 (2014) · Zbl 1305.65134
[40] Peng, J.; Wei, Y., Approximating k-means-type clustering via semidefinite programming, SIAM J. Optim., 18, 186-205 (2007) · Zbl 1146.90046
[41] Potra, FA, Weighted complementarity problems—a new paradigm for computing equilibria, SIAM J. Optim., 22, 1634-1654 (2012) · Zbl 1273.90217
[42] Powell, M.; Fletcher, R., A method for nonlinear constraints in minimization problems, Optimization, 283-298 (1969), New York: Academic Press, New York
[43] Povh, J.; Rendl, F.; Wiegele, A., A boundary point method to solve semidefinite programs, Computing, 78, 277-286 (2006) · Zbl 1275.90055
[44] Rockafellar, RT, Convex Analysis (1970), Princeton: Princeton University Press, Princeton · Zbl 0193.18401
[45] Rockafellar, RT, Augmented Lagrangians and applications of the proximal point algorithm in convex programming, Math. Oper. Res., 1, 97-116 (1976) · Zbl 0402.90076
[46] Schizas, ID; Ribeiro, A.; Giannakis, GB, Consensus in ad hoc WSNs with noisy links—part I: distributed estimation of deterministic signals, IEEE Trans. Signal Process., 56, 350-364 (2008) · Zbl 1390.94395
[47] Sloane, N.: Challenge problems: independent sets in graphs. https://oeis.org/A265032/a265032.html. Accessed 16 Aug 2019
[48] Sun, DF; Toh, K-C; Yang, LQ, 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 (2015) · Zbl 1328.90083
[49] Teo, CH; Vishwanathan, SVN; Smola, A.; V. Le, Q., Bundle methods for regularized risk minimization, J. Mach. Learn. Res., 11, 313-365 (2010)
[50] Toh, K-C, Solving large scale semidefinite programs via an iterative solver on the augmented systems, SIAM J. Optim., 14, 670-698 (2004) · Zbl 1071.90026
[51] Toh, K-C, An inexact primal-dual path-following algorithm for convex quadratic SDP, Math. Program., 112, 1, 221-254 (2008) · Zbl 1136.90027
[52] Trick, M., Chvatal, V., Cook, W., Johnson, D., McGeoch, C., Tarjan, R.: The Second DIMACS implementation challenge: NP hard problems: maximum clique, graph coloring, and satisfiability. Rutgers University (1992). http://dimacs.rutgers.edu/Challenges/. Accessed 16 Aug 2019
[53] Wang, B.; Zou, H., Another look at distance-weighted discrimination, J. R. Stat. Soc. B, 80, 177-198 (2018) · Zbl 1380.62028
[54] Wiegele, A.: Biq Mac library—a collection of Max-Cut and quadratic \(0-1\) programming instances of medium size. Technical report (2007). http://biqmac.uni-klu.ac.at/biqmaclib.pdf. Accessed 16 Aug 2019
[55] Yan, Z.; Gao, SY; Teo, CP, On the design of sparse but efficient structures in operations, Manag. Sci., 64, 2973-3468 (2018)
[56] Yang, LQ; Sun, DF; Toh, K-C, SDPNAL+: a majorized semismooth Newton-CG augmented Lagrangian method for semidefinite programming with nonnegative constraints, Math. Program. Comput., 7, 331-366 (2015) · Zbl 1321.90085
[57] Zhang, N., Wu, J., Zhang, L.W.: A linearly convergent majorized ADMM with indefinite proximal terms for convex composite programming and its applications (2018). arXiv: 1706.01698v2 · Zbl 1441.90123
[58] Zhao, XY; Sun, DF; Toh, K-C, A Newton-CG augmented Lagrangian method for semidefinite programming, SIAM J. Optim., 20, 1737-1765 (2010) · Zbl 1213.90175
[59] Zhu, H.; Cano, A.; Giannakis, GB, Distributed consensus-based demodulation: algorithms and error analysis, IEEE Trans. Wirel. Commun., 9, 2044-2054 (2010)
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.