*********************************
There is now a CONTENT FREEZE for Mercury while we switch to a new platform. It began on Friday, March 10 at 6pm and will end on Wednesday, March 15 at noon. No new content can be created during this time, but all material in the system as of the beginning of the freeze will be migrated to the new platform, including users and groups. Functionally the new site is identical to the old one. webteam@gatech.edu
*********************************
TITLE: Understanding and improving convex formulations via lifted representations
ABSTRACT:
Mathematical optimization problems arise in all areas of science and engineering. The distinction convex/nonconvex has usually played the role of boundary between "easy" and "hard" problems. In the recent years it was shown that several hard nonconvex problems can be very successfully tackled using so-called convex relaxations. Such techniques have been applied in diverse areas such as signal processing, imaging, statistics, control theory, robotics, power flow, etc.
At the heart of convex relaxation methods lies the question of obtaining tractable representations of a convex hull of a set of points. In this talk I will discuss lifted representations of convex sets, in which the "hard" convex set is expressed as the projection of a simpler one living in a higher-dimensional space. I will present a new method to construct improved semidefinite programming lifts for polytopes and will give two applications of our method. First I will show how it provides the first family of polytopes in increasing dimensions with a growing gap between LP and SDP extension complexity. Second I will show how our method can be used to solve a conjecture of Laurent from 2003 on the Lasserre hierarchy for the maximum cut problem.
Bio
Hamza Fawzi is a PhD candidate at MIT in the Electrical Engineering and Computer Science department, Laboratory for Information and Decision Systems. He obtained a Diplome d’Ingenieur from Mines ParisTech, France in 2010 and a M.S. in Electrical Engineering from UCLA in 2011. He is broadly interested in the theory and applications of mathematical optimization, and more generally in the mathematical and computational aspects of problems in information and decision sciences.
