Tuesday, September 27, 2016 - 4:00pm to Wednesday, September 28, 2016 - 3:55pm
Event Calendar Category
LIDS Seminar Series
Speaker Name
Steve Wright
Affiliation
University of Wisconsin-Madison
Building and Room Number
32-141
A permutation of n components appears among the variables or in the formulation of several interesting optimization problems, including quadratic assignment, 2-SUM, and projection onto the unit simplex or an l-1 ball. One device used to formulate continuous relaxations of these problems is the Birkhoff polytope, the convex hull of the set of permutation matrices, which requires O(n^2) variables to represent. We propose instead relaxed formulations that make use of sorting networks (described in a 2015 paper of Goemans), practical versions of which require only O(n (log n)^2) variables and constraints. In several settings, our modified formulations, in conjunction with heuristics for converting the relaxed solutions into permutations, can yield better quality results for less computation. Separately, we discuss the operation of projecting onto the convex hull of all possible permutations of a vector c in R^n, in which there are d distinct elements. (The permutahedron and the simplex are two examples.) When the projection is performed with respect to certain popular Bregman divergences, our unified approach has complexity O(n log d), matching or improving on specialized algorithms for certain special cases of c.
This talk represents work with Cong Han Lim.
Stephen J. Wright holds the George B. Dantzig Professorship, the Sheldon Lubar Chair, and the Amar and Balinder Sohi Professorship of Computer Sciences at the University of Wisconsin-Madison. His research is in computational optimization and its applications to many areas of science and engineering. Prior to joining UW-Madison in 2001, Wright was an Assistant Professor at North Carolina State University, a Senior Computer Scientist at Argonne National Laboratory (1990-2001), and a Professor at the University of Chicago (2000-2001). He has served as Chair of the Mathematical Optimization Society and as a Trustee of the Society for Industrial and Applied Mathematics (SIAM). He is a Fellow of SIAM. In 2014, he won the W.R.G. Baker award from IEEE.
Wright is the author / coauthor of widely used text / reference books in optimization including "Primal Dual Interior-Point Methods" (SIAM, 1997) and "Numerical Optimization" (2nd Edition, Springer, 2006, with J. Nocedal). He has published widely on optimization theory, algorithms, software, and applications.
Wright is current editor-in-chief of the SIAM Journal on Optimization and previously served as editor-in-chief or associate editor of Mathematical Programming (Series A), Mathematical Programming (Series B), SIAM Review, SIAM Journal on Scientific Computing, and several other journals and book series.