博士生论坛

您当前的位置: 首页 > 博士生论坛 > 学术报告 > 正文

SDPNAL+: A Majorized Semismooth Newton-CG Augmented Lagrangian Method

发布时间:2014-11-19     来源:    点击数:

主题:SDPNAL+: AMajorized Semismooth Newton-CG Augmented Lagrangian Method for SemidefiniteProgramming with Nonnegative Constraints

 

报告人:Defeng Sun 教授(新加坡国立大学)

 

日期:2014610日上午1000

 

地点:知新楼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].

版权所有:山东大学中泰证券金融研究院
   地址:中国山东省济南市山大南路27号   邮编:250100    电话:0531-88364100   院长信箱: sxyuanzhang@sdu.edu.cn