TITLE: Packing Ellipsoids with Overlap (with application to Chromosome Arrangement)

SPEAKER: Stephen Wright

ABSTRACT:

Problems of packing shapes with maximal density, sometimes into a container of restricted size, are classical in discrete mathematics. We describe here the problem of packing a given set of ellipsoids of different sizes into a finite container, in a way that allows overlap but that minimizes the maximum overlap between adjacent ellipsoids. We describe a bilevel optimization algorithm for finding local solutions of this problem, both the general case and the simpler special case in which the ellipsoids are spheres. Tools from conic optimization, especially semidefinite programming, are key to the algorithm. Finally, we describe the motivating application - chromosome arrangement in cell nuclei - and compare the computational results obtained with this approach to experimental observations.

This talk represents joint work with Caroline Uhler (IST Austria)

BIO:  Stephen J. Wright is a Professor of Computer Sciences at the University of Wisconsin-Madison. His research interests lie in computational optimization and its applications to science and engineering. Prior to joining UW-Madison in 2001, Wright was at Argonne National Laboratory (1990-2001), and was a Professor of Computer Science at the University of Chicago (2000-2001). During 2007-2010, he served as chair of the Mathematical Optimization
Society, and he is currently serving a third term as an elected member of the Board of Trustees of the Society for Industrial and Applied Mathematics (SIAM). Wright is the author or co-author of widely used books in numerical optimization including "Primal Dual Interior-Point
Methods" (SIAM, 1997) and "Numerical Optimization" (2nd Edition, Springer, 2006, with J. Nocedal). He has also authored over 95 refereed journal papers on optimization theory, algorithms, software, and applications, along with over 40 refereed conference papers and
book chapters. He is coauthor of widely used software for linear programming (PCx) and quadratic programming (OOQP) based on interior-point methods, and GPSR and SpaRSA for compressed sensing. His recent work has included optimization algorithms for problems in machine learning and computational biology.