SDPNAL+: a majorized semismooth Newton-CG augmented Lagrangian method for semidefinite programming with nonnegative constraints. (English) Zbl 1321.90085
Summary: In this paper, we present a majorized semismooth Newton-CG augmented Lagrangian method, called SDPNAL+, for semidefinite programming (SDP) with partial or full nonnegative constraints on the matrix variable. SDPNAL+ is a much enhanced version of SDPNAL introduced by X.-Y. Zhao et al. [SIAM J. Optim. 20, No. 4, 1737–1765 (2010; Zbl 1213.90175)] for solving generic SDPs. SDPNAL works very efficiently for nondegenerate SDPs but may encounter numerical difficulty for degenerate ones. Here we tackle this numerical difficulty by employing a majorized semismooth Newton-CG augmented Lagrangian method coupled with a convergent 3-block alternating direction method of multipliers introduced recently by D. Sun et al. [SIAM J. Optim. 25, No. 2, 882–915 (2015; Zbl 1328.90083)]. Numerical results for various large scale SDPs with or without nonnegative constraints show that the proposed method is not only fast but also robust in obtaining accurate solutions. It outperforms, by a significant margin, two other competitive publicly available first order methods based codes: (1) an alternating direction method of multipliers based solver called SDPAD by Z. Wen et al. [Math. Program. Comput. 2, No. 3–4, 203–230 (2010; Zbl 1206.90088)] and (2) a two-easy-block-decomposition hybrid proximal extragradient method called 2EBD-HPE by R. Monteiro et al. [“A first-order block-decomposition method for solving two-easy-block structured semidefinite programs”, Math. Program. Comput. 6, No. 2, 103–150 (2014; doi:10.1007/s12532-013-0062-7)]. In contrast to these two codes, we are able to solve all the 95 difficult SDP problems arising from the relaxations of quadratic assignment problems tested in SDPNAL to an accuracy of \(10^{-6}\) efficiently, while SDPAD and 2EBD-HPE successfully solve 30 and 16 problems, respectively. In addition, SDPNAL+ appears to be the only viable method currently available to solve large scale SDPs arising from rank-1 tensor approximation problems constructed by J. Nie and L. Wang [SIAM J. Matrix Anal. Appl. 35, No. 3, 1155–1179 (2014; Zbl 1305.65134)]. The largest rank-1 tensor approximation problem we solved (in about 14.5 h) is nonsym(21,4), in which its resulting SDP problem has matrix dimension \(n=9261\) and the number of equality constraints \(m=12{,}326{,}390\).
MSC:
| 90C06 | Large-scale problems in mathematical programming |
| 90C22 | Semidefinite programming |
| 90C25 | Convex programming |
| 65F10 | Iterative numerical methods for linear systems |
References:
| [1] | Arnold, V.I.: On matrices depending on parameters. Russ. Math. Surv. 26, 29-43 (1971) · Zbl 0259.15011 · doi:10.1070/RM1971v026n02ABEH003827 |
| [2] | Bonnans, J.F., Shapiro, A.: Perturbation Analysis of Optimization Problems. Springer, Berlin (2000) · Zbl 0966.49001 · doi:10.1007/978-1-4612-1394-9 |
| [3] | Borwein, J.M., Lewis, A.S.: Convex Analysis and Nonlinear Optimization: Theory and Examples, vol. 3. Springer, Berlin (2006) · Zbl 1116.90001 |
| [4] | Burer, S.: On the copositive representation of binary and continuous nonconvex quadratic programs. Math. Program. 120, 479-495 (2009) · Zbl 1180.90234 · doi:10.1007/s10107-008-0223-z |
| [5] | Burer, S., Monteiro, R.D., Zhang, Y.: A computational study of a gradient-based log-barrier algorithm for a class of large-scale sdps. Math. Program. 95, 359-379 (2003) · Zbl 1030.90076 · doi:10.1007/s10107-002-0353-7 |
| [6] | 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. (to appear) · Zbl 1332.90193 |
| [7] | Eisenblätter, A., Grötschel, M., Koster, A.M.: Frequency planning and ramifications of coloring. Discuss. Math. Graph Theory 22, 51-88 (2002) · Zbl 1055.05147 · doi:10.7151/dmgt.1158 |
| [8] | Hahn, P., Anjos, M.: QAPLIB—a quadratic assignment problem library. http://www.seas.upenn.edu/qaplib · Zbl 1206.90088 |
| [9] | Hiriart-Urruty, J.-B., Strodiot, J.-J., Nguyen, V.H.: Generalized Hessian matrix and second-order optimality conditions for problems with \[C^{1,1}\] C1,1 data. Appl. Math. Optim. 11, 43-56 (1984) · Zbl 0542.49011 · doi:10.1007/BF01442169 |
| [10] | Monteiro, R., Ortiz, C., Svaiter, B.: A first-order block-decomposition method for solving two-easy-block structured semidefinite programs. Math. Program. Comput. 6, 103-150 (2014) · Zbl 1342.49045 |
| [11] | Moreau, J.J.: Décomposition orthogonale d’un espace hilbertien selon deux cones mutuellement polaires. C. R. Acad. Sci. 255, 238-240 (1962) · Zbl 0109.08105 |
| [12] | Nie, J., Wang, L.: Regularization methods for SDP relaxations in large-scale polynomial optimization. SIAM J. Optim. 22, 408-428 (2012) · Zbl 1250.65080 · doi:10.1137/110825844 |
| [13] | Nie, J., Wang, L.: Semidefinite relaxations for best rank-1 tensor approximations. SIAM J. Matrix Anal. Appl. 35, 1155-1179 (2014) · Zbl 1305.65134 · doi:10.1137/130935112 |
| [14] | Pang, J.-S., Sun, D.-F., Sun, J.: Semismooth homeomorphisms and strong stability of semidefinite and lorentz complementarity problems. Math. Oper. Res. 28, 39-63 (2003) · Zbl 1082.90115 · doi:10.1287/moor.28.1.39.14258 |
| [15] | Peng, J., Wei, Y.: Approximating k-means-type clustering via semidefinite programming. SIAM J. Optim. 18, 186-205 (2007) · Zbl 1146.90046 · doi:10.1137/050641983 |
| [16] | Povh, J., Rendl, F.: Copositive and semidefinite relaxations of the quadratic assignment problem. Discret. Optim. 6, 231-241 (2009) · Zbl 1167.90597 · doi:10.1016/j.disopt.2009.01.002 |
| [17] | Rockafellar, R.T.: Conjugate duality and optimization. CBMS-NSF Regional Conf. Ser. Appl. Math. vol. 16. SIAM, Philadelphia (1974) · Zbl 0296.90036 |
| [18] | Rockafellar, R.T.: Augmented Lagrangians and applications of the proximal point algorithm in convex programming. Math. Oper. Res. 1, 97-116 (1976) · Zbl 0402.90076 · doi:10.1287/moor.1.2.97 |
| [19] | Rockafellar, R.T.: Monotone operators and the proximal point algorithm. SIAM J. Control Optim. 14, 877-898 (1976) · Zbl 0358.90053 · doi:10.1137/0314056 |
| [20] | Sloane, N.: Challenge problems: independent sets in graphs. http://www.research.att.com/njas/doc/graphs.html (2005) · Zbl 1305.65134 |
| [21] | Sun, D.-F., Sun, J.: Semismooth matrix-valued functions. Math. Oper. Res. 27, 150-169 (2002) · Zbl 1082.49501 · doi:10.1287/moor.27.1.150.342 |
| [22] | Sun, D.-F., Toh, K.-C., Yang, L.-Q.: A convergent 3-block semi-proximal alternating direction method of multipliers for conic programming with 4-type constraints. SIAM J. Optim. (to appear) · Zbl 1328.90083 |
| [23] | 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 · doi:10.1137/S1052623402419819 |
| [24] | Trick, M., Chvatal, V., Cook, B., Johnson, D., McGeoch, C., Tarjan, R.: The second dimacs implementation challenge—NP hard problems: maximum clique, graph coloring, and satisfiability. http://dimacs.rutgers.edu/Challenges/ (1992) · Zbl 1250.65080 |
| [25] | Wen, Z., Goldfarb, D., Yin, W.: Alternating direction augmented Lagrangian methods for semidefinite programming. Math. Program. Comput. 2, 203-230 (2010) · Zbl 1206.90088 · doi:10.1007/s12532-010-0017-1 |
| [26] | Zhao, X.-Y., Sun, D.-F., Toh, K.-C.: A Newton-CG augmented Lagrangian method for semidefinite programming. SIAM J. Optim. 20, 1737-1765 (2010) · Zbl 1213.90175 · doi:10.1137/080718206 |
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. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
