×

zbMATH — the first resource for mathematics

SDPNAL+: A Matlab software for semidefinite programming with bound constraints (version 1.0). (English) Zbl 1432.90104
Summary: Sdpnal+ is a MATLAB software package that implements an augmented Lagrangian based method to solve large scale semidefinite programming problems with bound constraints. The implementation was initially based on a majorized semismooth Newton-CG augmented Lagrangian method, here we designed it within an inexact symmetric Gauss-Seidel based semi-proximal ADMM/ALM (alternating direction method of multipliers/augmented Lagrangian method) framework for the purpose of deriving simpler stopping conditions and closing the gap between the practical implementation of the algorithm and the theoretical algorithm. The basic code is written in MATLAB, but some subroutines in C language are incorporated via Mex files. We also design a convenient interface for users to input their SDP models into the solver. Numerous problems arising from combinatorial optimization and binary integer quadratic programming problems have been tested to evaluate the performance of the solver. Extensive numerical experiments conducted in [L. Yang et al., Math. Program. Comput. 7, No. 3, 331–366 (2015; Zbl 1321.90085)] show that the proposed method is quite efficient and robust, in that it is able to solve 98.9% of the 745 test instances of SDP problems arising from various applications to the accuracy of \(10^{-6}\) in the relative KKT residual.

MSC:
90C22 Semidefinite programming
PDF BibTeX XML Cite
Full Text: DOI arXiv
References:
[1] 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
[2] Chen, L.; Sun, D. F.; 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
[3] 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
[4] M.Grant and S.Boyd, CVX: Matlab software for disciplined convex programming, version 2.1, 2014. Available at http://cvxr.com/cvx.
[5] P.Hahn and M.Anjos, QAPLIB - A quadratic assignment problem library. Available at http://www.seas.upenn.edu/qaplib.
[6] Leung, N.-H. Z.; Toh, K. C., An SDP-based divide-and-conquer algorithm for large scale noisy anchor-free graph realization, SIAM J. Sci. Comput., 31, 4351-4372 (2009) · Zbl 1203.93157
[7] Li, X. D.; Sun, D. F.; 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
[8] J.Löfberg, Yalmip: A tool box for modeling and optimization in matlab, 2004 IEEE International Symposium on Computer Aided Control Systems Design, 2004.
[9] Lovasz, L., On the shannon capacity of a graph, IEEE Trans. Inform. Theory, 25, 1-7 (1979) · Zbl 0395.94021
[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] Nie, J.; Wang, L., Semidefinite relaxations for best rank-1 tensor approximations, SIAM J. Matrix Anal. Appl., 35, 1155-1179 (2014) · Zbl 1305.65134
[12] Peng, J.; Wei, Y., Approximating k-means-type clustering via semidefinite programming, SIAM J. Optim., 18, 186-205 (2007) · Zbl 1146.90046
[13] Povh, J.; Rendl, F., Copositive and semidefinite relaxations of the quadratic assignment problem, Discrete Optim., 6, 231-241 (2009) · Zbl 1167.90597
[14] N.Sloane, Challenge problems: Independent sets in graphs, 2005. Available at http://www.research.att.com/njas/doc/graphs.html.
[15] Sturm, J. F., Using SeDuMi 1.02, a Matlab toolbox for optimization over symmetric cones, Optim. Methods Softw., 11, 625-653 (1999) · Zbl 0973.90526
[16] 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., 25, 882-915 (2015) · Zbl 1328.90083
[17] 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
[18] Toh, K. C.; Todd, M. J.; Tutuncu, R. H., SDPT3 - A Matlab software package for semidefinite programming, Optim. Methods Softw., 11, 545-581 (1999) · Zbl 0997.90060
[19] M.Trick, V.Chvatal, B.Cook, D.Johnson, C.McGeoch, and R.Tarjan, The second DIMACS implementation challenge - NP hard problems: Maximum clique, graph coloring, and satisfiability, 1992. Available at http://dimacs.rutgers.edu/Challenges/.
[20] Tutuncu, R. H.; Toh, K. C.; Todd, M. J., Solving semidefinite-quadratic-linear programs using SDPT3, Math. Program., 95, 189-217 (2003) · Zbl 1030.90082
[21] Wen, Z.; Goldfarb, D.; Yin, W., Alternating direction augmented Lagrangian methods for semidefinite programming, Math. Program. Comput., 2, 203-230 (2010) · Zbl 1206.90088
[22] A.Wiegele, Biq mac library, 2007. Available at http://biqmac.uni-klu.ac.at/biqmaclib.html.
[23] Yamashita, M.; Fujisawa, K.; Kojima, M., Implementation and evaluation of SDPA 6.0 (semidefinite programming algorithm 6.0), Optim. Methods Softw., 18, 491-505 (2003) · Zbl 1106.90366
[24] Yang, L. Q.; Sun, D. F.; 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
[25] 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
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.