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.
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} }