报告主题：置换矩阵约束优化问题的L_p正则化算法
报告人：刘亚锋 助理研究员（中国科学院数学与系统科学研究院）
报告时间：2017年 6月3日（周六）15:30
报告地点：校本部G508
邀请人：徐姿
主办部门：8455新葡萄场网站数学系
报告摘要： In this talk, we consider the optimization problem over permutation matrices, which finds wide applications in facility layout, chip design, scheduling, etc. Since the problem is NP-hard due to the combinatorial nature of permutation matrices, we relax the variable to be the more tractable doubly stochastic matrices and add an $L_p$-norm regularization term to the objective function. We show that the optimal solutions of the $L_p$-regularized problem are the same as the original problem if the regularization parameter is sufficiently large. We further establish a lower bound estimation of the nonzero entries of the stationary points of the $L_p$-regularized problem and some connections between its local minimizers and the permutation matrices. Then we propose an efficient $L_p$ regularization algorithm with local refinements. The algorithm approximately solves a sequence of $L_p$ regularization subproblems by the projected gradient method using a nonmontone line search with the Barzilai-Borwein step sizes. Its performance can be further improved if it is combined with certain local search methods, the cutting plane techniques as well as a new negative proximal point scheme. Extensive numerical results on QAPLIB and the bandwidth minimization problem show that our proposed algorithms can often find reasonably high quality solutions within a competitive amount of time.
欢迎教师、学生参加 ！
