Skip to main navigationSkip to main content
The University of Southampton
CORMSIS Centre for Operational Research, Management Sciences and Information Systems

A 2-phase augmented Lagrangian approach for large scale matrix optimization Event

16:00 - 17:00
25 September 2014
Room 8033 (8B), building 54 (Mathematics)

For more information regarding this event, please telephone Houduo Qi on +23683 or email .

Event details

CORMSIS Seminar by Professor Defeng Sun

 Abstract: 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 Zhao, Sun and Toh [SIAM Journal on Optimization, 20 (2010), pp.~1737--1765] 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 Sun, Toh and Yang [arXiv preprint arXiv:1404.5378, (2014)]. 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 Wen, Goldfarb and Yin [Mathematical Programming Computation, 2 (2010), pp.~203--230] and (2) a two-easy-block-decomposition hybrid proximal extragradient method called 2EBD-HPE by Monteiro, Ortiz and Svaiter [Mathematical Programming Computation, (2013), pp.~1--48]. 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 Nie and Wang [arXiv preprint arXiv:1308.6562, (2013)]. The largest rank-1 tensor approximation problem we solved (in about 14.5 hours) is {\tt nonsym(21,4)}, in which its resulting SDP problem has matrix dimension $n = 9,261$ and the number of equality constraints $m =12,326,390$. [This is a joint work with Liuqin Yang and Kim-Chuan Toh at National University of Singapore].

Speaker information

Professor Defeng Sun,National University of Singapore,Defeng Sun is Professor at Department of Mathematics, National University of Singapore. He received his PhD in Operations Research and Control Theory from the Institute of Applied Mathematics, Chinese Academy of Sciences, China in 1995. He completed his post-doctoral training at the University of New South Wales, Australia. His research interests are mainly on Optimization, a subject of studying best decision-making with limited resources, with side interest in financial risk management. He currently serves as associate editor to Mathematical Programming Series A and Series B, SIAM Journal on Optimization and Journal of China Operations Research Society.

Privacy Settings