$L_p$-norm regularization algorithms for optimization over permutation matrices

Bo Jiang (jiangbonjnu.edu.cn)
Ya-Feng Liu (yafliulsec.cc.ac.cn)
Zaiwen Wen (wenzwpku.edu.cn)

Abstract: Optimization problems over permutation matrices appear widely in facility layout, chip design, scheduling, pattern recognition, computer vision, graph matching, etc. Since this 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 ($0 < p < 1$) regularization term to the objective function. The optimal solutions of the $L_p$-regularized problem are the same as the original problem if the regularization parameter is sufficiently large. A lower bound estimation of the nonzero entries of the stationary points and some connections between the local minimizers and the permutation matrices are further established. Then we propose an $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.

Keywords: permutation matrix, doubly stochastic matrix, quadratic assignment problem, $L_p$ regularization, cutting plane, negative proximal point, Barzilai-Borwein method

Category 1: Integer Programming (0-1 Programming )

Category 2: Nonlinear Optimization (Constrained Nonlinear Optimization )

Citation: @article{JiangLiuWen2016, author = {Jiang, Bo and Liu, Ya-Feng and Wen, Zaiwen}, title = {\$L\_p\$-norm Regularization Algorithms for Optimization Over Permutation Matrices}, journal = {SIAM Journal on Optimization}, volume = {26}, number = {4}, pages = {2284-2313}, year = {2016}, doi = {10.1137/15M1048021}, URL = {https://doi.org/10.1137/15M1048021}, eprint = {https://doi.org/10.1137/15M1048021} }

Download: [PDF]

Entry Submitted: 11/12/2015
Entry Accepted: 11/13/2015
Entry Last Modified: 06/06/2018

Modify/Update this entry