Laboratoire d'informatique de l'École polytechnique

DSOS and SDSOS Techniques in Optimization and Control

Speaker: Amir Ali Ahmadi (Princeton, ORFE)
Location: Room Flageolet, Turing building
Date: Tue, 28 Jun 2016, 14:00-15:00

Abstract: In recent years, algebraic techniques in optimization such as sum of squares (SOS) programming have led to powerful semi-definite programming relaxations for a wide range of NP-hard problems in computational mathematics. We begin by giving an overview of these techniques, emphasizing their implications for optimization and control, and pointing out some challenges that remain in terms of scalability. We then introduce new algebraic relaxation schemes that are very similar to SOS relaxations in nature but instead of semi-definite programs result in linear or second order cone programs. These are what we call DSOS and SDSOS programs. We show that these relaxations are orders of magnitude more scalable than SOS relaxations while enjoying many of the same asymptotic theoretical guarantees.

Based on joint work with Anirudha Majumdar.