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_58: In this note, we consider the permutahedron, the convex hull of all permutations of @math 1,2?,n . We show how to obtain an extended formulation for this polytope from any sorting network. By using the optimal Ajtai---Komlos---Szemeredi sorting network, this extended formulation has @math ?(nlogn) variables and inequalities. Furthermore, from basic polyhedral arguments, we show that this is best possible (up to a multiplicative constant) since any extended formulation has at least @math Ω(nlogn) inequalities. The results easily extend to the generalized permutahedron.
@cite_7: Seriation seeks to reconstruct a linear order between variables using unsorted, pairwise similarity information. It has direct applications in archeology and shotgun gene sequencing for example. We write seriation as an optimization problem by proving the equivalence between the seriation and combinatorial 2-SUM problems on similarity matrices (2-SUM is a quadratic minimization problem over permutations). The seriation problem can be solved exactly by a spectral algorithm in the noiseless case and we derive several convex relaxations for 2-SUM to improve the robustness of seriation solutions in noisy settings. These convex relaxations also allow us to impose structural constraints on the solution, hence solve semi-supervised seriation problems. We derive new approximation bounds for some of these relaxations and present numerical experiments on archeological data, Markov chains and DNA assembly from shotgun gene sequencing data.
@cite_56: The Birkhoff polytope (the convex hull of the set of permutation matrices) is frequently invoked in formulating relaxations of optimization problems over permutations. The Birkhoff polytope is represented using @math variables and constraints, significantly more than the @math variables one could use to represent a permutation as a vector. Using a recent construction of Goemans (2010), we show that when optimizing over the convex hull of the permutation vectors (the permutahedron), we can reduce the number of variables and constraints to @math in theory and @math in practice. We modify the recent convex formulation of the 2-SUM problem introduced by (2013) to use this polytope, and demonstrate how we can attain results of similar quality in significantly less computational time for large @math . To our knowledge, this is the first usage of Goemans' compact formulation of the permutahedron in a convex optimization problem. We also introduce a simpler regularization scheme for this convex formulation of the 2-SUM problem that yields good empirical results.
Recently, Fogel @cite_7 used QAP to solve the seriation and 2-SUM problems. QAP considered therein takes the following special structure: where @math is binary symmetric, @math , and @math . Here, @math represents a diagonal matrix whose diagonal elements are @math . They used the regularization term @math with @math , where @math denotes the identity matrix of size @math , to construct a convex relaxation problem over @math for . Using a recent result of Goemans @cite_58 , Lim and Wright @cite_56 constructed a new convex relaxation problem over a convex hull of the permutation vectors for . In their problem, the number of variables and constraints reduces to @math in theory and @math in practice. The advantage of this new formulation was illustrated by numerical experiments. However, as pointed in @cite_56 , it is still unclear how to extend their new formulation to the more general QAP .