  


Beyond the Birkhoff Polytope: Convex Relaxations for Vector Permutation Problems
Cong Han Lim (conghancs.wisc.edu) Abstract: 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 Θ(n^2) variables and constraints, significantly more than the n 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 Θ(n log n) in theory and Θ(n log^2 n) in practice. We modify the recent convex formulation of the 2SUM problem introduced by Fogel et al. (2013) to use this polytope, and demonstrate how we can attain results of similar quality in significantly less computational time for large n. 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 2SUM problem that yields good empirical results. Keywords: permutahedron; sorting network; seriation Category 1: Convex and Nonsmooth Optimization Citation: Download: [PDF] Entry Submitted: 07/24/2014 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  