Jon Lee (U. Michigan) will give a seminar on A geometric view of some relaxations in non-convex optimization. Mr Lee is visiting LIX for two months, until the end of July.

Abstract: Convex relaxation is at the heart of general-purpose methods for dealing with non-convexities in optimization. Non-convexities take many forms: integrality and low-dimensional non-convex functions are often encountered in mathematical-optimization model. We will look at some typical relaxations and seek to understand the fundamental trade off of tightness vs heaviness via a geometric approach. In particular, we will look in detail at: (i) facility-location problems, (ii) graph problems (e.g., packing, boolean-quadric/cut problems), and (iii) triple-products.