关于举行中科院应用数学研究所丁超副研究员学术报告会的通知

报告题目：A proximal DC approach for quadratic assignment problem

报  告  人：丁超  副研究员（中科院应用数学研究所）

报告时间：2019年9月19日（星期四）上午9:45-11:00             

报告地点：4号楼318会议室

邀  请  人：潘少华  教授

欢迎广大师生前往！

数学学院

2019年9月6日

报告摘要：

In this talk, we show that the quadratic assignment problem (QAP) can be reformulated to an equivalent rank constrained doubly nonnegative (DNN) problem. Under the framework of the difference of convex functions (DC) approach, a semi-proximal DC algorithm (DCA) is proposed for solving the relaxation of the rank constrained DNN problem whose subproblems can be solved by the semi-proximal augmented Lagrangian method (sPALM). We show that the generated sequence converges to a stationary point of the corresponding DC problem, which is feasible to the rank constrained DNN problem. Moreover, numerical experiments demonstrate that for most QAP instances, the proposed approach can find the global optimal solutions efficiently, and for others, the proposed algorithm is able to provide good feasible solutions in a reasonable time.