We will present a geometric perspective on duality and algorithmic aspects of convex mixed-integer optimization. The duality theory will be based on the notion of lattice-free convex sets, which makes connections with ideas in geometry of numbers. For the algorithmic perspective, we first introduce a concept that generalizes several different notions of a "centerpoint" in the literature. We then develop an oracle-based algorithm for convex mixed-integer optimization based on centerpoints. Further, we show that algorithms based on centerpoints are "best possible" in a certain sense. Motivated by this, we establish several structural results about this concept and provide efficient algorithms for computing these points. Our main motivation is to understand the complexity of oracle based convex mixed-integer optimization.

Bio

Amitabh Basu is an associate professor in the Department of Applied Mathematics and Statistics at Johns Hopkins University. He was a visiting assistant professor in the Dept. of Mathematics at University of California, Davis, from 2010-2013. He obtained his Ph.D. in 2010 from Carnegie Mellon University with a thesis on mixed-integer optimization. He received an M.S. in computer science from Stony Brook University in 2006, and a bachelor's in computer science from Indian Institute of Technology, Delhi in 2004. His research interests are in optimization, with an emphasis on its discrete aspects, and its applications in machine learning and physics.