Michael Baes (University of Zurich)

Mixed-integer convex optimization: approximations algorithms and duality
Joint work with Alberto del Pia, Yurii Nesterov, Shmuel Onn, Timm Oertel, Christian Wagner, and Robert Weismantel.
Wednesday 26 August 2015 at 15.00, JCMB 4325B

Abstract

The problem of minimizing a convex function over a convex set with the extra requirement that some variable must be integral, in spite of its intrinsic difficulty, enjoys enough structural properties to deserve the development of dedicated solvers. However, most known methods cannot offer any quality guarantee of the approximate solution they provide after a prescribed time.

In the first part of the talk, I will present two different methodologies to address this concern, both inspired from first-order methods for purely convex optimization problems. The results we obtain from these techniques hint at a general conjecture on the complexity of solving Mixed-Integer Convex problems approximately. In a second part of the talk, I will show a new approach for studying duality of mixed-integer convex problems, which also hint at our general conjecture.

Seminars by year

Current 2016 2015 2014 2013 2012 2011 2010 2009 2008 2007 2006 2005 2004 2003 2002 2001 2000 1999 1998 1997 1996