Optimization Online


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

Bo Jiang (jiangbo***at***njnu.edu.cn)
Ya-Feng Liu (yafliu***at***lsec.cc.ac.cn)
Zaiwen Wen (wenzw***at***pku.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: @techreport{jiang2015lp, title={$L_p$-norm regularization algorithms for optimization over permutation matrices }, author={Jiang, Bo and Liu, Ya-Feng and Wen, Zaiwen}, institution ={Optimization online}, year={2015}, month={November} }

Download: [PDF]

Entry Submitted: 11/12/2015
Entry Accepted: 11/13/2015
Entry Last Modified: 08/24/2016

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Optimization Society