- | ||||
|
![]()
|
$L_p$-norm regularization algorithms for optimization over permutation matrices
Bo Jiang (jiangbo 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 Modify/Update this entry | ||
Visitors | Authors | More about us | Links | |
Subscribe, Unsubscribe Digest Archive Search, Browse the Repository
|
Submit Update Policies |
Coordinator's Board Classification Scheme Credits Give us feedback |
Optimization Journals, Sites, Societies | |
![]() |