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

报告人：北京工业大学，赵欣苑副教授

报告时间：2021年11月8日 9:00-

报告地点：腾讯会议164 141 386

报告摘要：

In this paper, we show that the quadratic assignment problem (QAP) can be reformulated to the rank constrained doubly nonnegative (DNN) problem. But the rank constrained DNN problem is still NP-hard. However, under the framework of the difference of convex functions (DC) approach, we design a semi-proximal DC algorithm to solve the relaxation of the rank constrained DNN problem whose subproblems are solved by the semi-proximal augmented Lagrangian method (sPALM). The generated sequence converges to a stationary point of the corresponding DC problem with a suitable parameter. Numerical examples from QAPLIB demonstrate that the proposed approach is very efficient to obtain the feasible solutions of the rank constrained DNN problems. For some cases, we can find the optimal solutions of QAPs directly; for the rest, we can provide good feasible solutions of QAPs in a reasonable time.

报告人简介：

赵欣苑，北京工业大学理学部副教授、数学和统计专业博士生导师。2009年毕业于新加坡国立大学获数学专业博士学位，导师为Toh Kim Chuan教授和Defeng Sun教授。2010年入职北京工业大学应用数理公司。主要从事大规模矩阵优化理论、算法及其应用，统计和机器学习中优化算法的研究，主持和参与多项国家基金委项目、北京市教委项目及横向科研项目，研究成果主要发表在SIAM Journal on Optimization、Optimization Methods and Software、Pacific Journal of Optimization、Signal, Image and Video Processing等刊物上，是大规模半定规划求解器SDPNAL/SDPNAL+主要开发成员之一。曾获得北京运筹学会《青年优秀论文》一等奖(2010)，入选北京工业大学青年导师国际化能力发展计划(2012)，北京工业大学优秀教师(2016)。主要学术兼职有中国运筹学会数学规划分会理事，北京市运筹学会理事。