主题：SDPNAL+: AMajorized Semismooth Newton-CG Augmented Lagrangian Method for SemidefiniteProgramming with Nonnegative Constraints
报告人：Defeng Sun 教授（新加坡国立大学）
日期：2014年6月10日上午10：00
地点：知新楼B-1248
报告摘要：In this paper, wepresent a majorized semismooth Newton-CG augmented Lagrangian method, called SDPNAL+, for semidefiniteprogramming (SDP) with partial or full nonnegative constraints on the matrixvariable. SDPNAL+ is a much enhanced version of SDPNAL introduced by Zhao, Sunand Toh [SIAM Journal on Optimization, 20 (2010), pp.~1737--1765] for solvinggeneric SDPs. SDPNAL works very efficiently for nondegenerate SDPs but mayencounter numerical difficulty for degenerate ones. Here we tackle thisnumerical difficulty by employing a majorized semismooth Newton-CG augmentedLagrangian method coupled with a convergent 3-block alternating directionmethod of multipliers introducedrecently by Sun, Toh and Yang [arXiv preprint arXiv:1404.5378, (2014)].Numerical results for various large scale SDPs with or without nonnegativeconstraints show that the proposed method is not only fast but also robust inobtaining accurate solutions. It outperforms, by a significant margin, twoother competitive publicly available first order methods based codes: (1) an alternating direction methodof multipliers based solver called SDPADby Wen, Goldfarb and Yin [Mathematical Programming Computation, 2 (2010), pp.~203--230]and (2) a two-easy-block-decomposition hybrid proximal extragradient methodcalled 2EBD-HPE by Monteiro, Ortiz and Svaiter [Mathematical ProgrammingComputation, (2013), pp.~1--48]. Incontrast to these two codes, we are able to solve all the 95 difficult SDPproblems arising from the relaxations of quadratic assignment problems testedin SDPNAL to an accuracy of 10^{-6} efficiently, while SDPAD and 2EBD-HPEsuccessfully solve 30 and 16 problems, respectively. In addition, SDPNAL$+$appears to be the only viable method currently available to solve large scaleSDPs arising from rank-1 tensor approximation problems constructed by Nie andWang [arXiv preprint arXiv:1308.6562, (2013)]. The largest rank-1 tensorapproximation problem we solved (in about 14.5 hours) is { nonsym(21,4)}, in which its resulting SDP problem has matrixdimension n = 9,261 and the number of equality constraints m =12,326,390. [Thisis a joint work with Liuqin Yang and Kim-Chuan Toh at National University ofSingapore].
