SDPNAL+ swMATH ID: 13239 Software Authors: Yang, Liuqin; Sun, Defeng; Toh, Kim-Chuan Description: SDPNAL+: a majorized semismooth Newton-CG augmented Lagrangian method for semidefinite programming with nonnegative constraints.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 06444987)]. 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. Homepage: http://www.math.nus.edu.sg/~mattohkc/SDPNALplus.html Dependencies: Matlab Keywords: semidefinite programming; degeneracy; augmented Lagrangian; semismooth Newton-CG method Related Software: SDPT3; SeDuMi; QSDPNAL; QAPLIB; Mosek; DIMACS; SDPLR; SDPA; Biq Mac; SCS; BBCPOP; Gurobi; SDPNAL; GloptiPoly; UCI-ml; BiqMac; 2EBD-HPE; QSDP; CPLEX; k-means++ Cited in: 71 Publications Standard Articles 2 Publications describing the Software, including 2 Publications in zbMATH Year SDPNAL+: A Matlab software for semidefinite programming with bound constraints (version 1.0). Zbl 1432.90104Sun, Defeng; Toh, Kim-Chuan; Yuan, Yancheng; Zhao, Xin-Yuan 2020 SDPNAL+: a majorized semismooth Newton-CG augmented Lagrangian method for semidefinite programming with nonnegative constraints. Zbl 1321.90085Yang, Liuqin; Sun, Defeng; Toh, Kim-Chuan 2015 all top 5 Cited by 125 Authors 21 Toh, Kim Chuan 15 Sun, Defeng 7 Kim, Sunyoung 5 Cui, Ying 5 Hu, ShengLong 5 Kojima, Masakazu 5 Li, Xudong 4 Ding, Chao 4 Zhao, Xinyuan 3 Chen, Liang 3 Ma, Shiqian 3 Tran Dinh Quoc 2 Cevher, Volkan 2 Chang, Xiaokai 2 Garcia, Joaquim Dias 2 Huang, Zheng-Hai 2 Ito, Naoki 2 Li, Qingna 2 Liang, Ling 2 Liu, Sanyang 2 Liu, Yafeng 2 Piccialli, Veronica 2 Sotirov, Renata 2 Sudoso, Antonio M. 2 Sun, Jie 2 Takeda, Akiko 2 Tropp, Joel A. 2 Udell, Madeleine 2 Wiegele, Angelika 2 Wolkowicz, Henry 2 Yamashita, Makoto 2 Yang, Liuqin 2 Yuan, Yancheng 2 Yurtsever, Alp 2 Zheng, Mengmeng 1 Ahmadi, Amir Ali 1 Arima, Naohiko 1 Azuma, Godai 1 Campos, Juan S. 1 Chen, Shixiang 1 Chen, Weikun 1 Chklovskii, Dmitri B. 1 de Meijer, Frank 1 Ding, Lijun 1 Ding, Mingcai 1 Dowson, Oscar 1 Eisenach, Carson 1 Fercoq, Olivier 1 Fukuda, Mituhiro 1 Gaar, Elisabeth 1 Ghasemi, Mehdi 1 Goulart, Paul J. 1 Graham, Naomi 1 Guo, Feng 1 Hu, Hao 1 Huang, Pengfei 1 Im, Jiyoung 1 Jiang, Zhuoxuan 1 Khoo, Yuehaw 1 Komeiji, Hikaru 1 Lasserre, Jean-Bernard 1 Legat, Benoît 1 Li, Guoyin 1 Li, Xinxin 1 Li, Yang 1 Li, Yiyong 1 Li, Yongfeng 1 Lin, Tianyi 1 Lin, Youyicun 1 Ling, Shuyang 1 Liu, Han 1 Liu, Xin 1 Lu, Shu 1 Lubin, Miles 1 Majumdar, Anirudha 1 Marshall, Murray Angus 1 Misener, Ruth 1 Mixon, Dustin G. 1 Nakatsukasa, Yuji 1 Narayanan, Vishnu 1 Oliveira, Danilo Elias 1 Pang, Jong-Shi 1 Parpas, Panos 1 Pataki, Gábor 1 Punnen, Abraham P. 1 Qi, Houduo 1 Rauhut, Holger 1 Rendl, Franz 1 Rontsis, Nikitas 1 Russo Russo, Anna 1 Sarkar, Purnamrita 1 Saunderson, James 1 Sen, Bodhisattva 1 Sengupta, Anirvan Mayukh 1 Shinde, Nimita 1 So, Anthony Man-Cho 1 Song, Xiaoliang 1 Souto, Mario 1 Stojanac, Željka 1 Strohmer, Thomas ...and 25 more Authors all top 5 Cited in 26 Serials 11 SIAM Journal on Optimization 9 Mathematical Programming. Series A. Series B 9 Computational Optimization and Applications 4 INFORMS Journal on Computing 4 Optimization Methods & Software 4 Mathematical Programming Computation 3 Mathematics of Operations Research 3 Journal of Global Optimization 2 Optimization 2 Asia-Pacific Journal of Operational Research 2 SIAM Journal on Scientific Computing 2 Journal of Machine Learning Research (JMLR) 2 SIAM Journal on Mathematics of Data Science 1 ACM Transactions on Mathematical Software 1 Applied Mathematics and Computation 1 Journal of the American Statistical Association 1 Journal of Optimization Theory and Applications 1 Applied Numerical Mathematics 1 Computers & Operations Research 1 SIAM Journal on Matrix Analysis and Applications 1 Journal of Scientific Computing 1 Numerical Algorithms 1 European Journal of Operational Research 1 Linear Algebra and its Applications 1 Information and Inference 1 SIAM Journal on Applied Algebra and Geometry all top 5 Cited in 16 Fields 68 Operations research, mathematical programming (90-XX) 20 Numerical analysis (65-XX) 7 Calculus of variations and optimal control; optimization (49-XX) 5 Linear and multilinear algebra; matrix theory (15-XX) 5 Statistics (62-XX) 2 Field theory and polynomials (12-XX) 2 Algebraic geometry (14-XX) 2 Computer science (68-XX) 1 Commutative algebra (13-XX) 1 Real functions (26-XX) 1 Operator theory (47-XX) 1 Convex and discrete geometry (52-XX) 1 Global analysis, analysis on manifolds (58-XX) 1 Game theory, economics, finance, and other social and behavioral sciences (91-XX) 1 Systems theory; control (93-XX) 1 Information and communication theory, circuits (94-XX) Citations by Year