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.