  


$L_p$norm regularization algorithms for optimization over permutation matrices
Bo Jiang (jiangbonjnu.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 NPhard 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 BarzilaiBorwein 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, BarzilaiBorwein method Category 1: Integer Programming (01 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, YaFeng and Wen, Zaiwen}, institution ={Optimization online}, year={2015}, month={November} } 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  