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 @math -norm ( @math ) regularization term to the objective function. The optimal solutions of the @math -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 @math regularization algorithm with local refinements. The algorithm approximately solves a sequence of @math 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.
@cite_42: 
@cite_13: TAO HUANG: Continuous Optimization Methods for the Quadratic Assignment Problem (Under the direction of Jon W. Tolle) In this dissertation we have studied continuous optimization techniques as they are applied in nonlinear 0-1 programming. Specifically, the methods of relaxation with a penalty function have been carefully investigated. When the strong equivalence properties hold, we are guaranteed an integer solution to the original 0-1 problem. The quadratic assignment problem (QAP) possesses such properties and consequently we have developed an algorithm for the QAP based on the method of relaxation using the quadratic penalty function. In our algorithm we have applied two pre-conditioning techniques that enables us to devise a scheme to find a good initial point and hence obtain good solutions to the QAP. Furthermore, we have shown how quadratic cuts can be used to improve on the current solutions. Extensive numerical results on several sets of QAP test problems (including the QAPLIB) have been reported and these results show our algorithm produces good solutions for certain classes of problems in a small amount of time.
@cite_17: This paper uses the formulation of the quadratic assignment problem as that of minimizing a concave quadratic function over the assignment polytope. Cutting plane procedures are investigated for solving this problem. A lower bound derived on the number of cuts needed for termination indicates that conventional cutting plane procedures would require a huge computational effort for the exact solution of the quadratic assignment problems. However, several heuristics which are derived from the cutting planes produce optimal or good quality solutions early on in the search process. An illustrative example and computational results are presented.
Xia @cite_42 proposed a Lagrangian smoothing algorithm for QAP which solves a sequence of @math regularization subproblem X , (A^ X B X^ ) + |X |_ ^2 with dynamically decreasing parameters @math The initial value @math in subproblem was chosen such that the problem is convex and the subproblem with fixed @math was approximately solved by the Frank-Wolfe algorithm up to fixed number of iterations (it was called the truncated Frank-Wolfe method in @cite_42 ). Note that Bazaraa and Sherali @cite_17 first considered regularization problem where @math is chosen such that the problem is strongly concave, but they only solved once. In addition, Huang @cite_13 used the quartic term @math to construct the regularization problem, where @math is the Hadamard product and @math is the matrix of all ones.